C語言算法舉例分析

這篇文章主要介紹“C語言算法舉例分析”，在日常操作中，相信很多人在C語言算法舉例分析問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C語言算法舉例分析”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

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

用Python語言實現如下：

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語言實現如下：

#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; }

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

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

=======================================================   語言                               時間 (秒) =======================================================   Java                               0.133   C Language                         0.006   CPython                            0.534   Javascript V8                      0.284

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

=======================================================   語言                              時間（秒） =======================================================   Java                               0.300   C Language                         0.172   CPython                            47.909   Javascript V8                      24.179

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

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

為了找到問題的答案，我搬出了反匯編器，發現了以下現象：

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、不同的編譯器版本及不同的優化選項（-Ox）會產生不同的匯編代碼。

• 2、反匯編方法：gcc -g -O2 test.c -o test;objdumb -d test>test.txt  讀者可以自己嘗試變換優化選項對比反匯編結果）

最主要的部分是計算下一個斐波那契數值的內部循環：

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行實現了變量交換，264行增加循環計數值，雖然看起來比較奇怪，265行實現了b=a+t。然后做一個簡單地比較，***一個跳轉指令跳到循環開始出繼續執行。

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

loop:   t = a         a = b         ii = i+1         b = a+t         if(n > i) goto loop

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

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

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

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

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

現在，不是所有分支指令都是一樣的，有些可以很***的預測，但是另一些幾乎不可能進行預測。前面例子中的循環中的分支指令——就像反匯編代碼中267行——是最容易預測的其中一種，這個分支指令會連續向后跳轉100,000,000次。

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

void main(void) {     for(int i = 0; i < 1000000; i++) {          int n = random();          if(n >= 0) {             printf("positive!\n");         } else {             printf("negative!\n");         }     } }

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

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

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     } }

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

到此，關于“C語言算法舉例分析”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！