Re: [Caml-list] Re: Pervasives.compare output type

[Jason Hickey <jyh@cs.caltech.edu>]

Bardur Arantsson wrote:
> Actually, since integers in OCaml are limited to (n-1) bits where n=32
> or n=64 depending on architecture, overflow shouldn't be a problem. (The
> comments in byterun/compare.c also seem to agree with that.)
> 
> Even so, it would be very slow to the polymorphic compare to compare
> integers, so if one cares about efficiency, direct subtraction is
> preferable.
> 

This discussion just came up on the MetaPRL list.  Here is an excerpt.

---

By the way, I tried using subtraction for a comparison, and it failed 
miserably:(

...

It is easy to explain--transitivity breaks.  For example, using 
subtraction, the following two relations hold: (min_int < 0) and (0 < 
1); however (min_int > 1).  Oops...

Aleksey Nogin wrote some micro-benchmarks.  These are 
back-of-the-envelope, so don't take them as definitive.
> I wrote the following test:
> 
> ------------
> 
> open Printf
> open Unix
> 
> let f1  x       y = Pervasives.compare x y
> let f2 (x: int) y = Pervasives.compare x y
> let f3  x       y = if x=y then Pervasives.compare "s1" "s2" else if x < y then -1 else 1
> let f4 (x: int) y = if x=y then Pervasives.compare "s1" "s2" else if x < y then -1 else 1
> let f5  x       y = let i = Pervasives.compare x y in if i = 0 then Pervasives.compare "s1" "s2" else i
> let f6 (x: int) y = let i = Pervasives.compare x y in if i = 0 then Pervasives.compare "s1" "s2" else i
> let f7  x       y = match Pervasives.compare x y with 0 -> Pervasives.compare "s1" "s2" | i -> i
> let f8 (x: int) y = match Pervasives.compare x y with 0 -> Pervasives.compare "s1" "s2" | i -> i
> 
> let time name f =
>    let t1=Unix.times () in
>       for i = 10 to 30000000 do ignore(f i 20) done;
>       let t2=Unix.times () in
>          eprintf "Function %s: user time: %f; system time: %f\n%!" name (t2.tms_utime -. t1.tms_utime) (t2.tms_stime -. t1.tms_s
> time)
> 
> let time_all () =
>    time "f1" f1;
>    time "f2" f2;
>    time "f3" f3;
>    time "f4" f4;
>    time "f5" f5;
>    time "f6" f6;
>    time "f7" f7;
>    time "f8" f8
> 
> let () =
>    time_all ();
>    time_all ();
>    time_all ()
> 
> -----------------
> 
> and here are rhe approximate running times:
> 
> Function f1: user time: 1.060000; system time: 0.000000
> Function f2: user time: 0.520000; system time: 0.000000
> Function f3: user time: 2.970000; system time: 0.000000
> Function f4: user time: 0.340000; system time: 0.000000
> Function f5: user time: 1.110000; system time: 0.000000
> Function f6: user time: 0.570000; system time: 0.000000
> Function f7: user time: 1.110000; system time: 0.000000
> Function f8: user time: 0.550000; system time: 0.000000
> 
> -- 
> Aleksey Nogin 

Jason

-- 
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257