[Caml-list] Comparing floats

[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.

Re: [Caml-list] Comparing floats

[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"

Re: [Caml-list] Comparing floats

[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

Re: [Caml-list] Comparing floats

[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.

Re: [Caml-list] Comparing floats

[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.
> 
> - Xavier Leroy
> 

Re: [Caml-list] Comparing floats

[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 */
}

Re: [Caml-list] Comparing floats

[Boris Yakobowski]

[-- Attachment #1: Type: text/plain, Size: 1137 bytes --]

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,

On Thu, Jul 23, 2015 at 10:35 AM, Sébastien Hinderer <
Sebastien.Hinderer@inria.fr> 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?
>
> 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
>



-- 
Boris

[-- Attachment #2: Type: text/html, Size: 1918 bytes --]

Re: [Caml-list] Comparing floats

[Jacques-Henri Jourdan]

[-- Attachment #1.1: Type: text/plain, Size: 1440 bytes --]



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.

> 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,
>
> On Thu, Jul 23, 2015 at 10:35 AM, Sébastien Hinderer
> <Sebastien.Hinderer@inria.fr <mailto:Sebastien.Hinderer@inria.fr>> 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?
>
>     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
>
>
>
>
> -- 
> Boris


[-- Attachment #1.2: Type: text/html, Size: 3591 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Caml-list] Comparing floats

[Boris Yakobowski]

[-- Attachment #1: Type: text/plain, Size: 1924 bytes --]

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.

On Thu, Jul 23, 2015 at 5:14 PM, Jacques-Henri Jourdan <
jacques-henri.jourdan@inria.fr> wrote:

>
>
> 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.
>
>   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,
>
> On Thu, Jul 23, 2015 at 10:35 AM, Sébastien Hinderer <
> <Sebastien.Hinderer@inria.fr>Sebastien.Hinderer@inria.fr> 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?
>>
>> 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
>>
>
>
>
> --
> Boris
>
>
>


-- 
Boris

[-- Attachment #2: Type: text/html, Size: 4050 bytes --]

Re: [Caml-list] Comparing floats

[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

Re: [Caml-list] Comparing floats

[Goswin von Brederlow]

On Thu, Jul 23, 2015 at 11:54:38AM +0200, Mr. Herr wrote:
> 
> 
> 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...

There are many cases where you have a polymorphic function (as in the
code does not allow to infere that the type is float) doing lots of
compares or you pass compare as argument to a polymorphic function. By
specifically forcing the type to be float you can gain a lot of
performance.

If the type system already inferes the float type itself then you gain
nothing. But that doesn't always happen (at the right time).

MfG
	Goswin