作者littleshan (我正在想要換什麼)
看板C_and_CPP
標題Re: [問題] 兩層for迴圈的效果
時間Sat May 27 00:53:01 2017
實驗最快
#include <stdio.h>
#include <stdint.h>
inline uint64_t rdtsc(
void)
{
uint32_t hi, lo;
asm volatile (
"rdtsc" :
"=a"(lo),
"=d"(hi));
return ((
uint64_t)lo) | (((
uint64_t)hi)<<
32);
}
uint64_t calc(
uint64_t outer,
uint64_t inner)
{
uint64_t s =
0;
for(
uint64_t i =
1; i <= outer; ++i){
for(
uint64_t j =
1; j <= inner; ++j){
s += i*j;
}
}
return s;
}
int main()
{
uint64_t t0 = rdtsc();
uint64_t sum1 = calc(
100ul,
1000000ul);
uint64_t t1 = rdtsc();
uint64_t sum2 = calc(
1000000ul,
100ul);
uint64_t t2 = rdtsc();
printf(
"sum1 = %lu, used %lu cycles\n", sum1, t1-t0);
printf(
"sum2 = %lu, used %lu cycles\n", sum2, t2-t1);
return 0;
}
使用 gcc 6.3 用 -O2 編譯
執行環境 Linux 4.9.18 with Intel Core i5-7260U
結果:
sum1 = 2525002525000000, used 356 cycles
sum2 = 2525002525000000, used 2633286 cycles
造成這樣差異的原因,是 gcc 把 calc() 函式直接 inline
然後展開內層迴圈的運算結果
第一個 function call 轉為 asm 後長這樣:
movabsq $
500000499999, %
rdx
movq %
rdx, %
rdi
.p2align 4,,
10
.p2align 3
.L15:
leaq (%
rdx,%
rax), %
rcx
addq $
1, %
rax
addq %
rdi, %
rdx
addq %
rcx, %
rsi
cmpq $
101, %
rax
jne .L15
看起來有點複雜,翻回 C 就是這樣:
rax =
1;
rdx =
500000499999;
do{
rcx = rdx + rax;
rdx +=
500000499999;
sum += rcx;
rax++;
}
while(rax !=
101);
我不知道為什麼不直接加 500000500000 就好,不過這不是重點
重點是這樣迴圈只跑了 100 次
相較於第二個 function call,同樣的展開方式迴圈會跑 1000000 次
當然是第一種方式比較快,而且也很剛好差了一萬倍左右
不過這一切都取決於 compiler 最佳化
未來會不會不管怎麼呼叫都直接在 compile time 算出答案給你,其實很有可能
到時候兩種作法就一樣快了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.25.242.143
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1495817584.A.C52.html
1F:推 Hazukashiine: 推實驗精神 05/27 01:18
2F:推 mh2ant: 好猛 05/27 11:49
3F:推 cuteSquirrel: 推 動手做! 05/27 19:34
4F:推 shadow0326: 推 05/28 13:16
5F:推 xxxx9659: 好猛!! 06/04 14:49