Блог

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

В node.js (версия 12.16.3), почему избавление от цикла for вокруг функции find в этом примере приводит к резкому увеличению производительности? (5600 мс сокращены до 250 мс)

Проблема не появляется, если я изменяю значение во втором массиве с 1e10 на 1e9 или меньше, или если я изменяю значение в первом массиве с 1 на 1e10 или больше.

 const nSims = 1e8

const arrays = [];
arrays[0] = [1];
arrays[1] = [1e10];

console.time('a')
for (var i = 0; i < nSims; i  ) {
    for (var j = 0; j < 2; j  ) {
        arrays[j].find((value) => value > 0);
    }
}
console.timeEnd('a') // 5600 ms

console.time('b')
for (var i = 0; i < nSims; i  ) {
    arrays[0].find((value) => value > 0);
    arrays[1].find((value) => value > 0);
}
console.timeEnd('b') // 250 ms  

Здесь разработчик версии 8.

«Медленный случай» — это истинная стоимость вызова Array.find с обратным вызовом: для каждого элемента встроенная реализация Array.find выполняет вызов предоставленного обратного вызова. Помимо выполнения этой базовой работы, которую вы просили его выполнить, реализация на самом деле довольно оптимизирована, как Array.find встроенная, так и предоставленная функция обратного вызова.

Быстрый вариант выигрывает от определенных дополнительных оптимизаций в версии 8: если вызов Array.find когда-либо видел массивы только одного типа (включая внутреннее представление, см. Ниже), то в системе сбора отзывов о типах предусмотрена специальная обработка, а оптимизирующий компилятор выдает специальную встроенную версию, которая, в частности, имеет то преимущество, что она также может встроить предоставленный обратный вызов, специализированный для этого типа массивов. Как вы можете видеть здесь, эта оптимизация обеспечивает значительное увеличение скорости, когда она применима.

Причина, по которой [1e9] и [1e10] являются разными типами массивов, заключается в том, что 1e9 это 30-разрядное целое число, поэтому V8 внутренне выбирает представление «small integer» (он же «smi», 31-разрядный signed int) для элементов массива. 1e10 Однако для этого потребовалось бы 34 бита, поэтому V8 выбирает двойное (64-разрядное представление с плавающей запятой) для элементов массива. Итак, если одно и то же вхождение Array.find встречается с обоими [1e9] (или [1] , если уж на то пошло) и [1e10] , оно решает «Я видел здесь более одного типа массива, включение более одного специального случая, вероятно, стоит дороже, чем оно того стоит, давайте использовать общую версию». Вы могли бы сказать, что в данном случае это решение слишком пессимистично, но такова природа эвристики: движкам нужны правила, чтобы решать, что делать, и поскольку они не могут предсказать, что ваш код будет делать в будущем, им просто нужно сделать некоторое предположение — которое может оказаться хорошим предположением или не очень хорошим предположением 🙂

Это не связано с наличием цикла как такового; перебор списка массивов — это всего лишь один из способов заставить одно и то же Array.find столкнуться с несколькими типами массивов. Вы могли бы запустить возврат к общему пути без цикла, используя функцию, которая вызывается с другими входными данными; или у вас мог бы быть цикл (который повторяет что-то еще), все еще оставаясь на быстром пути.

@Anton написал:

Похоже, что метод find имеет некоторые проблемы.

Я бы так не выразился. Движку нелегко оптимизировать Array.find в той же степени, что и написанный вручную цикл for — например, потому, что движок обычно не может встроить пользовательские обратные вызовы во встроенные функции. Как объяснялось выше, V8 знает достаточно хитростей, чтобы иметь возможность выполнять такое встраивание в некоторых ситуациях, но не всегда.

Это далеко не единственный случай, когда написанная от руки замена встроенной функции может обеспечить более высокую производительность; во многих случаях это связано с тем, что встроенные функции являются более общими (т. Е. Поддерживают более странные угловые варианты), чем написанная от руки замена. Также бывает так, что за пределами целевых микробенчмарков довольно редко (хотя, конечно, не невозможно) можно найти случай, когда эти различия действительно имеют значение.

Примечание: Возможно, это неправильный ответ, но это просто очень большой комментарий (мне нужны фрагменты кода для иллюстрации).

Это пример из вопроса (для a и менее секунды для b это занимает более 5 секунд):

 const nSims = 1e8

const arrays = [];
arrays[0] = [1];
arrays[1] = [1e10];

console.time('a')
for (var i = 0; i < nSims; i  ) {
    for (var j = 0; j < 2; j  ) {
        arrays[j].find((value) => value > 0);
    }
}
console.timeEnd('a') // 5600 ms

console.time('b')
for (var i = 0; i < nSims; i  ) {
    arrays[0].find((value) => value > 0);
    arrays[1].find((value) => value > 0);
}
console.timeEnd('b') // 250 ms  

Это произойдет, если мы изменим 1e10 на 1e9 (здесь «magic»):

 const nSims = 1e8

const arrays = [];
arrays[0] = [1];
arrays[1] = [1e9];

console.time('a')
for (var i = 0; i < nSims; i  ) {
    for (var j = 0; j < 2; j  ) {
        arrays[j].find((value) => value > 0);
    }
}
console.timeEnd('a') // 5600 ms

console.time('b')
for (var i = 0; i < nSims; i  ) {
    arrays[0].find((value) => value > 0);
    arrays[1].find((value) => value > 0);
}
console.timeEnd('b') // 250 ms  

Похоже, у этого find метода есть некоторые проблемы. Вот что произойдет, если мы заменим его на for итерацию ( a и b становится близким и занимает менее 1 секунды):

 const nSims = 1e8

const arrays = [];
arrays[0] = [1];
arrays[1] = [1e10];

function find(arr) {
  for (let i = 0; i < arr.length; i  ) {
    if (arr[i] > 0) return arr[i];
  }
}

console.time('a')
for (var i = 0; i < nSims; i  ) {
    for (var j = 0; j < 2; j  ) {
        find(arrays[j]);
    }
}
console.timeEnd('a')

console.time('b')
for (var i = 0; i < nSims; i  ) {
    find(arrays[0]);
    find(arrays[1]);
}
console.timeEnd('b')