奇怪的JavaScript性能表现

Question

当我在 JavaScript 中实现 ChaCha20 时，遇到了一些奇怪的行为。

我的第一个版本是这样构建的（我们称之为“封装版本”）：

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.: 这里是链接:

内联的

封装的

- K. Biermann

---

评论不适合进行长时间的讨论；此对话已被移至聊天室。 - George Stocker

1. 创建数组的成本很高：重复使用相同的缓冲区。
2. 给我们展示一下您的U32TO8_LE，这可能会很昂贵。
3. 在quarterRound中，缓存所有值，进行数学计算，然后存储结果。我猜这里有很大的收益（8个数组间接引用而不是……28！）。
4. 您还可以考虑将8个具有相关参数的函数绑定在一起，只需将x作为最后一个参数而不是第一个参数进行更改。我非常确定通过这些操作性能将大幅提升。

- GameAlchemist

Answer 1

回归是因为在V8的当前优化编译器Crankshaft的一个传递中遇到了错误。

如果您查看Crankshaft对于缓慢的“内联”情况所做的操作，您会注意到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通常会尝试在优化代码中将整数值表示为实际的整数。

Crankshaft 的最宽整数表示是 int32，而一半的 uint32 值无法在其中表示。为了部分缓解这个限制，Crankshaft 执行名为 uint32 分析的优化传递。该传递试图确定将 uint32 值表示为 int32 值是否安全 - 这是通过查看如何使用 uint32 值来完成的：某些操作（例如按位操作）不关心“符号”，只关心各个位，其他操作（例如取消优化或从整数转换为双精度浮点数）可以以特殊方式处理实际上是 uint32 的 int32。如果分析成功 - 所有对 uint32 值的使用都是安全的 - 则以特殊方式标记此操作，否则（发现某些用途不安全）则不标记该操作，并且如果产生不适合 int32 范围（任何大于 0x7fffffff）的 uint32 值，则会取消优化。

在这种情况下，分析没有将x[i]标记为安全的uint32操作 - 因此当x[i]的结果超出int32范围时，它会被取消优化。之所以不将x[i]标记为安全，是因为它的一个用途是由内联器在内联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安全，并且不会改变结果。

- Vyacheslav Egorov