迭代C中的链表慢于Go

编辑：在得到一些反馈后,我创建了一个 new example,它应该更具可重复性.

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

解决方法

前言：我不是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,1执行.(它在段2上启动第一个循环以避免在空检查之前发生分配)

实际上,clang输出的指令比Go少一些,并且应该执行更少的RAM访问(以另外一个浮点寄存器为代价).可以想象,仅在不同的顺序中执行几乎相同的指令应该花费相同的时间,但是这没有考虑流水线和分支预测.

Takeaways One可能会试图手动优化此代码并编写汇编,如果它是一个关键但很小的循环.忽略了显而易见的原因(它更危险/更复杂/更容易出现错误)还要考虑到,虽然Go生成的代码对于我测试过的两个Intel x86-64处理器来说速度更快,但有可能是AMD处理器你会得到相反的结果.使用N第1代英特尔也可能会得到不同的结果.

我的全面调查如下：

调查

注意我已尽可能缩短示例,包括截断文件名,并从汇编列表中删除多余的绒毛,因此您的输出可能与我的略有不同.但无论如何,我继续.

所以我跑去构建-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.nextstuff之后,在第一次迭代时被跳过.在这种情况下,您可以将此视为更像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

迭代C中的链表慢于Go

解决方法

猜你在找的C&C++相关文章