我一直在用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
解决方法
所以我被激发了,并决定看一下为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
