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…

Accepted Answer

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

Running time Array#unshift vs Array#shift

Solution

Problem