Toxic Elephant

Some thoughts on Ruby's speed

Posted by matijs 02/03/2013 at 16h42

Yesterday, I read Alex Gaynor’s slides on dynamic language
speed.
It’s an interesting argument, but I’m not totally convinced.

At a high level, the argument is as follows, it seems:

• For a comparable algorithm, Ruby et al. do much more work behind the
  scenes than ‘fast’ languages such as C.
• In particular, they do a lot of memory allocation.
• Therefore, we should add tools to those languages that allow us to do
  memory allocation more efficiently.

Allocation

As an example, the creation of an array of squared integers is
presented, where the runtime needs to dynamically allocate ever larger
arrays to hold its result.

I can see the argument there, but I’m not convinced the solution is
correct, for the example given. In particular, how much time is spent
allocating and re-allocating the array of object references, and how
much is spent elsewehere?

<typo:code lang=“ruby”>
require ‘benchmark’

def doubles_unallocated n
buf = []
i = 1; j = 0
while j < n do
buf[i - 1] = i * i
i += 1; j += 1
end
buf
end

def doubles_preallocated n
buf = Array.new n
i = 1; j = 0
while j < n do
buf[j] = i * i
i += 1; j += 1
end
buf
end

n = 10000

Benchmark.bmbm do |x|
x.report(“unallocated”) { n.times { doubles_unallocated 1000 } }
x.report(“preallocated”) { n.times { doubles_preallocated 1000 } }
end
</typo:code>

A typical result on Ruby 1.9.3 would be (I’m not showing the rehearsal section here):

                   user     system      total        real
unallocated    1.480000   0.020000   1.500000 (  1.493959)
preallocated   1.370000   0.030000   1.400000 (  1.404668)

Taking several runs into account, I conclude that pre-allocating the
array shaves off 7 to 13 percent of the runtime.

Algorithms

The algorithms used above are obviously not idiomatic Ruby, but they
have the advantage of allowing a comparison of allocated and unallocated
arrays. Normally, I would probably use map with a range. Similarly, the
Python code presented in the slides looks odd to me. I would have
expected something using list comprehensions.

Here is the idiomatic Ruby implementation:

<typo:code lang=“ruby”>
def doubles_map n
(1..n).map {|i| i * i }
end
</typo:code>

And here is the Ruby equivalent of the Python example given (using
each versus for gives no difference in speed):

<typo:code lang=“ruby”>
def doubles_each n
buf = []
(1..n).each do |i|
buf « i * i
end
buf
end
</typo:code>

For Ruby, doubles_map is the idiomatic implementation. It also has the
advantage that a dedicated implementation of Range#map would be able
to allocate the result array in one go, transparantly avoiding the
array growing overhead. Using list comprehensions in Python would
probably have the same advantage.

Unfortunately, doubles_map is also a lot slower than doubles_each,
except on MRI 1.8. Here is the benchmark I ran with a fixed-array
version thrown in for good measure:

<typo:code lang=“ruby”>
ARR = (1..1000).to_a
def doubles_fixed_array
ARR.map {|i| i * i }
end

n = 10000

Benchmark.bmbm do |x|
x.report(“using map”) { n.times { doubles_map 1000 } }
x.report(“using each”) { n.times { doubles_each 1000 } }
x.report(“using a fixed array”) { n.times { doubles_fixed_array } }
end
</typo:code>

Here is the result for MRI 1.9.3:

                          user     system      total        real
using map             1.220000   0.000000   1.220000 (  1.217607)
using each            1.070000   0.020000   1.090000 (  1.091302)
using a fixed array   0.940000   0.020000   0.960000 (  0.969685)

And for MRI 1.8.7:

                          user     system      total        real
using map             2.790000   0.000000   2.790000 (  2.795956)
using each            3.630000   0.010000   3.640000 (  3.644272)
using a fixed array   2.120000   0.010000   2.130000 (  2.133636)

A better Range#map

These benchmark results made me wonder how Range#map is implemented.
Since it is written in Ruby, I checked the Rubinius implementation, and there
at least the problem seems due to the lack of a dedicated Range#map
implementation: The generic Enumerable#map is used, effectively turning
it into doubles_each. I’m not entirely sure why it is actually slower,
perhaps that’s due to the double yield involved and/or argument
splatting.

Here are the results of the previous benchmark, run on Rubinius 2.0.0-rc1:

                          user     system      total        real
using map             1.312082   0.004000   1.316082 (  1.316717)
using each            0.996062   0.000000   0.996062 (  0.997418)
using a fixed array   0.720045   0.000000   0.720045 (  0.724615)

I made the following simple dedicated implementation for Range#map.
It falls back to the default Enumerable#map for most cases, except for
Fixnums:

<typo:code lang=“ruby”>
class Range
def map
if block_given? && Fixnum === @begin
first, last = @begin, @end
last -= 1 if @excl
size = last - first + 1

  out = Array.new size
  out_tuple = out.tuple

  i = first
  j = 0
  while i <= last
    out_tuple[j] = yield i
    i += 1
    j += 1
  end

  out
else
  super
end

end
end
</typo:code>

This makes doubles_map run slightly faster than the fixed array
version:

                          user     system      total        real
using map             0.648040   0.000000   0.648040 (  0.650103)
using each            0.928058   0.000000   0.928058 (  0.930109)
using a fixed array   0.680042   0.004001   0.684043 (  0.686719)

Benchmarking Still Needed

While examining these options, I found that there are many ways to write
this code, each subtly different, each with a different performance on
different Rubies (the examples using while are the slowest on MRI
1.9.3, but the fastest on Rubinus). So, if you really want your code to
be fast, you still have to benchmark, you still have to know which Ruby
implementation your code will run on, and you still have to try all the
options.