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