------art_628_1431551.1139777415689
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Here's my solution for this week's quiz. Normally, I just watch the
quizzing, but this one happens to be one that I'm already doing, as
part of a larger library of external iterators.

The key insight is to realize that Continuations were used in the
original because an independant call stack is needed (to run #each
in), separate from the call stack of the user of Generator. However,
Continuations are only one way to get another call stack; you could
also use a Thread, which doesn't have the same performance problems
in ruby.

In order to implement Generator#current, I had to invent Queue#peek,
which tells you what the next element is without taking it from the
Queue. Actually, I'm using a SizedQueue, not a plain Queue. Otherwise,
the memory used by the queue could grow without bounds.

#rewind was also a small challenge, until I realized that you could
just restart the Thread. (Hopefully, the enum or block will return
the same results the second time through.)

It's not allowed in the original, but this version permits you to
pass both an enum and a block to the generator. The results of the
block are passed up once the enum is exhausted.

Another interesting new feature is Generator#<<, which allows you to
add more items to the Generator once it has been created. This was
originally a misunderstood implementation of yield.

It's clear that this version is faster than the original callcc-
based Generator, but I'm not sure how to compare with James'
results. I was unable to run his benchmark to completion on my
machine. Somewhat modified, I see differences of around 3 orders
of magnitude, but performance of the callcc-based version seems
non-linearly dependant on input size.

I also found that bumping the queue size up to 400 from the original
32 made about a 4x difference in running time. I guess context
switches are expensive...

I am curious to see how James made his own solution so blazing fast.

The requirement for synchronous generators took me by surprise at
the last minute. It was easy enough to add synchronicity, but it
looks like there would be a performance cost from the extra
context switches. And is maybe not needed in the majority of cases.
So, I put the synchronous capability in a subclass. Sure enough,
when I ran the benchmark, the synchronous version pretty much
wipes out any performance gain from the bigger queue.

Benchmarks: (take with a grain of salt)

### Construction ###

Rehearsal -----------------------------------------------------------------
Caleb's Generator               0.020000   0.000000   0.020000 (  0.015167)
Caleb's Synchronous Generator   0.000000   0.000000   0.000000 (  0.003251)
Old callcc Generator            0.000000   0.000000   0.000000 (  0.004067)
-------------------------------------------------------- total: 0.020000sec

                                    user     system      total        real
Caleb's Generator               0.010000   0.000000   0.010000 (  0.014414)
Caleb's Synchronous Generator   0.010000   0.000000   0.010000 (  0.003384)
Old callcc Generator            0.000000   0.000000   0.000000 (  0.004027)

### next() ###

Rehearsal -----------------------------------------------------------------
Caleb's Generator               0.050000   0.000000   0.050000 (  0.092768)
Caleb's Synchronous Generator   0.270000   0.000000   0.270000 (  0.306566)
each                            0.000000   0.000000   0.000000 (  0.000732)
Old callcc Generator            8.410000   0.960000   9.370000 ( 10.738060)
-------------------------------------------------------- total: 9.690000sec

                                    user     system      total        real
Caleb's Generator               0.030000   0.000000   0.030000 (  0.069023)
Caleb's Synchronous Generator   0.200000   0.000000   0.200000 (  0.256574)
each                            0.000000   0.000000   0.000000 (  0.000392)
Old callcc Generator            7.400000   0.960000   8.360000 (  8.679449)

------art_628_1431551.1139777415689
Content-Type: application/octet-stream; name="mygenerator.rb"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="mygenerator.rb"
X-Attachment-Id: file0

CnJlcXVpcmUgJ3RocmVhZCcKCmNsYXNzIFF1ZXVlCiAjIFJldHJpZXZlcyBuZXh0IGRhdGEgZnJv
bSB0aGUgcXVldWUsIHdpdGhvdXQgcHVsbGluZyBpdCBvZmYgdGhlIHF1ZXVlLgogIyBJZiB0aGUg
cXVldWUgaXMgZW1wdHksIHRoZSBjYWxsaW5nIHRocmVhZCBpcwogIyBzdXNwZW5kZWQgdW50aWwg
ZGF0YSBpcyBwdXNoZWQgb250byB0aGUgcXVldWUuIAogIyBJZiArbm9uX2Jsb2NrKyBpcyB0cnVl
LCB0aGUKICMgdGhyZWFkIGlzbid0IHN1c3BlbmRlZCwgYW5kIGFuIGV4Y2VwdGlvbiBpcyByYWlz
ZWQuCiAgZGVmIHBlZWsobm9uX2Jsb2NrPWZhbHNlKQogICAgcmFpc2UgVGhyZWFkRXJyb3IsICJx
dWV1ZSBlbXB0eSIgaWYgbm9uX2Jsb2NrIGFuZCBlbXB0eT8KICAgIFRocmVhZC5wYXNzIHdoaWxl
IChlbXB0eT8pCiAgICBUaHJlYWQuY3JpdGljYWw9dHJ1ZQogICAgICByZXN1bHQ9QHF1ZS5maXJz
dAogICAgVGhyZWFkLmNyaXRpY2FsPWZhbHNlCiAgICByZXN1bHQKICBlbmQKZW5kCgoKY2xhc3Mg
TXlHZW5lcmF0b3IKICAgIGRlZiBpbml0aWFsaXplKGVudW09W10scXNpemU9NDAwLCZibG9jaykK
ICAgICAgQGV4dHJhcz1bXQogICAgICBAZXh0cmFzbXV0ZXg9TXV0ZXgubmV3CiAgICAgIGluaXQo
ZW51bSxxc2l6ZSwmYmxvY2spCiAgICBlbmQKICAgICAgICAKICAgIGRlZiBpbml0KGVudW0scXNp
emUsJmJsb2NrKQogICAgICBAYmxvY2s9YmxvY2sKICAgICAgQHBvcz0wCiAgICAgIEBlbnVtPWVu
dW0KICAgICAgQHE9cT1TaXplZFF1ZXVlLm5ldyhxc2l6ZSkKICAgICAgQHRocmVhZD1UaHJlYWQu
bmV3ewogICAgICAgIHN0b3BfdGhyZWFkCiAgICAgICAgZW51bS5lYWNoe3xpdGVtfCAKICAgICAg
ICAgIHE8PGl0ZW0gCiAgICAgICAgICBzdG9wX3RocmVhZAogICAgICAgIH0KICAgICAgICBibG9j
a1tzZWxmXSBpZiBibG9jawogICAgICAgIGk9MAogICAgICAgIHdoaWxlIGk8QGV4dHJhcy5zaXpl
CiAgICAgICAgICBxLnB1c2ggQGV4dHJhc211dGV4LnN5bmNocm9uaXplIHsgQGV4dHJhc1tpXSB9
CiAgICAgICAgICBpKz0xCiAgICAgICAgZW5kCiAgICAgIH0KICAgIGVuZAoKICAgICNubyBzeW5j
aHJvbml6YXRpb24gd2l0aCB0aHJlYWQgYnkgZGVmYXVsdAogICAgZGVmIHN0b3BfdGhyZWFkOyBl
bmQKICAgIGRlZiBzdGFydF90aHJlYWQ7IGVuZAogICAgICAgIAogICAgI3Nob3VsZCBvbmx5IGJl
IGNhbGxlZCBmcm9tIGluc2lkZSBjb25zdHJ1Y3RvcidzIGJsb2NrCiAgICBkZWYgeWllbGQoaXRl
bSkKICAgICAgQHEucHVzaCBpdGVtICAgIAogICAgICBzdG9wX3RocmVhZAogICAgZW5kCgogICAg
ZGVmIDw8KGl0ZW0pCiAgICAgIEBleHRyYXNtdXRleC5zeW5jaHJvbml6ZSB7IEBleHRyYXM8PGl0
ZW0gfQogICAgZW5kCgogICAgZGVmIGJlZ2luIQogICAgICBAdGhyZWFkLmtpbGwKICAgICAgaW5p
dChAZW51bSxAcS5tYXgsJkBibG9jaykKICAgICAgMAogICAgZW5kCiAgICAKICAgIGRlZiByZWFk
YWhlYWQxCiAgICAgIHJhaXNlIEVPRkVycm9yIGlmIGVvZj8KICAgICAgc3RhcnRfdGhyZWFkCiAg
ICAgIEBxLnBlZWsKICAgIHJlc2N1ZSBUaHJlYWRFcnJvcjoKICAgICAgcmFpc2UgRU9GRXJyb3IK
ICAgIGVuZAoKICAgIGRlZiByZWFkMQogICAgICBzdGFydF90aHJlYWQKICAgICAgcmVzdWx0PUBx
LnBvcAojICAgICAgcmFpc2UgRU9GRXJyb3IgaWYgIXJlc3VsdCAmJiBlb2Y/CiAgICAgIEBwb3Mr
PTEKICAgICAgcmVzdWx0CiAgICByZXNjdWUgVGhyZWFkRXJyb3I6CiAgICAgIHJhaXNlIEVPRkVy
cm9yCiAgICBlbmQKICAgIAogICAgZGVmIGVvZj8KICAgICAgc3RhcnRfdGhyZWFkIHdoaWxlIEBx
LmVtcHR5PyBhbmQgQHRocmVhZC5hbGl2ZT8KICAgICAgQHEuZW1wdHk/IGFuZCAhQHRocmVhZC5h
bGl2ZT8KICAgIGVuZAoKICAgIGRlZiBlYWNoKCZibG9jaykKICAgICAgYmVnaW4hCiAgICAgIHdo
aWxlKHNlbGYubmV4dD8pCiAgICAgICAgYmxvY2suY2FsbCByZWFkMQogICAgICBlbmQKICAgIGVu
ZCAgICAKICAgIGluY2x1ZGUgRW51bWVyYWJsZQogICAgCiAgICBhdHRyIDpwb3MKCiAgICAjbWV0
aG9kcyBmb3IgR2VuZXJhdG9yIGNvbXBhdGliaWxpdHk6CiAgICBkZWYgcmV3aW5kOyBiZWdpbiE7
IHNlbGYgZW5kCiAgICBhbGlhcyBjdXJyZW50IHJlYWRhaGVhZDEKICAgIGFsaWFzIG5leHQgcmVh
ZDEKICAgIGFsaWFzIGVuZD8gZW9mPwogICAgYWxpYXMgaW5kZXggcG9zCiAgICBkZWYgbmV4dD87
ICFlbmQ/IGVuZAplbmQKCmNsYXNzIE15U3luY2hyb25vdXNHZW5lcmF0b3IgPCBNeUdlbmVyYXRv
cgogIGRlZiBzdG9wX3RocmVhZAogICAgVGhyZWFkLnN0b3AKICBlbmQKICAKICBkZWYgc3RhcnRf
dGhyZWFkCiAgICBpZiBAcS5lbXB0eT8KICAgICAgQHRocmVhZC53YWtldXAgCiAgICAgIFRocmVh
ZC5wYXNzCiAgICBlbmQKICBlbmQKCmVuZAo------art_628_1431551.1139777415689--