Ross Bamford
2/14/2006 4:43:00 PM
On Tue, 2006-02-14 at 01:57 +0900, James Edward Gray II wrote:
> On Feb 10, 2006, at 7:53 AM, Ruby Quiz wrote:
>
> > This week's Ruby Quiz is to write FasterGenerator, your own re-
> > implementation of
> > Generator with an eye towards working faster.
>
> Is anyone willing to benchmark the submitted solutions, the old
> callcc generator, and the new threaded generator for me? I"m not
> usually much of a fan, but it's probably worth seeing them this time,
> and I'm horribly busy right now.
Here's some I ran up on Ruby 1.8.4-2005-12-24, and results of test runs
too. Apologies for the length of this. I tried to be sure I got all the
entries, but let me know if I missed any.
In these tests and timings, please note that Jacob Fugal's entry was
patched with one line to solve a deadlock issue (as described in my
message a few minutes ago, along with said patch).
### Construction ###
Rehearsal -------------------------------------------------------------
New Thread Generator 0.240000 0.060000 0.300000 ( 0.355258)
Old callcc Generator 0.260000 0.090000 0.350000 ( 0.362992)
RossBamfordGenerator 1.060000 0.060000 1.120000 ( 1.177169)
JesseYoonGenerator 2.470000 0.090000 2.560000 ( 2.577881)
JacobFugalGenerator 0.020000 0.000000 0.020000 ( 0.016604)
JEGIIGenerator 0.000000 0.000000 0.000000 ( 0.003643)
HorndudeGenerator 1.210000 0.010000 1.220000 ( 1.226004)
DaveLeeGenerator 0.010000 0.000000 0.010000 ( 0.007378)
ChristofferLernoGenerator 0.010000 0.000000 0.010000 ( 0.004829)
CalebClausenSyncGenerator 3.300000 0.070000 3.370000 ( 3.364630)
CalebClausenGenerator 7.320000 0.100000 7.420000 ( 7.455628)
--------------------------------------------------- total: 16.380000sec
user system total real
New Thread Generator 4.510000 0.090000 4.600000 ( 4.629948)
Old callcc Generator 0.100000 0.070000 0.170000 ( 0.172726)
RossBamfordGenerator 5.750000 0.040000 5.790000 ( 5.840663)
JesseYoonGenerator 7.250000 0.100000 7.350000 ( 7.385956)
JacobFugalGenerator 0.030000 0.000000 0.030000 ( 0.027147)
JEGIIGenerator 0.010000 0.000000 0.010000 ( 0.009369)
HorndudeGenerator 2.070000 0.010000 2.080000 ( 2.093749)
DaveLeeGenerator 0.010000 0.000000 0.010000 ( 0.009289)
ChristofferLernoGenerator 0.010000 0.000000 0.010000 ( 0.004079)
CalebClausenSyncGenerator 8.960000 0.100000 9.060000 ( 9.087102)
CalebClausenGenerator 13.890000 0.120000 14.010000 ( 14.085276)
### next() ###
Rehearsal -------------------------------------------------------------
New Thread Generator 0.530000 0.010000 0.540000 ( 0.582000)
Old callcc Generator 1.440000 0.340000 1.780000 ( 1.869542)
RossBamfordGenerator 0.520000 0.000000 0.520000 ( 0.553655)
JesseYoonGenerator 1.350000 0.010000 1.360000 ( 1.406985)
JacobFugalGenerator 0.470000 0.000000 0.470000 ( 0.509629)
JEGIIGenerator 0.040000 0.000000 0.040000 ( 0.085259)
HorndudeGenerator 0.000000 0.000000 0.000000 ( 0.006366)
DaveLeeGenerator 0.060000 0.000000 0.060000 ( 0.055963)
ChristofferLernoGenerator 0.060000 0.000000 0.060000 ( 0.100153)
CalebClausenSyncGenerator 0.660000 0.000000 0.660000 ( 0.710609)
CalebClausenGenerator 0.440000 0.000000 0.440000 ( 0.495331)
---------------------------------------------------- total: 5.930000sec
user system total real
New Thread Generator 0.530000 0.000000 0.530000 ( 0.529631)
Old callcc Generator 1.480000 0.260000 1.740000 ( 1.753356)
RossBamfordGenerator 0.500000 0.010000 0.510000 ( 0.511533)
JesseYoonGenerator 1.420000 0.010000 1.430000 ( 1.431172)
JacobFugalGenerator 0.470000 0.000000 0.470000 ( 0.472486)
JEGIIGenerator 0.040000 0.000000 0.040000 ( 0.042084)
HorndudeGenerator 0.000000 0.000000 0.000000 ( 0.006730)
DaveLeeGenerator 0.060000 0.000000 0.060000 ( 0.053328)
ChristofferLernoGenerator 0.060000 0.000000 0.060000 ( 0.055085)
CalebClausenSyncGenerator 0.670000 0.010000 0.680000 ( 0.674632)
CalebClausenGenerator 0.440000 0.000000 0.440000 ( 0.442706)
And on a current 1.9.0 (2006-2-13), just for informational value:
### Construction ###
Rehearsal -------------------------------------------------------------
New Thread Generator 0.180000 0.010000 0.190000 ( 0.186852)
Old callcc Generator 0.210000 0.060000 0.270000 ( 0.267589)
RossBamfordGenerator 0.190000 0.010000 0.200000 ( 0.200867)
JesseYoonGenerator 1.250000 0.040000 1.290000 ( 1.288486)
JacobFugalGenerator 0.220000 0.000000 0.220000 ( 0.228049)
JEGIIGenerator 0.010000 0.000000 0.010000 ( 0.003091)
DaveLeeGenerator 0.000000 0.000000 0.000000 ( 0.004096)
ChristofferLernoGenerator 0.000000 0.000000 0.000000 ( 0.002906)
CalebClausenSyncGenerator 0.240000 0.000000 0.240000 ( 0.234202)
CalebClausenGenerator 3.320000 0.040000 3.360000 ( 3.370295)
---------------------------------------------------- total: 5.780000sec
user system total real
New Thread Generator 0.210000 0.000000 0.210000 ( 0.205367)
Old callcc Generator 0.070000 0.000000 0.070000 ( 0.071999)
RossBamfordGenerator 0.210000 0.000000 0.210000 ( 0.211517)
JesseYoonGenerator 0.260000 0.000000 0.260000 ( 0.271282)
JacobFugalGenerator 0.010000 0.000000 0.010000 ( 0.011128)
JEGIIGenerator 0.000000 0.000000 0.000000 ( 0.003410)
DaveLeeGenerator 0.000000 0.000000 0.000000 ( 0.003958)
ChristofferLernoGenerator 0.000000 0.000000 0.000000 ( 0.002700)
CalebClausenSyncGenerator 0.220000 0.000000 0.220000 ( 0.230006)
CalebClausenGenerator 2.970000 0.030000 3.000000 ( 3.008657)
### next() ###
Rehearsal -------------------------------------------------------------
New Thread Generator 0.370000 0.000000 0.370000 ( 0.432432)
Old callcc Generator 1.310000 0.260000 1.570000 ( 1.579197)
RossBamfordGenerator 0.350000 0.010000 0.360000 ( 0.365862)
JesseYoonGenerator 0.950000 0.010000 0.960000 ( 0.968764)
JacobFugalGenerator 0.450000 0.000000 0.450000 ( 0.464338)
JEGIIGenerator 0.040000 0.000000 0.040000 ( 0.041824)
DaveLeeGenerator 0.060000 0.000000 0.060000 ( 0.050352)
ChristofferLernoGenerator 0.040000 0.000000 0.040000 ( 0.052046)
CalebClausenSyncGenerator 0.530000 0.000000 0.530000 ( 0.532814)
CalebClausenGenerator 0.400000 0.000000 0.400000 ( 0.400555)
---------------------------------------------------- total: 4.780000sec
user system total real
New Thread Generator 0.370000 0.010000 0.380000 ( 0.371918)
Old callcc Generator 1.430000 0.020000 1.450000 ( 1.459838)
RossBamfordGenerator 0.350000 0.010000 0.360000 ( 0.353515)
JesseYoonGenerator 0.950000 0.000000 0.950000 ( 0.958286)
JacobFugalGenerator 0.450000 0.010000 0.460000 ( 0.452084)
JEGIIGenerator 0.040000 0.000000 0.040000 ( 0.042236)
DaveLeeGenerator 0.050000 0.000000 0.050000 ( 0.050518)
ChristofferLernoGenerator 0.050000 0.000000 0.050000 ( 0.050332)
CalebClausenSyncGenerator 0.530000 0.000000 0.530000 ( 0.528834)
CalebClausenGenerator 0.380000 0.000000 0.380000 ( 0.381354)
(Horndude's solution was ommitted from 1.9 testing owing to a c-side
Ruby garbage collection bug that appears intermittently under 1.8 and
reliably with 1.9. It appears to be marking an invalid object with
rb_gc_mark()).
I also (having too little to do, and too much time to do it in) ran
James' original test-cases, plus the realtime test posted in the NG and
a simple endless iterator test (posted below the results). Two passed
all, two passed endless but not realtime, and the others didn't pass
either (but still passed the basic tests of course).
###### Supporting everything #####
### TESTING: rbamf_fgenerator.rb
Loaded suite tests
Started
.....
Finished in 1.059739 seconds.
5 tests, 1560 assertions, 0 failures, 0 errors
### TESTING: jfugal_faster_generator.rb
Loaded suite tests
Started
.....
Finished in 1.063294 seconds.
5 tests, 1560 assertions, 0 failures, 0 errors
###### Supporting infinite iterators but *not* realtime. #####
### TESTING: davelee_generator.rb
Loaded suite tests
Started
....E
Finished in 1.075006 seconds.
1) Error:
test_realtime(TC_TGenerator):
NoMethodError: undefined method `size' for nil:NilClass
./davelee_generator.rb:82:in `spent?'
./davelee_generator.rb:32:in `current'
./davelee_generator.rb:55:in `next'
tests.rb:179:in `test_realtime'
tests.rb:177:in `test_realtime'
tests.rb:174:in `test_realtime'
5 tests, 1557 assertions, 0 failures, 1 errors
### TESTING: jesse_yoon_generator.rb
Loaded suite tests
Started
....F
Finished in 1.081433 seconds.
1) Failure:
test_realtime(TC_TGenerator)
[tests.rb:179:in `test_realtime'
tests.rb:177:in `test_realtime'
tests.rb:174:in `test_realtime']:
<0> expected but was
<nil>.
5 tests, 1558 assertions, 1 failures, 0 errors
###### No endless iterator / realtime support #####
### TESTING: horndude_generator.so
Loaded suite tests
Started
...EE
Finished in 30.657187 seconds.
1) Error:
test_endless(TC_TGenerator):
RuntimeError: Endless iterators unsupported
tests.rb:153:in `test_endless'
tests.rb:120:in `test_endless'
2) Error:
test_realtime(TC_TGenerator):
NoMethodError: undefined method `entries' for #<TC_TGenerator::C:0xb7ed80d4>
tests.rb:176:in `initialize'
tests.rb:176:in `test_realtime'
tests.rb:174:in `test_realtime'
5 tests, 54 assertions, 0 failures, 2 errors
### TESTING: christoffer_lerno_generator.rb
Loaded suite tests
Started
...E./christoffer_lerno_generator.rb:5: warning: default `to_a' will be obsolete
F
Finished in 30.560389 seconds.
1) Error:
test_endless(TC_TGenerator):
RuntimeError: Endless iterators unsupported
tests.rb:153:in `test_endless'
tests.rb:120:in `test_endless'
2) Failure:
test_realtime(TC_TGenerator)
[tests.rb:179:in `test_realtime'
tests.rb:177:in `test_realtime'
tests.rb:174:in `test_realtime']:
<0> expected but was
<#<TC_TGenerator::C:0xb7ebef80 @value=0>>.
5 tests, 55 assertions, 1 failures, 1 errors
### TESTING: jeg_generator.rb
Loaded suite tests
Started
...E./jeg_generator.rb:10: warning: default `to_a' will be obsolete
F
Finished in 30.538217 seconds.
1) Error:
test_endless(TC_TGenerator):
RuntimeError: Endless iterators unsupported
tests.rb:153:in `test_endless'
tests.rb:120:in `test_endless'
2) Failure:
test_realtime(TC_TGenerator)
[tests.rb:179:in `test_realtime'
tests.rb:177:in `test_realtime'
tests.rb:174:in `test_realtime']:
<0> expected but was
<#<TC_TGenerator::C:0xb7f86f80 @value=0>>.
5 tests, 55 assertions, 1 failures, 1 errors
### TESTING: caleb_clausen_generator.rb
Loaded suite tests
Started
....F
Finished in 2.093395 seconds.
1) Failure:
test_realtime(TC_TGenerator)
[tests.rb:179:in `test_realtime'
tests.rb:177:in `test_realtime'
tests.rb:174:in `test_realtime']:
<0> expected but was
<nil>.
The endless test-case is simply:
def test_endless
$generators.each do |clz|
t = Thread.new do
# 1, 2, 3, 4 ... etc
g = clz.new do |g|
i = 0
while true
g.yield(i)
i += 1
end
end
assert_equal 0, g.next
999.times do |n|
assert_equal(n+1, g.next)
end
assert_equal 1000, g.current
500.times do |n|
assert_equal(n + 1000, g.next)
end
g.rewind
assert_equal 0, g.next
assert_equal 1, g.next
end
c = 0
until t.stop?
if c >= 30
t.kill
fail "Endless iterators unsupported"
end
c += 1
sleep(1)
end
end
end
The timings were obtained on a P4 1.75Ghz 1Gb RAM, Fedora Core 4 (Kernel
2.6.14-1.1653_FC4), with Ruby 1.8.4-2005-12-24 and Ruby
1.9.0-2006-02-13. If anyone wants I can package up the renamed generator
classes, benchmark and tests and email them over.
--
Ross Bamford - rosco@roscopeco.REMOVE.co.uk