Array # unshift vs Array # shift runtime

Question

I expected the runtime of Array#shift and Array#unshift to be Θ(n) . The reason is that the machine needs to scroll through each element of the array and assign it a key to the left or right.

In the case of Array#unshift , assuming that only one value is passed as an argument, and that there are many elements of the array, I assumed that assigning a value to array[0] does not have a significant impact on the running time. In other words, when the number of array elements is large and the number of variables passed to Array#unshift is small, I expected Array#shift and Array#unshift to have the same run time.

When running tests on Ruby 2.1.2, these assumptions are invalid. 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 redistributes the array and completely copies it:

  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 , obviously, does not always do something like this:

  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; }