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

编辑：收到一些反馈后，我创建了一个新的例子 https://stackoverflow.com/questions/50282452/iterating-over-linked-list-in-c-is-slower-than-in-go-with-analogous-memory-ac这应该更具可重复性。

我一直在用 C++ 编写一个项目，其中涉及大量链表迭代。为了获得基准，我用 Go 重写了代码。令人惊讶的是，我发现 Go 实现的运行速度始终快了约 10%，即使在将 -O 标志传递给 clang++ 后也是如此。也许我只是错过了 C++ 中的一些明显的优化，但我已经用头撞墙一段时间了，进行了各种调整。

这是一个简化版本，在 C++ 和 Go 中具有相同的实现，其中 Go 程序运行得更快。它所做的只是创建一个包含 3000 个节点的链表，然后计算迭代该列表 1,000,000 次所需的时间（C++ 中为 7.5 秒，Go 中为 6.8 秒）。

C++:

#include <iostream>
#include <chrono>

using namespace std;
using ms = chrono::milliseconds;

struct Node {
    Node *next;
    double age;
};

// Global linked list of nodes
Node *nodes = nullptr;

void iterateAndPlace(double age) {
    Node *node = nodes;
    Node *prev = nullptr;

    while (node != nullptr) {
        // Just to make sure that age field is accessed
        if (node->age > 99999) {
            break;
        }

        prev = node;
        node = node->next;
    }

    // Arbitrary action to make sure the compiler
    // doesn't optimize away this function
    prev->age = age;
}

int main() {
    Node x = {};
    std::cout << "Size of struct: " << sizeof(x) << "\n"; // 16 bytes

    // Fill in global linked list with 3000 dummy nodes
    for (int i=0; i<3000; i++) {
        Node* newNode = new Node;
        newNode->age = 0.0;
        newNode->next = nodes;
        nodes = newNode;
    }

    auto start = chrono::steady_clock::now();
    for (int i=0; i<1000000; i++) {
        iterateAndPlace(100.1);
    }

    auto end = chrono::steady_clock::now();
    auto diff = end - start;
    std::cout << "Elapsed time is :  "<< chrono::duration_cast<ms>(diff).count()<<" ms "<<endl;
}

Go:

package main
import (
    "time"
    "fmt"
    "unsafe"
)

type Node struct {
    next *Node
    age float64
}

var nodes *Node = nil

func iterateAndPlace(age float64) {
    node := nodes
    var prev *Node = nil

    for node != nil {
        if node.age > 99999 {
            break
        }
        prev = node
        node = node.next
    }

    prev.age = age
}

func main() {
    x := Node{}
    fmt.Printf("Size of struct: %d\n", unsafe.Sizeof(x)) // 16 bytes

    for i := 0; i < 3000; i++ {
        newNode := new(Node)
        newNode.next = nodes
        nodes = newNode
    }

    start := time.Now()
    for i := 0; i < 1000000; i++ {
        iterateAndPlace(100.1)
    }
    fmt.Printf("Time elapsed: %s\n", time.Since(start))
}

我的 Mac 的输出：

$ go run minimal.go
Size of struct: 16
Time elapsed: 6.865176895s

$ clang++ -std=c++11 -stdlib=libc++ minimal.cpp -O3; ./a.out
Size of struct: 16
Elapsed time is :  7524 ms

铿锵版本：

$ clang++ --version
Apple LLVM version 8.0.0 (clang-800.0.42.1)
Target: x86_64-apple-darwin15.6.0
Thread model: posix

编辑： UKMonkey 提出了这样一个事实：在 Go 中节点可以连续分配，但在 C++ 中则不行。为了测试这一点，我在 C++ 中使用向量连续分配，这并没有改变运行时：

// Fill in global linked list with 3000 contiguous dummy nodes
vector<Node> vec;
vec.reserve(3000);
for (int i=0; i<3000; i++) {
    vec.push_back(Node());
}

nodes = &vec[0];
Node *curr = &vec[0];
for (int i=1; i<3000; i++) {
    curr->next = &vec[i];
    curr = curr->next;
    curr->age = 0.0;
}

我检查了生成的链表确实是连续的：

std::cout << &nodes << " " << &nodes->next << " " << &nodes->next->next << " " << &nodes->next->next->next << "\n";
0x1032de0e0 0x7fb934001000 0x7fb934001010 0x7fb934001020

前言：我不是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 = node
3b. set node = node.next

其中每一个都由多个汇编指令表示，但 Go 和 C++ 输出的块的顺序不同。 C++ 有效地按顺序执行此操作3a, 1, 2, 3b。 Go 版本按顺序执行3, 2, 1。 （它在段 2 上启动第一个循环，以避免在空检查之前发生赋值）

实际上，clang++ 输出的指令比 Go 少，并且应该执行更少的 RAM 访问（以多一个浮点寄存器为代价）。人们可能会想象，只是以不同的顺序执行几乎相同的指令，最终会花费相同的时间，但这并没有考虑流水线和分支预测。

要点如果这是一个关键但很小的循环，人们可能会想要手动优化此代码并编写汇编。忽略明显的原因（它更危险/更复杂/更容易出现错误），还需要考虑到，虽然 Go 生成的代码对于我测试的两个 Intel x86-64 处理器来说更快，但对于 AMD处理器你会得到相反的结果。使用第 N+1 代英特尔，您也可能会得到不同的结果。

我的完整调查如下：

调查

NOTE我已经剪掉了尽可能短的示例，包括截断文件名，并从程序集列表中删除多余的内容，因此您的输出可能与我的输出略有不同。但无论如何，我继续。

所以我跑了go build -gcflags -S main.go要获得此程序集列表，我只真正查看 iterateAndPlace。

"".iterateAndPlace STEXT nosplit size=56 args=0x8 locals=0x0
    00000 (main.go:16)   TEXT    "".iterateAndPlace(SB), NOSPLIT, $0-8
    00000 (main.go:16)   FUNCDATA    $0, gclocals·2a5305abe05176240e61b8620e19a815(SB)
    00000 (main.go:16)   FUNCDATA    $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    00000 (main.go:17)   MOVQ    "".nodes(SB), AX
    00007 (main.go:17)   MOVL    $0, 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

如果您丢失了上下文，我将在此处粘贴带有行号的原始列表：

16  func iterateAndPlace(age float64) {
17      node := nodes
18      var prev *Node = nil
19
20      for node != nil {
21          if node.age > 99999 {
22              break
23          }
24          prev = node
25          node = node.next
26      }
27
28      prev.age = age
29  }

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

1. 它没有为第 24 行生成任何代码，prev = node。那是因为它意识到赋值可能会被欺骗：在遍历中得到node.next它使用 CX 寄存器，其值为prev。这可能是 SSA 编译器可以实现的一个很好的优化，但它是多余的。
2. 检查node.age的if语句被重新排序为after the node = node.next东西，在第一次迭代时被跳过。在这种情况下，您可以将其视为更像 do..while 循环。总体来说很小，因为它只真正改变了第一次迭代。但也许这就足够了？

那么让我们跳到 C++ 程序集，您可以从中获得clang++ -S -mllvm --x86-asm-syntax=intel -O3 minimal.cpp.

.quad   4681608292164698112     ## double 99999
# note I snipped some stuff here
__Z15iterateAndPlaced:                  ## @_Z15iterateAndPlaced
## BB#0:
    push    rbp
Lcfi0:
    .cfi_def_cfa_offset 16
Lcfi1:
    .cfi_offset rbp, -16
    mov rbp, rsp
Lcfi2:
    .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, 0x90
LBB0_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_2
LBB0_3:
    movsd   qword ptr [rdx + 8], xmm0
    pop rbp
    ret

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

出于复制目的，我使用的版本（在 OSX High Sierra 上的 x86-64 darwin mac 上）

$ go version
go version go1.9.3 darwin/amd64

$ clang++ --version
Apple LLVM version 9.0.0 (clang-900.0.39.2)
Target: x86_64-apple-darwin17.4.0