From: Jesse Yoon <zeisu@...>
Date: 2006-02-13T18:07:28+09:00
Subject: Re: FasterGenerator (#66)

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)

-- 
Posted via http://www.ruby-forum.com/.