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