Re: [Caml-list] Beware of compare (and Ocaml beaten by Java)

[Xavier Leroy <xavier.leroy@inria.fr>]

> Why isn't compare compiled as '-'? According to the definition
> of compare this should be okay.

I assume you mean "compare at type int -> int -> int", because for
types represented as pointers, pointer subtraction wouldn't give
reliable results -- for one thing, the GC can move blocks around.

Even on integer arguments, "-" cannot be used due to arithmetic
overflow:

  compare min_int max_int = -1    (* correct *)
  min_int - max_int = 1           (* incorrect *)

So, replacing "compare" by "-" is only valid for small integer types
such as "char" and enumerated datatypes, and I felt this wasn't
important enough to implement.  (Given your example, you'll disagree,
of course.)

> The core of the slow program is
> 
> (* compare two substrings of the SAME text 
>    [compare x y] returns [0] if [x=y], a negative integer if
>    [x<y], and a positive integer if [x>y] *)
> let rec same_substr_compare str idx1 idx2 : int =
>   let length = String.length str in
>   (* shortest string is smaller *)
>   if idx1 = length then -1 else
>   if idx2 = length then 1 else 
>   (* compare one char *)
>   let res = compare str.[idx1] str.[idx2] in
>   (* char was equal, recurse *)
>   if res = 0 then same_substr_compare str (idx1+1) (idx2+1)
>   (* char was different, finished *)
>   else res ;;

I get the impression that same_substr_compare never returns 0; is this
intentional?

> 3. Mergesort (=Array.stable_sort) is faster than 
> heapsort (=Array.sort). (runtime down from 60s to 40s).
> (I also tried quicksort (=Sort.array), but after 8 hours
> it still hadn't finished.)

This is a bit surprising: you might have hit one of those cases where
Quicksort is O(n^2), but it could also be the case that Sort.array
malfunctions because your comparison function is not a proper
comparison function (it doesn't return 0 for equal things).

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr