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

Question

编辑:得到一些反馈后，我创建了一个 new example这应该更具可重复性。

我一直在用 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;
}

走:

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++ 中连续分配了一个 vector ，这并没有改变运行时:

// 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++专家或汇编专家。但我知道他们中的一点，也许足够危险。

所以我被激怒了，决定看一看为 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 代英特尔，您会得到不同的结果。

我的完整调查如下:

调查

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

所以我跑了 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  }

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

它没有为第 24 行生成任何代码，prev = node .那是因为它意识到赋值可以被欺骗:在遍历中获取 node.next它使用 CX 寄存器，其值为 prev .这可能是一个很好的优化，SSA 编译器可以意识到这是多余的。

检查 node.age 的 if 语句被重新排序在 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