From: Caleb Clausen Date: 2006-02-13T05:50:33+09:00 Subject: Re: FasterGenerator (#66) ------=_Part_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) ------=_Part_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= ------=_Part_628_1431551.1139777415689--