Jay Fields has a nice post about the goodness of Enumerable#inject in Ruby. Like anyone who enjoys functional programming, I appreciate the concept behind inject and its possible usage. Your language may implement it with a method called inject, a function fold or reduce, but the concept is the same. I think that there is nothing inherently evil about using Enumerable#inject in your code, however one must be very careful and question whether there are simpler alternatives available. Abuse of creative usage of inject or cleverness is often paid for in terms of the readability of the code and can’t be discouraged enough. Another good reason not use inject is when performance counts and we are dealing with large datasets. In Ruby 1.8 in fact, inject is much slower than an equivalent solution implemented with the each iterator or other available methods. People will tell you that this doesn’t matter, but in the real world, having a method take twice as long because you opted for inject rather than each, is not always justifiable or acceptable.
For example, the following snippet benchmarks four different methods for summing the first n natural numbers. It benchmarks them for n = 10, 102, 103, 104, 105, 106, 107 and 108. Please note that the problem at hand can be solved arithmetically, like Gauss did when he was 10, but it will serve us well to test differences in the raw speed of the compared methods provided by Ruby.
The sum_with_while is admittedly ugly, and entirely not idiomatic. No Rubyist would write the method in that way. It’s there though, in order to have a non-iterator, loop-based solution which doesn’t rely on methods from the Enumerable class. It will give us some perspective. Also, the choice of reopening the Integer class, rather than writing methods that accept n as an argument, is entirely arbitrary and doesn’t affect the benchmark in any way.
require 'benchmark'
include Benchmark
class Integer
def sum_with_inject
(1..self).inject(0) { |sum, i| sum + i }
end
def sum_with_each
sum = 0
(1..self).each { |i| sum += i }
sum
end
def sum_with_times
sum = 0
(self+1).times { |i| sum += i }
sum
end
def sum_with_while
sum, i = 0, 1
while i <= self
sum += i
i += 1
end
sum
end
end
(1..8).each do |p|
n = 10**p
puts "=== 10^#{p} ==="
benchmark do |x|
x.report("inject: ") { n.sum_with_inject }
x.report("each: ") { n.sum_with_each }
x.report("times: ") { n.sum_with_times }
x.report("while: ") { n.sum_with_while }
end
end
These are the results on my MacBook Pro Core 2 Duo 2.2GHz with ruby 1.8.6 (2007-09-24 patchlevel 111) [i686-darwin9.2.0]:
=== 10^1 ===
inject: 0.000000 0.000000 0.000000 ( 0.000071)
each: 0.000000 0.000000 0.000000 ( 0.000020)
times: 0.000000 0.000000 0.000000 ( 0.000018)
while: 0.000000 0.000000 0.000000 ( 0.000022)
=== 10^2 ===
inject: 0.000000 0.000000 0.000000 ( 0.000084)
each: 0.000000 0.000000 0.000000 ( 0.000043)
times: 0.000000 0.000000 0.000000 ( 0.000041)
while: 0.000000 0.000000 0.000000 ( 0.000058)
=== 10^3 ===
inject: 0.000000 0.000000 0.000000 ( 0.000677)
each: 0.000000 0.000000 0.000000 ( 0.000335)
times: 0.000000 0.000000 0.000000 ( 0.000338)
while: 0.000000 0.000000 0.000000 ( 0.000492)
=== 10^4 ===
inject: 0.010000 0.000000 0.010000 ( 0.008473)
each: 0.010000 0.000000 0.010000 ( 0.003258)
times: 0.000000 0.000000 0.000000 ( 0.003142)
while: 0.000000 0.000000 0.000000 ( 0.004887)
=== 10^5 ===
inject: 0.120000 0.000000 0.120000 ( 0.115180)
each: 0.060000 0.000000 0.060000 ( 0.071298)
times: 0.070000 0.000000 0.070000 ( 0.063845)
while: 0.080000 0.000000 0.080000 ( 0.079443)
=== 10^6 ===
inject: 1.410000 0.010000 1.420000 ( 1.414042)
each: 0.870000 0.000000 0.870000 ( 0.882625)
times: 0.870000 0.000000 0.870000 ( 0.875730)
while: 1.030000 0.000000 1.030000 ( 1.039151)
=== 10^7 ===
inject: 14.320000 0.030000 14.350000 ( 14.351873)
each: 9.050000 0.030000 9.080000 ( 9.086909)
times: 9.120000 0.020000 9.140000 ( 9.137516)
while: 10.610000 0.020000 10.630000 ( 10.654512)
=== 10^8 ===
inject: 144.070000 0.310000 144.380000 (144.517040)
each: 90.380000 0.360000 90.740000 ( 90.898424)
times: 89.960000 0.280000 90.240000 ( 90.476917)
while: 106.760000 0.380000 107.140000 (107.741355)
These results are not surprising. The ugly sum_with_while method is just slightly faster than the sum_with_inject one, while sum_with_each and sum_with_times are significantly faster than sum_with_inject. For n sufficiently large, each is (linearly) about 1.5 times faster than inject. Again, nothing new, if you have done some number crunching with Ruby, you already know a few tricks and the fact that inject is notoriously slow.
Just out of curiosity, I decided to see how things have improved with Ruby 1.9. Here comes the surprise: ruby 1.9.0 (2008-03-21 revision 15825) [i686-darwin9.2.0] yields the following results.
=== 10^1 ===
inject: 0.000000 0.000000 0.000000 ( 0.000045)
each: 0.000000 0.000000 0.000000 ( 0.000038)
times: 0.000000 0.000000 0.000000 ( 0.000040)
while: 0.000000 0.000000 0.000000 ( 0.000016)
=== 10^2 ===
inject: 0.000000 0.000000 0.000000 ( 0.000311)
each: 0.000000 0.000000 0.000000 ( 0.000293)
times: 0.000000 0.000000 0.000000 ( 0.000292)
while: 0.000000 0.000000 0.000000 ( 0.000014)
=== 10^3 ===
inject: 0.000000 0.000000 0.000000 ( 0.003008)
each: 0.000000 0.000000 0.000000 ( 0.002914)
times: 0.000000 0.000000 0.000000 ( 0.002891)
while: 0.000000 0.000000 0.000000 ( 0.000079)
=== 10^4 ===
inject: 0.020000 0.010000 0.030000 ( 0.029825)
each: 0.020000 0.010000 0.030000 ( 0.028448)
times: 0.020000 0.010000 0.030000 ( 0.028573)
while: 0.000000 0.000000 0.000000 ( 0.000717)
=== 10^5 ===
inject: 0.230000 0.090000 0.320000 ( 0.315088)
each: 0.210000 0.100000 0.310000 ( 0.306036)
times: 0.210000 0.090000 0.300000 ( 0.304437)
while: 0.030000 0.000000 0.030000 ( 0.021261)
=== 10^6 ===
inject: 2.410000 0.920000 3.330000 ( 3.332743)
each: 2.320000 0.930000 3.250000 ( 3.259242)
times: 2.320000 0.920000 3.240000 ( 3.233116)
while: 0.320000 0.000000 0.320000 ( 0.328699)
=== 10^7 ===
inject: 24.190000 9.150000 33.340000 ( 33.387602)
each: 23.350000 9.180000 32.530000 ( 32.795653)
times: 23.220000 9.100000 32.320000 ( 32.394359)
while: 3.360000 0.020000 3.380000 ( 3.377791)
=== 10^8 ===
inject: 243.020000 91.920000 334.940000 (335.498686)
each: 234.440000 92.490000 326.930000 (332.153885)
times: 234.680000 93.470000 328.150000 (355.418129)
while: 33.840000 0.160000 34.000000 ( 34.151623)
Look carefully, the good news is that while has been sped up by a factor of 3. You may notice that the execution time of the methods which employ inject, each and times are essentially the same in Ruby 1.9. This could be considered good news too, if we didn’t take a look at the previous output. All three methods in Ruby 1.9 are 2 to 3 times slower than in Ruby 1.8. each and times were both faster than while and are now 10 times slower! Forget about inject for a second, which after all can be avoided; but idiomatic Ruby code uses each iterators all over the place. Am I missing something, or Houston, do we have a problem? This loss of performance, if confirmed, should be considered as a bug.
To expose the extent of this regression, let’s see how JRuby 1.1RC3 (with the -J-server option enabled) performs:
==== 10^1 ===
inject: 0.150000 0.000000 0.150000 ( 0.150000)
each: 0.001000 0.000000 0.001000 ( 0.001000)
times: 0.001000 0.000000 0.001000 ( 0.001000)
while: 0.000000 0.000000 0.000000 ( 0.000000)
==== 10^2 ===
inject: 0.001000 0.000000 0.001000 ( 0.002000)
each: 0.001000 0.000000 0.001000 ( 0.001000)
times: 0.001000 0.000000 0.001000 ( 0.001000)
while: 0.000000 0.000000 0.000000 ( 0.001000)
==== 10^3 ===
inject: 0.011000 0.000000 0.011000 ( 0.011000)
each: 0.017000 0.000000 0.017000 ( 0.018000)
times: 0.012000 0.000000 0.012000 ( 0.012000)
while: 0.004000 0.000000 0.004000 ( 0.003000)
==== 10^4 ===
inject: 0.092000 0.000000 0.092000 ( 0.091000)
each: 0.020000 0.000000 0.020000 ( 0.020000)
times: 0.018000 0.000000 0.018000 ( 0.018000)
while: 0.008000 0.000000 0.008000 ( 0.008000)
==== 10^5 ===
inject: 0.059000 0.000000 0.059000 ( 0.058000)
each: 0.030000 0.000000 0.030000 ( 0.030000)
times: 0.031000 0.000000 0.031000 ( 0.031000)
while: 0.024000 0.000000 0.024000 ( 0.024000)
==== 10^6 ===
inject: 0.377000 0.000000 0.377000 ( 0.377000)
each: 0.269000 0.000000 0.269000 ( 0.268000)
times: 0.251000 0.000000 0.251000 ( 0.251000)
while: 0.153000 0.000000 0.153000 ( 0.154000)
==== 10^7 ===
inject: 3.411000 0.000000 3.411000 ( 3.411000)
each: 2.558000 0.000000 2.558000 ( 2.558000)
times: 2.492000 0.000000 2.492000 ( 2.493000)
while: 1.386000 0.000000 1.386000 ( 1.385000)
==== 10^8 ===
inject: 33.743000 0.000000 33.743000 ( 33.743000)
each: 25.408000 0.000000 25.408000 ( 25.408000)
times: 25.127000 0.000000 25.127000 ( 25.128000)
while: 13.834000 0.000000 13.834000 ( 13.835000)
sum_with_while (the quickest one of the lot) in JRuby is 2.5 times faster than Ruby 1.9, or almost 8 times faster than Ruby 1.8. inject, each and times are 10 to 13 times faster in JRuby than 1.9.
Believe it or not, even Rubinius is faster than Ruby 1.9 (excluding while):
=== 10^1 ===
inject: 0.000222 0.000000 0.000222 ( 0.000230)
each: 0.000152 0.000000 0.000152 ( 0.000154)
times: 0.000140 0.000000 0.000140 ( 0.000141)
while: 0.000148 0.000000 0.000148 ( 0.000149)
=== 10^2 ===
inject: 0.000390 0.000000 0.000390 ( 0.000394)
each: 0.000232 0.000000 0.000232 ( 0.000239)
times: 0.000164 0.000000 0.000164 ( 0.000165)
while: 0.000153 0.000000 0.000153 ( 0.000165)
=== 10^3 ===
inject: 0.001210 0.000000 0.001210 ( 0.001208)
each: 0.000827 0.000000 0.000827 ( 0.000828)
times: 0.000396 0.000000 0.000396 ( 0.000388)
while: 0.000223 0.000000 0.000223 ( 0.000224)
=== 10^4 ===
inject: 0.015619 0.000000 0.015619 ( 0.015602)
each: 0.006985 0.000000 0.006985 ( 0.006980)
times: 0.002393 0.000000 0.002393 ( 0.002397)
while: 0.001104 0.000000 0.001104 ( 0.001105)
=== 10^5 ===
inject: 0.212239 0.000000 0.212239 ( 0.212221)
each: 0.155911 0.000000 0.155911 ( 0.155898)
times: 0.114280 0.000000 0.114280 ( 0.114267)
while: 0.081416 0.000000 0.081416 ( 0.081400)
=== 10^6 ===
inject: 2.339344 0.000000 2.339344 ( 2.339332)
each: 1.880382 0.000000 1.880382 ( 1.880340)
times: 1.441064 0.000000 1.441064 ( 1.441048)
while: 1.277817 0.000000 1.277817 ( 1.277779)
=== 10^7 ===
inject: 23.969469 0.000000 23.969469 ( 23.969452)
each: 20.468222 0.000000 20.468222 ( 20.468203)
times: 16.952604 0.000000 16.952604 ( 16.952586)
while: 14.341948 0.000000 14.341948 ( 14.341921)
=== 10^8 ===
inject: 285.504220 0.000000 285.504220 (285.504203)
each: 233.995257 0.000000 233.995257 (233.995240)
times: 200.869457 0.000000 200.869457 (200.869444)
while: 196.518120 0.000000 196.518120 (196.518106)
Is this issue with Ruby 1.9 being addressed?
Update:
Upon further investigation, the issue has been confirmed on Mac OS X, but it doesn’t exist on Linux. From within a virtual machine running Ubuntu on my Mac, I got the following results:
=== 10^1 ===
inject: 0.000000 0.000000 0.000000 ( 0.000017)
each: 0.000000 0.000000 0.000000 ( 0.000009)
times: 0.000000 0.000000 0.000000 ( 0.000009)
while: 0.000000 0.000000 0.000000 ( 0.000007)
=== 10^2 ===
inject: 0.000000 0.000000 0.000000 ( 0.000025)
each: 0.000000 0.000000 0.000000 ( 0.000031)
times: 0.000000 0.000000 0.000000 ( 0.000024)
while: 0.000000 0.000000 0.000000 ( 0.000013)
=== 10^3 ===
inject: 0.000000 0.000000 0.000000 ( 0.000253)
each: 0.000000 0.000000 0.000000 ( 0.000131)
times: 0.000000 0.000000 0.000000 ( 0.000144)
while: 0.000000 0.000000 0.000000 ( 0.000001)
=== 10^4 ===
inject: 0.000000 0.000000 0.000000 ( 0.000000)
each: 0.000000 0.000000 0.000000 ( 0.000000)
times: 0.000000 0.000000 0.000000 ( 0.000000)
while: 0.000000 0.000000 0.000000 ( 0.000000)
=== 10^5 ===
inject: 0.040000 0.000000 0.040000 ( 0.028453)
each: 0.020000 0.000000 0.020000 ( 0.027007)
times: 0.030000 0.000000 0.030000 ( 0.025450)
while: 0.010000 0.000000 0.010000 ( 0.015040)
=== 10^6 ===
inject: 0.360000 0.000000 0.360000 ( 0.358824)
each: 0.340000 0.000000 0.340000 ( 0.333370)
times: 0.370000 0.000000 0.370000 ( 0.378156)
while: 0.240000 0.000000 0.240000 ( 0.243033)
=== 10^7 ===
inject: 4.040000 0.000000 4.040000 ( 4.046872)
each: 4.120000 0.010000 4.130000 ( 4.160456)
times: 3.530000 0.000000 3.530000 ( 3.544973)
while: 2.610000 0.000000 2.610000 ( 2.613019)
=== 10^8 ===
inject: 44.870000 0.040000 44.910000 ( 45.146779)
each: 37.590000 0.020000 37.610000 ( 37.803406)
times: 36.550000 0.010000 36.560000 ( 36.618813)
while: 26.690000 0.010000 26.700000 ( 26.747007)
Conclusion: the inject, each and times methods are much slower in Ruby 1.9 on Mac. As you can see from the comments, this seems to be caused by the fact that the function sigsetjmp() was introduced during revision 15124 and it happens to be much slower on Mac OS X than it is on Linux.
Get more stuff like this
Subscribe to my mailing list to receive similar updates about programming.
Thank you for subscribing. Please check your email to confirm your subscription.
Something went wrong.
Try the 1.9.0 that was released on Christmas. inject is faster than both 1.8.6 and the version of 1.9.0 that you used. The fact that inject has gotten much slower between those releases at least tells us something.
Wow, great numbers for JRuby. May we include this benchmark in our suite?
Of course Charles, please go ahead.
Have you tried running these benchmarks against Rubinius? I am curious
Lawrence: I ran it against the five implementations I have access to: Ruby 1.8.6p111, Ruby 1.9 trunk, Rubinius trunk, MacRuby trunk, and JRuby trunk. The results on my system are here:
http://pastie.org/170572
Good idea Lawrence, I’ve added Rubinius’ results. 🙂
I can’t reproduce that benchmarks. On my machine I get:
All compiled from sourced and updated from svn today. For all results look at pastie: http://pastie.caboo.se/170627
So, ruby1.9 is more that 2x faster that MRI, but the fastest jruby :).
Radarek, that’s odd. Charles’ results are close to mine, but yours aren’t. I wonder if this is a Linux vs Mac issue.
Thanks Hans-Georg. There is definitely a huge performance regression for these methods in Ruby 1.9, at least on Mac. I’ll try it out on Linux.
I wonder if there is some sort of clean up going on inside of Enumerable. Anyone know if they are doing something that currently slows down these methods, but in the long term will regain the speed?
JD
Hi James, it appears to be a Mac only issue, therefore I don’t think it’s something done intentionally.
I wrote a script to find when this happened. On my mac, using this inject benchmark I found on the Ruby talk mailing list (http://pastie.caboo.se/170752), the runtime jumps from 3 seconds to 35 seconds at revision 15124. The diff between 15123 and 15124 can be seen here: http://pastie.caboo.se/170751
I hope that helps figuring this out.
That’s excellent, Chris. 🙂
http://pastie.caboo.se/170779
@Andrés Suárez: Your results are explained by three possible factors:
1) Are you running the script on Linux/Windows or Mac? The problem appears to be a Mac only issue;
2) The version of Ruby 1.9 that introduces the performance problem is a recent one, not the one that was released at Christmas that you tested;
3) Did you run JRuby with the -J-server option and with the latest version of the JDK?
Antonio Cangiano, I guess that you should change title to “‘inject’, ‘each’ and ‘times’ methods much slower in Ruby 1.9 on Mac OS X” :).
@Radarek: Done. 🙂
1) I’m running the script under Windows.
2) Sorry, but I don’t know where to find the binaries of Ruby 1.9.0-1
3) You’ve reason. After installing the last jdk and using the “J-server” option the result are much better:
http://pastie.caboo.se/171028
=== 10^7 ===
inject: 3.266000 0.000000 3.266000 ( 3.270037)
each: 2.406000 0.000000 2.406000 ( 2.402494)
times: 2.344000 0.000000 2.344000 ( 2.343239)
while: 1.031000 0.000000 1.031000 ( 1.045526)
=== 10^8 ===
inject: 33.094000 0.000000 33.094000 ( 33.102321)
each: 24.828000 0.000000 24.828000 ( 24.827342)
times: 23.922000 0.000000 23.922000 ( 23.919247)
while: 10.297000 0.000000 10.297000 ( 10.299023)
Thanks, and keep doing your good work Antonio.
The benchmarks seem very high ( slow) on Windows using ruby 1.8.6 (2007-03-13 patchlevel 0) [i386-mswin32]
=== 10^7 ===
inject: 35.735000 0.265000 36.000000 ( 36.297000)
each: 23.171000 0.172000 23.343000 ( 23.550000)
times: 22.422000 0.250000 22.672000 ( 22.804000)
while: 30.407000 0.156000 30.563000 ( 30.882000)
=== 10^8 ===
inject: 362.296000 2.469000 364.765000 (368.944000)
each: 235.922000 2.203000 238.125000 (240.274000)
times: 228.188000 2.172000 230.360000 (231.533000)
while: 249.031000 2.141000 251.172000 (252.498000)
Is this typical for the Windows version of ruby.exe?