FasterGenerator (#66)

Ruby
41

On Tue, 2006-02-14 at 01:57 +0900, James Edward G. II wrote:

On Feb 10, 2006, at 7:53 AM, Ruby Q. wrote:

This week’s Ruby Q. 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 F.'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:inspent?’
    ./davelee_generator.rb:32:in current' ./davelee_generator.rb:55:innext’
    tests.rb:179:in test_realtime' tests.rb:177:intest_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:intest_realtime’
    tests.rb:174:in `test_realtime’]:
    <0> expected but was
    .

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:intest_endless’

  2. Error:
    test_realtime(TC_TGenerator):
    NoMethodError: undefined method entries' for #<TC_TGenerator::C:0xb7ed80d4> tests.rb:176:ininitialize’
    tests.rb:176:in test_realtime' tests.rb:174:intest_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:intest_endless’

  2. Failure:
    test_realtime(TC_TGenerator)
    [tests.rb:179:in test_realtime' tests.rb:177:intest_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:intest_endless’

  2. Failure:
    test_realtime(TC_TGenerator)
    [tests.rb:179:in test_realtime' tests.rb:177:intest_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:intest_realtime’
    tests.rb:174:in `test_realtime’]:
    <0> expected but was
    .

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.

42

On 2/14/06, Ross B. [email protected] wrote:

next()

…

CalebClausenSyncGenerator 0.660000 0.000000 0.660000 ( 0.710609)
CalebClausenGenerator 0.440000 0.000000 0.440000 ( 0.495331)

Interesting. I saw much larger speedups (4-10x) from using the
non-Sync version on my system. Maybe my results weren’t statistically
significant… If it’s only 1/3 faster, it hardly seems worth it to
have the non-Sync version at all.

(Also, I would have thought that mine should pass the realtime
tests… but I never tried it.)

Thanks for this summary, Ross.

43

On 2/14/06, Ross B. [email protected] wrote:

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

As James said, thanks for doing this Ross.

I hadn’t added test_realtime to my test set, but now I have and this
bug is fixed. I have attached the fixed version for anyone who cares.
For the hell of it, I also optimized by manually inlining some method
calls, and eliminating redundant bounds checking. This should now
pass all tests and run much faster.

These are basically the optimizations:

def current

  • raise EOFError if spent?
  • @array[@index]
  • @array.fetch(@index) rescue raise EOFError
    end

def end?

  • spent?
  • @index >= @array.size
    end

def next

  • result = current
  • begin
  •  result = @array.fetch(@index)
  • rescue
  •  raise EOFError
  • end
    @index += 1
    result
    end

def next?

  • not end?
  • @index < @array.size
    end

Dave

44

On Wed, 2006-02-15 at 02:54 +0900, Dave L. wrote:

I hadn’t added test_realtime to my test set, but now I have and this
bug is fixed. I have attached the fixed version for anyone who cares.
For the hell of it, I also optimized by manually inlining some method
calls, and eliminating redundant bounds checking. This should now
pass all tests and run much faster.

It does pass all the tests (including a new one based on Luke
Blanshard’s stateful code), but I can’t imagine what on earth is going
on here (see assertion counts):

[rosco@jukebox 66]$ ruby tests.rb davelee_generator.rb
Loaded suite tests
Started
…
Finished in 1.067421 seconds.

6 tests, 1561 assertions, 0 failures, 0 errors

[rosco@jukebox 66]$ ruby tests.rb davelee_generator.rb
Loaded suite tests
Started
…
Finished in 1.078261 seconds.

6 tests, 422 assertions, 0 failures, 0 errors

[rosco@jukebox 66]$ ruby tests.rb davelee_generator.rb
Loaded suite tests
Started
…
Finished in 1.012041 seconds.

6 tests, 1561 assertions, 0 failures, 0 errors

[rosco@jukebox 66]$ ruby tests.rb davelee_generator.rb
Loaded suite tests
Started
…
Finished in 1.065682 seconds.

6 tests, 682 assertions, 0 failures, 0 errors

[rosco@jukebox 66]$ ruby tests.rb davelee_generator.rb
Loaded suite tests
Started
…
Finished in 1.071149 seconds.

6 tests, 422 assertions, 0 failures, 0 errors

It seems to be jumping early out of the endless test judging by the
number of missing assertions. It only happens sometimes (1561 is a full
pass) and it does happen with the old version too (only just noticed
it).

I ran updated timings since they don’t use endless iterators anyway.
Here’s the result (on 1.8.4):

Construction

Rehearsal -------------------------------------------------------------
New Thread Generator 0.270000 0.050000 0.320000 ( 0.379841)
Old callcc Generator 0.290000 0.090000 0.380000 ( 0.381635)
RossBamfordGenerator 1.150000 0.060000 1.210000 ( 1.269793)
JesseYoonGenerator 2.700000 0.100000 2.800000 ( 2.797546)
JacobFugalGenerator 0.020000 0.000000 0.020000 ( 0.022782)
JEGIIGenerator 0.010000 0.000000 0.010000 ( 0.008398)
HorndudeGenerator 1.290000 0.020000 1.310000 ( 1.308930)
DaveLeeGenerator 0.010000 0.000000 0.010000 ( 0.007556)
ChristofferLernoGenerator 0.000000 0.000000 0.000000 ( 0.004950)
CalebClausenSyncGenerator 3.610000 0.070000 3.680000 ( 3.696594)
CalebClausenGenerator 7.940000 0.130000 8.070000 ( 8.151407)
--------------------------------------------------- total: 17.810000sec

                            user     system      total        real

New Thread Generator 5.050000 0.090000 5.140000 ( 5.184013)
Old callcc Generator 0.100000 0.080000 0.180000 ( 0.183245)
RossBamfordGenerator 6.490000 0.050000 6.540000 ( 6.663615)
JesseYoonGenerator 8.170000 0.110000 8.280000 ( 8.356455)
JacobFugalGenerator 0.040000 0.000000 0.040000 ( 0.150496)
JEGIIGenerator 0.000000 0.000000 0.000000 ( 0.003616)
HorndudeGenerator 2.310000 0.020000 2.330000 ( 2.325253)
DaveLeeGenerator 0.010000 0.000000 0.010000 ( 0.010512)
ChristofferLernoGenerator 0.000000 0.000000 0.000000 ( 0.004091)
CalebClausenSyncGenerator 10.320000 0.160000 10.480000 ( 10.493258)
CalebClausenGenerator 15.580000 0.190000 15.770000 ( 15.832376)

next()

Rehearsal -------------------------------------------------------------
New Thread Generator 0.560000 0.000000 0.560000 ( 0.618782)
Old callcc Generator 1.670000 0.330000 2.000000 ( 2.090583)
RossBamfordGenerator 0.560000 0.010000 0.570000 ( 0.634513)
JesseYoonGenerator 1.960000 0.010000 1.970000 ( 2.037655)
JacobFugalGenerator 0.520000 0.000000 0.520000 ( 0.568505)
JEGIIGenerator 0.040000 0.000000 0.040000 ( 0.124053)
HorndudeGenerator 0.020000 0.000000 0.020000 ( 0.054959)
DaveLeeGenerator 0.030000 0.000000 0.030000 ( 0.080798)
ChristofferLernoGenerator 0.060000 0.000000 0.060000 ( 0.123206)
CalebClausenSyncGenerator 0.740000 0.010000 0.750000 ( 0.801426)
CalebClausenGenerator 0.490000 0.000000 0.490000 ( 0.561398)
---------------------------------------------------- total: 7.010000sec

                            user     system      total        real

New Thread Generator 0.550000 0.000000 0.550000 ( 0.561499)
Old callcc Generator 1.740000 0.060000 1.800000 ( 1.809145)
RossBamfordGenerator 0.560000 0.000000 0.560000 ( 0.558627)
JesseYoonGenerator 1.610000 0.010000 1.620000 ( 1.626749)
JacobFugalGenerator 0.500000 0.010000 0.510000 ( 0.501115)
JEGIIGenerator 0.040000 0.000000 0.040000 ( 0.043879)
HorndudeGenerator 0.010000 0.000000 0.010000 ( 0.007551)
DaveLeeGenerator 0.040000 0.010000 0.050000 ( 0.034707)
ChristofferLernoGenerator 0.060000 0.000000 0.060000 ( 0.064452)
CalebClausenSyncGenerator 0.750000 0.000000 0.750000 ( 0.754337)
CalebClausenGenerator 0.530000 0.010000 0.540000 ( 0.533183)

45

On Thu, 2006-02-16 at 01:46 +0900, Dave L. wrote:

  •  ... [manual thread timeout code] ...

  •  fail "Endless iterators unsupported" unless t.join(30)

Ahh, cool. I knew there must be a better way to do that. Thanks :slight_smile:

Anyway, here is a new benchmark run. Check out your numbers:

Construction

Rehearsal -------------------------------------------------------------
New Thread Generator 0.260000 0.040000 0.300000 ( 0.359351)
Old callcc Generator 0.310000 0.100000 0.410000 ( 0.409978)
RossBamfordGenerator 1.060000 0.060000 1.120000 ( 1.143501)
JesseYoonGenerator 2.530000 0.090000 2.620000 ( 2.644731)
JacobFugalGenerator 0.020000 0.000000 0.020000 ( 0.017337)
JEGIIGenerator 0.000000 0.000000 0.000000 ( 0.003492)
HorndudeGenerator 1.210000 0.010000 1.220000 ( 1.176024)
DaveLeeGenerator 0.010000 0.000000 0.010000 ( 0.006422)
ChristofferLernoGenerator 0.010000 0.000000 0.010000 ( 0.005104)
CalebClausenSyncGenerator 2.780000 0.080000 2.860000 ( 2.872062)
CalebClausenGenerator 7.400000 0.110000 7.510000 ( 7.537113)
--------------------------------------------------- total: 14.860000sec

                            user     system      total        real

New Thread Generator 4.740000 0.090000 4.830000 ( 4.859650)
Old callcc Generator 0.060000 0.090000 0.150000 ( 0.157226)
RossBamfordGenerator 6.010000 0.050000 6.060000 ( 6.344554)
JesseYoonGenerator 7.520000 0.110000 7.630000 ( 7.642123)
JacobFugalGenerator 0.010000 0.000000 0.010000 ( 0.020769)
JEGIIGenerator 0.000000 0.000000 0.000000 ( 0.004785)
HorndudeGenerator 2.070000 0.010000 2.080000 ( 2.113591)
DaveLeeGenerator 0.010000 0.000000 0.010000 ( 0.010756)
ChristofferLernoGenerator 0.000000 0.000000 0.000000 ( 0.004356)
CalebClausenSyncGenerator 9.250000 0.120000 9.370000 ( 9.404799)
CalebClausenGenerator 14.170000 0.170000 14.340000 ( 14.400167)

next()

Rehearsal -------------------------------------------------------------
New Thread Generator 0.540000 0.000000 0.540000 ( 0.613446)
Old callcc Generator 1.530000 0.300000 1.830000 ( 1.920241)
RossBamfordGenerator 0.510000 0.000000 0.510000 ( 0.588254)
JesseYoonGenerator 1.390000 0.010000 1.400000 ( 1.475440)
JacobFugalGenerator 0.470000 0.000000 0.470000 ( 0.546782)
JEGIIGenerator 0.040000 0.000000 0.040000 ( 0.086357)
HorndudeGenerator 0.000000 0.000000 0.000000 ( 0.006002)
DaveLeeGenerator 0.030000 0.000000 0.030000 ( 0.116365)
ChristofferLernoGenerator 0.060000 0.000000 0.060000 ( 0.101321)
CalebClausenSyncGenerator 0.660000 0.000000 0.660000 ( 0.741025)
CalebClausenGenerator 0.450000 0.010000 0.460000 ( 0.544104)
---------------------------------------------------- total: 6.000000sec

                            user     system      total        real

New Thread Generator 0.550000 0.000000 0.550000 ( 0.566899)
Old callcc Generator 1.510000 0.200000 1.710000 ( 1.725167)
RossBamfordGenerator 0.510000 0.000000 0.510000 ( 0.514021)
JesseYoonGenerator 1.360000 0.000000 1.360000 ( 1.378787)
JacobFugalGenerator 0.460000 0.010000 0.470000 ( 0.467460)
JEGIIGenerator 0.040000 0.000000 0.040000 ( 0.041809)
HorndudeGenerator 0.000000 0.000000 0.000000 ( 0.007873)
DaveLeeGenerator 0.030000 0.000000 0.030000 ( 0.037849)
ChristofferLernoGenerator 0.060000 0.000000 0.060000 ( 0.056630)
CalebClausenSyncGenerator 0.660000 0.000000 0.660000 ( 0.670666)
CalebClausenGenerator 0.420000 0.010000 0.430000 ( 0.432745)

According to this and the tests, the entries now stack up like this.
I’ve used the benchmark next() speed above to order the entries fastest
to slowest on raw iteration:

== Supporting all functionality

  • Dave L.
  • Jacob F.
  • Ross B.

== Supporting either endless or realtime/stateful iterators, or both

  • Caleb C. (Generator) (Endless, no realtime)
  • Caleb C. (SyncGenerator) (Realtime, no endless)
  • Jesse Y. (Endless, no realtime)

== Supporting neither endless nor realtime/stateful iterators

  • Horndude
  • James Edward G. II
  • Christoffer Lerno

Assuming there isn’t some gap in the tests (sorry, ever the cynic) your
fixed version has some very impressive performance, nice job.

Now I’m off to see if I can properly figure out how you made it work :slight_smile:

46

On 2/14/06, Ross B. [email protected] wrote:

It seems to be jumping early out of the endless test judging by the
number of missing assertions. It only happens sometimes (1561 is a full
pass) and it does happen with the old version too (only just noticed
it).

I hope I’ve fixed the thread bugs I had. At least, I can no longer
duplicate this problem.

In the tests file you sent me, I made the following change:

  •  c = 0

  •  until t.stop?

  •    if c >= 30

  •      t.kill

  •      fail "Endless iterators unsupported"

  •    end

  •    c += 1

  •    sleep(1)

  •  end

  •  fail "Endless iterators unsupported" unless t.join(30)

Dave

47

Ross B. wrote:

Hi,

Well, I’ve snapped a string on my guitar and my computer won’t play MP3s
today for some reason,

I’ve come to believe that having a backup set of guitar strings is
nearly as important as having a backup for your hard disk.

–
– Jim W.

48

Hi,

Well, I’ve snapped a string on my guitar and my computer won’t play MP3s
today for some reason, so inevitably boredom started to creep in. I
started playing around with the generator stuff, specifically about the
coroutine discussion earlier in this thread. Just wanted to see if I
could really get my head around continuations and all that.

It starts with some private methods on Kernel, which are then used to
implement the generator, but can be used elsewhere too:

module Kernel
private
def coreset(blk)
Thread.current[:"#{blk.inspect.hash}_codone"] = nil
end

def coyield?(blk)
Thread.current[:"#{blk.inspect.hash}_codone"] ? false : true
end

def coyield(blk, *args)
raise “Coroutine exhausted” if
Thread.current[:"#{blk.inspect.hash}_codone"]

catch :coreturn do
  next_item = (Thread.current[:coreturn] ||= []).pop

  if next_item
    next_item.call
  else
    final = blk.call(*args)
    Thread.current[:"#{blk.inspect.hash}_codone"] = true
    throw :coreturn, final
  end
end

end

def coreturn(val)
callcc do |return_cc|
(Thread.current[:coreturn] ||= []) << return_cc
throw :coreturn, val
end
end
end

class CoGenerator
def initialize(enum = nil, &blk)
@blk, @pos = blk, 0

if enum
  @blk = lambda { enum.each { |e| coreturn e } }
end

end

def rewind
@pos = 0
coreset @blk
end

def next
@pos += 1
@current = coyield(@blk)
end

def current
@current
end

def next?
coyield? @blk
end

def end?
!self.next?
end

def each
rewind
yield coyield(@blk) while coyield?(@blk)
end

def pos
@pos
end
end

It would be used like:

g = CoGenerator.new do
  coreturn 6
  # Some work
  coreturn 7
  # More work
  coreturn 8
  # Yet more work
  9
end

p g.next while g.next?
# ->
#   6
#   7
#   8
#   9

Obviously this isn’t for the quiz (it’d be dead last, being based on
continuations, and it doesn’t actually have the Generator API) but just,
well, for fun. And something to do. It was fun to write, but it’s a toy.
I dread to think what it mightn’t do properly, or at all :slight_smile: It’s
behaviour in multithreaded code could well be a bit counter-intuitive
too, I’m afraid I don’t know much about how coroutines work in other
languages.

It times a bit faster than the old callcc generator, because it’s using
less continuations (just the one) but really I guess it’s just a test of
the coyield/coreturn stuff.

Anyway, enough about that… Music shop will be open now :slight_smile:

49

On Thu, 2006-02-16 at 22:52 +0900, Jim W. wrote:

Ross B. wrote:

Hi,

Well, I’ve snapped a string on my guitar and my computer won’t play MP3s
today for some reason,

I’ve come to believe that having a backup set of guitar strings is
nearly as important as having a backup for your hard disk.

I’ve been lulled by living two minutes walk away from a well stocked
music shop that, as it transpires, is closed Wednesday afternoon and
Thursday morning.

Definitely got a backup set now, though :slight_smile: