From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 9DAB0BC84 for ; Thu, 24 Mar 2005 23:07:21 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j2OM7LmS025808 for ; Thu, 24 Mar 2005 23:07:21 +0100 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA19214 for ; Thu, 24 Mar 2005 23:07:20 +0100 (MET) Received: from swordfish.cs.caltech.edu (swordfish.cs.caltech.edu [131.215.44.124]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2OM7JIr007774 for ; Thu, 24 Mar 2005 23:07:20 +0100 Received: from [10.1.209.229] (mystic.caltech.edu [131.215.220.112]) by swordfish.cs.caltech.edu (Postfix) with ESMTP id D7163DF2EE; Thu, 24 Mar 2005 14:07:18 -0800 (PST) Message-ID: <42433A1C.2060203@cs.caltech.edu> Date: Thu, 24 Mar 2005 14:07:24 -0800 From: Jason Hickey User-Agent: Mozilla Thunderbird 0.9 (X11/20041127) X-Accept-Language: en-us, en MIME-Version: 1.0 To: caml-list@inria.fr Subject: Re: [Caml-list] Re: Pervasives.compare output type References: <42430B3B.60408@barettadeit.com> <20050324194115.GB9518@furbychan.cocan.org> <87acosu5c9.fsf@qrnik.zagroda> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 42433A19.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 42433A17.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 pervasives:01 integers:01 ocaml:01 byterun:01 integers:01 subtraction:01 subtraction:01 oops:01 printf:01 pervasives:01 eprintf:01 utime:01 utime:01 ...:98 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: 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