Pervasives.compare: slow?

Pervasives.compare: slow?

[David Monniaux]

I used Pervasives.compare as a comparison function between hash values
(16-byte strings). Pervasives.compare is a polymorphic hack that works by
induction on the type information left for the garbage collector; even if
you specify Pervasives.compare : string -> string -> int, it still invokes
the polymorphic function.

There is apparently a 20-25% performance penalty using this form instead
of a simple comparison procedure for 16-byte strings. I suspect the
performance hit is even higher for more complex data structures.

Would it be possible to have ad hoc generated comparison functions? That
sounds like it needs including polytypic features into the language, which
is some very big stuff.

Perhaps including a String.compare function would be easier.

Regards,

David Monniaux            http://www.di.ens.fr/~monniaux
Laboratoire d'informatique de l'École Normale Supérieure,
Paris, France

Re: Pervasives.compare: slow?

[Judicael Courant]

On 19 jun, David Monniaux wrote:
> Perhaps including a String.compare function would be easier.
> 

Adding a function "compare" to the String module would be a very good
idea indeed. May I suggest that a "type t = string" be added also ?

Hence, one could write

module StringSet = Set.Make(String)

module StringMap = Map.Make(String)

instead of

module StringSet =
  Set.Make(struct
             type t = string
             let compare = compare
           end)

module StringMap =
  Map.Make(struct
             type t = string
             let compare = compare
           end)



(This could be done for modules Char, Int32, Int64 and NativeInt also)

By the way, one also could add functions "equal" and "hash" to these
modules...


Judicaël.
-- 
Judicael.Courant@lri.fr, http://www.lri.fr/~jcourant/
(+33) (0)1 69 15 64 85
"Montre moi des morceaux de ton monde, et je te montrerai le mien"
Tim, matricule #929, condamné à mort.
http://rozenn.picard.free.fr/tim.html

Re: Pervasives.compare: slow?

[Xavier Leroy]

> I used Pervasives.compare as a comparison function between hash values
> (16-byte strings). Pervasives.compare is a polymorphic hack that works by
> induction on the type information left for the garbage collector; even if
> you specify Pervasives.compare : string -> string -> int, it still invokes
> the polymorphic function.
> 
> There is apparently a 20-25% performance penalty using this form instead
> of a simple comparison procedure for 16-byte strings. I suspect the
> performance hit is even higher for more complex data structures.
> 
> Would it be possible to have ad hoc generated comparison functions? That
> sounds like it needs including polytypic features into the language, which
> is some very big stuff.

Actually, there is some "polytypic" optimisations going on in the
compiler.  For instance, the compiler will replace the generic "="
function by integer equality if both arguments are known to be of type
int.

Such "type-based strength reduction", as I like to call it, is
currently applied to all boolean comparisons (=, <>, <, <=, >, >=) but
not to "compare".  It could be done for "compare" as well; it's just
that no one has yet expressed a strong need for this...

- Xavier Leroy

Re: Pervasives.compare: slow?

[Anton Moscal]

On Tue, 20 Jun 2000, Judicael Courant wrote:

> idea indeed. May I suggest that a "type t = string" be added also ?
> 
> 
> 
> (This could be done for modules Char, Int32, Int64 and NativeInt also)

I argee. Also, add `type t = intxxx' in corresponding modules and
implement module Int with the same signature as of IntXX for usual
Caml int will be a good idea. This necessary for parametrisation functors
by the Int types. BigInt module also will be good idea.

Regards,
Anton Moscal

Re: Pervasives.compare: slow?

[Ruchira Datta]

David Monniaux wrote:

>Pervasives.compare is a polymorphic hack ...
>There is apparently a 20-25% performance penalty using this form instead
>of a simple comparison procedure for 16-byte strings. I suspect the
>performance hit is even higher for more complex data structures.

On p. 359 of _ML for the Working Programmer_, Paulson defines a function

fun member (x:string, l) = List.exists (fn y => x=y) l;

On the next page he says,

"The functor declares function member for internal use....  The membership
test is specific to type string because polymorphic equality can be slow."

He seems to imply that in Standard ML, if the type of the things being
compared is specified beforehand, then a type-specific comparison is used.
I don't know if something similar holds in Objective Caml.

Ruchira Datta
datta@math.berkeley.edu