Странная производительность JavaScript

Когда я реализовывал ChaCha20 в JavaScript, я наткнулся на странное поведение.

Моя первая версия была построена следующим образом (назовем ее «Инкапсулированная версия»):

function quarterRound(x, a, b, c, d) {
    x[a] += x[b]; x[d] = ((x[d] ^ x[a]) << 16) | ((x[d] ^ x[a]) >>> 16);
    x[c] += x[d]; x[b] = ((x[b] ^ x[c]) << 12) | ((x[b] ^ x[c]) >>> 20);
    x[a] += x[b]; x[d] = ((x[d] ^ x[a]) <<  8) | ((x[d] ^ x[a]) >>> 24);
    x[c] += x[d]; x[b] = ((x[b] ^ x[c]) <<  7) | ((x[b] ^ x[c]) >>> 25);
}

function getBlock(buffer) {
    var x = new Uint32Array(16);

    for (var i = 16; i--;) x[i] = input[i];
    for (var i = 20; i > 0; i -= 2) {
        quarterRound(x, 0, 4, 8,12);
        quarterRound(x, 1, 5, 9,13);
        quarterRound(x, 2, 6,10,14);
        quarterRound(x, 3, 7,11,15);
        quarterRound(x, 0, 5,10,15);
        quarterRound(x, 1, 6,11,12);
        quarterRound(x, 2, 7, 8,13);
        quarterRound(x, 3, 4, 9,14);
    }
    for (i = 16; i--;) x[i] += input[i];
    for (i = 16; i--;) U32TO8_LE(buffer, 4 * i, x[i]);
    input[12]++;
    return buffer;
}

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

function getBlock(buffer) {
    var x = new Uint32Array(16);

    for (var i = 16; i--;) x[i] = input[i];
    for (var i = 20; i > 0; i -= 2) {
        x[ 0] += x[ 4]; x[12] = ((x[12] ^ x[ 0]) << 16) | ((x[12] ^ x[ 0]) >>> 16);
        x[ 8] += x[12]; x[ 4] = ((x[ 4] ^ x[ 8]) << 12) | ((x[ 4] ^ x[ 8]) >>> 20);
        x[ 0] += x[ 4]; x[12] = ((x[12] ^ x[ 0]) <<  8) | ((x[12] ^ x[ 0]) >>> 24);
        x[ 8] += x[12]; x[ 4] = ((x[ 4] ^ x[ 8]) <<  7) | ((x[ 4] ^ x[ 8]) >>> 25);
        x[ 1] += x[ 5]; x[13] = ((x[13] ^ x[ 1]) << 16) | ((x[13] ^ x[ 1]) >>> 16);
        x[ 9] += x[13]; x[ 5] = ((x[ 5] ^ x[ 9]) << 12) | ((x[ 5] ^ x[ 9]) >>> 20);
        x[ 1] += x[ 5]; x[13] = ((x[13] ^ x[ 1]) <<  8) | ((x[13] ^ x[ 1]) >>> 24);
        x[ 9] += x[13]; x[ 5] = ((x[ 5] ^ x[ 9]) <<  7) | ((x[ 5] ^ x[ 9]) >>> 25);
        x[ 2] += x[ 6]; x[14] = ((x[14] ^ x[ 2]) << 16) | ((x[14] ^ x[ 2]) >>> 16);
        x[10] += x[14]; x[ 6] = ((x[ 6] ^ x[10]) << 12) | ((x[ 6] ^ x[10]) >>> 20);
        x[ 2] += x[ 6]; x[14] = ((x[14] ^ x[ 2]) <<  8) | ((x[14] ^ x[ 2]) >>> 24);
        x[10] += x[14]; x[ 6] = ((x[ 6] ^ x[10]) <<  7) | ((x[ 6] ^ x[10]) >>> 25);
        x[ 3] += x[ 7]; x[15] = ((x[15] ^ x[ 3]) << 16) | ((x[15] ^ x[ 3]) >>> 16);
        x[11] += x[15]; x[ 7] = ((x[ 7] ^ x[11]) << 12) | ((x[ 7] ^ x[11]) >>> 20);
        x[ 3] += x[ 7]; x[15] = ((x[15] ^ x[ 3]) <<  8) | ((x[15] ^ x[ 3]) >>> 24);
        x[11] += x[15]; x[ 7] = ((x[ 7] ^ x[11]) <<  7) | ((x[ 7] ^ x[11]) >>> 25);
        x[ 0] += x[ 5]; x[15] = ((x[15] ^ x[ 0]) << 16) | ((x[15] ^ x[ 0]) >>> 16);
        x[10] += x[15]; x[ 5] = ((x[ 5] ^ x[10]) << 12) | ((x[ 5] ^ x[10]) >>> 20);
        x[ 0] += x[ 5]; x[15] = ((x[15] ^ x[ 0]) <<  8) | ((x[15] ^ x[ 0]) >>> 24);
        x[10] += x[15]; x[ 5] = ((x[ 5] ^ x[10]) <<  7) | ((x[ 5] ^ x[10]) >>> 25);
        x[ 1] += x[ 6]; x[12] = ((x[12] ^ x[ 1]) << 16) | ((x[12] ^ x[ 1]) >>> 16);
        x[11] += x[12]; x[ 6] = ((x[ 6] ^ x[11]) << 12) | ((x[ 6] ^ x[11]) >>> 20);
        x[ 1] += x[ 6]; x[12] = ((x[12] ^ x[ 1]) <<  8) | ((x[12] ^ x[ 1]) >>> 24);
        x[11] += x[12]; x[ 6] = ((x[ 6] ^ x[11]) <<  7) | ((x[ 6] ^ x[11]) >>> 25);
        x[ 2] += x[ 7]; x[13] = ((x[13] ^ x[ 2]) << 16) | ((x[13] ^ x[ 2]) >>> 16);
        x[ 8] += x[13]; x[ 7] = ((x[ 7] ^ x[ 8]) << 12) | ((x[ 7] ^ x[ 8]) >>> 20);
        x[ 2] += x[ 7]; x[13] = ((x[13] ^ x[ 2]) <<  8) | ((x[13] ^ x[ 2]) >>> 24);
        x[ 8] += x[13]; x[ 7] = ((x[ 7] ^ x[ 8]) <<  7) | ((x[ 7] ^ x[ 8]) >>> 25);
        x[ 3] += x[ 4]; x[14] = ((x[14] ^ x[ 3]) << 16) | ((x[14] ^ x[ 3]) >>> 16);
        x[ 9] += x[14]; x[ 4] = ((x[ 4] ^ x[ 9]) << 12) | ((x[ 4] ^ x[ 9]) >>> 20);
        x[ 3] += x[ 4]; x[14] = ((x[14] ^ x[ 3]) <<  8) | ((x[14] ^ x[ 3]) >>> 24);
        x[ 9] += x[14]; x[ 4] = ((x[ 4] ^ x[ 9]) <<  7) | ((x[ 4] ^ x[ 9]) >>> 25);
    }
    for (i = 16; i--;) x[i] += input[i];
    for (i = 16; i--;) U32TO8_LE(buffer, 4 * i, x[i]);
    input[12]++;
    return buffer;
}

Но результат был не совсем таким, как ожидалось:

Инкапсулированная производительность

против.

Встроенная производительность

Хотя разница в производительности в Firefox и Safari незначительна или не важна, снижение производительности в Chrome огромно ... Есть идеи, почему это происходит?

P.S .: Если изображения слишком маленькие, откройте их на новой вкладке:)

PP.S .: Вот ссылки:

Inlined

Инкапсулированный

12 голосов | спросил K. Biermann 3 AMpFri, 03 Apr 2015 02:14:43 +030014Friday 2015, 02:14:43

1 ответ


0

Регрессия происходит из-за ошибки в одном из проходов текущего оптимизирующего компилятора V8 Crankshaft.

Если вы посмотрите, что Crankshaft делает с медленным «встроенным» случаем, вы заметите, что функция getBlock постоянно деоптимизируется.

Чтобы убедиться, что вы можете просто передать флаг --trace-deopt в V8 и прочитать вывод, который он выводит на консоль, или использовать инструмент под названием IRHydra .

Я собрал выходные данные V8 как для встроенных, так и для неподключенных случаев, вы можете изучить их в IRHydra:

Вот что он показывает для «встроенного» случая:

список методов

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

Это означает, что getBlock постоянно оптимизируется и деоптимизируется. В «инкапсулированном» случае ничего подобного нет:

введите описание изображения здесь

Здесь getBlock оптимизируется один раз и никогда не деоптимизируется.

Если мы заглянем внутрь getBlock, то увидим, что это загрузка массива из Uint32Array, которая деоптимизирует, потому что результатом этой загрузки является значение, которое не вписывается в значение int32.

введите описание изображения здесь

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

Самое широкое целочисленное представление коленчатого вала - это int32 и половина uint32 значения не представимы в нем. Чтобы частично смягчить это ограничение, Crankshaft выполняет этап оптимизации, который называется uint32 analysis . Этот проход пытается выяснить, безопасно ли представлять значение uint32 как int32 - это достигается путем просмотра того, как используется это значение uint32: некоторые операции, например побитовые, не заботятся о «знаке», а только об отдельных битах, другие операции (например, деоптимизация или преобразование из целого числа в двойное) могут быть научены обрабатывать int32-то-то-фактически-uint32 особым образом. Если анализ успешен - все использования значения uint32 безопасны - тогда эта операция помечается особым образом, в противном случае (некоторые использования найдены небезопасно) операция не помечена и будет отменена, если она выдаст значение uint32, которое не вписывается в int32 диапазон (все, что выше 0x7fffffff).

В этом случае анализ не помечал x[i] как безопасный uint32 - поэтому она была деоптимизирована, когда результат x[i] был вне int32 диапазон. Причина, по которой вы не пометили x[i] как безопасную, заключалась в том, что одно из его применений - искусственная инструкция, создаваемая inliner при вставке U32TO8_LE, считается небезопасным. Вот исправление для V8 , которое устраняет проблему, а также содержит небольшую иллюстрацию проблемы:

 var u32 = new Uint32Array(1);
u32[0] = 0xFFFFFFFF;  // this uint32 value doesn't fit in int32

function tr(x) {
  return x|0;
  //     ^^^ - this use is uint32-safe
}
function ld() {
  return tr(u32[0]);
  //     ^  ^^^^^^ uint32 op, will deopt if uses are not safe
  //     |
  //     \--- tr is inlined into ld and an hidden artificial 
  //          HArgumentObject instruction was generated that
  //          captured values of all parameters at entry (x)
  //          This instruction was considered uint32-unsafe
  //          by oversight.
}

while (...) ld();

Вы не сталкивались с этой ошибкой в ​​"инкапсулированной" версии, потому что собственный вкладчик Crankshaft исчерпал бюджет, прежде чем он достиг U32TO8_LE сайта вызова , Как вы можете видеть в IRHydra, только первые три вызова quarterRound являются встроенными:

введите описание изображения здесь

Вы можете обойти эту ошибку, изменив U32TO8_LE(buffer, 4 * i, x[i]) на U32TO8_LE(buffer, 4 * i, x[i]|0), который использует только значение x[i] для uint32-safe и не меняет результат.

ответил Vyacheslav Egorov 10 PMpFri, 10 Apr 2015 15:59:55 +030059Friday 2015, 15:59:55

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132