加減乘除需多久? -- 估計C語言中基本運算所需的時間

隨著個人電腦的時脈不斷增加，同一個程式的執行速度也越來越快，但是你可有估計過，在現今 2GHz 的 CPU 上，執行一個C語言的加法指令要花多少時間? 而乘法、除法要花多少時間呢?

在 Jon Bentley 的經典著作 Programming Pearls 中，他給了一個範例程式 timemod.c (註1) 來估計計算所需的時間成本。他的方法是跑一個雙層 for 迴圈，在裡面執行各種運算，並計算所花費的時間。

我以一台2009年的個人電腦來做實驗，

CPU為 Intel Core 2 Quad Q8200，時脈為 2.33GHz，Cache大小如下:

  L1 Data Cache = 4*32 KBytes

  L1 Inst. Cache = 4*32 KBytes

  L2 Cache=2048 KBytes*2

編譯器為Visual C++ 2010 Express，Optimization選項全部關掉。

以下為列出各種運算的執行時間，單位均是奈秒(nanosecond):

C Time Cost Model, n=5000

Integer Arithmetic (n=5000)

 {}                    44    44    45    44    45     1.8

 k++                   60    59    57    55    57     2.3

 k = i + j             65    65    65    65    65     2.6

 k = i - j             65    65    65    65    65     2.6

 k = i * j             64    65    65    65    64     2.6

 k = i / j            106   102   100   100    91     4.0

 k = i % j            114   101   100   100   100     4.1

 k = i & j             65    65    65    64    65     2.6

 k = i | j             65    65    65    65    64     2.6

首先看整數運算，先看最上面的藍色底色部分，{}是指兩層空迴圈所消耗的時間。前面五個數字是執行n^2=25000000次花的時間(milliseconds)，一共執行五次，最後面的數字是統計這五次執行總共花費的時間，計算每次迴圈內部所花的時間(nanoseconds)。

第二行是在迴圈中放入單一的指令 k++，由最後的數字可知迴圈內部花費了 2.3-1.8 = 0.5 nanoseconds(ns)。相較於 Bentley 的結果是45倍的速度!

接下來是加法和減法，一個指令花費約 0.8ns。令我有點驚訝的是乘法和加法一樣快。至於除法也很快，一個的花費是 2.2ns，不過是加法的 2.75 倍而已。取餘數和除法幾乎相同。

Floating Point Arithmetic (n=5000)

 fj=j;                 87    87    88    87    89     3.5

 fj=j; fk = fi + fj;   87    86    86    86    86     3.4

 fj=j; fk = fi - fj;   87    86    86    86    86     3.4

 fj=j; fk = fi * fj;   88    87    88    88    88     3.5

 fj=j; fk = fi / fj;  216   215   215   215   215     8.6

浮點數加、減、乘法花費 1.6ns。

Array Operations (n=5000)

 k = i + j             65    65    65    64    64     2.6

 k = x[i] + j          75    75    76    75    75     3.0

 k = i + x[j]          75    75    76    75    76     3.0

 k = x[i] + x[j]       88    86    86    86    86     3.5

Comparisons (n=5000)

 if (i < j) k++        70    70    70    70    70     2.8

 if (x[i] < x[j]) k++  86    86    75    96    86     3.4

原本以為 if 很慢，沒想到只花了 2.8-2.3 = 0.5 ns。

Array Comparisons and Swaps (n=5000)

 k = (x[i]<x[k]) ? -1:1  119   120   119   120   119  4.8

 k = intcmp(x+i, x+j)    141   140   140   140   140  5.6

 swapmac(i, j)           131   131   131   131   131  5.2

 swapfunc(i, j)          224   226   224   217   231  9.0

Max Function, Macro and Inline (n=5000)

 k = (i > j) ? i : j   91    92    92    93    92     3.7

 k = maxmac(i, j)      97    97    97    97    97     3.9

 k = maxfunc(i, j)    184   185   185   185   185     7.4

Math Functions (n=1000)

 fk = j+fi;             3     2     2     3     3     2.6

 k = rand();           27    27    27    27    27    27.0

 fk = sqrt(j+fi)       24    23    23    24    24    23.6

 fk = sin(j+fi)        44    44    44    44    44    44.0

 fk = sinh(j+fi)      475   476   475   474   475   475.0

 fk = asin(j+fi)       60    60    60    60    60    60.0

 fk = cos(j+fi)        44    44    45    44    45    44.4

 fk = tan(j+fi)        56    59    55    56    56    56.4

Memory Allocation (n=500)

 free(malloc(4000));    85    83    85    84    85   337.6
 free(malloc(16000));   83    83    83    82    83   331.2
 free(malloc(64000));   97    97    98    97    96   388.0
 free(malloc(128000));  94    95    94    94    93   376.0
Secs: 18.17

記憶體配置花費的時間和大小有關，在16KBytes以下需要花費約340ns，在128KBytes左右增加為380ns。

參考資料

[1] 關於此程式的詳細說明，請見 Programming Pearls 的附錄3