1. 首页
  2. 问题
  3. 在C ++中迭代链接列表比在Go中慢
小编典典

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

go

编辑：获得一些反馈后，我创建了一个新示例，该示例应更具可重复性。

我一直在用C 编写一个项目，其中涉及许多链表迭代。为了获得基准，我重写了Go中的代码。令人惊讶的是，我发现即使将-O标志传递给clang，Go实现的运行速度也始终稳定〜10％。可能我只是缺少一些C ++的明显优化，但是我已经通过各种调整将自己的头撞墙了一段时间了。

这是一个简化的版本，在C和Go中具有相同的实现，其中Go程序运行速度更快。它要做的就是创建一个具有3000个节点的链表，然后花1000000次遍历此列表所需的时间（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

lang版本：

$ 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

阅读 210

收藏
2020-07-02

共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上开始第一个循环，以避免在空检查之前发生分配）

实际上，与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, $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. if语句检查node.age是再下令 后 的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
2020-07-02