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?
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 } }
endA 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:
def doubles_map n
(1..n).map {|i| i * i }
endAnd here is the Ruby equivalent of the Python example given (using
each versus for gives no difference in speed):
def doubles_each n
buf = []
(1..n).each do |i|
buf << i * i
end
buf
endFor 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:
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 } }
endHere 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:
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
endThis 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.
