伯樂(lè)在線導(dǎo)讀：本文作者在開發(fā)Dynym項(xiàng)目，這是一個(gè)動(dòng)態(tài)語(yǔ)言的通用運(yùn)行時(shí)。在開發(fā)時(shí)，作者以其他語(yǔ)言的運(yùn)行速度作為基礎(chǔ)比較語(yǔ)言的運(yùn)行速度，因此發(fā)現(xiàn)了一些小秘密。迭代計(jì)算斐波那契數(shù)列是測(cè)試各種語(yǔ)言執(zhí)行速度的常見方法。作者以不同的語(yǔ)言進(jìn)行測(cè)試，最終發(fā)現(xiàn)C語(yǔ)言要比Python編寫的計(jì)算斐波那契數(shù)列快278.5倍。在底層開發(fā)，以及專注性能的應(yīng)用程序中，選擇是顯而易見的。而為什么會(huì)有如此大的運(yùn)行性能差距呢。作者進(jìn)一步研究了程序的反匯編代碼，發(fā)現(xiàn)差別出在內(nèi)存的訪問(wèn)次數(shù)，以及預(yù)測(cè)的CPU指令的正確性方面。（感謝 乾龍_ICT 的熱心翻譯。如果其他朋友也有不錯(cuò)的原創(chuàng)或譯文，可以嘗試提交到伯樂(lè)在線。）以下是譯文。
原作者注：在本文最開始，我并沒(méi)說(shuō)明進(jìn)行模2^64的計(jì)算——我當(dāng)然明白那些不是“正確的”斐波那契數(shù)列，其實(shí)我不是想分析大數(shù)，我只是想探尋編譯器產(chǎn)生的代碼和計(jì)算機(jī)體系結(jié)構(gòu)而已。
最近，我一直在開發(fā)Dynvm——一個(gè)通用的動(dòng)態(tài)語(yǔ)言運(yùn)行時(shí)。就像其他任何好的語(yǔ)言運(yùn)行時(shí)項(xiàng)目一樣，開發(fā)是由基準(zhǔn)測(cè)試程序驅(qū)動(dòng)的。因此，我一直在用基準(zhǔn)測(cè)試程序測(cè)試各種由不同語(yǔ)言編寫的算法，以此對(duì)其典型的運(yùn)行速度有一個(gè)感覺上的認(rèn)識(shí)。一個(gè)經(jīng)典的測(cè)試就是迭代計(jì)算斐波那契數(shù)列。為簡(jiǎn)單起見，我以2^64為模，用兩種語(yǔ)言編寫實(shí)現(xiàn)了該算法。
用Python語(yǔ)言實(shí)現(xiàn)如下：
1 2 3 4 5 6 7 8 9 10 | 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語(yǔ)言實(shí)現(xiàn)如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #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;} |
用其他語(yǔ)言實(shí)現(xiàn)的代碼示例，我已放在github上。
Dynvm包含一個(gè)基準(zhǔn)測(cè)試程序框架，該框架可以允許在不同語(yǔ)言之間對(duì)比運(yùn)行速度。在一臺(tái)Intel i7-3840QM（調(diào)頻到1.2 GHz)機(jī)器上，當(dāng) n=1,000,000 時(shí)，對(duì)比結(jié)果如下：
1 2 3 4 5 6 7 | ======================================================= 語(yǔ)言 時(shí)間 (秒)======================================================= Java 0.133 C Language 0.006 CPython 0.534 Javascript V8 0.284 |
很明顯，C語(yǔ)言是這里的老大，但是java的結(jié)果有點(diǎn)誤導(dǎo)性，因?yàn)榇蟛糠值臅r(shí)間是由JIT編譯器啟動(dòng)（~120ms）占用的。當(dāng)n=100,000,000時(shí)，結(jié)果變得更明朗：
1 2 3 4 5 6 7 | ======================================================= 語(yǔ)言 時(shí)間（秒）======================================================= Java 0.300 C Language 0.172 CPython 47.909 Javascript V8 24.179 |
在這里，我們探究下為什么C語(yǔ)言在2013年仍然很重要，以及為什么編程世界不會(huì)完全“跳槽”到Python或者V8/Node。有時(shí)你需要原始性能，但是動(dòng)態(tài)語(yǔ)言仍在這方面艱難掙扎著，即使對(duì)以上很簡(jiǎn)單的例子而言。我個(gè)人相信這種情況會(huì)克服掉，通過(guò)幾個(gè)項(xiàng)目我們能在這方面看到很大的希望：JVM、V8、PyPy、LuaJIT等等，但在2013年我們還沒(méi)有到達(dá)“目的地”。
然而，我們無(wú)法回避這樣的問(wèn)題：為什么差距如此之大？在C語(yǔ)言和Python之間有278.5倍的性能差距！最不可思議的地方是，從語(yǔ)法角度講，以上例子中的C語(yǔ)言和Python內(nèi)部循環(huán)基本上一模一樣。
為了找到問(wèn)題的答案，我搬出了反匯編器，發(fā)現(xiàn)了以下現(xiàn)象：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 0000000000400480 <main>:247 400480: 48 83 ec 08 sub $0x8,%rsp248 400484: 48 8b 7e 08 mov 0x8(%rsi),%rdi249 400488: ba 0a 00 00 00 mov $0xa,%edx250 40048d: 31 f6 xor %esi,%esi251 40048f: e8 cc ff ff ff callq 400460 <strtol@plt>252 400494: 48 98 cltq253 400496: 31 d2 xor %edx,%edx254 400498: 48 85 c0 test %rax,%rax255 40049b: 74 26 je 4004c3 <main+0x43>256 40049d: 31 c9 xor %ecx,%ecx257 40049f: 31 f6 xor %esi,%esi258 4004a1: bf 01 00 00 00 mov $0x1,%edi259 4004a6: eb 0e jmp 4004b6 <main+0x36>260 4004a8: 0f 1f 84 00 00 00 00 nopl 0x0(%rax,%rax,1)261 4004af: 00262 4004b0: 48 89 f7 mov %rsi,%rdi263 4004b3: 48 89 d6 mov %rdx,%rsi264 4004b6: 48 83 c1 01 add $0x1,%rcx265 4004ba: 48 8d 14 3e lea (%rsi,%rdi,1),%rdx266 4004be: 48 39 c8 cmp %rcx,%rax267 4004c1: 77 ed ja 4004b0 <main+0x30>268 4004c3: be ac 06 40 00 mov $0x4006ac,%esi269 4004c8: bf 01 00 00 00 mov $0x1,%edi270 4004cd: 31 c0 xor %eax,%eax271 4004cf: e8 9c ff ff ff callq 400470 <__printf_chk@plt>272 4004d4: 31 c0 xor %eax,%eax273 4004d6: 48 83 c4 08 add $0x8,%rsp274 4004da: c3 retq275 4004db: 90 nop |
（譯注：
最主要的部分是計(jì)算下一個(gè)斐波那契數(shù)值的內(nèi)部循環(huán)：
1 2 3 4 5 6 | 262 4004b0: 48 89 f7 mov %rsi,%rdi263 4004b3: 48 89 d6 mov %rdx,%rsi264 4004b6: 48 83 c1 01 add $0x1,%rcx265 4004ba: 48 8d 14 3e lea (%rsi,%rdi,1),%rdx266 4004be: 48 39 c8 cmp %rcx,%rax267 4004c1: 77 ed ja 4004b0 <main+0x30> |
變量在寄存器中的分配情況如下：
1 2 3 4 5 | a: %rsib: %rdxt: %rdii: %rcxn: %rax |
262和263行實(shí)現(xiàn)了變量交換，264行增加循環(huán)計(jì)數(shù)值，雖然看起來(lái)比較奇怪，265行實(shí)現(xiàn)了b=a+t。然后做一個(gè)簡(jiǎn)單地比較，最后一個(gè)跳轉(zhuǎn)指令跳到循環(huán)開始出繼續(xù)執(zhí)行。
手動(dòng)反編譯以上代碼，代碼看起來(lái)是這樣的：
1 2 3 4 5 | loop: t = a a = b i = i+1 b = a+t if(n > i) goto loop |
整個(gè)內(nèi)部循環(huán)僅用六條X86-64匯編指令就實(shí)現(xiàn)了（很可能內(nèi)部微指令個(gè)數(shù)也差不多。譯者注：Intel X86-64處理器會(huì)把指令進(jìn)一步翻譯成微指令，所以CPU執(zhí)行的實(shí)際指令數(shù)要比匯編指令多）。CPython解釋模塊對(duì)每一條高層的指令字節(jié)碼至少需要六條甚至更多的指令來(lái)解釋，相比而言，C語(yǔ)言完勝。除此之外，還有一些其他更微妙的地方。
拉低現(xiàn)代處理器執(zhí)行速度的一個(gè)主要原因是對(duì)于主存的訪問(wèn)。這個(gè)方面的影響十分可怕，在微處理器設(shè)計(jì)時(shí)，無(wú)數(shù)個(gè)工程時(shí)（engineering hours）都花費(fèi)在找到有效地技術(shù)來(lái)“掩藏”訪存延時(shí)。通用的策略包括：緩存、推測(cè)預(yù)取、load-store依賴性預(yù)測(cè)、亂序執(zhí)行等等。這些方法確實(shí)在使機(jī)器更快方面起了很大作用，但是不可能完全不產(chǎn)生訪存操作。
在上面的匯編代碼中，從沒(méi)訪問(wèn)過(guò)內(nèi)存，實(shí)際上變量完全存儲(chǔ)在CPU寄存器中。現(xiàn)在考慮CPython：所有東西都是堆上的對(duì)象，而且所有方法都是動(dòng)態(tài)的。動(dòng)態(tài)特性太普遍了，以至于我們沒(méi)有辦法知道，a+b執(zhí)行integer_add(a, b)、string_concat(a, b)、還是用戶自己定義的函數(shù)。這也就意味著很多時(shí)間花在了在運(yùn)行時(shí)找出到底調(diào)用了哪個(gè)函數(shù)。動(dòng)態(tài)JIT運(yùn)行時(shí)會(huì)嘗試在運(yùn)行時(shí)獲取這個(gè)信息，并動(dòng)態(tài)產(chǎn)生x86代碼，但是這并不總是非常直接的（我期待V8運(yùn)行時(shí)會(huì)表現(xiàn)的更好，但奇怪的是它的速度只是Python的0.5倍）。因?yàn)镃Python是一個(gè)純粹的翻譯器，在每個(gè)循環(huán)迭代時(shí)，很多時(shí)間花在了解決動(dòng)態(tài)特性上，這就需要很多不必要的訪存操作。
除了以上內(nèi)存在搞鬼，還有其他因素?，F(xiàn)代超標(biāo)量亂序處理器核一次性可以取好幾條指令到處理器中，并且“在最方便時(shí)”執(zhí)行這些指令，也就是說(shuō)：鑒于結(jié)果仍然是正確的，指令執(zhí)行順序可以任意。這些處理器也可以在同一個(gè)時(shí)鐘周期并行執(zhí)行多條指令，只要這些指令是不相關(guān)的。Intel Sandy Bridge CPU可以同時(shí)將168條指令重排序，并可以在一個(gè)周期中發(fā)射（即開始執(zhí)行指令）至多6條指令，同時(shí)結(jié)束（即指令完成執(zhí)行）至多4條指令！粗略地以上面斐波那契舉例，Intel這個(gè)處理器可以大約把28（譯者注：28*6=168）個(gè)內(nèi)部循環(huán)重排序，并且?guī)缀蹩梢栽诿恳粋€(gè)時(shí)鐘周期完成一個(gè)循環(huán)！這聽起來(lái)很霸氣，但是像其他事一樣，細(xì)節(jié)總是非常復(fù)雜的。
我們假定8條指令是不相關(guān)的，這樣處理器就可以取得足夠的指令來(lái)利用指令重排序帶來(lái)的好處。對(duì)于包含分支指令的指令流進(jìn)行重排序是非常復(fù)雜的，也就是對(duì)if-else和循環(huán)（譯者注：if-else需要判斷后跳轉(zhuǎn)，所以必然包含分支指令）產(chǎn)生的匯編代碼。典型的方法就是對(duì)于分支指令進(jìn)行預(yù)測(cè)。CPU會(huì)動(dòng)態(tài)的利用以前分支執(zhí)行結(jié)果來(lái)猜測(cè)將來(lái)要執(zhí)行的分支指令的執(zhí)行結(jié)果，并且取得那些它“認(rèn)為”將要執(zhí)行的指令。然而，這個(gè)推測(cè)有可能是不正確的，如果確實(shí)不正確，CPU就會(huì)進(jìn)入復(fù)位模式（譯者注：這里的復(fù)位不是指處理器reset，而是CPU流水線的復(fù)位），即丟棄已經(jīng)取得的指令并且重新開始取指。這種復(fù)位操作有可能對(duì)性能產(chǎn)生很大影響。因此，對(duì)于分支指令的正確預(yù)測(cè)是另一個(gè)需要花費(fèi)很多工程時(shí)的領(lǐng)域。
現(xiàn)在，不是所有分支指令都是一樣的，有些可以很完美的預(yù)測(cè)，但是另一些幾乎不可能進(jìn)行預(yù)測(cè)。前面例子中的循環(huán)中的分支指令——就像反匯編代碼中267行——是最容易預(yù)測(cè)的其中一種，這個(gè)分支指令會(huì)連續(xù)向后跳轉(zhuǎn)100,000,000次。
以下是一個(gè)非常難預(yù)測(cè)的分支指令實(shí)例：
1 2 3 4 5 6 7 8 9 10 11 | 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ī)的（事實(shí)上在C語(yǔ)言中遠(yuǎn)非如此），那么對(duì)于if-else的預(yù)測(cè)還不如隨便猜來(lái)的準(zhǔn)確。幸運(yùn)的是，大部分的分支指令沒(méi)有這么頑皮，但是也有很少一部分和上面例子中的循環(huán)分支指令一樣變態(tài)。
回到我們的例子上：C代碼實(shí)現(xiàn)的斐波那契數(shù)列，只產(chǎn)生一個(gè)非常容易預(yù)測(cè)的分支指令。相反地，CPython代碼就非常糟糕。首先，所有純粹的翻譯器有一個(gè)“分配”循環(huán)，就像下面的例子：
1 2 3 4 5 6 7 8 9 | 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 }} |
編譯器無(wú)論如何處理以上代碼，至少有一個(gè)間接跳轉(zhuǎn)指令是必須的，而這種間接跳轉(zhuǎn)指令是比較難預(yù)測(cè)的。
接下來(lái)回憶一下，動(dòng)態(tài)語(yǔ)言必須在運(yùn)行時(shí)確定如“ADD指令的意思是什么”這樣基本的問(wèn)題，這當(dāng)然會(huì)產(chǎn)生——你猜對(duì)了——更加變態(tài)的分支指令。
以上所有因素加起來(lái)，最后導(dǎo)致一個(gè)278.5倍的性能差距！現(xiàn)在，這當(dāng)然是一個(gè)很簡(jiǎn)單的例子，但是其他的只會(huì)比這更變態(tài)。這個(gè)簡(jiǎn)單例子足以凸顯低級(jí)靜態(tài)語(yǔ)言（例如C語(yǔ)言）在現(xiàn)代軟件中的重要地位。我當(dāng)然不是2013年里C語(yǔ)言最大的粉絲，但是C語(yǔ)言仍然主導(dǎo)著低級(jí)控制領(lǐng)域及對(duì)性能要求高的應(yīng)用程序領(lǐng)域。
聯(lián)系客服
