Почему #map более эффективен, чем #each?

Question

Когда у тебя есть только молоток, все выглядит как гвоздь. Так что можно сказать о методе Array#each в Ruby, прежде чем открыть для себя полезность, элегантность и удовольствие c от Array#map и Array#select и другие итерируемые методы. Что мне любопытно, так это:

Почему при использовании более точного итерируемого метода наблюдается реальное увеличение производительности? Это правда в целом?

Например, в

require 'benchmark'

array = (1..100000).to_a

puts Benchmark.measure {
  100.times do
    array.map { |el| el.even? }
  end
}

puts Benchmark.measure {
  100.times do
    new_array = []
    array.each do |el| 
      new_array << el.even? 
    end
  end
}

# ruby bench.rb
# 0.450598   0.015524   0.466122 (  0.466802)
# 0.496796   0.018525   0.515321 (  0.516196)

Benchmark всегда показана временная разница в производительности в пользу Array#map. В следующем коде:

puts Benchmark.measure {
  100.times do
    array.select { |el| el.even? }
  end
}

puts Benchmark.measure {
  100.times do
    new_array = []
    array.each do |el| 
      if el.even? 
         new_array << el
      end
    end
  end
}

# ruby bench.rb
# 0.405254   0.007965   0.413219 (  0.413733)
# 0.471416   0.008875   0.480291 (  0.481079)

Array#select каждый раз разбивает джерри Array#each.

Так почему же эти более точные методы дают заметно лучшую производительность? И это общая аксиома в Ruby и / или во всех языках?

Answer 1

В обоих ваших примерах второй фрагмент кода выделяет в 100 раз больше памяти, чем первый фрагмент кода. Он также выполняет приблизительно log_1.5 (100) изменения размера массива (при условии стандартной реализации учебника динамического массива c с коэффициентом роста 1,5). Изменение размера массива обходится дорого (выделение нового фрагмента памяти, затем O (n) копирование всех элементов в новый фрагмент памяти). В более общем смысле, сборщики мусора ненавидят мутацию , они гораздо эффективнее собирают множество мелких недолговечных объектов, чем поддерживают несколько крупных долгоживущих объектов.

Другими словами, в В первом примере вы измеряете Array#map и Array#select соответственно, тогда как во втором примере вы измеряете не только Array#each, но также Array#<<, а также изменение размера массива и выделение памяти. По результатам бенчмаркинга невозможно определить, какой из них вносит свой вклад. Как однажды сказал Зед Шоу: «Если вы хотите измерить что-то, не измеряйте другое дерьмо» .

Но даже если вы исправите эту ошибку в своем тесте, вообще говоря, больше специализированные операции имеют больше информации, чем обычные, поэтому более общие операции обычно не могут быть быстрее специализированных.

В вашем конкретном примере c это может быть что-то очень простое, например, вы использование реализации Ruby, которая не очень хороша для оптимизации кода Ruby (например, YARV, и, в отличие от, например, Truffle Ruby), в то же время оптимизированная собственная реализация Array#map и Array#select (опять же Возьмем в качестве примера YARV, который имеет C реализации для обоих из них и, как правило, не способен очень хорошо оптимизировать код Ruby).

И, наконец, написать правильные микробенчмарки сложно. Действительно, очень, очень сложно. Я рекомендую прочесть и понять всю эту дискуссионную ветку mechanical-sympathy Список рассылки: JMH vs Caliper: справочная тема . Хотя речь идет конкретно о Java бенчмаркинге (на самом деле о JVM бенчмаркинге), многие из аргументов применимы к любому современному высокопроизводительному движку OO, например Rubinius, Truffle Ruby и др. c. и в меньшей степени также в YARV. Обратите внимание, что большая часть обсуждения посвящена написанию микробенчмарков harnesses , а не написанию микробенчмарок как таковых, то есть речь идет о написании каркасов, которые позволяют разработчикам писать правильные микробенчмарки без необходимости знать об этом материале но, к сожалению, даже с лучшими жетонами микробенчмарков (а Ruby Benchmark на самом деле не очень хороший), вам все равно нужно иметь очень глубокое понимание современных компиляторов, сборщиков мусора, механизмов исполнения, процессоров, аппаратные архитектуры, но также и статистика.

Вот хороший пример неудачного теста, который может быть неочевиден для неподготовленного автора тестов: Почему печать «B» значительно медленнее, чем печать «#»? .

Answer 2

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

Давайте напишем программу, которая выполняет ту же задачу (итерация по массиву 100 раз. Вот и все.) без сохранения какого-либо результата (потому что я не уверен, какого рода желаемого результата)

Вот фрагмент кода для bench.rb file

require 'benchmark'
array = (1..100000).to_a
puts Benchmark.measure {
  100.times do
    array.map { |el| el.even? }
  end
}

puts Benchmark.measure {
  100.times do
    array.each { |el| el.even? }
  end
}

puts Benchmark.measure {
  100.times do
    array.select { |el| el.even? }
  end
}

Я выполнил этот код 3 раза, и результаты следующим образом:

Output: 

Attempt 1:
0.548562   0.021844   0.570406 (  0.571088)
0.457079   0.000345   0.457424 (  0.457774)
0.516487   0.010758   0.527245 (  0.527843)

Attempt 2:
0.544863   0.021756   0.566619 (  0.568487)
0.458062   0.000514   0.458576 (  0.459249)
0.508665   0.010847   0.519512 (  0.520401)

Attempt 3:
0.583084   0.022554   0.605638 (  0.606023)
0.509447   0.000665   0.510112 (  0.511088)
0.548483   0.012212   0.560695 (  0.561534)

Я могу видеть Array#each в качестве явного победителя на основе письменного примера. Выходные данные могут варьироваться в зависимости от ваших требований, но основное правило должно быть таким же, чтобы алгоритмы возвращали тот же желаемый выходной результат.

Answer 3

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