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

Question

编辑:在得到一些反馈后,我创建了一个新的例子,它应该更具可重复性.

我一直在用C++编写一个涉及大量链表迭代的项目.为了获得基准,我在Go中重写了代码.令人惊讶的是,我发现即使将-O标志传递给clang ++之后,Go实现仍然以大约10%的速度运行.可能我只是错过了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;
}

走:

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

Answer 1

前言：我不是C++专家或汇编专家。但我对其中的一点了解，也许足以构成危险。

\n\n

所以我很生气，决定看一下为 Go 生成的汇编器，然后根据 clang++ 的输出检查它。

\n\n

高层总结

\n\n

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

\n\n

紧密循环之所以重要，是因为现代 CPU 执行指令的速度通常比从内存加载要引用的代码（例如比较）的相关值要快。为了实现极快的速度，CPU 执行了许多技巧，包括流水线、分支预测等。紧密循环通常是流水线的祸根，并且实际上，如果值之间存在依赖关系，则分支预测可能只有很小的帮助。

\n\n

从根本上来说，遍历循环有四个主要块：

\n\n

1. If `node` is null, exit the loop.\n2. If `node.age` > 999999, exit the loop.\n3a. set prev = node\n3b. set node = node.next\n

\n\n

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

\n\n

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

\n\n

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

\n\n

我的完整调查如下：

\n\n\n\n

调查

\n\n

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

\n\n

所以我跑了go build -gcflags -S main.go获取这个程序集列表，而我只是真正查看 iterateAndPlace。

\n\n

"".iterateAndPlace STEXT nosplit size=56 args=0x8 locals=0x0\n    00000 (main.go:16)   TEXT    "".iterateAndPlace(SB), NOSPLIT, $0-8\n    00000 (main.go:16)   FUNCDATA    $0, gclocals\xc2\xb72a5305abe05176240e61b8620e19a815(SB)\n    00000 (main.go:16)   FUNCDATA    $1, gclocals\xc2\xb733cdeccccebe80329f1fdbee7f5874cb(SB)\n    00000 (main.go:17)   MOVQ    "".nodes(SB), AX\n    00007 (main.go:17)   MOVL    $0, CX\n    00009 (main.go:20)   JMP 20\n    00011 (main.go:25)   MOVQ    (AX), DX\n    00014 (main.go:25)   MOVQ    AX, CX\n    00017 (main.go:25)   MOVQ    DX, AX\n    00020 (main.go:20)   TESTQ   AX, AX\n    00023 (main.go:20)   JEQ 44\n    00025 (main.go:21)   MOVSD   8(AX), X0\n    00030 (main.go:21)   MOVSD   $f64.40f869f000000000(SB), X1\n    00038 (main.go:21)   UCOMISD X1, X0\n    00042 (main.go:21)   JLS 11\n    00044 (main.go:21)   MOVSD   "".age+8(SP), X0\n    00050 (main.go:28)   MOVSD   X0, 8(CX)\n    00055 (main.go:29)   RET\n

\n\n

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

\n\n

16  func iterateAndPlace(age float64) {\n17      node := nodes\n18      var prev *Node = nil\n19\n20      for node != nil {\n21          if node.age > 99999 {\n22              break\n23          }\n24          prev = node\n25          node = node.next\n26      }\n27\n28      prev.age = age\n29  }\n

\n\n

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

\n\n

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

\n\n

那么让我们跳到 C++ 程序集，它是从clang++ -S -mllvm --x86-asm-syntax=intel -O3 minimal.cpp.

\n\n

.quad   4681608292164698112     ## double 99999\n# note I snipped some stuff here\n__Z15iterateAndPlaced:                  ## @_Z15iterateAndPlaced\n## BB#0:\n    push    rbp\nLcfi0:\n    .cfi_def_cfa_offset 16\nLcfi1:\n    .cfi_offset rbp, -16\n    mov rbp, rsp\nLcfi2:\n    .cfi_def_cfa_register rbp\n    mov rcx, qword ptr [rip + _nodes]\n    xor eax, eax\n    movsd   xmm1, qword ptr [rip + LCPI0_0] ## xmm1 = mem[0],zero\n    .p2align    4, 0x90\nLBB0_2:                                 ## =>This Inner Loop Header: Depth=1\n    mov rdx, rax\n    mov rax, rcx\n    movsd   xmm2, qword ptr [rax + 8] ## xmm2 = mem[0],zero\n    ucomisd xmm2, xmm1\n    ja  LBB0_3\n## BB#1:                                ##   in Loop: Header=BB0_2 Depth=1\n    mov rcx, qword ptr [rax]\n    test    rcx, rcx\n    mov rdx, rax\n    jne LBB0_2\nLBB0_3:\n    movsd   qword ptr [rdx + 8], xmm0\n    pop rbp\n    ret\n

\n\n

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

\n\n\n\n

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

\n\n

$ go version\ngo version go1.9.3 darwin/amd64\n\n$ clang++ --version\nApple LLVM version 9.0.0 (clang-900.0.39.2)\nTarget: x86_64-apple-darwin17.4.0\n

\n