Ruby Array Performance

The above chart summarizes the amortized performance of various ruby array operations. It shows that add (array concatenation), '<<' (append), and unshift are linear time, while pop and shift are O(1). It's interesting to note that like pop, shift is also implemented in a way that doesn't require the array to be copied. This might lead one to expect that shifting and then unshifting would be a cheaper operation than just unshifting (because by shifting first, we make room for the unshifted element, meaning no array copy is needed), but this isn't the case in ruby 1.9.2:

'<<' (append) is much cheaper than array concatenation using '+', but is still linear time when operating on a newly initialized large array, because at least one array copy is required to allocate more space.

However, the amortized time of appending N elements to an empty array is O(1).

Here's the code I used for this:

def benchmark(samples, sizes)
  results = []
  for n in sizes
    array = Array.new(n,1)
    start = Time.now
    samples.times{ yield array }
    results << (Time.now - start)*1000/samples
  end
  results
end

samples = 100
sizes = [10_000, 50_000, 100_000, 250_000, 500_000, 750_000, 1_000_000, 1_250_000, 1_500_000, 2_000_000, 3_000_000, 4_000_000, 5_000_000]

results = {}
results['<<'] = benchmark(samples, sizes) {|array| array << 1}
#results['shift'] = benchmark(samples,sizes) {|array| array.shift}
results['unshift'] = benchmark(samples,sizes) {|array| array.unshift(1)}
#results['shift then unshift'] = benchmark(samples,sizes) do |array|
#  array.shift
#  array.unshift(1)
#end
#results['add'] = benchmark(samples,sizes) {|array| array + [1]}
#results['pop'] = benchmark(samples,sizes) {|array| array.pop}

data = []
for key in results.keys
  data << sizes
  data << results[key]
end

require 'googlecharts'
puts Gchart.line_xy( :theme => :thirty7signals,
                      :title => 'Ruby Array Operation Speed',
                      :data => data,
                      :axis_with_labels => 'x',
                      :legend => results.keys,
                      :encoding => 'text',
                      :max_value => 'false'
                     ).sub!('chds=,', 'chds=a')