Czas pracy Array # unshift vs Array # shift

Question

Oczekiwano, że czas działania Array#shift i Array#unshift będzie równy Θ(n). Powodem jest to, że maszyna musi przechodzić przez każdy element tablicy i przypisywać go do klucza w lewo lub w prawo do niego.

W przypadku Array#unshift, zakładając, że tylko jedna wartość jest przekazywana jako argument i jest wiele elementów tablicy, założyłem, że przypisanie wartości dla array[0] nie ma znaczącego wpływu na czas działania. Innymi słowy, gdy liczba elementów macierzy jest wysoka, a liczba zmiennych przekazywanych do Array#unshift jest niska, oczekiwałem, że Array#shift i Array#unshift będą miały taki sam czas działania.

Podczas wykonywania testów porównawczych w Ruby 2.1.2 te założenia nie są prawdziwe. Czemu?

Kod:

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 

Wynik:

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

W MRI Ruby 2.1.2 unshift ma realloc tablicę i skopiuj go w całości:

   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 najwyraźniej nie zawsze rób coś takiego:

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