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

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

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.

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

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

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

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

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?

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

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

class Test extends CoRoutine
{
    public int value;

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

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

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

 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.

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

Thank you.

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

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.

#include "ruby.h"

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

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;

    rb_define_alloc_func(cGen, gen_alloc);

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!

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)

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