Forum: Ruby FasterGenerator (#66)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2006-02-10 15:55
(Received via mailing list)
The three rules of Ruby Q.:

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 Q. 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 T. 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 Q. 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/rd...

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 C. (Guest)
on 2006-02-10 16:24
(Received via mailing list)
Ruby Q. 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 G. (Guest)
on 2006-02-10 16:34
(Received via mailing list)
On Feb 10, 2006, at 8:24 AM, Pit C. 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 G. II
Matthew M. (Guest)
on 2006-02-10 18:08
(Received via mailing list)
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 G. (Guest)
on 2006-02-10 18:23
(Received via mailing list)
On Feb 10, 2006, at 10:08 AM, Matthew M. 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:

#!/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 G. II
James G. (Guest)
on 2006-02-10 18:28
(Received via mailing list)
On Feb 10, 2006, at 10:23 AM, James Edward G. 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 G. II
James G. (Guest)
on 2006-02-10 18:32
(Received via mailing list)
On Feb 10, 2006, at 10:28 AM, James Edward G. 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 C. has already
told you one of the flaws with my approach...  ;)

James Edward G. II
Matthew M. (Guest)
on 2006-02-10 18:34
(Received via mailing list)
> > 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 G. (Guest)
on 2006-02-10 18:43
(Received via mailing list)
On Feb 10, 2006, at 10:34 AM, Matthew M. 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 G. II
Matthew M. (Guest)
on 2006-02-10 19:36
(Received via mailing list)
> 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 L. (Guest)
on 2006-02-10 20:45
(Received via mailing list)
On 2/10/06, James Edward G. II <removed_email_address@domain.invalid> wrote:
>                                user     system      total        real
> ------------------------------------------------- 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 G. (Guest)
on 2006-02-10 20:50
(Received via mailing list)
On Feb 10, 2006, at 12:45 PM, Dave L. wrote:

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

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 G. II
Jacob F. (Guest)
on 2006-02-12 07:24
(Received via mailing list)
On 2/10/06, Ruby Q. <removed_email_address@domain.invalid> wrote:
> This week's Ruby Q. 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 F.
Ross B. (Guest)
on 2006-02-12 08:51
(Received via mailing list)
On Sun, 2006-02-12 at 14:24 +0900, Jacob F. wrote:
> On 2/10/06, Ruby Q. <removed_email_address@domain.invalid> wrote:
> > This week's Ruby Q. 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.
Christoffer Lernö (Guest)
on 2006-02-12 11:23
(Received via mailing list)
Newbie jumping in here.

On Feb 10, 2006, at 17:23 , James Edward G. 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:
>

...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ö (Guest)
on 2006-02-12 11:43
(Received via mailing list)
> at the new version!)
>
> This week's Ruby Q. 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 (Guest)
on 2006-02-12 13:30
(Received via mailing list)
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());
        }
    }
}
Luke B. (Guest)
on 2006-02-12 15:01
(Received via mailing list)
James Edward G. II wrote:
> On Feb 10, 2006, at 8:24 AM, Pit C. 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...

More importantly than endless generators, it seems to me, is ones that
depend on other shared state.  The hardest part about generators is the
fact that (to do them correctly) they must be suspended between calls to
g.yield.  Here's an illustration of what I mean:

    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.

Perhaps a more interesting quiz would be BetterGenerator that looks like
Python's upcoming PEP 342 (http://python.org/peps/pep-0342.html).


Luke B.
Jacob F. (Guest)
on 2006-02-12 18:42
(Received via mailing list)
On 2/12/06, Luke B. <removed_email_address@domain.invalid> wrote:
> 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 F.
James G. (Guest)
on 2006-02-12 19:07
(Received via mailing list)
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 G. II
Jacob F. (Guest)
on 2006-02-12 19:10
(Received via mailing list)
On 2/11/06, Jacob F. <removed_email_address@domain.invalid> wrote:
> On 2/10/06, Ruby Q. <removed_email_address@domain.invalid> wrote:
> > This week's Ruby Q. 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:

Ok, since last night I've corrected my implementation to not evaluate
ahead, as per H. Yamamoto's and Luke B.'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 F.
James G. (Guest)
on 2006-02-12 20:23
(Received via mailing list)
On Feb 12, 2006, at 11:10 AM, Jacob F. wrote:

> Ok, since last night I've corrected my implementation to not evaluate
> ahead, as per H. Yamamoto's and Luke B.'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 G. II
Christoffer Lernö (Guest)
on 2006-02-12 20:58
(Received via mailing list)
On Feb 12, 2006, at 19:23 , James Edward G. II wrote:
> James Edward G. 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 B. (Guest)
on 2006-02-12 21:33
(Received via mailing list)
Jacob F. wrote:
>>     end
> expect, and it has nothing to do with an initial advance or anything.
> be done.
>

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 B.
Ross B. (Guest)
on 2006-02-12 22:12
(Received via mailing list)
On Mon, 2006-02-13 at 02:10 +0900, Jacob F. wrote:

> Ok, since last night I've corrected my implementation to not evaluate
> ahead, as per H. Yamamoto's and Luke B.'s comments.

I did the same, and it's pretty much killed my implementation :(. It
turns out to be quite similar to the new standard generator
implementation, but I didn't look beforehand, I promise :) I've used
this kind of setup before in Java. Previously I had it running the block
in variable-size chunks  with optimisation for non-block usage, when an
enum that responds_to? :length is supplied to the constructor. Like in
those performance tests ;)

Anyway, it now satisfies the extra conditions discussed I think, but
it's performance isn't too hot anymore. Particularly on 1.8, threading
seems to be fairly slow anyway. I also ran it under 1.9 against the 1.9
generator for comparison (it's a sliver quicker, but I suspect that's
because my one isn't very robust). These numbers are with 100 tests,
1000 elements as used in Jacob's benchmark.

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

>> $ ruby bench.rb

### Construction ###

Rehearsal --------------------------------------------------------------
1.8.4-2005-12-24 Generator   0.020000   0.010000   0.030000 (  0.111110)
My generator                 0.010000   0.000000   0.010000 (  0.065179)
----------------------------------------------------- total: 0.040000sec

                                 user     system      total        real
1.8.4-2005-12-24 Generator   0.000000   0.010000   0.010000 (  0.015034)
My generator                 0.010000   0.000000   0.010000 (  0.010767)

### next() ###

Rehearsal --------------------------------------------------------------
1.8.4-2005-12-24 Generator  19.640000   0.420000  20.060000 ( 22.134238)
My generator                10.720000   0.090000  10.810000 ( 11.349895)
---------------------------------------------------- total: 30.870000sec

                                 user     system      total        real
1.8.4-2005-12-24 Generator  19.310000   0.250000  19.560000 ( 20.453355)
My generator                 9.950000   0.060000  10.010000 ( 10.507884)


>> $ ruby9 bench.rb

### Construction ###

Rehearsal --------------------------------------------------------------
1.9.0-2006-02-13 Generator   0.000000   0.000000   0.000000 (  0.057187)
My generator                 0.010000   0.000000   0.010000 (  0.005367)
----------------------------------------------------- total: 0.010000sec

                                 user     system      total        real
1.9.0-2006-02-13 Generator   0.000000   0.000000   0.000000 (  0.003844)
My generator                 0.010000   0.000000   0.010000 (  0.004790)

### next() ###

Rehearsal --------------------------------------------------------------
1.9.0-2006-02-13 Generator   3.780000   0.030000   3.810000 (  4.021680)
My generator                 3.610000   0.020000   3.630000 (  3.758884)
----------------------------------------------------- total: 7.440000sec

                                 user     system      total        real
1.9.0-2006-02-13 Generator   3.950000   0.030000   3.980000 (  4.021709)
My generator                 3.590000   0.030000   3.620000 (  3.762839)
Caleb C. (Guest)
on 2006-02-12 22:50
(Received via mailing list)
Here's my solution for this week's quiz. Normally, I just watch the
quizzing, but this one happens to be one that I'm already doing, as
part of a larger library of external iterators.

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

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

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

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

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

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

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

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

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

Benchmarks: (take with a grain of salt)

### Construction ###

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

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

### next() ###

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

                                    user     system      total
real
Caleb's Generator               0.030000   0.000000   0.030000 (
0.069023)
Caleb's Synchronous Generator   0.200000   0.000000   0.200000 (
0.256574)
each                            0.000000   0.000000   0.000000 (
0.000392)
Old callcc Generator            7.400000   0.960000   8.360000 (
8.679449)
Dave L. (Guest)
on 2006-02-13 06:51
(Received via mailing list)
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
Yukihiro M. (Guest)
on 2006-02-13 06:55
(Received via mailing list)
Hi,

In message "Re: [QUIZ] FasterGenerator (#66)"
    on Fri, 10 Feb 2006 22:53:06 +0900, Ruby Q.
<removed_email_address@domain.invalid> writes:

|This week's Ruby Q. 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.
Jay A. (Guest)
on 2006-02-13 07:53
(Received via mailing list)
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
Dave L. (Guest)
on 2006-02-13 08:08
(Received via mailing list)
On 2/12/06, Dave L. <removed_email_address@domain.invalid> wrote:
> 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

forgot one thing:

- intended to handle infinite generators.

Dave
Jesse Y. (Guest)
on 2006-02-13 11:07
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)
Jacob F. (Guest)
on 2006-02-13 18:14
(Received via mailing list)
On 2/12/06, Ross B. <removed_email_address@domain.invalid> 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 F.
Caleb C. (Guest)
on 2006-02-13 18:18
(Received via mailing list)
On 2/13/06, Jesse Y. <removed_email_address@domain.invalid> 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 G. (Guest)
on 2006-02-13 18:47
(Received via mailing list)
On Feb 13, 2006, at 3:07 AM, Jesse Y. 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 G. II
James G. (Guest)
on 2006-02-13 18:50
(Received via mailing list)
On Feb 12, 2006, at 10:55 PM, Yukihiro M. 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 G. II
James G. (Guest)
on 2006-02-13 18:57
(Received via mailing list)
On Feb 10, 2006, at 7:53 AM, Ruby Q. wrote:

> This week's Ruby Q. 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 G. II
Jesse Y. (Guest)
on 2006-02-14 02:39
James G. 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 G. II

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

Jesse
Ross B. (Guest)
on 2006-02-14 17:44
(Received via mailing list)
On Tue, 2006-02-14 at 01:14 +0900, Jacob F. wrote:
> On 2/12/06, Ross B. <removed_email_address@domain.invalid> 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 B. (Guest)
on 2006-02-14 18:43
(Received via mailing list)
On Tue, 2006-02-14 at 01:57 +0900, James Edward G. II wrote:
> On Feb 10, 2006, at 7:53 AM, Ruby Q. wrote:
>
> > This week's Ruby Q. 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 F.'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.
James G. (Guest)
on 2006-02-14 18:56
(Received via mailing list)
On Feb 14, 2006, at 10:42 AM, Ross B. wrote:

> Here's some I ran up on Ruby 1.8.4-2005-12-24, and results of test
> runs
> too.

We all owe Ross a *huge* thank you for this effort!

James Edward G. II
Ross B. (Guest)
on 2006-02-14 19:08
(Received via mailing list)
On Wed, 2006-02-15 at 01:42 +0900, Ross B. 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 C.'s entry when I said that.
Dave L. (Guest)
on 2006-02-14 19:56
(Received via mailing list)
On 2/14/06, Ross B. <removed_email_address@domain.invalid> wrote:
> 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

As James said, thanks for doing this Ross.

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.

These are basically the optimizations:

   def current
-    raise EOFError if spent?
-    @array[@index]
+    @array.fetch(@index) rescue raise EOFError
   end

   def end?
-    spent?
+    @index >= @array.size
   end

   def next
-    result = current
+    begin
+      result = @array.fetch(@index)
+    rescue
+      raise EOFError
+    end
     @index += 1
     result
   end

   def next?
-    not end?
+    @index < @array.size
   end


Dave
Caleb C. (Guest)
on 2006-02-14 21:25
(Received via mailing list)
On 2/14/06, Ross B. <removed_email_address@domain.invalid> 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 B. (Guest)
on 2006-02-14 21:43
(Received via mailing list)
On Wed, 2006-02-15 at 02:54 +0900, Dave L. 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 L. (Guest)
on 2006-02-15 18:46
(Received via mailing list)
On 2/14/06, Ross B. <removed_email_address@domain.invalid> 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
Ross B. (Guest)
on 2006-02-15 21:00
(Received via mailing list)
On Thu, 2006-02-16 at 01:46 +0900, Dave L. wrote:
>
> -      ... [manual thread timeout code] ...
> +      fail "Endless iterators unsupported" unless t.join(30)

Ahh, cool. I knew there must be a better way to do that. Thanks :)

Anyway, here is a new benchmark run. Check out your numbers:

### Construction ###

Rehearsal -------------------------------------------------------------
New Thread Generator        0.260000   0.040000   0.300000 (  0.359351)
Old callcc Generator        0.310000   0.100000   0.410000 (  0.409978)
RossBamfordGenerator        1.060000   0.060000   1.120000 (  1.143501)
JesseYoonGenerator          2.530000   0.090000   2.620000 (  2.644731)
JacobFugalGenerator         0.020000   0.000000   0.020000 (  0.017337)
JEGIIGenerator              0.000000   0.000000   0.000000 (  0.003492)
HorndudeGenerator           1.210000   0.010000   1.220000 (  1.176024)
DaveLeeGenerator            0.010000   0.000000   0.010000 (  0.006422)
ChristofferLernoGenerator   0.010000   0.000000   0.010000 (  0.005104)
CalebClausenSyncGenerator   2.780000   0.080000   2.860000 (  2.872062)
CalebClausenGenerator       7.400000   0.110000   7.510000 (  7.537113)
--------------------------------------------------- total: 14.860000sec

                                user     system      total        real
New Thread Generator        4.740000   0.090000   4.830000 (  4.859650)
Old callcc Generator        0.060000   0.090000   0.150000 (  0.157226)
RossBamfordGenerator        6.010000   0.050000   6.060000 (  6.344554)
JesseYoonGenerator          7.520000   0.110000   7.630000 (  7.642123)
JacobFugalGenerator         0.010000   0.000000   0.010000 (  0.020769)
JEGIIGenerator              0.000000   0.000000   0.000000 (  0.004785)
HorndudeGenerator           2.070000   0.010000   2.080000 (  2.113591)
DaveLeeGenerator            0.010000   0.000000   0.010000 (  0.010756)
ChristofferLernoGenerator   0.000000   0.000000   0.000000 (  0.004356)
CalebClausenSyncGenerator   9.250000   0.120000   9.370000 (  9.404799)
CalebClausenGenerator      14.170000   0.170000  14.340000 ( 14.400167)

### next() ###

Rehearsal -------------------------------------------------------------
New Thread Generator        0.540000   0.000000   0.540000 (  0.613446)
Old callcc Generator        1.530000   0.300000   1.830000 (  1.920241)
RossBamfordGenerator        0.510000   0.000000   0.510000 (  0.588254)
JesseYoonGenerator          1.390000   0.010000   1.400000 (  1.475440)
JacobFugalGenerator         0.470000   0.000000   0.470000 (  0.546782)
JEGIIGenerator              0.040000   0.000000   0.040000 (  0.086357)
HorndudeGenerator           0.000000   0.000000   0.000000 (  0.006002)
DaveLeeGenerator            0.030000   0.000000   0.030000 (  0.116365)
ChristofferLernoGenerator   0.060000   0.000000   0.060000 (  0.101321)
CalebClausenSyncGenerator   0.660000   0.000000   0.660000 (  0.741025)
CalebClausenGenerator       0.450000   0.010000   0.460000 (  0.544104)
---------------------------------------------------- total: 6.000000sec

                                user     system      total        real
New Thread Generator        0.550000   0.000000   0.550000 (  0.566899)
Old callcc Generator        1.510000   0.200000   1.710000 (  1.725167)
RossBamfordGenerator        0.510000   0.000000   0.510000 (  0.514021)
JesseYoonGenerator          1.360000   0.000000   1.360000 (  1.378787)
JacobFugalGenerator         0.460000   0.010000   0.470000 (  0.467460)
JEGIIGenerator              0.040000   0.000000   0.040000 (  0.041809)
HorndudeGenerator           0.000000   0.000000   0.000000 (  0.007873)
DaveLeeGenerator            0.030000   0.000000   0.030000 (  0.037849)
ChristofferLernoGenerator   0.060000   0.000000   0.060000 (  0.056630)
CalebClausenSyncGenerator   0.660000   0.000000   0.660000 (  0.670666)
CalebClausenGenerator       0.420000   0.010000   0.430000 (  0.432745)

According to this and the tests, the entries now stack up like this.
I've used the benchmark next() speed above to order the entries fastest
to slowest on raw iteration:

== Supporting all functionality

* Dave L.
* Jacob F.
* Ross B.

== Supporting either endless or realtime/stateful iterators, or both

* Caleb C. (Generator) (Endless, no realtime)
* Caleb C. (SyncGenerator) (Realtime, no endless)
* Jesse Y. (Endless, no realtime)

== Supporting neither endless nor realtime/stateful iterators

* Horndude
* James Edward G. II
* Christoffer Lerno

Assuming there isn't some gap in the tests (sorry, ever the cynic) your
fixed version has some very impressive performance, nice job.

Now I'm off to see if I can properly figure out how you made it work :)
Ross B. (Guest)
on 2006-02-16 13:23
(Received via mailing list)
Hi,

Well, I've snapped a string on my guitar and my computer won't play MP3s
today for some reason, so inevitably boredom started to creep in. I
started playing around with the generator stuff, specifically about the
coroutine discussion earlier in this thread. Just wanted to see if I
could *really* get my head around continuations and all that.

It starts with some private methods on Kernel, which are then used to
implement the generator, but can be used elsewhere too:

module Kernel
  private
  def coreset(blk)
    Thread.current[:"#{blk.inspect.hash}_codone"] = nil
  end

  def coyield?(blk)
    Thread.current[:"#{blk.inspect.hash}_codone"] ? false : true
  end

  def coyield(blk, *args)
    raise "Coroutine exhausted" if
Thread.current[:"#{blk.inspect.hash}_codone"]

    catch :coreturn do
      next_item = (Thread.current[:coreturn] ||= []).pop

      if next_item
        next_item.call
      else
        final = blk.call(*args)
        Thread.current[:"#{blk.inspect.hash}_codone"] = true
        throw :coreturn, final
      end
    end
  end

  def coreturn(val)
    callcc do |return_cc|
      (Thread.current[:coreturn] ||= []) << return_cc
      throw :coreturn, val
    end
  end
end

class CoGenerator
  def initialize(enum = nil, &blk)
    @blk, @pos = blk, 0

    if enum
      @blk = lambda { enum.each { |e| coreturn e } }
    end
  end

  def rewind
    @pos = 0
    coreset @blk
  end

  def next
    @pos += 1
    @current = coyield(@blk)
  end

  def current
    @current
  end

  def next?
    coyield? @blk
  end

  def end?
    !self.next?
  end

  def each
    rewind
    yield coyield(@blk) while coyield?(@blk)
  end

  def pos
    @pos
  end
end

It would be used like:

	g = CoGenerator.new do
	  coreturn 6
	  # Some work
	  coreturn 7
	  # More work
	  coreturn 8
	  # Yet more work
	  9
	end

	p g.next while g.next?
	# ->
	#   6
	#   7
	#   8
	#   9

Obviously this isn't for the quiz (it'd be dead last, being based on
continuations, and it doesn't actually have the Generator API) but just,
well, for fun. And something to do. It was fun to write, but it's a toy.
I dread to think what it mightn't do properly, or at all :) It's
behaviour in multithreaded code could well be a bit counter-intuitive
too, I'm afraid I don't know much about how coroutines work in other
languages.

It times a bit faster than the old callcc generator, because it's using
less continuations (just the one) but really I guess it's just a test of
the coyield/coreturn stuff.

Anyway, enough about that... Music shop will be open now :)
Jim W. (Guest)
on 2006-02-16 15:50
Ross B. wrote:
> Hi,
>
> Well, I've snapped a string on my guitar and my computer won't play MP3s
> today for some reason,

I've come to believe that having a backup set of guitar strings is
nearly as important as having a backup for your hard disk.

--
-- Jim W.
Ross B. (Guest)
on 2006-02-17 02:00
(Received via mailing list)
On Thu, 2006-02-16 at 22:52 +0900, Jim W. wrote:
> Ross B. wrote:
> > Hi,
> >
> > Well, I've snapped a string on my guitar and my computer won't play MP3s
> > today for some reason,
>
> I've come to believe that having a backup set of guitar strings is
> nearly as important as having a backup for your hard disk.

I've been lulled by living two minutes walk away from a well stocked
music shop that, as it transpires, is closed Wednesday afternoon and
Thursday morning.

Definitely got a backup set now, though :)
This topic is locked and can not be replied to.