在C ++中迭代链接列表比在Go中慢

在C ++中迭代链接列表比在Go中慢,第1张

在C ++中迭代链接列表比在Go中慢

前言:我不是C ++专家或汇编专家。但是我了解其中的一些知识,也许足以危险。

因此,我很激动,因此决定看一下为Go生成的汇编程序,然后跟着对clang ++的输出进行检查。

高层总结

稍后,我在x86-64汇编器中浏览两种语言的汇编器输出。此示例中代码的基本“关键部分”是一个非常紧密的循环。因此,它是该程序花费时间的最大贡献者。

紧密循环之所以如此重要,是因为现代CPU的执行指令通常比可以从内存中加载要引用的代码的相关值(例如进行比较)更快。为了实现它们所达到的超快速度,CPU执行了许多技巧,包括流水线化,分支预测等。紧密的循环通常是流水线的祸根,而实际上,如果值之间存在依赖关系,则分支预测可能仅会有所帮助。

从根本上讲,遍历循环包含四个主要块:

1. If `node` is null, exit the loop.2. If `node.age` > 999999, exit the loop.3a. set prev = node3b. set node = node.next

这些中的每一个都由几个汇编器指令表示,但是Go和C 输出的块的顺序不同。C 有效地按顺序进行

3a, 1, 2, 3b
。Go版本按顺序进行
3,2, 1
。(它在段2上开始第一个循环,以避免在空检查之前发生分配)

实际上,与Go相比,clang
++输出的指令要少一些,并且应该进行较少的RAM访问(以增加一个浮点寄存器为代价)。可能有人会想到,以不同的顺序执行几乎相同的指令应该花费相同的时间,但这并未考虑流水线和分支预测。

要点
如果一个关键但很小的循环,可能会尝试手动优化此代码并编写汇编。忽略明显的原因(风险更大/更复杂/更容易出现错误),还需要考虑到,尽管Go生成的代码对于我测试过的两个Intel
x86-64处理器而言都更快,但AMD可能处理器,您将得到相反的结果。使用第N + 1代Intel,您也有可能获得不同的结果。

我的全面调查如下:


调查

注意: 我已经尽可能地简短了一些示例,包括截断文件名以及从程序集列表中删除多余的绒毛,因此您的输出可能看起来与我的略有不同。但是无论如何,我继续。

所以我跑去

go build -gcflags -S main.go
获得该程序集清单,而我只是在真正地查看iterateAndPlace。

"".iterateAndPlace STEXT nosplit size=56 args=0x8 locals=0x0    00000 (main.go:16)   TEXT    "".iterateAndPlace(SB), NOSPLIT, 
16  func iterateAndPlace(age float64) {17      node := nodes18      var prev *Node = nil1920      for node != nil {21          if node.age > 99999 {22   break23          }24          prev = node25          node = node.next26      }2728      prev.age = age29  }
-8 00000 (main.go:16) FUNCDATA
prev = node
, gclocals·2a5305abe05176240e61b8620e19a815(SB) 00000 (main.go:16) FUNCDATA , gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB) 00000 (main.go:17) MOVQ "".nodes(SB), AX 00007 (main.go:17) MOVL
node.next
, CX 00009 (main.go:20) JMP 20 00011 (main.go:25) MOVQ (AX), DX 00014 (main.go:25) MOVQ AX, CX 00017 (main.go:25) MOVQ DX, AX 00020 (main.go:20) TESTQ AX, AX 00023 (main.go:20) JEQ 44 00025 (main.go:21) MOVSD 8(AX), X0 00030 (main.go:21) MOVSD $f64.40f869f000000000(SB), X1 00038 (main.go:21) UCOMISD X1, X0 00042 (main.go:21) JLS 11 00044 (main.go:21) MOVSD "".age+8(SP), X0 00050 (main.go:28) MOVSD X0, 8(CX) 00055 (main.go:29) RET

万一您失去上下文,我将在此处粘贴原始行和行号:

prev

我立即注意到一些有趣的事情:

  1. 它没有为第24行生成任何代码。这是因为已经意识到分配可以被欺骗:在遍历
    node = node.next
    时使用CX寄存器(即的值)来获取赋值
    clang++ -S -mllvm --x86-asm-syntax=intel -O3minimal.cpp
    。这可能是SSA编译器可以实现的一个很好的优化冗余。
  2. if语句检查node.age是再下令
    .quad   4681608292164698112     ## double 99999# note I snipped some stuff here__Z15iterateAndPlaced:       ## @_Z15iterateAndPlaced## BB#0:    push    rbpLcfi0:    .cfi_def_cfa_offset 16Lcfi1:    .cfi_offset rbp, -16    mov rbp, rspLcfi2:    .cfi_def_cfa_register rbp    mov rcx, qword ptr [rip + _nodes]    xor eax, eax    movsd   xmm1, qword ptr [rip + LCPI0_0] ## xmm1 = mem[0],zero    .p2align    4, 0x90LBB0_2:## =>This Inner Loop Header: Depth=1    mov rdx, rax    mov rax, rcx    movsd   xmm2, qword ptr [rax + 8] ## xmm2 = mem[0],zero    ucomisd xmm2, xmm1    ja  LBB0_3## BB#1:          ##   in Loop: Header=BB0_2 Depth=1    mov rcx, qword ptr [rax]    test    rcx, rcx    mov rdx, rax    jne LBB0_2LBB0_3:    movsd   qword ptr [rdx + 8], xmm0    pop rbp    ret
    prev
    东西,那就是在第一次循环跳过。在这种情况下,您可以将其视为do..while循环。总体上来说是次要的,因为它只会真正改变第一次迭代。但是也许就足够了吗?

因此,让我们跳到您从中获得的C ++程序集

$ go versiongo version go1.9.3 darwin/amd64$ clang++ --versionApple LLVM version 9.0.0 (clang-900.0.39.2)Target: x86_64-apple-darwin17.4.0

这真的很有趣。生成的程序集总体上非常相似(忽略了汇编程序列出语法的方式上的细微差别)-它对不分配进行了类似的优化。此外,C
++似乎消除了每次完成比较时都加载99999的需要(Go版本每次都在比较之前加载它)。


为了复制目的,我使用的东西的版本(在OSX High Sierra的x86-64 darwin mac上)



欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5048759.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-11-15
下一篇 2022-11-15

发表评论

登录后才能评论

评论列表(0条)

保存