对二叉树进行反优化会降低性能

Question

我需要一些帮助来优化以下代码。我不明白如何重写代码以避免非优化。下面是在Node平台上运行非常慢的代码。我从benchmarksgame-team二叉树基准测试中提取了它，并添加了一些小的变化。

当它与--trace-deopt一起运行时，显示热路径中的功能被去优化，即

[bailout (kind: deopt-lazy, reason: (unknown)): begin. deoptimizing 0x02117de4aa11 <JSFunction bottomUpTree2 (sfi = 000002F24C7D7539)>, opt id 3, bytecode offset 9, deopt exit 17, FP to SP delta 80, caller SP 0x00807d7fe6f0, pc 0x7ff6afaca78d]

基准，使用node --trace-deopt a 20

运行它

function mainThread() {
const maxDepth = Math.max(6, parseInt(process.argv[2]));
const stretchDepth = maxDepth + 1;
const check = itemCheck(bottomUpTree(stretchDepth));
console.log(`stretch tree of depth ${stretchDepth}t check: ${check}`);
const longLivedTree = bottomUpTree(maxDepth);
for (let depth = 4; depth <= maxDepth; depth += 2) {
const iterations = 1 << maxDepth - depth + 4;
work(iterations, depth);
}
console.log(`long lived tree of depth ${maxDepth}t check: ${itemCheck(longLivedTree)}`);
}
function work(iterations, depth) {
let check = 0;
for (let i = 0; i < iterations; i++) {
check += itemCheck(bottomUpTree(depth));
}
console.log(`${iterations}t trees of depth ${depth}t check: ${check}`);
}
function TreeNode(left, right) {
return {left, right};
}
function itemCheck(node) {
if (node.left === null) {
return 1;
}
return 1 + itemCheck2(node);
}
function itemCheck2(node) {
return itemCheck(node.left) + itemCheck(node.right);
}
function bottomUpTree(depth) {
return depth > 0
? bottomUpTree2(depth)
: new TreeNode(null, null);
}
function bottomUpTree2(depth) {
return new TreeNode(bottomUpTree(depth - 1), bottomUpTree(depth - 1))
}
console.time();
mainThread();
console.timeEnd();

Answer 1

(这里是V8开发人员)

这个问题的前提是不正确的:几个开发无关紧要，不影响性能。试图避免它们是徒劳的。

当试图提高某物的性能时，第一步是分析它。在这种情况下，概要文件显示基准正在花费:

• 在优化代码中约占46.3%的时间(树创建约占4/5，树迭代约占1/5)
• 在未优化代码
中约占0.1%的时间
• 大约52.8%的时间在垃圾收集器中，跟踪和释放所有这些短暂的对象。

这是一个人造的微基准。50%的GC时间从来没有发生在现实世界的代码中，除了尽可能快地分配多个gb的短寿命对象之外，它做了一些有用的事情。

事实上，称它们为"短命对象"在这种情况下有点不准确。虽然绝大多数正在构建的单个树确实是短期的，但代码在早期分配了一个超大的长寿命树。这欺骗了V8的自适应机制，使其假设所有未来的TreeNode也将是长寿命的，因此它将它们分配到"旧空间"中。如果猜测是正确的，这将节省时间，但最终会浪费时间，因为随后的TreeNode实际上是短暂的，最好放在"新空间"中。(它是为快速释放寿命较短的对象而优化的)。因此，通过重新排列操作顺序，我可以获得3倍的加速。

这是微基准测试的一个常见问题的典型例子:通过做一些极端和不现实的事情，它们经常创造出完全不能代表典型现实场景的情况。如果引擎开发人员针对这种微基准进行了优化，那么引擎在处理真实代码时的表现就会更差。如果JavaScript开发人员试图从微基准中获得洞察力，他们将编写在现实条件下性能更差的代码。

无论如何，如果您想优化这段代码，请尽量避免这些对象分配。

具体

---

:

像这样的人工微基准，就其本质而言，故意做无用的工作(例如:计算相同的值一百万次)。你说你想优化它，这意味着避免无用的工作，但你没有具体说明你想保留哪些无用的工作，如果有的话。因此，在没有首选项的情况下，我将假设所有

无用的工作都是无用的。我们来优化一下!查看代码，它创建了给定深度的完美二叉树，并对其节点进行计数。换句话说，它总结了以下示例中的1:
depth=0:

1

深度= 1:

1
/ 
1   1

深度= 2:

1
/   
1     1
/    / 
1   1 1   1

等等。如果你稍微思考一下，你就会意识到这样一个深度为N的树有(2 ** (N+1)) - 1个节点。所以我们可以替换:

itemCheck(bottomUpTree(depth));

(2 ** (depth+1)) - 1

(和类似的"stretchDepth"线).

接下来，我们可以处理无用的重复。由于x + x + x + x + ...N次与x*N相同，我们可以替换:

let check = 0;
for (let i = 0; i < iterations; i++) {
check += (2 ** (depth + 1)) - 1;
}

只有:

let check = ((2 ** (depth + 1)) - 1) * iterations;

我们从12秒减少到0.1秒。这五分钟的工作还不错吧?

剩余的时间几乎完全是由于longLivedTree。为了将相同的优化应用于创建和迭代该树的操作，我们必须将它们移动到一起，去掉它的"长寿命"。你能接受吗?您可以将总时间降低到不到一毫秒!这会使基准毫无用处吗?其实并没有比开始时更没用，只是更明显了。