Производительность цикла JavaScript - почему уменьшение итератора до 0 быстрее, чем увеличение

Question

В своей книге Даже более быстрые веб-сайты Стив Саундерс пишет, что простой способ улучшить производительность цикла - уменьшить итератор до 0, а не увеличивать его до общей длины ( на самом деле глава написана Николаем Ч. Закасом ). Это изменение может привести к экономии до 50% от первоначального времени выполнения, в зависимости от сложности каждой итерации. Например:

var values = [1,2,3,4,5];
var length = values.length;

for (var i=length; i--;) {
   process(values[i]);
}

Это почти идентично для цикла for, цикла do-while и цикла while.

Мне интересно, с чем это связано? Почему уменьшать итератор намного быстрее? (Мне интересны технические основы, а не тесты, подтверждающие это утверждение.)

---

РЕДАКТИРОВАТЬ: На первый взгляд используемый здесь синтаксис цикла выглядит неправильно. Нет length-1 или i>=0, поэтому давайте уточним (я тоже растерялся).

Вот общий синтаксис цикла:

for ([initial-expression]; [condition]; [final-expression])
   statement

• начальное выражение - var i=length

  Это объявление переменной вычисляется первым.

• состояние - i--

  Это выражение вычисляется перед каждой итерацией цикла. Он будет уменьшать переменную до первого прохождения цикла. Если это выражение оценивается как false, цикл заканчивается. В JavaScript это 0 == false, поэтому, если i в итоге равно 0, оно интерпретируется как false и цикл заканчивается.

• * ** 1 049 1050 * окончательное выражение * ** 1052 одна тысяча пятьдесят-одна *

  Это выражение вычисляется в конце каждой итерации цикла (перед следующей оценкой условие ). Это не нужно здесь и пусто. Все три выражения являются необязательными в цикле for.

Синтаксис цикла for не является частью вопроса, но, поскольку он немного необычен, я думаю, что это интересно прояснить. И, возможно, одна из причин, почему он быстрее, заключается в том, что он использует меньше выражений («трюк» 0 == false).

Answer 1

Я не уверен насчет Javascript, и в современных компиляторах это, вероятно, не имеет значения, но в «старые времена» этот код:

for (i = 0; i < n; i++){
  .. body..
}

сгенерирует

move register, 0
L1:
compare register, n
jump-if-greater-or-equal L2
-- body ..
increment register
jump L1
L2:

, тогда как код обратного счета

for (i = n; --i>=0;){
  .. body ..
}

сгенерирует

move register, n
L1:
decrement-and-jump-if-negative register, L2
.. body ..
jump L1
L2:

, поэтому внутри цикла он выполняет только две дополнительные инструкции вместо четырех.

Answer 2

Я считаю, что причина в том, что вы сравниваете конечную точку цикла с 0, что быстрее, чем повторное сравнение < length (или другой переменной JS).

Это связано с тем, что порядковые операторы <, <=, >, >= являются полиморфными, поэтому эти операторы требуют проверки типов как с левой, так и с правой стороны оператора, чтобы определить, какое поведение сравнения следует использовать.

Здесь есть несколько очень хороших тестов:

Какой самый быстрый способ кодирования цикла в JavaScript

Answer 3

Легко сказать, что итерация может иметь меньше инструкций. Давайте просто сравним эти два:

for (var i=0; i<length; i++) {
}

for (var i=length; i--;) {
}

Когда вы учитываете каждый доступ к переменной и каждый оператор как одну инструкцию, предыдущий цикл for использует 5 инструкций (чтение i, чтение length, оценка i<length, проверка (i<length) == true, приращение i ) в то время как последний использует только 3 инструкции (чтение i, проверка i == true, уменьшение i). Это соотношение 5: 3.

Answer 4

Как насчет использования обратного цикла while:

var values = [1,2,3,4,5]; 
var i = values.length; 

/* i is 1st evaluated and then decremented, when i is 1 the code inside the loop 
   is then processed for the last time with i = 0. */
while(i--)
{
   //1st time in here i is (length - 1) so it's ok!
   process(values[i]);
}

IMO, по крайней мере, этот код более читабелен, чем for(i=length; i--;)

Answer 5

Я также изучал скорость цикла, и мне было интересно найти этот тезис о том, что уменьшение - это быстрее, чем увеличение.Тем не менее, мне еще предстоит найти тест, который демонстрирует это.На jsperf есть много тестов цикла.Вот тот, который тестирует убывание:

http://jsperf.com/array-length-vs-cached/6

Кэширование длины вашего массива, однако (также рекомендуется книга Стива Соудерса), кажется, является выигрышной оптимизацией.

Answer 6

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

a) дополнительный поиск каждого свойства длины в каждом цикле

//example:
    for(var i = 0; src.length > i; i++)
//vs
    for(var i = 0, len = src.length; len > i; i++)

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

b) дополнительное присвоение переменной.

меньший коэффициент усиления обратного контура заключается в том, что для него требуется только одно присвоение переменной вместо 2

//example:
    var i = src.length; while(i--)

Answer 7

for увеличение или уменьшение в 2017 году

В современных движках JS увеличение в циклах for обычно происходит быстрее, чем уменьшение (на основе личных тестов Benchmark.js), также более обычное:

for (let i = 0; i < array.length; i++) { ... }

Это зависит от платформы и длины массива, если length = array.length имеет какой-либо значительный положительный эффект, но обычно это не так:

for (let i = 0, length = array.length; i < length; i++) { ... }

Последние версии V8 (Chrome, Node) имеют оптимизациидля array.length, поэтому length = array.length может быть эффективно опущен в любом случае.

Answer 8

Существует еще более «производительная» версия этого. Поскольку каждый аргумент в циклах for является необязательным, вы можете пропустить даже первый.

var array = [...];
var i = array.length;

for(;i--;) {
    do_teh_magic();
}

При этом вы пропускаете даже проверку на [initial-expression]. Таким образом, у вас остается всего одна операция.

Answer 9

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

Answer 10

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

for(var i = 0; i < array.length; i++) {
 ...
}

По сути, вы обращаетесь к свойству длины массива N (количество элементов) раз. Принимая во внимание, что когда вы уменьшаете, вы получаете к нему доступ только один раз. Это может быть причиной.

Но вы также можете написать инкрементный цикл следующим образом:

for(var i = 0, len = array.length; i < len; i++) {
 ...
}