Running time Array#unshift vs Array#shift

Question

I expected the running time of Array#shift and Array#unshift both to be Θ(n). Reason being that the machine needs to loop through each array member and assign it to the key left or right to it.

In the case of Array#unshift, assuming that only one value is passed in as an argument and that there are lots of array members, I assumed that the value assignment for array[0] is not having a significant impact on the running time. In other words, when the number of array members is high and the number of variables passed into Array#unshift is low, I expected Array#shift and Array#unshift to have the same running time.

When running benchmarks on Ruby 2.1.2, these assumptions do not hold true. Why?

Code:

require 'benchmark'

GC.disable    

number_of_elements = 25_600_000

a1 =[]
a2 = []
a3 = []
a4 = []
q1 = Queue.new
q2 = Queue.new

puts number_of_elements

number_of_elements.times do
  q1.enq(true)
  q2.enq(true)
  a1 << true
  a2 << true
  a3 << true
  a4 << true
end

number_of_operations = 1

Benchmark.bm do |bm|
  puts "Queue#enq('test')"
  bm.report do    
    number_of_operations.times { q1.enq('test') }
  end

  puts "Queue#deq"
  bm.report do    
    number_of_operations.times { q2.deq }
  end

  puts "Array#shift"
  bm.report do
    number_of_operations.times { a1.shift }
  end 

  puts "Array#unshift"
  bm.report do
    number_of_operations.times { a2.unshift('test') }    
  end 

  puts "Array#pop"
  bm.report do
    number_of_operations.times { a3.pop }
  end

  puts "Array#<<"
  bm.report do
    number_of_operations.times { a4 << 'test' }
  end      
end

Result:

25600000
       user     system      total        real
Queue#enq('test')
   0.000000   0.000000   0.000000 (  0.000006)
Queue#deq
   0.010000   0.020000   0.030000 (  0.029928)
Array#shift
   0.010000   0.020000   0.030000 (  0.032203)
Array#unshift
   0.080000   0.060000   0.140000 (  0.143272)
Array#pop
   0.000000   0.000000   0.000000 (  0.000004)
Array#<<
   0.000000   0.000000   0.000000 (  0.000007)

Answer 1

In MRI Ruby 2.1.2, unshift does realloc the array and copy it entirely:

              static VALUE
rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary)
{
    long len = RARRAY_LEN(ary);

    [...]

    ary_ensure_room_for_unshift(ary, argc);
    ary_memcpy(ary, 0, argc, argv);
    ARY_SET_LEN(ary, len + argc);
    return ary;
}

shift apparently does not always do something like that:

              static VALUE
rb_ary_shift_m(int argc, VALUE *argv, VALUE ary)
{
    VALUE result;
    long n;

    [...]

    rb_ary_modify_check(ary);
    result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST);
    n = RARRAY_LEN(result);
    if (ARY_SHARED_P(ary)) {
        if (ARY_SHARED_OCCUPIED(ARY_SHARED(ary))) {
            ary_mem_clear(ary, 0, n);
        }
        ARY_INCREASE_PTR(ary, n);
    }
    else {
        RARRAY_PTR_USE(ary, ptr, {
            MEMMOVE(ptr, ptr + n, VALUE, RARRAY_LEN(ary)-n);
        }); /* WB: no new reference */
    }
    ARY_INCREASE_LEN(ary, -n);

    return result;
}