On Mon, Sep 03, 2007 at 05:52:31PM +0900, Mauricio Fernandez wrote:
> I happened to have implemented ropes in OCaml recently, so I generated a Ruby
> extension using rocaml to see how well it would perform.
> 
[...]
> For SIZE = 1024, CHUNKS = 16384:
> 
> $ ruby eric_mahurin.rb StringRope
> [...]
> Build:   3.470000   0.040000   3.510000 (  3.588875)
> Sort:  89.110000   0.700000  89.810000 ( 92.179962)
> 
> $ time ruby -rocaml_rope bm.rb OCaml::Rope
> [...]
> Build:   0.360000   0.000000   0.360000 (  0.378352)
> Sort:   3.940000   0.040000   3.980000 (  4.079140)

Also for laughs, playing with the GC parameters and with a qsort implemented
in OCaml:

$ OCAMLRUNPARAM=s=512k ruby -rocaml_rope bm.rb OCaml::Rope
[...]
Build:	  0.290000   0.000000   0.290000 (  0.290908)
Sort:	  3.410000   0.040000   3.450000 (  3.547792)
Sort':	  0.830000   0.000000   0.830000 (  0.845180)

Yielding the expected >100x gain over Ruby.

The interface part:

method "qsort", [rope, INT] => rope method "qsort2", [rope, INT] => rope
I implemented the qsort function both in functional and imperative style, for the sake of those who prefer something that reads similarly to the Ruby version. The two variants are equally fast.
let (<<) = concat (* OCaml allows you to define new operators *) let to_i = int_of_string let to_s = to_string let rec qsort' size = function Empty -> Empty | rope -> let pivot = to_i (to_s (sub 0 8 rope)) in let len = 8 + size in let less = ref Empty in let more = ref Empty in let off = ref len in while !off < length rope do let slice = sub !off len rope in if to_i (to_s (sub !off 8 rope)) < pivot then less := !less << slice else more := !more << slice; off := !off + len done; qsort' size !less << sub 0 len rope << qsort' size !more let rec qsort size = function Empty -> Empty | rope -> let rec loop r pivot off len max less more = if off < max then begin if to_i (to_s (sub off 8 r)) < pivot then loop r pivot (off+len) len max (less << (sub off len r)) more else loop r pivot (off+len) len max less (more << (sub off len r)) end else (less, more) in let pivot = to_i (to_s (sub 0 8 rope)) in let len = 8 + size in let less, more = loop rope pivot len len (length rope) Empty Empty in qsort size less << sub 0 len rope << qsort size more
-- Mauricio Fernandez - http://eigenclass.org