这个函数为什么运行得慢？

Question

我一直在尝试进行实验，以查看函数中的局部变量是否存储在堆栈上。

因此，我编写了一个小型性能测试。

function test(fn, times){
    var i = times;
    var t = Date.now()
    while(i--){
        fn()
    }
    return Date.now() - t;
} 
ene
function straight(){
    var a = 1
    var b = 2
    var c = 3
    var d = 4
    var e = 5
    a = a * 5
    b = Math.pow(b, 10)
    c = Math.pow(c, 11)
    d = Math.pow(d, 12)
    e = Math.pow(e, 25)
}
function inversed(){
    var a = 1
    var b = 2
    var c = 3
    var d = 4
    var e = 5
    e = Math.pow(e, 25)
    d = Math.pow(d, 12)
    c = Math.pow(c, 11)
    b = Math.pow(b, 10)
    a = a * 5
}

我本以为反函数的运行速度会更快，但实际上得到了惊人的结果。

直到我测试其中一个函数时，它的运行速度比测试第二个函数时快10倍。

例子：

> test(straight, 10000000)
30
> test(straight, 10000000)
32
> test(inversed, 10000000)
390
> test(straight, 10000000)
392
> test(inversed, 10000000)
390

在进行替代顺序测试时，行为相同。

> test(inversed, 10000000)
25
> test(straight, 10000000)
392
> test(inversed, 10000000)
394

我在Chrome浏览器和Node.js中进行了测试，但我完全不知道为什么会出现这种情况。该效果持续到我刷新当前页面或重新启动Node REPL。

有什么可能导致性能显着下降（约为12倍）？

PS. 由于它似乎只在某些环境中工作，请写下您用于测试的环境。

我的环境是：

操作系统：Ubuntu 14.04
Node v0.10.37
Chrome 43.0.2357.134（正式版本）（64位）

/编辑
在Firefox 39上，每个测试需要大约5500毫秒，无论顺序如何。它似乎只会发生在特定的引擎上。

/编辑2
将函数内联到测试函数中使其始终以相同的时间运行。
如果参数函数始终相同，是否有可能进行内联优化？

- Krzysztof Wende

---

我猜这与垃圾回收有关。垃圾回收将在收集器清理所有剩余内容之前创建已使用内存的峰值。如果您改变函数的顺序，会有所区别吗？ - somethinghere

尝试切换您的测试方案：首先运行“反转”测试，然后再运行“正常”测试。 - robertklep

已在V8和Spidermonkey中确认。即使“inversed”和“straight”具有完全相同的定义，也会发生这种情况。可能调用多个函数会产生额外的开销。 - 1983

@KrzysztofWende 这也是我一直在阅读的内容。我没有发现任何迹象表明堆栈内存会被清除，也没有看到任何立即有用的原因。虽然我不是专家，但这个问题的答案对于任何程序员来说都可能很有趣。最终可能值得一份赏金。 - html_programmer

也许 fn 会被内联优化，直到它能够承载超过一个值的那一刻。 - 1983

Answer 1

一旦您使用两个不同的函数调用test，其中fn()所在的调用点变得超出了V8的多态内联缓存范围。

与V8中的方法调用o.m(...)相反，函数调用伴随着一个元素内联缓存而非真正的多态内联缓存。

因为V8无法在fn()的调用点处进行内联，它无法对您的代码应用各种优化。如果您在IRHydra中查看您的代码（我已经上传了编译产物到gist以方便您），您会注意到test的第一个优化版本（当它专门针对fn = straight时）具有完全空的主循环。

V8刚刚内联了straight并使用死代码消除优化删除了您希望进行基准测试的所有代码。在旧版本的V8中，V8会通过LICM将代码从循环中提升出来，因为该代码完全是循环不变量，而不是使用DCE。

当straight没有被内联时，V8无法应用这些优化-因此性能差异。新版本的V8仍将对straight和inversed本身应用DCE，将它们转换为空函数。

所以性能差异并不是很大（大约2-3倍）。旧版V8在DCE方面不够积极，这会导致内联和非内联情况之间的差异更大，因为内联情况的峰值性能仅取决于积极的循环不变代码运动（LICM）的结果。

有关此相关的说明，这表明为什么不应该编写这样的基准测试 - 因为它们的结果没有任何用处，最终你只是测量一个空循环。

如果您对多态及其在V8中的影响感兴趣，请查看我的文章"What's up with monomorphism"（“Not all caches are the same”一节讨论了与函数调用相关的缓存）。我还建议阅读我的一些关于微基准测试危害的演讲之一，例如2015年GOTO Chicago "Benchmarking JS" 演讲（video） - 这可能会帮助您避免常见陷阱。

- Vyacheslav Egorov

---

“Megamorphic”函数无法内联是我之前没有意识到的一个见解。感谢您让我更加了解引擎中这类优化（包括“单态”类型）。当函数变成megamorphic时，无法再应用优化，这是否意味着没有内联缓存可以放置在全局缓存中，并且在查找发生时会出现缺失？ - Travis J

我不确定我理解这个问题。函数不能变成巨型多态 - 这是函数内部每个操作的属性，例如属性访问 o.x 或函数调用 f()。当函数调用变成巨型多态时，V8只能无法内联调用 - 就是这样。 - Vyacheslav Egorov

Answer 2

你对栈的理解有误。

虽然“真正”的栈确实只有"Push"和"Pop"操作，但是对于用于执行的栈来说并不完全适用。除了"Push"和"Pop"之外，只要你知道变量的地址，就可以随意访问任何变量。这意味着局部变量的顺序并不重要，即使编译器没有为你重新排序。在伪汇编语言中，你似乎认为

var x = 1;
var y = 2;

x = x + 1;
y = y + 1;

翻译成类似于以下的东西

push 1 ; x
push 2 ; y

; get y and save it
pop tmp
; get x and put it in the accumulator
pop a
; add 1 to the accumulator
add a, 1
; store the accumulator back in x
push a
; restore y
push tmp
; ... and add 1 to y

事实上，真正的代码更像这样：

push 1 ; x
push 2 ; y

add [bp], 1
add [bp+4], 1

如果线程堆栈真的是一个真正的严格的堆栈，那么这将是不可能的，确实如此。在这种情况下，操作和局部变量的顺序比现在更为重要。相反，通过允许对堆栈上的值进行随机访问，可以为编译器和CPU节省大量工作。

回答您实际的问题，我怀疑这两个函数都没有实际做任何事情。您只修改了局部变量，并且函数没有返回任何东西-编译器完全可以删除函数体，甚至可能删除函数调用。如果确实如此，您观察到的任何性能差异可能只是测量工件或与调用函数/迭代固有成本相关的东西。

- Luaan

---

这更像是对于我为什么一开始的测试愚蠢的回答，而非对实际问题的回答，但无论如何感谢您的澄清。;) - Krzysztof Wende

@KrzysztofWende，我知道我在逃避问题，但我认为这可以帮助解释为什么你的测试基本上是无关紧要的。如果你真的只有push和pop，那将是可怕的 - 没有人会真正使用堆栈。 - Luaan

从数据结构的角度来看，它是什么样子的呢？ 如果它允许随机顺序，那么它就不是一个真正的堆栈。这些只是随意漂浮的内存指针吗？如果是，为什么还要称其为堆栈呢？ - Krzysztof Wende

@KrzysztofWende 所以，它仍然是一个栈 - 但它是一个允许随机访问的栈。它不允许随机分配或释放 - 这仍然是关于 push 和 pop 的专属操作（当你一次性丢弃多个堆栈帧时，像 "trim" 操作一样）。如果您愿意，可以将其视为增强型栈。 - Luaan

@KrzysztofWende：它更像是一个“帧”堆栈，每个帧都包含返回位置、传入参数和本地变量。在某些语言中（我不确定JavaScript），参数通常位于函数堆栈帧指针的“已知”负偏移处，而其本地变量则位于正偏移处。因此，它更像是一个对象堆栈，堆栈顶部对象的类型/布局与正在执行的函数一一对应。 - Eric Towers

Answer 3

将函数内联到测试函数中使其每次运行时间相同。是否可能存在一种优化方式，如果函数参数始终相同，则内联函数参数？

是的，这似乎正是您正在观察到的情况。如@Luaan所述，编译器很可能会删除straight和inverse函数的主体，因为它们没有任何副作用，只是操作一些局部变量。

当您首次调用test(..., 100000)时，经过一些迭代，优化编译器意识到被调用的fn()始终相同，并内联它，避免了昂贵的函数调用。现在它所做的只是1000万次减量一个变量并将其与0进行测试。

但是当您使用不同的fn调用test时，它必须取消优化。它以后可能会再次进行一些优化，但是现在知道有两个不同的函数要被调用，它无法再将它们内联。

由于您真正测量的唯一内容是函数调用，这导致了结果的巨大差异。

一项实验，以查看函数中的局部变量是否存储在堆栈上。

关于您实际的问题，单个变量不是存储在堆栈(堆栈机)中，而是存储在寄存器(寄存器机)中。它们在函数中声明或使用的顺序无关紧要。

然而，它们作为所谓的“堆栈帧”的一部分存储在堆栈上。每个函数调用都会有一个帧，存储其执行上下文的变量。在您的情况下，堆栈可能如下所示:

[straight: a, b, c, d, e]
[test: fn, times, i, t]
…

- Bergi

---

变量存储的方式是高度实现特定的问题，特别是一旦优化所涉及的函数 - 因为本地变量可能会简单地消失。 - Vyacheslav Egorov

@VyacheslavEgorov：是的，我并不是字面意思。只是在概念上，它们是词法环境的一部分，而词法环境又是堆栈帧的一部分。它们在实际实现中存储的方式完全不同。 - Bergi