What kind of sort do Array.sort ?

* What kind of sort do Array.sort ?
@ 2006-05-08 21:31 artboreb
  2006-05-08 22:23 ` [Caml-list] " Martin Jambon
  0 siblings, 1 reply; 4+ messages in thread
From: artboreb @ 2006-05-08 21:31 UTC (permalink / raw)
  To: caml-list

Dear Calmers,
Toying with a compiler (builded in Ocaml of course) of a language I 
developed which emits C code
I've written some bemchmarks to test it. For my surprise the same 
program written in Ocaml lasts
almost 6 times. It's about sorting an integer array, the timings are:

Ocaml  (ocamlopt -unsafe unix.cmxa qc.ml -o qc)
real    1m10.727s
user    1m9.074s
sys     0m0.001s

Mine   (gcc -I /usr/local/include -O3 -s x12.ao.c -o x12 
/usr/local/lib/libgc.a -lpthread)
real    0m18.536s
user    0m18.018s
sys     0m0.002s

times to take sorting 1000000 an array of 100 random ints
the Ocaml code is

open Format

let _ =
  if Array.length Sys.argv = 2 then
    begin
      Random.init (Unix.getpid ());
      let a = Array.make (int_of_string Sys.argv.(1)) 0 in
      for i = 0 to 1000000 do
        for j = 0 to Array.length a - 1 do a.(j) <- Random.bits () done;
         Array.sort (fun x y -> if x > y then 1 else if x = y then 0 
else -1) a
      done;
      for i = 0 to 99 do printf "%010d\n" a.(i) done
    end

I dont attach the C code emitted because is about 280 lines long,
my language (for the courious)

"ao.ao" INC

[Array Int Int] # RAPIDO RECURSIVO                                      

[(a l r) l r a l -> (hl hr p)                                           

   [l r] [l r >=] [l]                                                    

   [ [r] [a r -> p >= l r < & !] [r] [r 1 -] TREC (r)                    

     l l r =/= [a a r -> l <<- 1 +] IFTE (l)                             

     [l] [a l -> p <= l r < & !] [l] [l 1 +] TREC (l) l                  

     r l r =/= [a a l -> r <<- 1 -] IFTE] TREC (l)                       

   a p l <- hl l < [hl l 1 - Qsort] IFTE hr l > [l 1 + hr Qsort] IFTE    

] Qsort FUN

ARGC 2 =                                                                

   [ Getpid Srand [;Int] ARGV 1 -> Atoi MAKE Length 1 - (a n)            

     [[(i) a Rand i <<-] 0 n Upto a 0 n Qsort X-] 1000000 Times          

     a [?n] Fold                                                         

     #[] [Rand "%010d" FMT] Rnd_strnum FUN                               

  ] IFTE

Best regards,

Arturo Borquez
___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com

^ permalink raw reply	[flat|nested] 4+ messages in thread