一個簡單例子說明為什么C語言在2013年仍很重要

quasiceo 2014-01-19

展開全文

伯樂在線導(dǎo)讀：本文作者在開發(fā)Dynym項目，這是一個動態(tài)語言的通用運(yùn)行時。在開發(fā)時，作者以其他語言的運(yùn)行速度作為基礎(chǔ)比較語言的運(yùn)行速度，因此發(fā)現(xiàn)了一些小秘密。迭代計算斐波那契數(shù)列是測試各種語言執(zhí)行速度的常見方法。作者以不同的語言進(jìn)行測試，最終發(fā)現(xiàn)C語言要比Python編寫的計算斐波那契數(shù)列快278.5倍。在底層開發(fā)，以及專注性能的應(yīng)用程序中，選擇是顯而易見的。而為什么會有如此大的運(yùn)行性能差距呢。作者進(jìn)一步研究了程序的反匯編代碼，發(fā)現(xiàn)差別出在內(nèi)存的訪問次數(shù)，以及預(yù)測的CPU指令的正確性方面。（感謝 乾龍_ICT 的熱心翻譯。如果其他朋友也有不錯的原創(chuàng)或譯文，可以嘗試提交到伯樂在線。）以下是譯文。

原作者注：在本文最開始，我并沒說明進(jìn)行模2^64的計算——我當(dāng)然明白那些不是“正確的”斐波那契數(shù)列，其實我不是想分析大數(shù)，我只是想探尋編譯器產(chǎn)生的代碼和計算機(jī)體系結(jié)構(gòu)而已。

最近，我一直在開發(fā)Dynvm——一個通用的動態(tài)語言運(yùn)行時。就像其他任何好的語言運(yùn)行時項目一樣，開發(fā)是由基準(zhǔn)測試程序驅(qū)動的。因此，我一直在用基準(zhǔn)測試程序測試各種由不同語言編寫的算法，以此對其典型的運(yùn)行速度有一個感覺上的認(rèn)識。一個經(jīng)典的測試就是迭代計算斐波那契數(shù)列。為簡單起見，我以2^64為模，用兩種語言編寫實現(xiàn)了該算法。

用Python語言實現(xiàn)如下：

def fib(n):

SZ = 2**64

i = 0

a, b = 1, 0

while i < n:

t = b

b = (b+a) % SZ

a = t

i = i + 1

return b

用C語言實現(xiàn)如下：

#include <stdio.h>

#include <stdlib.h>

typedef unsigned long ulong;

int main(int argc, char *argv[])

{

ulong n = atoi(argv[1]);

ulong a = 1;

ulong b = 0;

ulong t;

for(ulong i = 0; i < n; i++) {

t = b;

b = a+b;

a = t;

}

printf("%lu\n", b);

return 0;

}

用其他語言實現(xiàn)的代碼示例，我已放在github上。

Dynvm包含一個基準(zhǔn)測試程序框架，該框架可以允許在不同語言之間對比運(yùn)行速度。在一臺Intel i7-3840QM（調(diào)頻到1.2 GHz)機(jī)器上，當(dāng) n=1,000,000 時，對比結(jié)果如下：

=======================================================

語言時間 (秒)

=======================================================

Java 0.133

C Language 0.006

CPython 0.534

Javascript V8 0.284

很明顯，C語言是這里的老大，但是java的結(jié)果有點誤導(dǎo)性，因為大部分的時間是由JIT編譯器啟動（~120ms）占用的。當(dāng)n=100,000,000時，結(jié)果變得更明朗：

=======================================================

語言時間（秒）

=======================================================

Java 0.300

C Language 0.172

CPython 47.909

Javascript V8 24.179

在這里，我們探究下為什么C語言在2013年仍然很重要，以及為什么編程世界不會完全“跳槽”到Python或者V8/Node。有時你需要原始性能，但是動態(tài)語言仍在這方面艱難掙扎著，即使對以上很簡單的例子而言。我個人相信這種情況會克服掉，通過幾個項目我們能在這方面看到很大的希望：JVM、V8、PyPy、LuaJIT等等，但在2013年我們還沒有到達(dá)“目的地”。

然而，我們無法回避這樣的問題：為什么差距如此之大？在C語言和Python之間有278.5倍的性能差距！最不可思議的地方是，從語法角度講，以上例子中的C語言和Python內(nèi)部循環(huán)基本上一模一樣。

為了找到問題的答案，我搬出了反匯編器，發(fā)現(xiàn)了以下現(xiàn)象：

0000000000400480 <main>:

247 400480: 48 83 ec 08 sub $0x8,%rsp

248 400484: 48 8b 7e 08 mov 0x8(%rsi),%rdi

249 400488: ba 0a 00 00 00 mov $0xa,%edx

250 40048d: 31 f6 xor %esi,%esi

251 40048f: e8 cc ff ff ff callq 400460 <strtol@plt>

252 400494: 48 98 cltq

253 400496: 31 d2 xor %edx,%edx

254 400498: 48 85 c0 test %rax,%rax

255 40049b: 74 26 je 4004c3 <main+0x43>

256 40049d: 31 c9 xor %ecx,%ecx

257 40049f: 31 f6 xor %esi,%esi

258 4004a1: bf 01 00 00 00 mov $0x1,%edi

259 4004a6: eb 0e jmp 4004b6 <main+0x36>

260 4004a8: 0f 1f 84 00 00 00 00 nopl 0x0(%rax,%rax,1)

261 4004af: 00

262 4004b0: 48 89 f7 mov %rsi,%rdi

263 4004b3: 48 89 d6 mov %rdx,%rsi

264 4004b6: 48 83 c1 01 add $0x1,%rcx

265 4004ba: 48 8d 14 3e lea (%rsi,%rdi,1),%rdx

266 4004be: 48 39 c8 cmp %rcx,%rax

267 4004c1: 77 ed ja 4004b0 <main+0x30>

268 4004c3: be ac 06 40 00 mov $0x4006ac,%esi

269 4004c8: bf 01 00 00 00 mov $0x1,%edi

270 4004cd: 31 c0 xor %eax,%eax

271 4004cf: e8 9c ff ff ff callq 400470 <__printf_chk@plt>

272 4004d4: 31 c0 xor %eax,%eax

273 4004d6: 48 83 c4 08 add $0x8,%rsp

274 4004da: c3 retq

275 4004db: 90 nop

（譯注：

1、不同的編譯器版本及不同的優(yōu)化選項（-Ox）會產(chǎn)生不同的匯編代碼。
2、反匯編方法：gcc -g -O2 test.c -o test;objdumb -d test>test.txt 讀者可以自己嘗試變換優(yōu)化選項對比反匯編結(jié)果）

最主要的部分是計算下一個斐波那契數(shù)值的內(nèi)部循環(huán)：

262 4004b0: 48 89 f7 mov %rsi,%rdi

263 4004b3: 48 89 d6 mov %rdx,%rsi

264 4004b6: 48 83 c1 01 add $0x1,%rcx

265 4004ba: 48 8d 14 3e lea (%rsi,%rdi,1),%rdx

266 4004be: 48 39 c8 cmp %rcx,%rax

267 4004c1: 77 ed ja 4004b0 <main+0x30>

變量在寄存器中的分配情況如下：

a: %rsi

b: %rdx

t: %rdi

i: %rcx

n: %rax

262和263行實現(xiàn)了變量交換，264行增加循環(huán)計數(shù)值，雖然看起來比較奇怪，265行實現(xiàn)了b=a+t。然后做一個簡單地比較，最后一個跳轉(zhuǎn)指令跳到循環(huán)開始出繼續(xù)執(zhí)行。

手動反編譯以上代碼，代碼看起來是這樣的：

loop: t = a

a = b

i = i+1

b = a+t

if(n > i) goto loop

整個內(nèi)部循環(huán)僅用六條X86-64匯編指令就實現(xiàn)了（很可能內(nèi)部微指令個數(shù)也差不多。譯者注：Intel X86-64處理器會把指令進(jìn)一步翻譯成微指令，所以CPU執(zhí)行的實際指令數(shù)要比匯編指令多）。CPython解釋模塊對每一條高層的指令字節(jié)碼至少需要六條甚至更多的指令來解釋，相比而言，C語言完勝。除此之外，還有一些其他更微妙的地方。

拉低現(xiàn)代處理器執(zhí)行速度的一個主要原因是對于主存的訪問。這個方面的影響十分可怕，在微處理器設(shè)計時，無數(shù)個工程時（engineering hours）都花費(fèi)在找到有效地技術(shù)來“掩藏”訪存延時。通用的策略包括：緩存、推測預(yù)取、load-store依賴性預(yù)測、亂序執(zhí)行等等。這些方法確實在使機(jī)器更快方面起了很大作用，但是不可能完全不產(chǎn)生訪存操作。

在上面的匯編代碼中，從沒訪問過內(nèi)存，實際上變量完全存儲在CPU寄存器中。現(xiàn)在考慮CPython：所有東西都是堆上的對象，而且所有方法都是動態(tài)的。動態(tài)特性太普遍了，以至于我們沒有辦法知道，a+b執(zhí)行integer_add(a, b)、string_concat(a, b)、還是用戶自己定義的函數(shù)。這也就意味著很多時間花在了在運(yùn)行時找出到底調(diào)用了哪個函數(shù)。動態(tài)JIT運(yùn)行時會嘗試在運(yùn)行時獲取這個信息，并動態(tài)產(chǎn)生x86代碼，但是這并不總是非常直接的（我期待V8運(yùn)行時會表現(xiàn)的更好，但奇怪的是它的速度只是Python的0.5倍）。因為CPython是一個純粹的翻譯器，在每個循環(huán)迭代時，很多時間花在了解決動態(tài)特性上，這就需要很多不必要的訪存操作。

除了以上內(nèi)存在搞鬼，還有其他因素?，F(xiàn)代超標(biāo)量亂序處理器核一次性可以取好幾條指令到處理器中，并且“在最方便時”執(zhí)行這些指令，也就是說：鑒于結(jié)果仍然是正確的，指令執(zhí)行順序可以任意。這些處理器也可以在同一個時鐘周期并行執(zhí)行多條指令，只要這些指令是不相關(guān)的。Intel Sandy Bridge CPU可以同時將168條指令重排序，并可以在一個周期中發(fā)射（即開始執(zhí)行指令）至多6條指令，同時結(jié)束（即指令完成執(zhí)行）至多4條指令！粗略地以上面斐波那契舉例，Intel這個處理器可以大約把28（譯者注：28*6=168）個內(nèi)部循環(huán)重排序，并且?guī)缀蹩梢栽诿恳粋€時鐘周期完成一個循環(huán)！這聽起來很霸氣，但是像其他事一樣，細(xì)節(jié)總是非常復(fù)雜的。

我們假定8條指令是不相關(guān)的，這樣處理器就可以取得足夠的指令來利用指令重排序帶來的好處。對于包含分支指令的指令流進(jìn)行重排序是非常復(fù)雜的，也就是對if-else和循環(huán)（譯者注：if-else需要判斷后跳轉(zhuǎn)，所以必然包含分支指令）產(chǎn)生的匯編代碼。典型的方法就是對于分支指令進(jìn)行預(yù)測。CPU會動態(tài)的利用以前分支執(zhí)行結(jié)果來猜測將來要執(zhí)行的分支指令的執(zhí)行結(jié)果，并且取得那些它“認(rèn)為”將要執(zhí)行的指令。然而，這個推測有可能是不正確的，如果確實不正確，CPU就會進(jìn)入復(fù)位模式（譯者注：這里的復(fù)位不是指處理器reset，而是CPU流水線的復(fù)位），即丟棄已經(jīng)取得的指令并且重新開始取指。這種復(fù)位操作有可能對性能產(chǎn)生很大影響。因此，對于分支指令的正確預(yù)測是另一個需要花費(fèi)很多工程時的領(lǐng)域。

現(xiàn)在，不是所有分支指令都是一樣的，有些可以很完美的預(yù)測，但是另一些幾乎不可能進(jìn)行預(yù)測。前面例子中的循環(huán)中的分支指令——就像反匯編代碼中267行——是最容易預(yù)測的其中一種，這個分支指令會連續(xù)向后跳轉(zhuǎn)100,000,000次。

以下是一個非常難預(yù)測的分支指令實例：

void main(void)

{

for(int i = 0; i < 1000000; i++) {

int n = random();

if(n >= 0) {

printf("positive!\n");

} else {

printf("negative!\n");

}

如果random()是真正隨機(jī)的（事實上在C語言中遠(yuǎn)非如此），那么對于if-else的預(yù)測還不如隨便猜來的準(zhǔn)確。幸運(yùn)的是，大部分的分支指令沒有這么頑皮，但是也有很少一部分和上面例子中的循環(huán)分支指令一樣變態(tài)。

回到我們的例子上：C代碼實現(xiàn)的斐波那契數(shù)列，只產(chǎn)生一個非常容易預(yù)測的分支指令。相反地，CPython代碼就非常糟糕。首先，所有純粹的翻譯器有一個“分配”循環(huán)，就像下面的例子：

void exec_instruction(instruction_t *inst)

{

switch(inst->opcode) {

case ADD: // do add

case LOAD: // do load

case STORE: // do store

case GOTO: // do goto

}

編譯器無論如何處理以上代碼，至少有一個間接跳轉(zhuǎn)指令是必須的，而這種間接跳轉(zhuǎn)指令是比較難預(yù)測的。

接下來回憶一下，動態(tài)語言必須在運(yùn)行時確定如“ADD指令的意思是什么”這樣基本的問題，這當(dāng)然會產(chǎn)生——你猜對了——更加變態(tài)的分支指令。

以上所有因素加起來，最后導(dǎo)致一個278.5倍的性能差距！現(xiàn)在，這當(dāng)然是一個很簡單的例子，但是其他的只會比這更變態(tài)。這個簡單例子足以凸顯低級靜態(tài)語言（例如C語言）在現(xiàn)代軟件中的重要地位。我當(dāng)然不是2013年里C語言最大的粉絲，但是C語言仍然主導(dǎo)著低級控制領(lǐng)域及對性能要求高的應(yīng)用程序領(lǐng)域。