[QUIZ] FasterGenerator (#66)

ruby-talk
1

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.

2

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

3

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?

4

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

···

On 2/10/06, Ruby Quiz <james@grayproductions.net> wrote:

This week's Ruby Quiz is to write FasterGenerator, your own
re-implementation of Generator with an eye towards working faster.

5

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

6

Hi,

···

In message "Re: [QUIZ] FasterGenerator (#66)" on Fri, 10 Feb 2006 22:53:06 +0900, Ruby Quiz <james@grayproductions.net> writes:

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:

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

              matz.

7

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

8

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

9

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

···

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.

10

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

···

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.

11

I will, yes, on Sunday. :slight_smile:

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

···

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?

12

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... :slight_smile: This is on a 2Ghz P4 / 1gig RAM.

···

On Sun, 2006-02-12 at 14:24 +0900, Jacob Fugal wrote:

On 2/10/06, Ruby Quiz <james@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: [...]

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

13

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());
        }
    }
}

14

Ok, since last night I've corrected my implementation to not evaluate
ahead, as per H. Yamamoto's and Luke Blanshard's comments. I had
originally done this, then removed it for time savings. For
correctness (which Luke's example brought to mind), I've reintroduced
it.

I also made the changes to the benchmark that Christoffer Lernö
suggested. Due to the slowness of the current generator (more
specifically, the current generator on my computer) I had to drop the
test constants in order to get it to finish in a reasonable time.

Here are my current benchmark results, with my benchmark code and
current implementation attached:

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

### Construction ###

Rehearsal -------------------------------------------------------------
Old callcc Generator 0.070000 0.140000 0.210000 ( 0.323153)
lukfugl's FasterGenerator 0.010000 0.000000 0.010000 ( 0.003346)
---------------------------------------------------- total: 0.220000sec

                                user system total real
Old callcc Generator 0.140000 0.090000 0.230000 ( 0.354175)
lukfugl's FasterGenerator 0.000000 0.000000 0.000000 ( 0.004274)

### next() ###

Rehearsal -------------------------------------------------------------
Old callcc Generator 300.130000 182.660000 482.790000 (495.950825)
lukfugl's FasterGenerator 5.550000 0.050000 5.600000 ( 5.751610)
-------------------------------------------------- total: 488.390000sec

                                user system total real
Old callcc Generator 225.030000 185.010000 410.040000 (425.286992)
lukfugl's FasterGenerator 5.690000 0.020000 5.710000 (
5.821117)

Jacob Fugal

faster_generator.rb (1.16 KB)

benchmark.rb (776 Bytes)

···

On 2/11/06, Jacob Fugal <lukfugl@gmail.com> wrote:

On 2/10/06, Ruby Quiz <james@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:

15

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.

···

On 2/13/06, Jesse Yoon <zeisu@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.

16

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

:slight_smile:

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.

17

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

···

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.

18

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.

···

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.

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

19

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

···

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:

20

> 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. :slight_smile:

But you just posted it. :slight_smile:

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