Почему <= медленнее, чем <с использованием этого фрагмента кода в V8?

Я читаю слайды. Преодолевая Javascript Speed Limit с V8, и есть пример, например, код ниже. Я не могу понять, почему <= медленнее, чем < в этом случае, может кто-нибудь объяснить это? Любые комментарии приветствуются.

Медленный:

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
}

(Подсказка: простые числа - это массив длины prime_count)

Быстрее:

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i < this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
}

[Подробнее] улучшение скорости является значительным, в моем локальном тестировании среды результаты следующие:

V8 version 7.3.0 (candidate)

Медленный:

 time d8 prime.js
 287107
 12.71 user 
 0.05 system 
 0:12.84 elapsed

Быстрее:

time d8 prime.js
287107
1.82 user 
0.01 system 
0:01.84 elapsed

Ответ 1

Я работаю над V8 в Google и хотел бы дать дополнительную информацию поверх существующих ответов и комментариев.

Для справки, здесь полный пример кода из слайдов:

var iterations = 25000;

function Primes() {
  this.prime_count = 0;
  this.primes = new Array(iterations);
  this.getPrimeCount = function() { return this.prime_count; }
  this.getPrime = function(i) { return this.primes[i]; }
  this.addPrime = function(i) {
    this.primes[this.prime_count++] = i;
  }
  this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
      if ((candidate % this.primes[i]) == 0) return true;
    }
    return false;
  }
};

function main() {
  var p = new Primes();
  var c = 1;
  while (p.getPrimeCount() < iterations) {
    if (!p.isPrimeDivisible(c)) {
      p.addPrime(c);
    }
    c++;
  }
  console.log(p.getPrime(p.getPrimeCount() - 1));
}

main();

Прежде всего, разница в производительности не имеет ничего общего с операторами < и <=. Поэтому, пожалуйста, не прыгайте через обручи, чтобы избежать <= в вашем коде, потому что вы читаете "Переполнение стека", что он медленный - это не так!

Во-вторых, люди указали, что массив "дырявый". Это было неясно из фрагмента кода в сообщении OP, но ясно, когда вы смотрите на код, который инициализирует this.primes:

this.primes = new Array(iterations);

Это приводит к массиву с HOLEY элементов HOLEY в V8, даже если массив заканчивается полностью заполненным/упакованным/смежным. В общем случае операции с дырчатыми массивами медленнее операций на упакованных массивах, но в этом случае разница незначительна: она составляет 1 дополнительную this.primes[i] (small integer) (чтобы защищать от отверстий) каждый раз, когда мы this.primes[i] в цикле внутри isPrimeDivisible. Ничего страшного!

TL; DR . Массив, являющийся HOLEY, не является проблемой здесь.

Другие отметили, что код читается за пределы. Обычно рекомендуется избегать чтения за пределами массивов, и в этом случае он действительно избежал бы значительного снижения производительности. Но почему же? V8 может обрабатывать некоторые из этих сценариев без привязки, что оказывает незначительное влияние на производительность. Что тогда такого особенного в этом конкретном случае?

this.primes[i] оценки читают результаты в этом. this.primes[i] не undefined в этой строке:

if ((candidate % this.primes[i]) == 0) return true;

И это подводит нас к реальной проблеме: теперь оператор % используется с нецелыми операндами!

integer % someOtherInteger можно вычислить очень эффективно; Двигатели JavaScript могут производить высокооптимизированный машинный код для этого случая.
integer % undefined с другой стороны, является способом менее эффективного Float64Mod, так как undefined представляется как double.

Фрагмент кода действительно можно улучшить, изменив <= в < на этой строке:

for (var i = 1; i <= this.prime_count; ++i) {

... не потому, что <= является каким-то превосходным оператором, чем <, но только потому, что это позволяет избежать превышений в этом конкретном случае.

Ответ 2

В других ответах и комментариях упоминается, что разница между двумя циклами состоит в том, что первая выполняет еще одну итерацию, чем вторая. Это верно, но в массиве, который растет до 25 000 элементов, одна итерация более или менее будет лишь незначительной разницей. Если предположить, что средняя длина по мере роста составляет 12 500, то разница, которую мы можем ожидать, должна составлять около 1/12 500 или только 0,008%.

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

this.primes - это непрерывный массив (каждый элемент имеет значение), а элементы - все числа.

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

Одним условием было бы, если некоторые элементы массива отсутствуют. Например:

let array = [];
a[0] = 10;
a[2] = 20;

Теперь какова ценность a[1]? Это не имеет значения. (Нельзя даже сказать, что оно имеет значение undefined - элемент массива, содержащий undefined значение, отличается от элемента массива, который полностью отсутствует.)

Невозможно представить это только с числами, поэтому механизм JavaScript вынужден использовать менее оптимизированный формат. Если a[1] содержится числовое значение, подобное двум другим элементам, массив может быть оптимизирован только в массив чисел.

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

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

this.primes[i] оценивается как undefined потому что i находится за концом массива.
candidate % undefined (для любого значения candidate) оценивает NaN.
NaN == 0 оценивается как false.
Следовательно, return true не выполняется.

Так что, как будто лишняя итерация никогда не происходила - она не влияет на остальную логику. Код дает тот же результат, что и без дополнительной итерации.

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

Второй цикл с < читает только те элементы, которые существуют в массиве, поэтому он позволяет оптимизировать массив и код.

Проблема описана на страницах 90-91 разговора, с соответствующим обсуждением на страницах до и после этого.

Мне довелось присутствовать на этой презентации Google I/O и поговорили с докладчиком (одним из авторов V8). Я использовал технику в своем собственном коде, который включал прочтение конца конца массива в качестве ошибочной (в ретроспективе) попытки оптимизировать одну конкретную ситуацию. Он подтвердил, что если вы попытаетесь даже прочитать конец массива, это предотвратит использование простого оптимизированного формата.

Если то, что сказал автор V8, по-прежнему верен, тогда чтение за концом массива не позволит ему оптимизироваться, и ему придется вернуться к более медленному формату.

Теперь возможно, что V8 был улучшен тем временем, чтобы эффективно обрабатывать этот случай, или что другие механизмы JavaScript обрабатывают его по-разному. Я не знаю, так или иначе, но эта деоптимизация - это то, о чем говорила презентация.

Ответ 3

TL; DR Более медленный цикл связан с обращением к массиву "вне пределов", который либо вынуждает движок перекомпилировать функцию с меньшими затратами, либо даже без оптимизации, ИЛИ не компилировать функцию с какой-либо из этих оптимизаций для начала ( если (JIT-) компилятор обнаружил/подозревал это условие перед первой версией компиляции 'version'), читайте ниже, почему;

Кто-то просто должен сказать это (совершенно удивленный, что никто уже не сделал):
Раньше было время, когда фрагмент OP был бы фактическим примером в книге для начинающих программистов, предназначенной для того, чтобы обрисовать/подчеркнуть, что "массивы" в javascript индексируются начиная с 0, а не с 1, и поэтому должны использоваться в качестве примера. распространенной "ошибки новичков" (разве вам не нравится, как я избегал фразы "ошибка программирования" ;)): доступ за пределы массива.

Пример 1:
Dense Array (будучи непрерывным (означает отсутствие пробелов между индексами) И фактически элементом в каждом индексе) из 5 элементов с использованием индексации на основе 0 (всегда в ES262).

var arr_five_char=['a', 'b', 'c', 'd', 'e']; // arr_five_char.length === 5
//  indexes are:    0 ,  1 ,  2 ,  3 ,  4    // there is NO index number 5

Таким образом, мы на самом деле не говорим о разнице в производительности между < vs <= (или "одной дополнительной итерацией"), но мы говорим:
"Почему правильный фрагмент (b) работает быстрее, чем ошибочный фрагмент (а)"?

Ответ двоякий (хотя с точки зрения разработчика языка ES262 оба являются формами оптимизации):

Представление данных: как представить/сохранить массив в памяти (объект, hashmap, "реальный" числовой массив и т.д.)
Функциональный машинный код: как скомпилировать код, который обращается/обрабатывает (читает/изменяет) эти "массивы"

Пункт 1 достаточно (и правильно ИМХО) объясняется принятым ответом, но это только тратит 2 слова ("код") на пункт 2: компиляция.

Точнее: JIT -Compilation и, что еще важнее, JIT- RE -Compilation!

Спецификация языка - это, по сути, просто описание набора алгоритмов ("шаги, которые необходимо выполнить для достижения определенного конечного результата"). Что, как выясняется, является очень красивым способом описания языка. И это оставляет фактический метод, который использует движок для достижения определенных результатов, открытым для разработчиков, предоставляя широкие возможности для поиска более эффективных способов получения определенных результатов. Механизм, соответствующий спецификации, должен давать результаты, соответствующие спецификации, для любого определенного ввода.

Теперь, когда javascript-код/библиотеки/использование увеличиваются и запоминается, сколько ресурсов (времени/памяти/и т.д.) Использует "настоящий" компилятор, становится ясно, что мы не можем заставить пользователей, посещающих веб-страницу, ждать так долго (и требовать их). иметь столько доступных ресурсов).

Представьте себе следующую простую функцию:

function sum(arr){
  var r=0, i=0;
  for(;i<arr.length;) r+=arr[i++];
  return r;
}

Совершенно ясно, верно? Не требует никаких дополнительных разъяснений, верно? Тип возвращаемого значения - Number, верно?
Ну.. нет, нет & нет... Это зависит от того, какой аргумент вы передаете параметру именованной функции arr...

sum('abcde');   // String('0abcde')
sum([1,2,3]);   // Number(6)
sum([1,,3]);    // Number(NaN)
sum(['1',,3]);  // String('01undefined3')
sum([1,,'3']);  // String('NaN3')
sum([1,2,{valueOf:function(){return this.val}, val:6}]);  // Number(9)
var val=5; sum([1,2,{valueOf:function(){return val}}]);   // Number(8)

Видишь проблему? Тогда подумайте, что это всего лишь ограбление огромных возможных перестановок... Мы даже не знаем, какой тип ТИП возвращает функцию, пока мы не закончим...

Теперь представьте, что этот же код function- фактически используется для разных типов или даже вариантов ввода, как в буквальном смысле (в исходном коде), так и в динамически создаваемых в программе "массивах".

Таким образом, если вам нужно скомпилировать функцию sum JUST ONCE, то единственный способ, который всегда возвращает специфицированный результат для любого и всех типов ввода, тогда, очевидно, что только выполнение ВСЕХ предписанных спецификаций основных AND подэтапов может гарантировать соответствие спецификации результаты (как безымянный браузер pre-y2k). Никаких оптимизаций (потому что никаких предположений) и мертвого медленно интерпретируемого скриптового языка не осталось.

JIT -Compilation (JIT как в Just In Time) является популярным в настоящее время решением.

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

Все это требует времени!

Все браузеры работают на своих движках, для каждой подверсии вы увидите, что вещи улучшаются и регрессируют. Строки были в какой-то момент в истории действительно неизменяемыми строками (следовательно, array.join был быстрее, чем конкатенация строк), теперь мы используем веревки (или аналогичные), которые снимают проблему. Оба возвращают результаты, соответствующие спецификации, и это то, что имеет значение!

Короче говоря: просто потому, что семантика языка javascript часто получает поддержку (как, например, с этой тихой ошибкой в примере с OP), не означает, что "глупые" ошибки увеличивают наши шансы того, что компилятор выплевывает быстрый машинный код. Предполагается, что мы написали "обычно" правильные инструкции: текущая мантра, которую мы "пользователи" (языка программирования) должны иметь: помочь компилятору, описать то, что мы хотим, одобрить общие идиомы (взять советы из asm.js для базового понимания какие браузеры могут попытаться оптимизировать и почему).

Из-за этого важно говорить о производительности, но ТАКЖЕ минное поле (и из-за указанного минного поля я действительно хочу закончить указанием (и цитированием) некоторого соответствующего материала:

Доступ к несуществующим свойствам объекта и элементам массива вне границ возвращает undefined значение вместо вызова исключения. Эти динамические функции делают программирование на JavaScript удобным, но они также затрудняют компиляцию JavaScript в эффективный машинный код.

...

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

Источник:
"JITProf: определение JIT- недружественного кода JavaScript"
Издание Беркли, 2014, Лян Гонг, Майкл Прадель, Кушик Сен.
http://software-lab.org/publications/jitprof_tr_aug3_2014.pdf

ASM.JS (также не нравится выход за пределы массива):

Опережающая сборка

Поскольку asm.js является строгим подмножеством JavaScript, эта спецификация определяет только логику проверки - семантика исполнения - это просто JavaScript. Тем не менее, проверенный asm.js поддается предварительной компиляции (AOT). Кроме того, код, сгенерированный компилятором AOT, может быть довольно эффективным, показывая:

распакованные представления целых чисел и чисел с плавающей точкой;

отсутствие проверок типов во время выполнения;

отсутствие сбора мусора; а также

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

http://asmjs.org/spec/latest/

и, наконец, https://blogs.windows.com/msedgedev/2015/05/07/bringing-asm-js-to-chakra-microsoft-edge/
Там, где есть небольшой подраздел об улучшениях внутренней производительности двигателя при удалении проверки границ (в то время как простое снятие проверки границ вне цикла уже показало улучшение на 40%).

РЕДАКТИРОВАТЬ:
обратите внимание, что несколько источников говорят о разных уровнях JIT- перекомпиляции вплоть до интерпретации.

Теоретический пример, основанный на приведенной выше информации относительно фрагмента OP:

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

Следовательно время тогда было:
Первый запуск (не удалось в конце) + выполнение всей работы заново с использованием более медленного машинного кода для каждой итерации + перекомпиляция и т.д., Очевидно, занимает в> 2 раза больше в этом теоретическом примере!

РЕДАКТИРОВАТЬ 2: (отказ от ответственности: гипотеза, основанная на фактах ниже)
Чем больше я думаю об этом, тем больше я думаю, что этот ответ мог бы на самом деле объяснить более доминирующую причину этого "штрафа" для ошибочного фрагмента a (или бонуса производительности за фрагмент b, в зависимости от того, как вы о нем думаете), именно поэтому Я назвал это (фрагмент кода) ошибкой программирования:

Довольно заманчиво предположить, что this.primes является чисто числовым "плотным массивом", который

Жестко запрограммированный литерал в исходном коде (известный отличный кандидат на превращение в "настоящий" массив, поскольку все уже известно компилятору до компиляции) ИЛИ
скорее всего, генерируется с использованием числовой функции, заполняющей предварительно заданный размер (new Array(/*size value*/)) в возрастающем последовательном порядке (еще один давно известный кандидат, чтобы стать "реальным" массивом).

Мы также знаем, что длина массива primes кэшируется как prime_count ! (с указанием намерения и фиксированного размера).

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

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

Как я пытался прояснить с помощью моего примера функции sum, передаваемый аргумент (аргументы) сильно влияет на то, что действительно должно произойти, и на то, как этот конкретный код компилируется в машинный код. Передача String в функцию sum не должна изменять строку, а менять способ ее компиляции JIT- Compiled! Передача массива для sum должна компилировать другую (возможно, даже дополнительную для этого типа или "форму", как они это называют, объекта, который был передан) версию машинного кода.

Как кажется, немного бонку конвертировать массив primes Typed_Array -like на лету во что-то, в то время как компилятор знает, что эта функция даже не собирается его модифицировать!

Под эти предположения, что оставляет 2 варианта:

Скомпилируйте как обработчик чисел, не допуская выходов за пределы, в конце столкнитесь с проблемой выхода за пределы, перекомпилируйте и переделайте работу (как описано в теоретическом примере в редактировании 1 выше)
Компилятор уже обнаружил (или подозревал?) Вне пределов доступа, и функция была JIT- скомпилирована так, как если переданный аргумент был разреженным объектом, что приводило к более медленному машинному коду (так как было бы больше проверок/преобразований/). принуждения и т.д.). Другими словами: функция никогда не подходила для определенных оптимизаций, она была скомпилирована так, как если бы она получила аргумент "разреженный массив" (-like).

Теперь мне действительно интересно, что из этих 2 это!

Ответ 4

Чтобы добавить к нему некоторую научность, здесь jsperf

https://jsperf.com/ints-values-in-out-of-array-bounds

Он проверяет контрольный регистр массива, заполненного ints и looping, делая модульную арифметику, оставаясь в пределах границ. Он имеет 5 тестовых случаев:

1. Замыкание за пределы
2. Holey массивы
3. Модульная арифметика против NaN
4. Полностью неопределенные значения
5. Используя new Array()

Это показывает, что первые 4 случая действительно плохи для производительности. Замыкание за пределы немного лучше, чем у остальных 3, но все 4 примерно на 98% медленнее, чем в лучшем случае.
new Array() почти так же хорош, как и исходный массив, всего на несколько процентов медленнее.

Ответ 5

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

PS: Я новичок в V8. Не знаю слишком много!

Ответ 6

Существует цикл for, и если вы зацикливаете я <= this.prime_count, вы делаете одну дополнительную итерацию по я <this.prime_count, поскольку она только циклы, пока я меньше, чем prime_count, а не до тех пор, пока я не станет равным prime_count.