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

Я читаю слайды Снятие ограничения скорости Javascript с помощью 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

Я работаю над версией 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();

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

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

this.primes = new Array(iterations);

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

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

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

Результаты чтения за пределами результатов приводят к тому, this.primes[i]что они находятся undefinedв этой строке:

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

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

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

• integer % undefinedс другой стороны, это означает, что он менее эффективен Float64Mod, так undefinedкак представлен как двойной.

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

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

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

В других ответах и ​​комментариях упоминается, что разница между двумя циклами заключается в том, что первый выполняет еще одну итерацию, чем второй. Это правда, но в массиве, который увеличивается до 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 обрабатывают его по-другому. Я не знаю, так или иначе, но эта деоптимизация - то, о чем говорилось в презентации.

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

Пример 1:
a 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) работает быстрее, чем ошибочный фрагмент (a)»?

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

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

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

Точнее: JIT-компиляция и, что еще важнее, JIT- RE -компиляция!

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

Теперь, когда 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)

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

Теперь представьте, что один и тот же функциональный код фактически используется для разных типов или даже вариантов ввода, как в буквальном смысле (в исходном коде), так и в динамически создаваемых в программе «массивах».

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

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

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

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

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

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

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

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

...

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

Источник:
«JITProf: Определение JIT-недружественного кода JavaScript»,
публикация Berkeley, 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, используя общие предположения (например, нет доступа за пределы)
• Работай
• БАМ, внезапно доступ к массиву выходит за пределы (прямо в конце).
• Дерьмо, говорит движок, давайте перекомпилируем isPrimeDivisible, используя разные (менее) допущения, и этот пример движка не пытается выяснить, может ли он повторно использовать текущий частичный результат, поэтому
• Пересчитайте всю работу, используя более медленную функцию (надеюсь, она завершится, в противном случае повторите и на этот раз просто интерпретируйте код).
• Вернуть результат

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы добавить к этому научности, вот jsperf

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

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

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

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