--
dD+E6QVmkjEoD2icmYf
Content-Type: text/plain
Content-Transfer-Encoding: 7bit
On Mon, 2006-02-13 at 02:10 +0900, Jacob Fugal wrote:
> Ok, since last night I've corrected my implementation to not evaluate
> ahead, as per H. Yamamoto's and Luke Blanshard'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)
--
Ross Bamford - rosco / roscopeco.REMOVE.co.uk
--
dD+E6QVmkjEoD2icmYf
Content-Disposition: attachment; filename=bench.rb
Content-Type: text/plain; name=bench.rb; charset=utf-8
Content-Transfer-Encoding: 7bit
#!/usr/local/bin/ruby -w
require "benchmark"
require "fgenerator"
require "generator"
#require "profile"
tests 00
enum 1..1000).to_a
puts
puts "### Construction ###"
puts
Benchmark.bmbm do |x|
x.report("#{RUBY_VERSION}-#{RUBY_RELEASE_DATE} Generator") do
tests.times { Generator.new(enum) }
end
x.report("My generator") do
tests.times { FGenerator.new(enum) }
end
end
puts
puts "### next() ###"
puts
Benchmark.bmbm do |x|
x.report("#{RUBY_VERSION}-#{RUBY_RELEASE_DATE} Generator") do
generator enerator.new(enum)
tests.times { generator.rewind; generator.next until generator.end? }
end
x.report("My generator") do
generator Generator.new { |g| enum.each { |i| g.yield i } }
tests.times { generator.rewind; generator.next until generator.end? }
end
end
--
dD+E6QVmkjEoD2icmYf
Content-Disposition: attachment; filename=fgenerator.rb
Content-Type: text/plain; name=fgenerator.rb; charset=utf-8
Content-Transfer-Encoding: 7bit
class FGenerator
include Enumerable
def initialize(enum il, &blk)
if enum
blk ambda { |g| enum.each { |i| g.yield i } }
end
init_generator(blk)
end
# This is called from the block, i.e. on the blk_thread.
# It sets the value then stops this thread, waking up
# the user thread instead.
def yield(obj)
Thread.critical rue
begin
@next << obj
@user_thread.run
Thread.stop
ensure
Thread.critical alse
end
self
end
# If @next is nil and @blk_thread is still there, this
# wakes it up and suspends this thread (it will be notified
# when the block next calls yield). After the block exits
# @blk_thread should be nil.
#
# After this, true is returned if there's no next item.
def end?
if @next.empty? && @blk_thread
Thread.critical rue
begin
@user_thread hread.current
@blk_thread.run
Thread.stop
ensure
@user_thread il
Thread.critical alse
end
end
@next.empty?
end
def next?
!self.end?
end
def current
raise EOFError if self.end?
@next.first
end
def next
raise EOFError if self.end?
@pos +
@next.shift
end
def rewind
@blk_thread.kill if @blk_thread
init_generator(@blk)
self
end
# careful with infinite blocks here!
def each
rewind
yield self.next until self.end?
end
def to_a
self.inject([]) { |ary, i| ary << i }
end
attr_reader :pos
private
# sets up ivars and makes a new thread (stopped) that
# will call the block. We'll then use the yield calls
# from the block to wait the thread and give control
# back to the user thread.
#
# This thread is notified by +next+ when first called,
# and as new items are needed.
def init_generator(blk)
@next, @pos ], 0
if @blk lk
@blk_thread hread.new do
# wait for it... (at first next call)
Thread.stop
begin
blk.call(self)
ensure
@blk_thread il
@user_thread.run
end
end
else
@blk_thread il
end
if @blk_thread
Thread.pass until @blk_thread.stop?
end
end
end
if $0 __FILE__
require 'test/unit'
class TC_FGenerator < 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
g.each { |x|
assert_equal(a[i], x)
i +
break if i 3
}
assert_equal(3, i)
i
g.each { |x|
assert_equal(a[i], x)
i +
}
assert_equal(5, i)
end
def test_to_a
g Generator.new { |g| [1,2,3,4,5,6,7,8,9,10].each { |i| g.yield i } }
assert_equal [1,2,3,4,5,6,7,8,9,10], g.to_a
end
def test_endless
g Generator.new do |g|
i 1
while true
g.yield(i+
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
end
end
--
dD+E6QVmkjEoD2icmYf
Content-Disposition: attachment; filename=queuetest.rb
Content-Type: text/plain; name=queuetest.rb; charset=utf-8
Content-Transfer-Encoding: 7bit
require "test/unit"
require "fgenerator"
class TestGenerator < Test::Unit::TestCase
class C
def value )
@value
end
def each
loop do
yield @value
end
end
end
def test_realtime
c .new
g Generator.new(c)
3.times do |i|
c.value
assert_equal(i, g.next())
end
end
end
--
dD+E6QVmkjEoD2icmYf--