FasterGenerator (#66)


#1

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/

  1. 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/rdoc/classes/Generator.html

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

require 'test/unit'

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

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

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

      g.yield 'Z'
    }

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

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

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

    assert_equal(g, g.rewind)

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

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

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

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

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

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

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

    g = Generator.new(a)

    i = 0

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

      i += 1

      break if i == 3
    }

    assert_equal(3, i)

    i = 0

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

      i += 1
    }

    assert_equal(5, i)
  end
end

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


#2

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


#3

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


#4

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?


#5

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

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

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

require “benchmark”

require “current_generator”
require “callcc_generator”
require “faster_generator”

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

puts
puts “### Construction ###”
puts

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

puts
puts “### next() ###”
puts

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

END

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

James Edward G. II


#6

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… :wink:

James Edward G. II


#7

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

I will, yes, on Sunday. :slight_smile:

But you just posted it. :slight_smile:

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


#8

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


#9

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

James Edward G. II


#10

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


#11

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

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


#12

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


#13

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.


#14

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


#15

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


#16

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


#17

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.


#18

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.


#19

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

}


#20

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