[Caml-list] Clarification for the configuration of comparison functions

[Caml-list] Clarification for the configuration of comparison functions

[SF Markus Elfring]

Hello,

I extended my software development experience a bit for the programming language
"OCaml". I find my knowledge incomplete here to resolve an issue like
"Comparison function application" alone.
https://github.com/elfring/OTCL/issues/4

How do you think about to discuss corresponding implementation details for an
evolving class library?

I would appreciate your advices.

Regards,
Markus

Re: [Caml-list] Clarification for the configuration of comparison functions

[Gerd Stolpmann]

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

Am Mittwoch, den 10.09.2014, 10:56 +0200 schrieb SF Markus Elfring:
> Hello,
> 
> I extended my software development experience a bit for the programming language
> "OCaml". I find my knowledge incomplete here to resolve an issue like
> "Comparison function application" alone.
> https://github.com/elfring/OTCL/issues/4

There are three reasons why you want to have your own comparison
function:

- You need a different ordering than provided by Pervasives.compare.
  For compound types the ordering of compare is implementation-defined,
  and currently the implementation prefers the fastest way of comparing.
  E.g. if you compare arrays, you don't get a lexicographic ordering.
  This is sometimes not what you need.
- Your values are cyclic. compare may hang if you try to compare cyclic
  values.
- Your values contains parts that cannot be compared, like functions.
  With a custom comparison function you can skip these parts.

Gerd

> How do you think about to discuss corresponding implementation details for an
> evolving class library?
> 
> I would appreciate your advices.
> 
> Regards,
> Markus
> 

-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
My OCaml site:          http://www.camlcity.org
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Caml-list] Clarification for the configuration of comparison functions

[Yotam Barnoy]

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

Another reason is performance. The generic, polymorphic comparison function
drops you out into C (which has a cost) and has to compare every single
possible value combination. A customized comparison function stays in ocaml
and handles only what you need ie. it's driven by type information that the
generic function lacks.

Yotam

On Wed, Sep 10, 2014 at 7:27 AM, Gerd Stolpmann <info@gerd-stolpmann.de>
wrote:

> Am Mittwoch, den 10.09.2014, 10:56 +0200 schrieb SF Markus Elfring:
> > Hello,
> >
> > I extended my software development experience a bit for the programming
> language
> > "OCaml". I find my knowledge incomplete here to resolve an issue like
> > "Comparison function application" alone.
> > https://github.com/elfring/OTCL/issues/4
>
> There are three reasons why you want to have your own comparison
> function:
>
> - You need a different ordering than provided by Pervasives.compare.
>   For compound types the ordering of compare is implementation-defined,
>   and currently the implementation prefers the fastest way of comparing.
>   E.g. if you compare arrays, you don't get a lexicographic ordering.
>   This is sometimes not what you need.
> - Your values are cyclic. compare may hang if you try to compare cyclic
>   values.
> - Your values contains parts that cannot be compared, like functions.
>   With a custom comparison function you can skip these parts.
>
> Gerd
>
> > How do you think about to discuss corresponding implementation details
> for an
> > evolving class library?
> >
> > I would appreciate your advices.
> >
> > Regards,
> > Markus
> >
>
> --
> ------------------------------------------------------------
> Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
> My OCaml site:          http://www.camlcity.org
> Contact details:        http://www.camlcity.org/contact.html
> Company homepage:       http://www.gerd-stolpmann.de
> ------------------------------------------------------------
>
>

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

Re: [Caml-list] Clarification for the configuration of comparison functions

[Gerd Stolpmann]

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

Am Mittwoch, den 10.09.2014, 08:07 -0400 schrieb Yotam Barnoy:
> Another reason is performance. The generic, polymorphic comparison
> function drops you out into C (which has a cost)

Don't think so. compare doesn't allocate memory, so the few extra
instructions in caml_c_call for making allocation available from C
aren't required. Calling compare shouldn't be slower than calling a
function written in OCaml.

>  and has to compare every single possible value combination.

That's more of a problem: there is a dispatch on the type of value to
compare, and this costs a bit of time.

There is something else that can speed up a custom compare: you can also
store a hash of the value inside the value, and use that for speeding up
comparison, e.g.

type t = ...
type t_cmp = t * int

let wrap x = (x, Hashtbl.hash x)

let my_compare (x1,h1) (x2,h2) =
  if h1=h2 then
    compare x1 x2
  else
    h1-h2

That trick can save a lot of time.

Gerd

>  A customized comparison function stays in ocaml and handles only what
> you need ie. it's driven by type information that the generic function
> lacks.
> 
> 
> Yotam
> 
> On Wed, Sep 10, 2014 at 7:27 AM, Gerd Stolpmann
> <info@gerd-stolpmann.de> wrote:
>         Am Mittwoch, den 10.09.2014, 10:56 +0200 schrieb SF Markus
>         Elfring:
>         > Hello,
>         >
>         > I extended my software development experience a bit for the
>         programming language
>         > "OCaml". I find my knowledge incomplete here to resolve an
>         issue like
>         > "Comparison function application" alone.
>         > https://github.com/elfring/OTCL/issues/4
>         
>         There are three reasons why you want to have your own
>         comparison
>         function:
>         
>         - You need a different ordering than provided by
>         Pervasives.compare.
>           For compound types the ordering of compare is
>         implementation-defined,
>           and currently the implementation prefers the fastest way of
>         comparing.
>           E.g. if you compare arrays, you don't get a lexicographic
>         ordering.
>           This is sometimes not what you need.
>         - Your values are cyclic. compare may hang if you try to
>         compare cyclic
>           values.
>         - Your values contains parts that cannot be compared, like
>         functions.
>           With a custom comparison function you can skip these parts.
>         
>         Gerd
>         
>         > How do you think about to discuss corresponding
>         implementation details for an
>         > evolving class library?
>         >
>         > I would appreciate your advices.
>         >
>         > Regards,
>         > Markus
>         >
>         
>         --
>         ------------------------------------------------------------
>         Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
>         My OCaml site:          http://www.camlcity.org
>         Contact details:        http://www.camlcity.org/contact.html
>         Company homepage:       http://www.gerd-stolpmann.de
>         ------------------------------------------------------------
>         
> 
> 

-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
My OCaml site:          http://www.camlcity.org
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Caml-list] Clarification for the configuration of comparison functions

[Adrien Nader]

On Wed, Sep 10, 2014, Gerd Stolpmann wrote:
> Am Mittwoch, den 10.09.2014, 08:07 -0400 schrieb Yotam Barnoy:
> > Another reason is performance. The generic, polymorphic comparison
> > function drops you out into C (which has a cost)
> 
> Don't think so. compare doesn't allocate memory, so the few extra
> instructions in caml_c_call for making allocation available from C
> aren't required. Calling compare shouldn't be slower than calling a
> function written in OCaml.

And calling C from OCaml is _very_ fast. Too fast to be a concern.

The other way round is slower, iirc maybe by a 100 factor.

(you should benchmark yourself if any of these might be a concern)

-- 
Adrien Nader

Re: [Caml-list] Clarification for the configuration of comparison functions

[Yotam Barnoy]

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

That's good to know. Thanks for clarifying.

Yotam

On Wed, Sep 10, 2014 at 8:37 AM, Adrien Nader <adrien@notk.org> wrote:

> On Wed, Sep 10, 2014, Gerd Stolpmann wrote:
> > Am Mittwoch, den 10.09.2014, 08:07 -0400 schrieb Yotam Barnoy:
> > > Another reason is performance. The generic, polymorphic comparison
> > > function drops you out into C (which has a cost)
> >
> > Don't think so. compare doesn't allocate memory, so the few extra
> > instructions in caml_c_call for making allocation available from C
> > aren't required. Calling compare shouldn't be slower than calling a
> > function written in OCaml.
>
> And calling C from OCaml is _very_ fast. Too fast to be a concern.
>
> The other way round is slower, iirc maybe by a 100 factor.
>
> (you should benchmark yourself if any of these might be a concern)
>
> --
> Adrien Nader
>

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

Re: [Caml-list] Clarification for the configuration of comparison functions

[Pippijn van Steenhoven]

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

On Wed, Sep 10, 2014 at 02:26:28PM +0200, Gerd Stolpmann wrote:
> type t = ...
> type t_cmp = t * int
> 
> let wrap x = (x, Hashtbl.hash x)
> 
> let my_compare (x1,h1) (x2,h2) =
>   if h1=h2 then
>     compare x1 x2
>   else
>     h1-h2

This code is incorrect when h1 is large and negative. You should use
"compare h1 h2" and annotate h1 and/or h2 with its type (int), so that
int-compare is called directly.

Also, if you store the hash before the actual value, compare will
probably stop comparing after it finds that the hashes are not equal, so
you can simply use the polymorphic compare on t_cmp. I don't know this
for sure, since I haven't looked at the source, but I would assume this
is true.

-- 
Pippijn

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: [Caml-list] Clarification for the configuration of comparison functions

[Gerd Stolpmann]

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

Am Mittwoch, den 10.09.2014, 08:40 -0400 schrieb Nick Lucaroni
> On Sep 10, 2014 8:27 AM, "Gerd Stolpmann" <info@gerd-stolpmann.de>
> wrote:
> > There is something else that can speed up a custom compare: you can
> also
> > store a hash of the value inside the value, and use that for
> speeding up
> > comparison, e.g.
> >
> > type t = ...
> > type t_cmp = t * int
> >
> > let wrap x = (x, Hashtbl.hash x)
> >
> > let my_compare (x1,h1) (x2,h2) =
> >   if h1=h2 then
> >     compare x1 x2
> >   else
> >     h1-h2
> 
> The hash difference here would cause issues, is it really worth it if
> you have to recover some ordering anyway? I can see the value in
> defining equality, though.

For example, if you need the ordering only for a Map or Set, it doesn't
matter how things are ordered.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
My OCaml site:          http://www.camlcity.org
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Caml-list] Clarification for the configuration of comparison functions

[Gerd Stolpmann]

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

Am Mittwoch, den 10.09.2014, 13:41 +0100 schrieb Pippijn van Steenhoven:
> On Wed, Sep 10, 2014 at 02:26:28PM +0200, Gerd Stolpmann wrote:
> > type t = ...
> > type t_cmp = t * int
> > 
> > let wrap x = (x, Hashtbl.hash x)
> > 
> > let my_compare (x1,h1) (x2,h2) =
> >   if h1=h2 then
> >     compare x1 x2
> >   else
> >     h1-h2
> 
> This code is incorrect when h1 is large and negative.

Hashtbl.hash returns non-negative ints. For other hash functions you are
correct.

>  You should use
> "compare h1 h2" and annotate h1 and/or h2 with its type (int), so that
> int-compare is called directly.
> 
> Also, if you store the hash before the actual value, compare will
> probably stop comparing after it finds that the hashes are not equal, so
> you can simply use the polymorphic compare on t_cmp. I don't know this
> for sure, since I haven't looked at the source, but I would assume this
> is true.

The OCaml manual doesn't define compare for tuples, so you cannot
exploit that. I wouldn't bet that compare runs from left to right over
the values, as OCaml is known for sometimes preferring right to left.
But maybe this could be a future language feature? If the OCaml manual
defined compare on tuples, this would in deed be a fine trick.

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
My OCaml site:          http://www.camlcity.org
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Caml-list] Clarification for the configuration of comparison functions

[Ben Millwood]

On 10 September 2014 13:51, Gerd Stolpmann <info@gerd-stolpmann.de> wrote:
> Am Mittwoch, den 10.09.2014, 13:41 +0100 schrieb Pippijn van Steenhoven:
>> Also, if you store the hash before the actual value, compare will
>> probably stop comparing after it finds that the hashes are not equal, so
>> you can simply use the polymorphic compare on t_cmp. I don't know this
>> for sure, since I haven't looked at the source, but I would assume this
>> is true.
>
> The OCaml manual doesn't define compare for tuples, so you cannot
> exploit that. I wouldn't bet that compare runs from left to right over
> the values, as OCaml is known for sometimes preferring right to left.
> But maybe this could be a future language feature? If the OCaml manual
> defined compare on tuples, this would in deed be a fine trick.

On the other hand, perhaps the fact that no-one is sure without
checking whether or not this works is indication enough that it is too
clever a trick for its own good, and just doing the obviously-right
thing is a more sensible option :)

Re: [Caml-list] Clarification for the configuration of comparison functions

[SF Markus Elfring]

>> https://github.com/elfring/OTCL/issues/4
> 
> There are three reasons why you want to have your own comparison
> function:

Thanks for your explanation.

Would you like to suggest any changes for the affected member functions?
https://github.com/elfring/OTCL/blob/51c5a0ff8b487cddc9318cac63c59bd5c23ae547/omap.ml#L121

Regards,
Markus

Re: [Caml-list] Clarification for the configuration of comparison functions

[Francois Berenger]

On 09/10/2014 10:56 PM, SF Markus Elfring wrote:
>>> https://github.com/elfring/OTCL/issues/4
>>
>> There are three reasons why you want to have your own comparison
>> function:
>
> Thanks for your explanation.
>
> Would you like to suggest any changes for the affected member functions?
> https://github.com/elfring/OTCL/blob/51c5a0ff8b487cddc9318cac63c59bd5c23ae547/omap.ml#L121

Are you sure about the compare on line 66?

> Regards,
> Markus
>
>

-- 
Regards,
Francois.

Re: [Caml-list] Clarification for the configuration of comparison functions

[SF Markus Elfring]

>> Would you like to suggest any changes for the affected member functions?
>> https://github.com/elfring/OTCL/blob/51c5a0ff8b487cddc9318cac63c59bd5c23ae547/omap.ml#L121
> 
> Are you sure about the compare on line 66?

No! - I do not feel familiar enough with the programming language "OCaml" so far
to decide changes here on my own.

...
let rec add ~cmp x data = function
...
      let c = compare x v in
...

That is one of the places where I have found a code smell. It is an
implementation detail for which I published the bug report "Comparison function
application" and started a corresponding clarification try on IRC and the
mailing list.
https://github.com/elfring/OTCL/issues/4

Should the shown function name be replaced by a call for "~cmp"?

Regards,
Markus

Re: [Caml-list] Clarification for the configuration of comparison functions

[Francois Berenger]

On 09/11/2014 10:10 AM, SF Markus Elfring wrote:
>>> Would you like to suggest any changes for the affected member functions?
>>> https://github.com/elfring/OTCL/blob/51c5a0ff8b487cddc9318cac63c59bd5c23ae547/omap.ml#L121
>>
>> Are you sure about the compare on line 66?
>
> No! - I do not feel familiar enough with the programming language "OCaml" so far
> to decide changes here on my own.
>
> ...
> let rec add ~cmp x data = function
> ...
>        let c = compare x v in
> ...
>
> That is one of the places where I have found a code smell. It is an
> implementation detail for which I published the bug report "Comparison function
> application" and started a corresponding clarification try on IRC and the
> mailing list.
> https://github.com/elfring/OTCL/issues/4
>
> Should the shown function name be replaced by a call for "~cmp"?

Probably, but I am also not familiar with this code base.

> Regards,
> Markus

Re: [Caml-list] Clarification for the configuration of comparison functions

[SF Markus Elfring]

>> Should the shown function name be replaced by a call for "~cmp"?
> 
> Probably, but I am also not familiar with this code base.

Can any other OCaml software designer give a definitive advice here besides the
original developers?

Regards,
Markus

Re: [Caml-list] Clarification for the configuration of comparison functions

[Frédéric Bour]

The cmp value is threaded but never used. It is a mistake.
The cmp value should either be used instead of compare or completely 
removed (but that's not what was intended).

"Luckily", the mistake is made at all comparison places in this file, so 
the resulting map still behaves like a map, just not with the expected 
ordering.

On 11/09/2014 10:33, SF Markus Elfring wrote:
>>> Should the shown function name be replaced by a call for "~cmp"?
>> Probably, but I am also not familiar with this code base.
> Can any other OCaml software designer give a definitive advice here besides the
> original developers?
>
> Regards,
> Markus
>

Re: [Caml-list] Clarification for the configuration of comparison functions

[SF Markus Elfring]

> The cmp value is threaded but never used. It is a mistake.

Would you like try my software update out?
https://github.com/elfring/OTCL/releases/tag/v1.2

Do you know any dedicated tool which can find such an issue by a static source
code analysis?

Regards,
Markus