Comparison of linked list vs array shift performance for FIFO queue

queue.rb

require 'rubygems'
require 'rspec'
require 'benchmark'

class FifoQueue

  def push(item)
    if (@head.nil? && @tail.nil?)
      @head = @tail = Wrapper.new(item)
    else
      wrapper = Wrapper.new(item)
      @tail.next = wrapper
      @tail = wrapper
    end
  end

  def pop
    val = @head.item 
    @head = @head.next
    val
  end

  private
  class Wrapper
    attr_reader :item
    attr_accessor :next

    def initialize(item)
      @item = item
    end
  end
end

class FifoQueue2

  def push(item)
    @q ||= []
    @q << item
  end

  def pop
    @q.shift
  end
end

describe FifoQueue do
  subject { FifoQueue.new }

  it "allows push and pop" do
    subject.push :foo
    subject.pop.should == :foo
  end

  it "allows many pushes and pops" do
    items = %w[foo bar baz heynow foobar]
    items.each {|item| subject.push item }
    items.each {|item| subject.pop.should == item }
  end
end

describe FifoQueue2 do
  subject { FifoQueue2.new }

  it "allows push and pop" do
    subject.push :foo
    subject.pop.should == :foo
  end

  it "allows many pushes and pops" do
    items = %w[foo bar baz heynow foobar]
    items.each {|item| subject.push item }
    items.each {|item| subject.pop.should == item }
  end
end

Benchmark.bm(1) do |x|
  x.report("linked-1,000    ") {
    f = FifoQueue.new
    (1..1_000).each{|num| f.push(num)}
    (1..1_000).each{|num| f.pop}
  }
  x.report("linked-10,000   ") {
    f = FifoQueue.new
    (1..10_000).each{|num| f.push(num)}
    (1..10_000).each{|num| f.pop}
  }
  x.report("linked-100,000  ") {
    f = FifoQueue.new
    (1..100_000).each{|num| f.push(num)}
    (1..100_000).each{|num| f.pop}
  }
  x.report("linked-1,000,000") {
    f = FifoQueue.new
    (1..1_000_000).each{|num| f.push(num)}
    (1..1_000_000).each{|num| f.pop}
  }
  x.report("shift-1,000     ") {
    f = FifoQueue2.new
    (1..1_000).each{|num| f.push(num)}
    (1..1_000).each{|num| f.pop}
  }
  x.report("shift-10,000    ") {
    f = FifoQueue2.new
    (1..10_000).each{|num| f.push(num)}
    (1..10_000).each{|num| f.pop}
  }
  x.report("shift-100,000   ") {
    f = FifoQueue2.new
    (1..100_000).each{|num| f.push(num)}
    (1..100_000).each{|num| f.pop}
  }
  x.report("shift-1,000,000 ") {
    f = FifoQueue2.new
    (1..1_000_000).each{|num| f.push(num)}
    (1..1_000_000).each{|num| f.pop}
  }
end

#mario:(git)queue[master]/$ ruby queue.rb 
                     #user     system      total        real
#linked-1,000      0.000000   0.000000   0.000000 (  0.004787)
#linked-10,000     0.050000   0.000000   0.050000 (  0.047661)
#linked-100,000    0.530000   0.020000   0.550000 (  0.554051)
#linked-1,000,000  7.950000   0.280000   8.230000 (  8.242793)
#shift-1,000       0.000000   0.000000   0.000000 (  0.002059)
#shift-10,000      0.020000   0.000000   0.020000 (  0.020310)
#shift-100,000     0.210000   0.000000   0.210000 (  0.207011)
#shift-1,000,000   2.720000   0.110000   2.830000 (  2.829217)
#....

#Finished in 0.00157 seconds
#4 examples, 0 failures
#mario:(git)queue[master]/$ ruby -v
#ruby 1.8.7 (2010-12-23 patchlevel 330) [x86_64-darwin10.6.0]

#mario:(git)queue[master]/$ ruby queue.rb 
                     #user     system      total        real
#linked-1,000      0.000000   0.000000   0.000000 (  0.003048)
#linked-10,000     0.030000   0.000000   0.030000 (  0.029437)
#linked-100,000    0.320000   0.010000   0.330000 (  0.326264)
#linked-1,000,000  3.120000   0.040000   3.160000 (  3.164152)
#shift-1,000       0.000000   0.000000   0.000000 (  0.001501)
#shift-10,000      0.010000   0.000000   0.010000 (  0.014590)
#shift-100,000     0.140000   0.000000   0.140000 (  0.146508)
#shift-1,000,000   1.450000   0.020000   1.470000 (  1.549194)
#....

#Finished in 0.00271 seconds
#4 examples, 0 failures
#mario:(git)queue[master]/$ ruby -v
#ruby 1.9.2p180 (2011-02-18 revision 30909) [x86_64-darwin10.6.0]