Benchmark

benchmark.md

• Array
• Deque (circular buffer)
• crystalline Deque (linked list)

crystal run --release bm.cr

class	unshift pop unshift	push shift push	push pop	unshift shift	each	insert length/8	insert length*3/5
array	1.405377	0.685335	0.015142	7.018896	0.000162	0.222118	0.101504
deque	0.000901	0.000897	0.021794	0.019965	0.000303	0.151282	0.301467
llist	0.017698	0.007257	0.124400	0.113744	0.937949

bm.cr

require "benchmark"
require "deque"

module Crystalline
  require "crystalline/containers/deque"

  class Deque
    alias_method push, push_back
    alias_method pop, pop_back
    alias_method unshift, push_front
    alias_method shift, pop_front
  end
end
alias LinkedList = Crystalline::Deque

CLASSES = {
  Array(Int32) => 0, Deque(Int32) => 1, LinkedList(Int32) => 2
}
lines = %w{array deque llist}.map { |s| ["**#{s}**"] }

title = ["class"]
macro compare(name, classes = CLASSES.keys)
  title << {{name}}
  {{classes}}.each do |cls|
    time = Benchmark.realtime do
      {{yield cls}}
    end
    lines[CLASSES[cls]] << "%.6f" % time.total_seconds
  end
  max = lines.map(&.length).max
  lines.each do |line|
    line << "" if line.length < max
  end
end


compare "unshift pop unshift" do |cls|
  c = cls.new
  n = 50000
  n.times do |i|
    c.unshift i
    c.pop
    c.unshift i
  end
end

compare "push shift push" do |cls|
  c = cls.new
  n = 50000
  n.times do |i|
    c.push i
    c.shift
    c.push i
  end
end

compare "push pop" do |cls|
  c = cls.new
  nn = 500
  n = 5000
  nn.times do
    n.times { |i| c.push i }
    n.times { |i| c.pop }
  end
end

compare "unshift shift" do |cls|
  c = cls.new
  nn = 500
  n = 5000
  nn.times do
    n.times { |i| c.unshift i }
    n.times { |i| c.shift }
  end
end

compare "each" do |cls|
  c = cls.new
  n = 10000
  n.times { |i| c.push i }
  n = 50000
  n.times do
    s = 0
    c.each do |x|
      s += x
    end
  end
end

compare "insert length/8", [Array(Int32), Deque(Int32)] do |cls|
  c = cls.new
  n = 30000
  n.times do |i|
    c.insert(c.length / 8, i)
  end
end

compare "insert length*3/5", [Array(Int32), Deque(Int32)] do |cls|
  c = cls.new
  n = 30000
  n.times do |i|
    c.insert(c.length * 3 / 5, i)
  end
end


puts title.join(" | ")
puts (["---"] * title.length).join(" | ")
lines.each do |line|
  puts line.join(" | ")
end