[QUIZ] FasterGenerator (#66)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Ruby includes a useful Generator library for switching internal iterators to
external iterators. It is used like this:

require 'generator'

# Generator from an Enumerable object
g = Generator.new(['A', 'B', 'C', 'Z'])

while g.next?
puts g.next
end

I've heard complaints in the past that this library is slow. One reason is that
it was implemented with continuations, which have performance issues in the
current version of Ruby. "Was" is the keyword there though, because I've just
learned that Generator was recently re-implemented. I learned some good tricks
reading the new version, so let's try fixing Generator ourselves. (No peeking
at the new version!)

This week's Ruby Quiz is to write FasterGenerator, your own re-implementation of
Generator with an eye towards working faster. (This is a small library. My
version is 54 lines.) It is possible to go even faster than the new
implementation, with certain trade-offs:

### Construction ###

Rehearsal -----------------------------------------------------------
Current Generator 0.340000 0.480000 0.820000 ( 0.828985)
Old callcc Generator 0.590000 0.840000 1.430000 ( 1.439255)
James's FasterGenerator 0.210000 1.040000 1.250000 ( 1.252359)
-------------------------------------------------- total: 3.500000sec

user system total real
Current Generator 0.750000 0.880000 1.630000 ( 1.630639)
Old callcc Generator 0.190000 1.170000 1.360000 ( 1.375868)
James's FasterGenerator 0.210000 1.230000 1.440000 ( 1.433152)

### next() ###

Rehearsal -----------------------------------------------------------
Current Generator 16.280000 0.100000 16.380000 ( 16.434828)
Old callcc Generator 9.260000 33.490000 42.750000 ( 42.997528)
James's FasterGenerator 0.030000 0.000000 0.030000 ( 0.038645)
------------------------------------------------- total: 59.160000sec

user system total real
Current Generator 15.940000 0.140000 16.080000 ( 16.425068)
Old callcc Generator 6.390000 30.160000 36.550000 ( 36.676838)
James's FasterGenerator 0.030000 0.000000 0.030000 ( 0.036880)

It you want to see the class documentation, you can find it here:

http://www.ruby-doc.org/stdlib/libdoc/generator/rdoc/classes/Generator.html

If you want to make sure your implementation is correct, you can use these tests
straight out of the current implementation:

require 'test/unit'

class TC_Generator < Test::Unit::TestCase
def test_block1
g = Generator.new { |g|
# no yield's
}

assert_equal(0, g.pos)
assert_raises(EOFError) { g.current }
end

def test_block2
g = Generator.new { |g|
for i in 'A'..'C'
g.yield i
end

g.yield 'Z'
}

assert_equal(0, g.pos)
assert_equal('A', g.current)

assert_equal(true, g.next?)
assert_equal(0, g.pos)
assert_equal('A', g.current)
assert_equal(0, g.pos)
assert_equal('A', g.next)

assert_equal(1, g.pos)
assert_equal(true, g.next?)
assert_equal(1, g.pos)
assert_equal('B', g.current)
assert_equal(1, g.pos)
assert_equal('B', g.next)

assert_equal(g, g.rewind)

assert_equal(0, g.pos)
assert_equal('A', g.current)

assert_equal(true, g.next?)
assert_equal(0, g.pos)
assert_equal('A', g.current)
assert_equal(0, g.pos)
assert_equal('A', g.next)

assert_equal(1, g.pos)
assert_equal(true, g.next?)
assert_equal(1, g.pos)
assert_equal('B', g.current)
assert_equal(1, g.pos)
assert_equal('B', g.next)

assert_equal(2, g.pos)
assert_equal(true, g.next?)
assert_equal(2, g.pos)
assert_equal('C', g.current)
assert_equal(2, g.pos)
assert_equal('C', g.next)

assert_equal(3, g.pos)
assert_equal(true, g.next?)
assert_equal(3, g.pos)
assert_equal('Z', g.current)
assert_equal(3, g.pos)
assert_equal('Z', g.next)

assert_equal(4, g.pos)
assert_equal(false, g.next?)
assert_raises(EOFError) { g.next }
end

def test_each
a = [5, 6, 7, 8, 9]

g = Generator.new(a)

i = 0

g.each { |x|
assert_equal(a[i], x)

i += 1

break if i == 3
}

assert_equal(3, i)

i = 0

g.each { |x|
assert_equal(a[i], x)

i += 1
}

assert_equal(5, i)
end
end

The Generator library also includes a SyncEnumerator class, but it is written to
use Generator and will work fine with a new version, as long as it is
API-compatible.

[Pit Capitain]

Ruby Quiz schrieb:

> Ruby includes a useful Generator library for switching internal iterators to
> external iterators. It is used like this:

> ...

> If you want to make sure your implementation is correct, you can use these tests
> straight out of the current implementation:

> ...

James, thanks for the new quiz. It would be interesting to add a
testcase with an endless internal iterator. I don't know the new
implementation of Generator, so I can't say whether an endless iterator
should be supported.

Regards,
Pit

[James Edward Gray II]

On Feb 10, 2006, at 8:24 AM, Pit Capitain wrote:

> It would be interesting to add a testcase with an endless internal
> iterator. I don't know the new implementation of Generator, so I
> can't say whether an endless iterator should be supported.

That's an interesting point we will certainly talk more about as we
start to see some solutions. Generator *can* handle endless
iterators. Quiz solvers can decide whether or not to limit
themselves with that additional requirement...

James Edward Gray II

[Matthew Moss]

Not being familiar with all the various Ruby packages and libs, I
first want to thank ya for posting a good set of test cases that I can
review, but was wondering if you also might post the code used to do
the timing?

[James Edward Gray II]

I will, yes, on Sunday. :)

I pulled down copies on the Generator library, before and after the
change. I then modified the class names so they could all peacefully
coexist, loaded them, and ran a trivial benchemark:

#!/usr/local/bin/ruby -w

require "benchmark"

require "current_generator"
require "callcc_generator"
require "faster_generator"

tests = 1000
enum = (1..10000).to_a

puts
puts "### Construction ###"
puts

Benchmark.bmbm do |x|
x.report("Current Generator") do
tests.times { CurrentGenerator.new(enum) }
end
x.report("Old callcc Generator") do
tests.times { CallCCGenerator.new(enum) }
end
x.report("James's FasterGenerator") do
tests.times { FasterGenerator.new(enum) }
end
end

puts
puts "### next() ###"
puts

Benchmark.bmbm do |x|
x.report("Current Generator") do
generator = CurrentGenerator.new(enum)
tests.times { generator.next until generator.end? }
end
x.report("Old callcc Generator") do
generator = CallCCGenerator.new(enum)
tests.times { generator.next until generator.end? }
end
x.report("James's FasterGenerator") do
generator = FasterGenerator.new(enum)
tests.times { generator.next until generator.end? }
end
end

__END__

I'll post the modified libraries to go with that after the spoiler
period. Obviously, you could go get them yourself, before then. I
strongly recommend writing a solution first though.

James Edward Gray II

[James Edward Gray II]

On Feb 10, 2006, at 10:23 AM, James Edward Gray II wrote:

> I pulled down copies on the Generator library, before and after the
> change. I then modified the class names so they could all
> peacefully coexist, loaded them, and ran a trivial benchemark:

In answering Matthew's question, I found a small mistake in the
benchmarks posted with the quiz (the timings for constructing my
FasterGenerator were wrong). Here are the corrected numbers:

### Construction ###

Rehearsal -----------------------------------------------------------
Current Generator 0.320000 0.320000 0.640000 ( 0.642583)
Old callcc Generator 0.610000 0.870000 1.480000 ( 1.480780)
James's FasterGenerator 0.000000 0.000000 0.000000 ( 0.003751)
-------------------------------------------------- total: 2.120000sec

user system total real
Current Generator 0.740000 0.720000 1.460000 ( 1.464659)
Old callcc Generator 0.220000 1.500000 1.720000 ( 1.714859)
James's FasterGenerator 0.010000 0.000000 0.010000 ( 0.003258)

### next() ###

Rehearsal -----------------------------------------------------------
Current Generator 16.610000 0.130000 16.740000 ( 17.032537)
Old callcc Generator 8.070000 32.740000 40.810000 ( 41.072265)
James's FasterGenerator 0.030000 0.000000 0.030000 ( 0.037034)
------------------------------------------------- total: 57.580000sec

user system total real
Current Generator 16.630000 0.120000 16.750000 ( 16.878429)
Old callcc Generator 7.440000 32.720000 40.160000 ( 40.336902)
James's FasterGenerator 0.040000 0.000000 0.040000 ( 0.035432)

James Edward Gray II

[James Edward Gray II]

On Feb 10, 2006, at 10:28 AM, James Edward Gray II wrote:

> ### Construction ###

> James's FasterGenerator 0.000000 0.000000 0.000000 ( 0.003751)

> ### next() ###

> James's FasterGenerator 0.030000 0.000000 0.030000 ( 0.037034)

Oh and don't be too impressed with those, Pit Capitain has already
told you one of the flaws with my approach... ;)

James Edward Gray II

[Matthew Moss]

> > Not being familiar with all the various Ruby packages and libs, I
> > first want to thank ya for posting a good set of test cases that I can
> > review, but was wondering if you also might post the code used to do
> > the timing?
>
> I will, yes, on Sunday. :)

But you just posted it. :)

Sorry, guess I wasn't clear. I wasn't looking to see your
implementation of Generator, I was to see your benchmarking code.

[James Edward Gray II]

On Feb 10, 2006, at 10:34 AM, Matthew Moss wrote:

> I wasn't looking to see your implementation of Generator, I was to
> see your benchmarking code.

It's not my implementation I am trying to hide, it's the current
Generator code the benchmark uses as a baseline. I realize it's
readily available, but I think solving this one is more fun if you
don't peek. :)

James Edward Gray II

[Matthew Moss]

> It's not my implementation I am trying to hide, it's the current
> Generator code the benchmark uses as a baseline. I realize it's
> readily available, but I think solving this one is more fun if you
> don't peek. :)

Okay.... ummm.... sure.... I won't peek. No, you can't make me.

(In case I still wasn't clear, I wasn't asking to peek at ANY
implementation of Generator, but rather wanted exactly what you
posted, which has nothing to do with Generator but everything to do
with benchmark, i.e., the thing I wanted to know about.)

[Dave Lee]

On 2/10/06, James Edward Gray II <ja...@grayproductions.net> wrote:
> Here are the corrected numbers:
>
> ### Construction ###
>
> Rehearsal -----------------------------------------------------------
> Current Generator 0.320000 0.320000 0.640000 ( 0.642583)
> Old callcc Generator 0.610000 0.870000 1.480000 ( 1.480780)
> James's FasterGenerator 0.000000 0.000000 0.000000 ( 0.003751)
> -------------------------------------------------- total: 2.120000sec
>
> user system total real
> Current Generator 0.740000 0.720000 1.460000 ( 1.464659)
> Old callcc Generator 0.220000 1.500000 1.720000 ( 1.714859)
> James's FasterGenerator 0.010000 0.000000 0.010000 ( 0.003258)
>
> ### next() ###
>
> Rehearsal -----------------------------------------------------------
> Current Generator 16.610000 0.130000 16.740000 ( 17.032537)
> Old callcc Generator 8.070000 32.740000 40.810000 ( 41.072265)
> James's FasterGenerator 0.030000 0.000000 0.030000 ( 0.037034)
> ------------------------------------------------- total: 57.580000sec
>
> user system total real
> Current Generator 16.630000 0.120000 16.750000 ( 16.878429)
> Old callcc Generator 7.440000 32.720000 40.160000 ( 40.336902)
> James's FasterGenerator 0.040000 0.000000 0.040000 ( 0.035432)

Off topic a bit, but what os/hardware are you using to get these numbers?

Dave

[James Edward Gray II]

A dual processor G5 at 2.0 Ghz (each processor), running Mac OS X
(10.4.4). The box has 2 Gigs of RAM.

James Edward Gray II

[Jacob Fugal]

On 2/10/06, Ruby Quiz <ja...@grayproductions.net> wrote:
> This week's Ruby Quiz is to write FasterGenerator, your own
> re-implementation of Generator with an eye towards working faster.

Here's the benchmark results from my own implementation:

galadriel:~/ruby/qotw/66$ ruby benchmark.rb

### Construction ###

Rehearsal -------------------------------------------------------------
Old callcc Generator 7.380000 1.000000 8.380000 ( 8.726668)
lukfugl's FasterGenerator 0.020000 0.000000 0.020000 ( 0.070048)
---------------------------------------------------- total: 8.400000sec

user system total real
Old callcc Generator 8.580000 0.960000 9.540000 ( 9.765350)
lukfugl's FasterGenerator 0.020000 0.000000 0.020000 ( 0.020035)

### next() ###

Rehearsal -------------------------------------------------------------
Old callcc Generator 10.750000 17.010000 27.760000 ( 28.587567)
lukfugl's FasterGenerator 0.680000 0.000000 0.680000 ( 0.744570)
--------------------------------------------------- total: 28.440000sec

user system total real
Old callcc Generator 11.490000 17.390000 28.880000 ( 29.853396)
lukfugl's FasterGenerator 0.650000 0.000000 0.650000 (
0.694442)

My machine is obviously painfully slower than James', and it looks
like my implementation isn't quite as quick as his, but it was fun
figuring out a few tricks. Now I'm gonna go look at the new code and
see if my implementation beats it too!

(I'll post my solution after the spoiler period expires tomorrow morning.)

Jacob Fugal

[Ross Bamford]

On Sun, 2006-02-12 at 14:24 +0900, Jacob Fugal wrote:
> On 2/10/06, Ruby Quiz <ja...@grayproductions.net> wrote:
> > This week's Ruby Quiz is to write FasterGenerator, your own
> > re-implementation of Generator with an eye towards working faster.
>

> Here's the benchmark results from my own implementation: [...]

Here's mine up to now. Being greedy I made two versions, because of the
infinite block problem mentioned on list. These are with 10000 elements
(the posted code) against the old Generator (I'm going to try the new
one later on, I want to try a few more optimisations first):

### Construction ###

Rehearsal ------------------------------------------------------------------
1.8.4-2005-12-24 Generator 0.070000 0.100000 0.170000 ( 0.204462)
Basic (fast) generator 0.010000 0.000000 0.010000 ( 0.006223)
Enhanced (***********) generator 0.650000 0.050000 0.700000 ( 0.702831)
--------------------------------------------------------- total: 0.880000sec

user system total real
1.8.4-2005-12-24 Generator 0.080000 0.070000 0.150000 ( 0.146903)
Basic (fast) generator 0.010000 0.000000 0.010000 ( 0.008860)
Enhanced (***********) generator 1.050000 0.020000 1.070000 ( 1.066803)

### next() ###

Rehearsal ------------------------------------------------------------------
1.8.4-2005-12-24 Generator 4.470000 0.240000 4.710000 ( 4.754501)
Basic (fast) generator 0.060000 0.000000 0.060000 ( 0.055710)
Enhanced (***********) generator 0.120000 0.000000 0.120000 ( 0.122150)
--------------------------------------------------------- total: 4.890000sec

user system total real
1.8.4-2005-12-24 Generator 4.480000 0.090000 4.570000 ( 4.606803)
Basic (fast) generator 0.060000 0.000000 0.060000 ( 0.060831)
Enhanced (***********) generator 0.110000 0.000000 0.110000 ( 0.119554)

I don't know how this compares with James's benchmark really, these Macs
are a bloody mystery to me... :) This is on a 2Ghz P4 / 1gig RAM.

--
Ross Bamford - ro...@roscopeco.REMOVE.co.uk

[Christoffer Lernö]

Newbie jumping in here.

On Feb 10, 2006, at 17:23 , James Edward Gray II wrote:

> On Feb 10, 2006, at 10:08 AM, Matthew Moss wrote:
>
>> Not being familiar with all the various Ruby packages and libs, I
>> first want to thank ya for posting a good set of test cases that I
>> can
>> review, but was wondering if you also might post the code used to do
>> the timing?
>
> I will, yes, on Sunday. :)
>
> I pulled down copies on the Generator library, before and after the
> change. I then modified the class names so they could all
> peacefully coexist, loaded them, and ran a trivial benchemark:
>

..snip..

> Benchmark.bmbm do |x|
> x.report("Current Generator") do
> generator = CurrentGenerator.new(enum)
> tests.times { generator.next until generator.end? }
> end

I have small problem with this. Won't this mean the loop will only
run 1 time?

The first time it correctly loops, but the next time "generator.end?"
will be true, and the following 999 runs will consequently does not
execute generator.next at all, right?

If we change the row to

test.times do
generator.rewind
generator.next until generator.end?
end

Isn't that giving us the desired test-behaviour?

/Christoffer

[Christoffer Lernö]

> I've heard complaints in the past that this library is slow. One
> reason is that
> it was implemented with continuations, which have performance
> issues in the
> current version of Ruby. "Was" is the keyword there though,
> because I've just
> learned that Generator was recently re-implemented. I learned some
> good tricks
> reading the new version, so let's try fixing Generator ourselves.
> (No peeking
> at the new version!)
>
> This week's Ruby Quiz is to write FasterGenerator, your own re-
> implementation of
> Generator with an eye towards working faster. (This is a small
> library. My
> version is 54 lines.) It is possible to go even faster than the new
> implementation, with certain trade-offs:

With the same trade-offs as James' version(?) (i.e. no infinite block
iterators) and with the hope that I don't have any bugs in the code,
I get something like this on a G4 1.67Mhz (after changing the tests
somewhat)

### next() ###

Rehearsal -----------------------------------------------------
Current Generator 20.360000 14.330000 34.690000 ( 51.788014)
My Generator 0.080000 0.010000 0.090000 ( 0.116704)
------------------------------------------- total: 34.780000sec

user system total real
Current Generator 23.200000 14.610000 37.810000 ( 53.145604)
My Generator 0.080000 0.010000 0.090000 ( 0.129965)

(and this code)

8<----

tests = 10
enum = (1..1000).to_a

puts
puts "### next() ###"
puts

Benchmark.bmbm do |x|

x.report("Current Generator") do

generator = Generator.new(enum)
tests.times {

generator.rewind
generator.next until generator.end?
}
end

x.report("My Generator") do
generator = MyGenerator.new(enum)
tests.times {

generator.rewind
generator.next until generator.end?
}
end

end

8<-----

I originally wanted to use the original values for tests and enum,
but I got bored waiting.

/Christoffer

[H.Yamamoto]

Hello. Please add this to quiz's rule.

Generator should suspend current calculation, and
resume it when next() is called. (I uses @queue as
array, but this is just for insurance. normally
@queue should not contain multiple values)

//////////////////////////////////////////

require "test/unit"
require "generator"

class TestGenerator < Test::Unit::TestCase

class C
def value=(x)
@value = x
end
def each
loop do
yield @value
end
end
end

def test_realtime
c = C.new
g = Generator.new(c)
3.times do |i|
c.value = i
assert_equal(i, g.next())
end
end

end

//////////////////////////////////////////

And python supports generator natively,
this behaves like HEAD's Generator class.

def generator():
global value
while True:
yield value

g = generator()
for i in xrange(3):
value = i
print g.next()

////////////////////////////////////////////

And this one is Java version.

abstract class CoRoutine
{
private final Thread _thread;

private final Object _lock = new Object();

private java.util.LinkedList _list = new java.util.LinkedList();

private boolean _terminated = false;

public CoRoutine()
{
final Object first_lock = new Object();

_thread = new Thread()
{
public void run()
{
synchronized(_lock)
{
synchronized (first_lock)
{
first_lock.notify();
}

try
{
_lock.wait();
}
catch (InterruptedException e)
{
throw new RuntimeException(e); // ???
}

try
{
CoRoutine.this.run();
}
finally
{
_terminated = true;

_lock.notify();
}
}
}
};

_thread.setDaemon(true);

synchronized(first_lock)
{
_thread.start();

try
{
first_lock.wait();
}
catch (InterruptedException e)
{
throw new RuntimeException(e); // ???
}
}
}

protected abstract void run();

protected final void yield(Object value)
{
synchronized(_lock)
{
_list.add(value);

_lock.notify();

try
{
_lock.wait();
}
catch (InterruptedException e)
{
throw new RuntimeException(e); // ???
}
}
}

private void ready() // must be called in synchronized(_lock)
{
if (!_terminated && _list.isEmpty())
{
_lock.notify();

try
{
_lock.wait();
}
catch (InterruptedException e)
{
throw new RuntimeException(e); // ???
}
}
}

public boolean hasNext()
{
synchronized(_lock)
{
ready();

return !_list.isEmpty();
}
}

public Object next()
{
synchronized(_lock)
{
ready();

if (_list.isEmpty())
{
throw new RuntimeException("EOF");
}

return _list.removeFirst();
}
}
}

//////////////////////////////////////////////////
// Main

class Test extends CoRoutine
{
public int value;

protected void run()
{
while (true)
{
yield(value);
}
}
}

class Main
{
public static void main(String[] args)
{
Test t = new Test();

for (int i = 0; i < 3; ++i)
{
t.value = i;

System.out.println(t.next());
}
}
}

[Jacob Fugal]

On 2/12/06, Luke Blanshard <lu...@blanshard.us> wrote:
> x = 1
> g = Generator.new do |g|
> 5.times {|i| g.yield [x,i].max}
> end
>
> until g.end?
> x = 10 if g.current > 2
> puts g.next
> end
>
> This outputs 1, 1, 2, 3, 10.
>
> The next question is, why is the API for this class so crappy? I would
> have expected the output to be 1, 1, 2, 10, 10. But creating the
> generator automatically advances to the first yield, and "next" advances
> to the next one while returning the previous one. This is just wrong.

Actually, there's no way (I can think of) to get the output you
expect, and it has nothing to do with an initial advance or anything.
My implementation doesn't advance to the yields until required, yet
has the same output. This is because of these two lines:

x = 10 if g.current > 2
puts g.next

g.current returns the current value. g.current is not greater than two
until g.current == 3. g.next then returns the same as g.current, while
also advancing the internal counter. The behavior your describing
would require changing the value of g.current by assigning to x. Can't
be done.

Jacob Fugal

[James Edward Gray II]

On Feb 12, 2006, at 3:23 AM, Christoffer Lernö wrote:

>> Benchmark.bmbm do |x|
>> x.report("Current Generator") do
>> generator = CurrentGenerator.new(enum)
>> tests.times { generator.next until generator.end? }
>> end
>
> I have small problem with this. Won't this mean the loop will only
> run 1 time?

Yes, you are right. That was silly of me.

I like your fix. Adding rewind() fixes things up.

Thank you.

James Edward Gray II

[Christoffer Lernö]

On Feb 12, 2006, at 19:23 , James Edward Gray II wrote:
> On Feb 12, 2006, at 11:10 AM, Jacob Fugal wrote:
>
>> Ok, since last night I've corrected my implementation to not evaluate
>> ahead, as per H. Yamamoto's and Luke Blanshard's comments.
>
> Mine does, of course, pull all the items in at once and has all the
> problems discussed with that approach. Attached is my
> implementation and the altered versions I have been using in
> benchmarks.
>
> James Edward Gray II

Mine looks like a clone of James':

class MyGenerator
attr_reader :index
def initialize(enum = nil)
if enum then
@array = enum.to_a
else
@array = Array.new
yield self
end
@index = 0
end
def current
raise EOFError unless next?
@array[@index]
end
def next
value = current
@index += 1
return value
end
def next?
return @index < @array.length
end
def rewind
@index = 0
self
end
def each(&block)
@array.each(&block)
end
def yield(value)
@array << value
end
def pos
return @index
end
def end?
return !next?
end
end

/Christoffer

[Luke Blanshard]

You are correct. My bad.

My point is that the API is pointlessly difficult. I think, actually,
that the C# iterator API is the cleanest I've seen: there is one
operation that attempts to advance to the next position, returning false
if it has reached the end, and another that returns the current value,
throwing an exception if it's still before the first advance.

And my other point is that, while you're going down the road of
coroutines, you might as well go the whole way.

Luke Blanshard

[Dave Lee]

This submission:

- passes the tests
- runs a couple orders faster than the continuation generator using
the provided bench
- runs the generator block in a separate thread
- intended to handle both stateful and stateless (functional) generator blocks
- provides a Generator::stateless constructor that allows for the
generator block to run for more than one callback to Generator#yield
- is uncommented

thanks,
Dave

[hornd...@gmail.com]

I'd been wanting to mess with writing ruby extensions so I wrote the
whole thing in c. I do realize one thing already: I'm using the
'entries' method to pull out what to iterate over instead of each. This
comes from something that I'm totally clear on: The contract for the
method is that we receive in an Enumrable object so can we assume that
this method will be implemented since it's part of the Enumerable
mixin? Anyways here's the code:

#include "ruby.h"

static ID id_entries;
typedef struct _gen
{
int curr;
VALUE values;
} Generator;

//Is there a built in way to do this?
#define TEST(t) t?Qtrue:Qfalse

static VALUE t_init(int argc, VALUE *argv, VALUE self)
{
Generator* gen;
Data_Get_Struct(self, Generator, gen);
if(argc > 0)
{
VALUE arr = rb_funcall(argv[0], id_entries, 0);
gen->values = arr;
}
else
{
VALUE arr = rb_ary_new();
gen->values = arr;
rb_yield(self);
}
gen->curr = 0;
return self;
}

static VALUE t_end_q(VALUE self)
{
Generator* gen;
Data_Get_Struct(self, Generator, gen);
int size = RARRAY(gen->values)->len;
int curr = gen->curr;
return TEST(curr >= size);
}

static VALUE t_next_q(VALUE self)
{
return TEST(!t_end_q(self));
}

static VALUE t_pos(VALUE self)
{
Generator* gen;
Data_Get_Struct(self, Generator, gen);
int curr = gen->curr;
return INT2NUM(curr);
}

static VALUE t_rewind(VALUE self)
{
Generator* gen;
Data_Get_Struct(self, Generator, gen);
gen->curr = 0;
return self;
}

static VALUE t_yield(VALUE self, VALUE element)
{
Generator* gen;
Data_Get_Struct(self, Generator, gen);
rb_ary_push(gen->values, element);
return gen->values;
}

static VALUE t_current(VALUE self)
{
if(t_end_q(self))
{
rb_raise(rb_eEOFError, "no more elements available");
return Qnil;
}
Generator* gen;
Data_Get_Struct(self, Generator, gen);
int curr = gen->curr;
return rb_ary_entry(gen->values, curr);
}

static VALUE t_next(VALUE self)
{
if(t_end_q(self))
{
rb_raise(rb_eEOFError, "no more elements available");
return Qnil;
}
Generator* gen;
Data_Get_Struct(self, Generator, gen);
int curr = gen->curr++;
VALUE temp = rb_ary_entry(gen->values, curr);
return temp;
}

static VALUE t_each(VALUE self)
{
Generator* gen;
Data_Get_Struct(self, Generator, gen);
gen->curr = 0;
rb_iterate(rb_each, gen->values, rb_yield, 0);
return self;
}

static void gen_free(void* p)
{
free(p);
}

static void gen_mark(void* p)
{
Generator* g = p;
rb_gc_mark(g->values);
}

static VALUE gen_alloc(VALUE klass)
{
Generator* gen = malloc(sizeof(Generator));
VALUE obj;
obj = Data_Wrap_Struct(klass, gen_mark, gen_free, gen);
return obj;
}

VALUE cGen;
void Init_generator_j()
{
id_entries = rb_intern("entries");
cGen = rb_define_class("GeneratorJ", rb_cObject);
rb_define_method(cGen, "initialize", t_init, -1);
rb_define_method(cGen, "next?", t_next_q, 0);
rb_define_method(cGen, "next", t_next, 0);
rb_define_method(cGen, "end?", t_end_q, 0);
rb_define_method(cGen, "pos", t_pos, 0);
rb_define_method(cGen, "index", t_pos, 0);
rb_define_method(cGen, "rewind", t_rewind, 0);
rb_define_method(cGen, "yield", t_yield, 1);
rb_define_method(cGen, "current", t_current, 0);
rb_define_method(cGen, "each", t_each, 0);

rb_define_alloc_func(cGen, gen_alloc);
}

I haven't written much c in a long while (let alone ruby in c) so be
kind. It doesn't seem to be much of a speed improvement at all over the
same code written in straight ruby, but it was educational for me.

I did mess with trying to get infinite generators to work, but I
cheated and looked at the code after a bit so I was tainted after that.
Here is a test case I made however if it's of any use. (require
'matrix' of course):

def fib(n) (Matrix[[1,1],[1,0]]**(n-1))[0,0] end
def test_fib

g = Generator.new do |g|

a, b = 0, 1
while true
g.yield a
a, b = b, a+b
end
end
100.times do |i|
assert_equal(i, g.pos)
assert_equal(fib(i), g.next)
end
end

Thanks!

-----Horndude77

[Jesse Yoon]

Here's my solution. Mine is pretty much similar in spirit to Caleb's
solution, except that we use different lock mechanisms. My first take
was to replace the Continuation with a thread and a SizedQueue. That is,
in the #initialize, I create a new thread with the given block (or the
one I generate with the given enum), which will eventually be blocked
when writing to the queue with the size of 1 in #yield. Once #next
dequeues the head, the #yield thread continues, etc.

This passed James's TC_Generator test suite, but miserably failed on
Luke's "shared state" test, although the code was supposed to handle the
case.

It turned out, if SizedQueue of size one is the only blocking mechanism,
you have two values waiting at the queue's door; one in the queue, the
other right before the queue, waiting to be unlocked. This made the
reponse to Luke's test 1, 1, 2, 3, 4 (and then 10, 10, 10, ... if I
increase the repetition). I needed to make the thread stop right after
it enqueued the value until #next consumes it.

My solution was to get rid of SizedQueue and to use a Mutex and a
ConditionVariable to accomplish just that. At that point I saw Caleb's
solution and thought that starting and stopping a thead should be much
slower than using Mutexes and Cond_Vars. To my surprise, that wasn't the
case. Mutex mechanism was much slower than Caleb's thread switching
solution.

Anyways, here's the code. Benchmark follows the code (I ran on a slower
notebook).

Thanks James for the nice quiz.

Jesse

#!/usr/bin/env ruby
require 'thread'

class Generator
include Enumerable

def initialize(enum = nil, &block)
if enum
@block = proc { |g|
enum.each { |x| g.yield x }
}
else
@block = block
end

@index = 0
@queue = []
@q_access = Mutex.new
@q_consumed = ConditionVariable.new

@thread = Thread.new(self, &@block)

self
end

def yield(value)
@q_access.synchronize {
@queue << value
@q_consumed.wait(@q_access)
}

self
end

def end?()
Thread.pass while @queue.empty? && @thread.alive?
@queue.empty? && !@thread.alive?
end

def next?()
!end?
end

def index()
@index
end

def pos()
@index
end

def next()
if end?
raise EOFError, "no more elements available"
end
ret = nil
@q_access.synchronize {
@index += 1
ret = @queue.shift
@q_consumed.signal
}

ret
end

def current()
if end?
raise EOFError, "no more elements available"
end

@queue.first
end

def rewind()
initialize(nil, &@block) if @index.nonzero?

self
end

def each
rewind

until end?
yield self.next
end

self
end
end

###
### tests = 10
### enum = (1..1000).to_a
###

### Construction ###

Rehearsal
----------------------------------------------------------------
Old callcc Generator 0.000000 0.000000 0.000000 (
0.003000)
Caleb's SynchronousGenerator 0.000000 0.000000 0.000000 (
0.003000)
Jesse's FasterGenerator 0.010000 0.010000 0.020000 (
0.016000)
------------------------------------------------------- total:
0.020000sec

user system total
real
Old callcc Generator 0.000000 0.010000 0.010000 (
0.003000)
Caleb's SynchronousGenerator 0.000000 0.000000 0.000000 (
0.002000)
Jesse's FasterGenerator 0.000000 0.000000 0.000000 (
0.003000)

### next() ###

Rehearsal
----------------------------------------------------------------
Old callcc Generator 4.116000 0.270000 4.386000 (
4.438000)
Caleb's SynchronousGenerator 1.181000 0.010000 1.191000 (
1.194000)
Jesse's FasterGenerator 2.674000 0.000000 2.674000 (
2.831000)
------------------------------------------------------- total:
8.251000sec

user system total
real
Old callcc Generator 4.066000 0.010000 4.076000 (
4.099000)
Caleb's SynchronousGenerator 1.212000 0.000000 1.212000 (
1.222000)
Jesse's FasterGenerator 2.704000 0.000000 2.704000 (
2.706000)

--
Posted via http://www.ruby-forum.com/.

[Jacob Fugal]

On 2/12/06, Ross Bamford <ros...@roscopeco.co.uk> wrote:
> (Incidentally, Jacob, Under 1.8 yours was testing about twice as fast as
> mine, but it seems to deadlock about half of the time? I have to
> interrupt after leaving it for up to a minute. I'm on Ruby 1.8.4
> i686-linux).

Hmm, while I didn't run into any deadlocks with my testing, I'm not
too surprised. I'm not very threading-savvy and could easily have made
some critical mistake. :)

I also realized that the implementation I posted to the list doesn't
rewind correctly. Currently it just drops back the @position marker,
but doesn't reset the @values array or generating block. This is bad
if the generator is rewound and the block should generate different
values on different runs (e.g. it's time dependent or sensitive to the
environment).

Jacob Fugal

[Caleb Clausen]

On 2/13/06, Jesse Yoon <ze...@hotmail.com> wrote:
> My solution was to get rid of SizedQueue and to use a Mutex and a
> ConditionVariable to accomplish just that. At that point I saw Caleb's
> solution and thought that starting and stopping a thead should be much
> slower than using Mutexes and Cond_Vars. To my surprise, that wasn't the
> case. Mutex mechanism was much slower than Caleb's thread switching
> solution.

A confession: I had just the tiniest peek at Jacob's entry before I
wrote that part of mine. I wasn't trying to, but my eyes did pass over
the phrase 'Thread.stop' in his code, so any credit for a clever
implementation should go to him.

[James Edward Gray II]

On Feb 13, 2006, at 3:07 AM, Jesse Yoon wrote:

> My solution was to get rid of SizedQueue and to use a Mutex and a
> ConditionVariable to accomplish just that. At that point I saw Caleb's
> solution and thought that starting and stopping a thead should be much
> slower than using Mutexes and Cond_Vars. To my surprise, that
> wasn't the
> case. Mutex mechanism was much slower than Caleb's thread switching
> solution.

I'm pretty sure they learned the same lesson changing the standard
library. Have a look at these commit messages:

* lib/generator.rb: uses Mutex instead of Thread.critical.
[ruby-dev:28184]

Then later:

Sorry, reverted. Mutex is damn slow.....

[James Edward Gray II]

On Feb 12, 2006, at 10:55 PM, Yukihiro Matsumoto wrote:

> I'd be happy to replace current implementation of generator.rb with
> the winning one.

I'm not sure we will do any better than the current implementation,
for the general case it needs to solve. That's actually what sparked
the idea for this quiz. We will see what people come up with though...

James Edward Gray II

[James Edward Gray II]

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.

A big thank you in advance to anyone who takes up the call...

James Edward Gray II

[Jesse Yoon]

James Gray wrote:
>
> I'm pretty sure they learned the same lesson changing the standard
> library. Have a look at these commit messages:
>
> * lib/generator.rb: uses Mutex instead of Thread.critical.
> [ruby-dev:28184]
>
> Then later:
>
> Sorry, reverted. Mutex is damn slow.....
>
> :)
>
> James Edward Gray II

Aha! Well, then we have a strong candidate for the next quiz, namely
BetterMutex? :-)

Jesse

[Daniel Sheppard]

> I'm pretty sure they learned the same lesson changing the standard
> library. Have a look at these commit messages:
>
> * lib/generator.rb: uses Mutex instead of Thread.critical.
> [ruby-dev:28184]
>
> Then later:
>
> Sorry, reverted. Mutex is damn slow.....
>
> :)
>
> James Edward Gray II

Which makes perfect sense, since Mutex is simply wrapping around
Thread.critical, Thread.stop and Thread.wakeup.

Mutex, as simple as it is, is overkill for what you're trying to do here
(switch between two threads in a deterministic manner). Since the number
of threads is fixed, you don't need to keep the thread list in an array,
and you can drop a couple of other checks because you know all the
calling code.

If raw speed is your goal, relying on any pure ruby will never get you
faster than just inlining the subset of that code that you're interested
in using - even if you're just completely duplicating the logic, it's
going to be that slightest bit faster as you've reduced the number of
messages sent - and I think it's safe to say that reducing the total
number of message sends will always make your program faster, barring
any change in IO.

That's not to say that inlining bastardised versions of other libraries
is a good idea... except where it is.

Now, if somebody went and implemented the thread standard library as a C
extension, then it might be worth using in this context... or maybe not.

[Ross Bamford]

On Tue, 2006-02-14 at 01:14 +0900, Jacob Fugal wrote:
> On 2/12/06, Ross Bamford <ros...@roscopeco.co.uk> wrote:
> > (Incidentally, Jacob, Under 1.8 yours was testing about twice as fast as
> > mine, but it seems to deadlock about half of the time? I have to
> > interrupt after leaving it for up to a minute. I'm on Ruby 1.8.4
> > i686-linux).
>
> Hmm, while I didn't run into any deadlocks with my testing, I'm not
> too surprised. I'm not very threading-savvy and could easily have made
> some critical mistake. :)

It's an easy mistake to make. When you stop threads right away you need
to wait for them in the main thread, otherwise it's possible
(increasingly so the faster a computer you have) that the code following
the Thread.new block will be executed before the new thread gets to the
Thread.stop.

I've been doing some benchmarking and stuff and the following patch
seems to fix it. It passes all the tests and is pretty quick so, nice
work :))

--- jfugal_faster_generator_orig.rb 2006-02-14 15:09:58.000000000 +0000
+++ jfugal_faster_generator.rb 2006-02-14 14:07:17.000000000 +0000
@@ -68,6 +68,7 @@
@block[self]
@mutex.synchronize{ @done = true }
}
+ Thread.pass until @thread.stop?
@thread.run if @thread.status and need_value?
Thread.pass while need_value?
end

[Ross Bamford]

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]

On Wed, 2006-02-15 at 01:42 +0900, Ross Bamford wrote:

> 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).

Oops, it was actually three that passed endless but not realtime - I
missed the result for Caleb Clausen's entry when I said that.

[Caleb Clausen]

On 2/14/06, Ross Bamford <ros...@roscopeco.co.uk> 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.

[Ross Bamford]

On Wed, 2006-02-15 at 02:54 +0900, Dave Lee 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)

[Dave Lee]

On 2/14/06, Ross Bamford <ros...@roscopeco.co.uk> wrote:

> Of course I can't rule out a buggy test but I've not noticed it on the
> others. Let me know what you think after you take a look.

I made a couple fixes, which eliminates the problem (of premature
exit), only now I'm running into a very strange problem:

NoMethodError: undefined method `stop' for #<Thread:0xb7f0ebe4 sleep>

I don't know how this is happening. I'll try looking later tonight.

Dave

[Ross Bamford]

On Wed, 2006-02-15 at 07:09 +0900, Dave Lee wrote:
> On 2/14/06, Ross Bamford <ros...@roscopeco.co.uk> wrote:
> > Of course I can't rule out a buggy test but I've not noticed it on the
> > others. Let me know what you think after you take a look.
>
> I made a couple fixes, which eliminates the problem (of premature
> exit), only now I'm running into a very strange problem:
>
> NoMethodError: undefined method `stop' for #<Thread:0xb7f0ebe4 sleep>

Hmm. I think stop is a singleton method on Thread, so you'd have to do
Thread.stop rather than thr.stop ?

[Dave Lee]

On 2/14/06, Ross Bamford <ros...@roscopeco.co.uk> wrote:
> Hmm. I think stop is a singleton method on Thread, so you'd have to do
> Thread.stop rather than thr.stop ?

ah right, thanks.

[Dave Lee]

On 2/14/06, Ross Bamford <ros...@roscopeco.co.uk> 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

[Jacob Fugal]

On 2/16/06, Ruby Quiz <ja...@grayproductions.net> wrote:
> Let's see how Jacob Fugal implemented that (with a small patch from Ross
> Bamford). Here's the setup:

<snip>

> Here are the rest of the methods for Jacob's solution:

<snip>

> def rewind
> @position = 0
> self
> end

One important thing: I've since realized that this implementation of
rewind was flawed. It should be something like:

def rewind
if @thread
@thread.kill if @thread.status
@thread = nil
end
@values = []
@position = 0
@done = false
end

My initial rewind just reset to the beginning of the list of generated
values, but for proper operation the list itself and the generating
thread should also be reset. @done needs to be reset as well, since
the previous run of @thread may have completed and marked @done as
true, and we definitely don't want that. I've got the if statement
around the operations on @thread since I don't want subsequent calls
to rewind to cause a NoMethodError on nil.

Given this structure in #rewind, we can also refactor #initialize a bit:

def initialize( enum=nil, &block )
self.rewind
@mutex = Mutex.new
@block = block

if enum
@block = proc{ |g|
enum.each{ |x| g.yield x }
}

end
end

Jacob Fugal