[Caml-list] Comparing floats

[Sébastien Hinderer]

Dear all,

What's the most efficient way to compare floats, please?
Is it the polymorphic compare function, or is there a more specialized
version of it?

I saw Float.compare mentionned on the web but that does not seem to exist
any longer?

Thanks,

Sébastien.

--
Caml-list mailing list. Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

[Francois Berenger]

On 07/23/2015 10:35 AM, Sébastien Hinderer wrote:
> Dear all,
>
> What's the most efficient way to compare floats, please?
> Is it the polymorphic compare function, or is there a more specialized
> version of it?
>
> I saw Float.compare mentionned on the web but that does not seem to exist
> any longer?

It exists in Batteries for sure and in Core I believe.

Also, maybe you can define:

let cmp_f (x: float) (y: float) = x -. y

> Thanks,
>
> Sébastien.
>

--
Regards,
Francois.
"When in doubt, use more types"

[Xavier Leroy]

On 23/07/2015 10:35, Sébastien Hinderer wrote:
> What's the most efficient way to compare floats, please?
> Is it the polymorphic compare function, or is there a more specialized
> version of it?

You'll get good performance by type-specializing Pervasives.compare:

let compare_float (x: float) (y: float) = compare x y

If you're absolutely sure your floats are not NaN, you can shave a few
CPU cycles:

let compare_float (x: float) (y: float) =
if x < y then -1 else if x > y then 1 else 0

- Xavier Leroy

[Mr. Herr]

On 23.07.2015 10:46, Francois Berenger wrote:
> On 07/23/2015 10:35 AM, Sébastien Hinderer wrote:
>> Dear all,
>>
>> What's the most efficient way to compare floats, please?
>> Is it the polymorphic compare function, or is there a more specialized
>> version of it?
>>
>> I saw Float.compare mentionned on the web but that does not seem to exist
>> any longer?
>
> It exists in Batteries for sure and in Core I believe.
>
> Also, maybe you can define:
>
> let cmp_f (x: float) (y: float) = x -. y

hmm, this will return float instead of int.

My test says that compare is compiled directly to the adequate internal function,
and if this even in byte code:

str@s131-intel:~/Projekte/Ocaml/ml> cat test_comparefl1.ml && echo -e
"------------\n" && ocamlc -dinstr test_comparefl1.ml
(*
Frage auf mailing list: wie am besten floats vergleichen?
*)
print_endline ("Pervasives.compare 2 floats gives me " ^ (string_of_int (compare 2.0
3.99)))
------------

const 3.99
push
const 2.0
ccall caml_float_compare, 2
push
getglobal Pervasives!
getfield 19
apply 1
push
const "Pervasives.compare 2 floats gives me "
push
getglobal Pervasives!
getfield 15
apply 2
push
getglobal Pervasives!
getfield 30
apply 1
makeblock 0, 0
setglobal Test_comparefl1!

------------------------------
/Str.

[Sébastien Hinderer]

Xavier Leroy (2015/07/23 11:01 +0200):

> On 23/07/2015 10:35, Sébastien Hinderer wrote:
> > What's the most efficient way to compare floats, please?
> > Is it the polymorphic compare function, or is there a more specialized
> > version of it?
>
> You'll get good performance by type-specializing Pervasives.compare:
>
> let compare_float (x: float) (y: float) = compare x y
>
> If you're absolutely sure your floats are not NaN, you can shave a few
> CPU cycles:
>
> let compare_float (x: float) (y: float) =
> if x < y then -1 else if x > y then 1 else 0

Thanks a lot Xavier!

Sébastien.

[Mr. Herr]

On 23.07.2015 11:01, Xavier Leroy wrote:
> On 23/07/2015 10:35, Sébastien Hinderer wrote:
>> What's the most efficient way to compare floats, please?
>> Is it the polymorphic compare function, or is there a more specialized
>> version of it?
> You'll get good performance by type-specializing Pervasives.compare:
>
> let compare_float (x: float) (y: float) = compare x y
>
> If you're absolutely sure your floats are not NaN, you can shave a few
> CPU cycles:
>
> let compare_float (x: float) (y: float) =
> if x < y then -1 else if x > y then 1 else 0
>

The assembler code says compare_float is directly compiled to a function that
compares the 2 values
in xmm0 and xmm1 registers, while Pervasives.compare is a library function written in
C doing the same thing.

The assembler code looks very very good.

But I doubt that you could measure a difference. The type system will always
yield the float_compare function, doesn't it? So far my quickcheck...

--- Assembler code of your suggested function:
camlTest_comparefl3__compare_float_1008:
.cfi_startproc
L102:
movsd (%rbx), %xmm0
movsd (%rax), %xmm1
comisd %xmm1, %xmm0
jbe .L101
movq $-1, %rax
ret
.align 4
L101:
comisd %xmm0, %xmm1
jbe .L100
movq $3, %rax
ret
.align 4
L100:
movq $1, %rax
ret
.cfi_endproc

--- C code of library function:

CAMLprim value caml_float_compare(value vf, value vg)
{
double f = Double_val(vf);
double g = Double_val(vg);
if (f == g) return Val_int(0);
if (f < g) return Val_int(-1);
if (f > g) return Val_int(1);
/* One or both of f and g is NaN. Order according to the
convention NaN = NaN and NaN < x for all other floats x. */
if (f == f) return Val_int(1); /* f is not NaN, g is NaN */
if (g == g) return Val_int(-1); /* g is not NaN, f is NaN */
return Val_int(0); /* both f and g are NaN */

[Boris Yakobowski]

Hi Sébastien,

I feel obligated to point out that the _semantics_ of floating-point
comparison is a bit tricky. IEEE 754 mandates that NaN == NaN should return
false (as well as NaN != NaN), breaking all algebraic laws known to mankind
:-). OCaml's operators '=' and '!=' follow this convention, but 'compare
nan nan' returns 0, which is usually the desired behavior. However,
'compare 0. (-0.)' also returns 0, while you might want to distinguish
those two values.

HTH,

--
Boris

[Jacques-Henri Jourdan]

Le 23/07/2015 13:34, Boris Yakobowski a écrit :
> Hi Sébastien,
>
> I feel obligated to point out that the _semantics_ of floating-point
> comparison is a bit tricky. IEEE 754 mandates that NaN == NaN should
> return false (as well as NaN != NaN), breaking all algebraic laws
> known to mankind :-).

Beaware:

Nan <> Nan -> true
Nan = Nan -> false
Nan != Nan and Nan == Nan : depends on the memory layout.

[Boris Yakobowski]

Indeed, thanks for the clarification...

I got confused when negating OCaml's '=' operator (a dangerous side-effect
of writing too much C!), hence the erroneous '!=' instead of <>. Regarding,
'nan <> nan', I had convinced myself that all comparisons with NaN returned
false. I wonder why <>/!= got a special treatment since e.g. 'nan < 1.' and
'1. < nan' both return false.

--
Boris

[Xavier Leroy]

On 23/07/15 18:34, Boris Yakobowski wrote:
> I got confused when negating OCaml's '=' operator (a dangerous side-effect
> of writing too much C!), hence the erroneous '!=' instead of <>. Regarding,
> 'nan <> nan', I had convinced myself that all comparisons with NaN returned
> false. I wonder why <>/!= got a special treatment since e.g. 'nan < 1.' and
> '1. < nan' both return false.

Perhaps so that (using Caml syntax) "x <> y" is always equivalent to
"not (x = y)". But I agree it can be viewed as yet another oddity
with NaNs.

Just to clarify my previous post:

let compare_float (x: float) (y: float) = compare x y

gives a total order over floats that behaves sensibly, if somewhat
arbitrarily, over NaN arguments: two NaNs are equal, and any NaN is
less than any non-NaN float. In contrast,

let compare_float (x: float) (y: float) =
if x < y then -1 else if x > y then 1 else 0

is not a proper order, because the implied equality is not transitive.
Consider:

compare_float 0.0 nan = 0
compare_float nan 1.0 = 0
compare_float 0.0 1.0 = -1

So, don't use the latter definition for e.g. sorting a list of floats
that can contain NaN. The former definition is more robust.

- Xavier Leroy