Странная производительность 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

Encapsulated

Ответ 1

Регрессия происходит из-за того, что вы нажмете ошибку в одном из проходов в текущем оптимизационном компиляторе V8 коленчатого вала.

Если вы посмотрите, что делает коленчатый вал для медленного "вложенного" случая, вы заметите, что функция getBlock постоянно деоптимизирует.

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

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

вложенный случай: http://mrale.ph/irhydra/2/#gist:1fefdc70567a924d4cf2
инкапсулированный случай: http://mrale.ph/irhydra/2/#gist:be3de64f860c78ca640b

Вот что он показывает для "вложенного" случая:

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

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

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

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

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

Максимальное целочисленное представление коленчатого вала int32, а половина значений uint32 в нем не представляются. Чтобы частично смягчить это ограничение, Crankshaft выполняет оптимизационный проход, называемый uint32. Этот проход пытается определить, можно ли представлять значение uint32 как значение int32, безопасно ли это представлять, как это делается, глядя на то, как это значение uint32 используется: некоторые операции, например. поразрядные, не заботятся о "знаке", а только о отдельных битах, другие операции (например, деоптимизация или преобразование из целого числа в double) можно научить обрабатывать int32-that-is-actual-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();

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

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