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

[Gerd Stolpmann <info@gerd-stolpmann.de>]

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