In Progress
Unit 1, Lesson 1
In Progress

Infinity

Video transcript & code

In the last episode, we included a predicate method called #full? in our bounded queue class.

def full?
  return false if @max_size == :infinite
  @max_size <= @items.size
end

It checks to see if the queue is at maximum capacity. In the process, it has to handle the special case of an unlimited-size queue, which is indicated by the @max_size variable containing a special :infinite symbol.

There's a way we can simplify this code. Ruby actually has a special value to represent infinity. In earlier versions of Ruby this value was a little bit hard to find. We had to divide a floating point number by zero in order to come across it.

1.0 / 0                         # => Infinity

Since Ruby 1.9.2 however, infinity has had its own constant, namespaced inside the Float class.

Float::INFINITY                 # => Infinity

As you might expect, Infinity is considered bigger than any other number in Ruby.

1000000000000000000000000000000000000000 < Float::INFINITY # => true

Knowing about infinity, we can simplify our Queue code. We replace our placeholder symbol with Float::INFINITY. That enables us to remove a line from the #full? predicate, and simply test if the queue size is equal to or greater than the max size.

require "thread"

class MyQueue
  def initialize(max_size = Float::INFINITY)
    @lock  = Mutex.new
    @items = []
    @item_available = ConditionVariable.new
    @max_size = max_size
    @space_available = ConditionVariable.new
  end

  def push(obj, timeout=:never, &timeout_policy)
    timeout_policy ||= -> do
      raise "Push timed out"
    end
    wait_for_condition(
      @space_available,
      ->{!full?},
      timeout,
      timeout_policy) do

      @items.push(obj)
      @item_available.signal
    end
  end

  def pop(timeout = :never, &timeout_policy)
    timeout_policy ||= ->{nil}
    wait_for_condition(
      @item_available,
      ->{@items.any?},
      timeout,
      timeout_policy) do 

      item = @items.shift 
      @space_available.signal unless full?
      item
    end
  end

  private

  def full?
    @max_size <= @items.size
  end

  def wait_for_condition(
      cv, condition_predicate, timeout=:never, timeout_policy=->{nil})
    deadline = timeout == :never ? :never : Time.now + timeout
    @lock.synchronize do
      loop do
        cv_timeout = timeout == :never ? nil : deadline - Time.now
        if !condition_predicate.call && cv_timeout.to_f >= 0
          cv.wait(@lock, cv_timeout) 
        end
        if condition_predicate.call
          return yield
        elsif deadline == :never || deadline > Time.now
          next
        else
          return timeout_policy.call
        end
      end
    end
  end
end

q = MyQueue.new
$shutdown = false

trap("INT") do
  $shutdown = true
end

producer = Thread.new do
  i = 0
  until($shutdown) do
    widget = "widget#{i+=1}"
    puts "producing #{widget}"
    q.push(widget, 0.1)
    sleep 0.1
  end
  puts "Producer shutting down"
end

def consume(thread, q)
  until($shutdown) do
    widget = q.pop
    if widget
      puts "#{thread} consuming #{widget}"
    else
      puts "BUG: No widget popped in #{thread}"
      exit(1)
    end
    sleep 0.5
  end
  puts "Consumer #{thread} shutting down"
end

Thread.abort_on_exception = true

threads = (1..3).map do |n|
  Thread.new do consume("thread #{n}", q) end
end

producer.join
threads.each(&:join)

Using infinity is an example of using a "benign value", which is something we'll return to in future episodes. A benign value is one that signals a special case while still being completely compatible with the code that handles the ordinary case. Contrast this with using a symbol, nil, or magic number like 0 or -1 to represent the "unlimited" case; any of which would have required a special check before the comparison.

That's it for today. Happy hacking!

Responses