Что быстрее в Ruby, `arr + = [x]` или `arr << x`

Ответ 1

Я считаю, что это не так, как MRI выделяет массивы (весь этот ответ очень специфичен для MRI). Ruby очень тяжело работает с массивами: небольшие массивы (< = 3 элемента) упакованы прямо в структуру RARRAY, например.

Другое дело, что если вы берете массив и начинаете добавлять значения по одному, рубин не увеличивает буфер по одному элементу за раз, он делает это в кусках: это более эффективно, за счет небольшой объем памяти.

Одним из инструментов для просмотра всего этого является использование memsize_of:

ObjectSpace.memspace_of([]) #=> 40 (on 64 bit platforms
ObjectSpace.memspace_of([1,2]) #=> 40 (on 64 bit platforms
ObjectSpace.memsize_of([1,2,3,4]) #=> 72
ObjectSpace.memsize_of([]<<1<<2<<3<<4) #=> 200

В первых двух случаях массив упаковывается в структуру RARRAY, поэтому размер памяти является лишь базовым размером любого объекта (40 байтов). В третьем случае рубину пришлось выделить массив для 4 значений (по 8 байт каждый), поэтому размер равен 40 + 32 = 72. В последнем случае рубин увеличил хранилище до 20 элементов

Это относится ко второму случаю. Блок внутри эталона имеет только что созданный массив, который все еще имеет некоторую резервную емкость:

 ObjectSpace.memsize_of((0..20).to_a) #=> 336, enough for nearly 40 elements.

<< может просто записать свой объект в соответствующий слот, тогда как += должен выделить новый массив (как объект, так и его буфер) и скопировать все данные.

Если я делаю

a = [1,2,3,4,5]
b  = a.dup
ObjectSpace.memsize_of(b) #=> 40

Здесь b делится своим буфером с a, поэтому сообщается, что без памяти больше основного размера объекта. В точке, где записывается b, рубину придется копировать данные (копировать при записи): в первом тесте BOTH += и << на самом деле выделяется новый буфер достаточный размер и копирование всех данных.

Здесь я получаю handwavy: это полностью объясняет вещи, если << и += выполняются одинаково, но это не то, что происходит. Мое чтение вещей - это то, что + проще. Все, что он должен делать, независимо от того, что выделяет буфер, и memcpy некоторые данные из 2-х мест - это быстро.

<<, с другой стороны, мутирует массив, поэтому он оплачивает накладные расходы на запись: он выполняет дополнительную работу по сравнению с +=. Например, Ruby должен отслеживать, кто делится буферами, чтобы сбор мусора исходного массива был возможен, когда никто больше не делится им.

Тест, который помогает мне убедить меня в правильности этой интерпретации, заключается в следующем:

require 'benchmark/ips'
b = (0..20).to_a.dup
y = 21
Benchmark.ips do |x|
  x.report('<<')   { a = b.dup; a << y }
  x.report('+=')   { a = b.dup; a += [y] }

  x.report('<<2')   { a = b.dup; a << y; a<< y}
  x.report('+=2')   { a = b.dup; a += [y]; a += [y] }
end

Это в основном тот же показатель, что и оригинал, но теперь добавляет 2 элемента. Для << копия накладных расходов на запись будет произведена только в первый раз. Я получаю результаты

              <<      1.325M (± 7.6%) i/s -      6.639M
              +=      1.742M (± 9.5%) i/s -      8.677M
             <<2      1.230M (±10.3%) i/s -      6.079M
             +=2      1.140M (±10.8%) i/s -      5.656M

Таким образом, добавление к массиву возвращается сверху, если вы делаете это дважды.

Ответ 2

На мой взгляд, для упрощения сравнения различных операторов мы должны удалить ненужный код и просто провести тест.

require 'benchmark/ips'

y = 10
Benchmark.ips do |x|
    x.report('<<')   { a = [0,1,2,3,4,5,6,7,8,9]; a << y }
    x.report('+=')   { a = [0,1,2,3,4,5,6,7,8,9]; a += [y] }
    x.report('push') { a = [0,1,2,3,4,5,6,7,8,9]; a.push(y) }
    x.report('[]=')  { a = [0,1,2,3,4,5,6,7,8,9]; a[a.size]=y }
    x.compare!
end

Результат вышеуказанного кода соответствует второму фрагменту кода, заданному в вопросе.

Calculating -------------------------------------
                  <<   101.735k i/100ms
                  +=   104.804k i/100ms
                push    92.863k i/100ms
                 []=    99.604k i/100ms
-------------------------------------------------
                  <<      2.134M (± 3.3%) i/s -     10.682M
                  +=      1.786M (±13.2%) i/s -      8.804M
                push      1.930M (±16.1%) i/s -      9.472M
                 []=      1.948M (± 7.9%) i/s -      9.761M

Comparison:
                  <<:  2134005.4 i/s
                 []=:  1948256.8 i/s - 1.10x slower
                push:  1930165.3 i/s - 1.11x slower
                  +=:  1785808.5 i/s - 1.19x slower

[Finished in 28.3s]

Почему << быстрее, чем +=?

Array#<< является самым быстрым из четырех способов добавления элемента в массив, потому что он делает именно это - добавляет элемент в массив. Наоборот, Array#+ добавляет элемент, но возвращает новую копию массива - создание новой копии массива делает ее самой медленной. (В документации можно использовать опцию toogle code для понимания дополнительной работы, выполняемой некоторыми методами)

Маркировка скамьи с dup

Если мы используем ниже код для маркировки стендов,

require 'benchmark/ips'

y = 10
Benchmark.ips do |x|
    x.report('<<')   { a = [0,1,2,3,4,5,6,7,8,9].dup; a << y }
    x.report('+=')   { a = [0,1,2,3,4,5,6,7,8,9].dup; a += [y] }
    x.report('push') { a = [0,1,2,3,4,5,6,7,8,9].dup; a.push(y) }
    x.report('[]=')  { a = [0,1,2,3,4,5,6,7,8,9].dup; a[a.size]=y }
    x.compare!
end

Ниже мы видим результаты:

Calculating -------------------------------------
                  <<    65.225k i/100ms
                  +=    76.106k i/100ms
                push    64.864k i/100ms
                 []=    63.582k i/100ms
-------------------------------------------------
                  <<      1.221M (±14.3%) i/s -      6.001M
                  +=      1.291M (±13.1%) i/s -      6.393M
                push      1.164M (±14.1%) i/s -      5.773M
                 []=      1.168M (±14.5%) i/s -      5.722M

Comparison:
                  +=:  1290970.6 i/s
                  <<:  1221029.0 i/s - 1.06x slower
                 []=:  1168219.3 i/s - 1.11x slower
                push:  1163965.9 i/s - 1.11x slower

[Finished in 28.3s]

Если мы внимательно посмотрим между двумя результатами, мы увидим только одно различие. Запись += стала первой, тогда как порядок остальных методов остался прежним с исходным результатом.

Почему результаты срабатывают при использовании dup?

Это моя дикая догадка, я предполагаю, что интерпретатор Ruby оптимизировал код и не создавал новый массив как часть +=, поскольку он знал, что он работает с только что созданной копией массива на dup