Re: [問題] 拆迴圈+效能測試

[littleshan (我要加入劍道社!)]

※ 引述《s3748679 (冷羽翼塵)》之銘言：
: → s3748679:@@a 因為這邊把迴圈拆了連i++和往回跳的動作都省啦~所以   10/13 20:49
: → s3748679:才會覺得在相同條件下會比較快就是了                     10/13 20:49
很合理的猜測
但你得要思考一下迴圈內做的事情
那就是從記憶體內讀取資料，然後存到另一塊記憶體內
除了 i++ 以及判斷迴圈成立條件之外沒有做任何事

所以其實最花時間的是記憶體搬移這件事
根據 Intel 的 Optimization Reference Manual
目前最主流的 Sandy Bridge 架構其 L1 cache latency 至少為 4 cycle
這遠大於 i++ 所需要花的時間
另一方面固定次數的 for 迴圈對 branch prediction 來說準確率非常高
因此迴圈的 branch 形成的額外成本並不高

反觀把迴圈拆開的版本
儘管少了 i++ 和 branch
但它的 code size 卻大幅成長
導致更多次的 instruction cache miss
迴圈內的工作已經是 memory intensive 而你還讓它雪上加霜 XD


再次得到算盤本是好物的結論

--
※ 發信站 :批踢踢實業坊(ptt.cc) 
◆ From: 118.168.56.96
推 ericinttu:只好來跪算盤了 (誤)
推 s3748679:來整理下: 1.branch prediction => i++ 所需要花的時間少
→ s3748679:2. code size太大 => cache miss(似乎是塞不進快取)
→ s3748679:嘿~剛挖一下wiki順便放上來好了~
→ s3748679:http://en.wikipedia.org/wiki/CPU_cache
→ s3748679:啊對~ 回樓主~ Thanks~ =ˇ=
推 VictorTom:推跪算盤XD
推 chchwy:推code size也是有locality呀
推 h9602b:推coding+算盤~~
推 h9602b:code size太大是一種,date size太大且存取不夠連續也是另一
→ h9602b:個cache miss的重大主因,前一陣子剛解過一個類似的問題,由
→ h9602b:物件中的某變數做sort,size二十幾萬,後來把存data的結構重
→ h9602b:寫,sort一樣是quicksort,時間從幾分鐘變成幾秒
→ h9602b:所以再次得證算盤是好物~~
推 tomap41017:請問算盤本是哪本啊?(我非本科系= =)
推 ericinttu:計算機組織的書, 白底, 封面有算盤.
→ ericinttu:很厚一本. 中英文的封面與頁數都差不多.
→ priv:感覺ericinttu應該也是老人了..
→ priv:因為第三版之後的國際版就沒算盤了XD
→ priv:而且頁數大幅度刪減，把材料移到光碟上去
推 stosto:白算盤要好好念阿
→ stosto:不過現在pipeline的數目是多少啊?
→ purincess:感覺應該還是有十幾二十個stage XD