[lnkForumImage]
TotalShareware - Download Free Software

Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] FasterGenerator (#66

James Gray

2/10/2006 1:53:00 PM

The three rules of Ruby Quiz:

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

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

http://www.rub...

3. Enjoy!

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

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

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

require 'generator'

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

while g.next?
puts g.next
end

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

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

### Construction ###

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

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

### next() ###

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

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

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

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

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.


28 Answers

Pit Capitain

2/10/2006 2:25:00 PM

0

Ruby Quiz schrieb:
> Ruby includes a useful Generator library for switching internal iterators to
> external iterators. It is used like this:
> ...
> If you want to make sure your implementation is correct, you can use these tests
> straight out of the current implementation:
> ...

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

Regards,
Pit


James Gray

2/10/2006 2:34:00 PM

0

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

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

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

James Edward Gray II


matthew.moss.coder

2/10/2006 4:08:00 PM

0

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 Gray

2/10/2006 4:24:00 PM

0

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

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

I will, yes, on Sunday. :)

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

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

require "benchmark"

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

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

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

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

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

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

__END__

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

James Edward Gray II



James Gray

2/10/2006 4:28:00 PM

0

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

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

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

### Construction ###

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

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

### next() ###

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

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

James Edward Gray II



James Gray

2/10/2006 4:33:00 PM

0

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

> ### Construction ###

> James's FasterGenerator 0.000000 0.000000 0.000000 ( 0.003751)

> ### next() ###

> James's FasterGenerator 0.030000 0.000000 0.030000 ( 0.037034)

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

James Edward Gray II


matthew.moss.coder

2/10/2006 4:35:00 PM

0

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

2/10/2006 4:44:00 PM

0

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

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

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

James Edward Gray II



matthew.moss.coder

2/10/2006 5:36:00 PM

0

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

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

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


Dave Lee

2/10/2006 6:46:00 PM

0

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

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

Dave