Re: [QUIZ] Twisting a Rope (#137)

On Fri, Aug 31, 2007 at 10:19:54PM +0900, Ruby Quiz wrote:
> by John Miller
> 
> This week's task is to implement the Rope data structure as a Ruby class.  This
> topic comes out of the ICFP programming competition
> (http://www.icfpcontest.com/) which had competitors manipulating a 7.5 million
> character string this year.

I happened to have implemented ropes in OCaml recently, so I generated a Ruby
extension using rocaml to see how well it would perform.

Without further ado, here are the results I'm getting for SIZE = 512 * 1024,
CHUNKS = 512:

$ time ruby -r himadri_choudhury.rb bm.rb Rope
Build:   0.130000   0.000000   0.130000 (  0.129476)
Sort:  10.340000   0.050000  10.390000 ( 10.648223)

$ time ruby -rocaml_rope bm.rb OCaml::Rope
Build:   0.020000   0.000000   0.020000 (  0.018946)
Sort:   0.100000   0.000000   0.100000 (  0.108499)

$ ruby eric_mahurin.rb StringRope
[...]
Build:   0.060000   0.000000   0.060000 (  0.057299)
Sort:   0.870000   0.000000   0.870000 (  0.896493)

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)

At that point the pure Ruby rope is taking over 6 times more memory than
the OCaml one. I ascribe this to iv_tbls being very heavy and to memory
fragmentation.

I benchmarked Himadri's implementation first and was surprised by the
exceedingly large speed difference --- I expected one, not two orders of
magnitude for this code, as there's enough Ruby code in common in qsort to
mask the speed gains in the rope operations. However, Eric's solution proved
that it was just due to a slow Ruby implementation.

Here's the interface definition (extconf.rb):


EXT_NAME = "ocaml_rope"
OCAML_PACKAGES = %w[]
CAML_LIBS = %w[]
CAML_OBJS = %w[]
CAML_FLAGS = ""
CAML_INCLUDES = []

require 'rocaml'

Interface.generate("ocaml_rope") do |iface|
  def_class("Rope", :under => "OCaml") do |c|
    rope = c.abstract_type

    fun "empty", UNIT => rope, :as => "new_empty"
    fun "of_string", STRING => rope, :as => "new_from_string"

    method "sub", [rope, INT, INT] => rope, :as => "slice"
    method "concat", [rope, rope] => rope
    method "length", rope => INT
    method "get", [rope, INT] => INT
    method "to_string", rope => STRING, :as => "to_s"
  end
end

require 'rocaml_extconf'


As you can see, OCaml::Rope is purely functional, and the interface differs a
bit from that expected by bm.rb (a modified version that works with immutable
ropes is attached), so I adapted it with the following ocaml_rope.rb, which
also loads the extension:


module OCaml # Rope will be placed in this module
end

require "ocaml_rope.so"

module OCaml
  class Rope
    def self.new(str = "")
      case str
      when String; new_from_string str
      when Rope; str
      when ""; new_empty
      else new_from_string(str.to_str) rescue new_from_string(str.to_s)
      end
    end

    def prepend(rope)
      rope.append(self)
    end

    alias_method :append, :concat
    alias_method :<<, :append
  end
end


The OCaml code is attached, in case anybody wants to look at it.
Incidentally, it weighs a bit under 220 lines, which is also the amount taken
by Himadri's and Eric's solutions. Unlike them, rope.ml features O(1)
concatenation for small elements; this accounts for a large part of the code
and the complexity of some patterns. O(1) concatenation doesn't really affect
performance in the use case exerted by bm.rb anyway.

-- 
Mauricio Fernandez  -   http://eigenclass.org