Benchmarking Functional vs Data Based Lists in Ruby

At GoGaRuCo 2010 (Golden Gate Ruby Conference), Jim Weirich (@jimweirich) gave a great keynote on Functional and Object Oriented programming in Ruby. In the pres, he threw up some code to implement lists using a simple data structure and alternatively as Procs that relied on closures to keep state.

It seemed like it would take a lot more work for Ruby to build all these Proc objects, but I wasn't actually sure, so I decided to benchmark it. As it turns out, the functional approach is the slowest, but it's closer to a data based approach than I would have expected.

Here is Jim's code for the data structure based approach:

List = Struct.new(:head, :tail)
Cons = ->(h,t) { List.new(h,t) }
Car = ->(list) { list.head }
Cdr = ->(list) { list.tail }


and here is his code for a Proc based approach (using the 1.9 syntax)

f_Cons = ->(h,t) { ->(s) { (s==:h) ? h : t } }
f_Car = ->(list) { list.(:h) }
f_Cdr = ->(list) { list.(:t) }


just out of curiosity, I also wrote a standard Class based approach as well (this uses the idiomatic object.message style rather than the "bare message" style which is more like what you'd see in a Lisp/Scheme based language)

class List2
attr_reader :car, :cdr

def initialize(car, cdr)
@car = car
@cdr = cdr
end

def self.Cons(car, cdr)
List2.new(car, cdr)
end
end


Just to show that all the implementations are working

#Data based
lst = Cons.(1, Cons.(Cons.(2, Cons.(3, nil)), Cons.(4, Cons.(5,nil))))
raise "Problem with Car and Cdr" unless Car.(Cdr.(Cdr.(l))) == 4

#Functional
f_lst = f_Cons.(1, f_Cons.(f_Cons.(2, f_Cons.(3, nil)), f_Cons.(4, f_Cons.(5,nil))))
raise "Problem with f_Car and f_Cdr" unless f_Car.(f_Cdr.(f_Cdr.(f_lst))) == 4

#Class based
c_lst = List2.Cons(1, List2.Cons(List2.Cons(2, List2.Cons(3, nil)), List2.Cons(4, List2.Cons(5,nil))))
raise "Problem with List2.car and List2.cdr" unless c_lst.cdr.cdr.car


and then I benchmarked them over 100,000 list creations and 5,000,000 extractions of the "4" from inside the list:

require 'benchmark'
c = 100_000
n = 5_000_000
#this benchmarks creates and extracting the "4" from (1, (2, 3), 4, 5)
Benchmark.bm do |rpt|
rpt.report("List Create") { c.times do; Cons.(1, Cons.(Cons.(2, Cons.(3, nil)), Cons.(4, Cons.(5,nil)))); end;}
rpt.report("List Extract") { n.times do; Car.(Cdr.(Cdr.(lst))); end;}
rpt.report("Func Create") { c.times do; f_Cons.(1, f_Cons.(f_Cons.(2, f_Cons.(3, nil)), f_Cons.(4, f_Cons.(5,nil)))); end;}
rpt.report("Func Extract") { n.times do; f_Car.(f_Cdr.(f_Cdr.(f_lst))); end;}
rpt.report("Class Create") { c.times do; List2.Cons(1, List2.Cons(List2.Cons(2, List2.Cons(3, nil)), List2.Cons(4, List2.Cons(5,nil)))); end;}
rpt.report("Class Extract") { n.times do; c_lst.cdr.cdr.car; end;}
end


and got this for results (on a 2.8GHz MacBookPro from 2008)

user system total real
List Create 0.270000 0.000000 0.270000 ( 0.263856)
List Extract 3.230000 0.000000 3.230000 ( 3.238410)
Func Create 0.630000 0.080000 0.710000 ( 0.699868)
Func Extract 6.410000 0.010000 6.420000 ( 6.417965)
Class Create 0.210000 0.000000 0.210000 ( 0.217196)
Class Extract 1.100000 0.000000 1.100000 ( 1.090477)


So the Functional approach is definitely slower that the list based (2.6x on create, 2x on extract), but that was a smaller gap than I expected.

I was also surprised that the Class based approach was so much faster than the List based approach (2.9x on extract) since the List implementation is just using Struct.new. It looks like executing a "stubby proc" is quite a bit slower than running an instance method.

For anyone who wants to play with this, all the code is up on github in a gist (http://gist.github.com/588512)