Fw: [請益] C語言memcpy()的效率問題

看板C_and_CPP作者 (kkk)時間11年前 (2014/04/09 11:10), 11年前編輯推噓8(8推 0噓 42→)
留言50則, 6人參與, 最新討論串1/2 (看更多)
※ [本文轉錄自 Soft_Job 看板 #1JHAVIT- ] 作者: kkkmode (kkk) 看板: Soft_Job 標題: [請益] C語言memcpy()的效率問題 時間: Wed Apr 9 09:52:15 2014 各位好, 我測試了一段程式,如下: #include <stdio.h> #define size 65536 void main(){ char source[size], destination[size]; int j; for(j=0; j<100000; j++) memcpy(destination, source, size); } 把size改成65535或65537執行速度大概會慢10倍(compiler沒設最佳化) 其他2的冪次方加減1也有此現象(例如1024改成1023或1025) 我覺得可能是cache沒命中造成的 但詳細的原因不是很清楚 如果各位知道原因的話請幫忙一下,謝謝 ****************************************************************** 補上編譯環境: IDE: code::blocks 13.12 compiler套件: TDM-GCC, v4.7.1, 32 bit 作業系統: windows 8.1 64 bit CPU: intel core-i3 2100 後來改在linux上測(也是沒有最佳化選項) 改變size(65536->65535),時間沒有差異 objdump也試過,我是輸入以下兩行指令: gcc -Wall -O0 -g main.c -o main.exe objdump -Sl --no-show-raw-insn main.exe > output.txt 但組語不熟且非常多行 看起來和亂碼一樣,所以投降了... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.44.11 ※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1397008338.A.77E.html
→
04/09 10:47, , 1F
有C&C++專版 這個本版似乎無關
04/09 10:47, 1F
※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: kkkmode (111.251.44.11), 04/09/2014 11:10:34
推
04/09 16:54, , 2F
我用你的code跑,在我筆電上,6553[567]都約0.22s(sys:0s)
04/09 16:54, 2F
→
04/09 16:55, , 3F
當然stdio.h換了string.h void改成int
04/09 16:55, 3F
→
04/09 16:57, , 4F
所以此現象應該跟OS或編譯器有關，memcpy的實作應該沒差
04/09 16:57, 4F
推
04/09 17:15, , 5F
有些 memcpy 的實作，記憶體有對齊的情況會用 SIMD 加速
04/09 17:15, 5F
→
04/10 00:14, , 6F
跟cache沒命中無關,跟memcpy實作有關.
04/10 00:14, 6F
→
04/10 10:54, , 7F
樓上可否提供參考資料? 很好奇速度會差異到10倍是如何實作
04/10 10:54, 7F
→
04/10 11:00, , 8F
起初有懷疑過實作,但看了一些src沒看出來,所以有點不解...
04/10 11:00, 8F
→
04/10 11:04, , 9F
因實際實驗不出原PO的結果,猜想應是整體環境不同所致
04/10 11:04, 9F
推
04/10 13:32, , 10F
看組合語言就會有答案。或至少要告訴我們是哪一種平台
04/10 13:32, 10F
推
04/10 14:29, , 11F
04/10 14:29, 11F
→
04/10 14:31, , 12F
多數內建的 memcpy 在有對齊的情況下，會用 SIMD 來做
04/10 14:31, 12F
→
04/10 14:31, , 13F
做測試時可以考慮完全關閉編譯器最佳化 :P 看看數字如何
04/10 14:31, 13F
→
04/10 14:32, , 14F
然而使用了 SIMD 也很難快到 10 倍...還是看組語最清楚
04/10 14:32, 14F
→
04/10 20:04, , 15F
objdump
04/10 20:04, 15F
※ 編輯: kkkmode (1.160.87.36), 04/10/2014 21:14:41 ※ 編輯: kkkmode (1.160.87.36), 04/10/2014 21:16:11 ※ 編輯: kkkmode (1.160.87.36), 04/10/2014 21:17:48
推
04/11 01:33, , 16F
以glibc-2.19為例,x86的memcpy實作有i586(以下)及i686(以上),
04/11 01:33, 16F
→
04/11 01:33, , 17F
i686下還做了multiarch,除了原來的i686,另增SSSE3及SSSE3+REP,
04/11 01:33, 17F
→
04/11 01:33, , 18F
當做成shared library時,可在runtime時,才判斷用i686的哪一種,
04/11 01:33, 18F
→
04/11 01:34, , 19F
但若是編譯時用 static link, 則固定使用原來的i686實作.
04/11 01:34, 19F
→
04/11 01:34, , 20F
我將上述i586,i686,sssse3,ssse3+rep幾種實作各別獨立出來,
04/11 01:34, 20F
→
04/11 01:34, , 21F
在幾款CPU上執行原PO程式搭配不同size,得到下列執行時間:
04/11 01:34, 21F
→
04/11 01:34, , 22F
(CPU:E5410) (size:65535) (size:65536) (size:65537)
04/11 01:34, 22F
→
04/11 01:34, , 23F
i586 0m5.183s 0m1.488s 0m1.951s
04/11 01:34, 23F
→
04/11 01:35, , 24F
i686 0m8.779s 0m0.873s 0m4.951s
04/11 01:35, 24F
→
04/11 01:35, , 25F
ssse3 0m0.697s 0m0.671s 0m0.696s
04/11 01:35, 25F
→
04/11 01:35, , 26F
ssse3+rep 0m0.645s 0m0.873s 0m0.648s
04/11 01:35, 26F
→
04/11 01:35, , 27F
(CPU:i3-2130) (size:65535) (size:65536) (size:65537)
04/11 01:35, 27F
→
04/11 01:35, , 28F
i586 0m0.542s 0m0.519s 0m1.262s
04/11 01:35, 28F
→
04/11 01:35, , 29F
i686 0m0.539s 0m0.244s 0m0.679s
04/11 01:35, 29F
→
04/11 01:36, , 30F
ssse3 0m0.191s 0m0.319s 0m0.190s
04/11 01:36, 30F
→
04/11 01:36, , 31F
ssse3+rep 0m0.218s 0m0.203s 0m0.218s
04/11 01:36, 31F
→
04/11 01:36, , 32F
(CPU:i5-650) (size:65535) (size:65536) (size:65537)
04/11 01:36, 32F
→
04/11 01:36, , 33F
i586 0m0.837s 0m0.608s 0m0.640s
04/11 01:36, 33F
→
04/11 01:36, , 34F
i686 0m0.954s 0m0.222s 0m0.547s
04/11 01:36, 34F
→
04/11 01:36, , 35F
ssse3 0m0.208s 0m0.322s 0m0.208s
04/11 01:36, 35F
→
04/11 01:36, , 36F
ssse3+rep 0m0.211s 0m0.219s 0m0.211s
04/11 01:36, 36F
→
04/11 01:36, , 37F
在上述的E5410搭配i686實作,確實發生類似原PO所述的狀況;
04/11 01:36, 37F
→
04/11 01:37, , 38F
而稍早的glibc版本(ex:2.7),並無i686 multiarch的方式,
04/11 01:37, 38F
→
04/11 01:37, , 39F
且i586和i686的實作在進版時,也常有修改.
04/11 01:37, 39F
→
04/11 01:38, , 40F
怎樣的搭配,會發生原PO的情況,也許都需要實測才可得知吧.
04/11 01:38, 40F
推
04/11 01:58, , 41F
推樓上，這才是做事的態度，我們得多學著點！
04/11 01:58, 41F
推
04/11 02:12, , 42F
根據大家推測應該是 alignment 的問題, 我把原PO程式的
04/11 02:12, 42F
→
04/11 02:12, , 43F
char source[size], destination[size];
04/11 02:12, 43F
→
04/11 02:12, , 44F
修改為
04/11 02:12, 44F
→
04/11 02:13, , 45F
char data[65536*4];
04/11 02:13, 45F
→
04/11 02:13, , 46F
char *source=data, *destination=data+65536*2;
04/11 02:13, 46F
→
04/11 02:13, , 47F
重複同樣的測試, 結果時間大約都是 size:65536 那行時間
04/11 02:13, 47F
→
04/11 02:13, , 48F
正負 2% 之內. 所以我想 alignment 的推測相當合理;
04/11 02:13, 48F
→
04/11 02:13, , 49F
但有個疑問是, E5410搭ssse3+rep看來似乎很反常?
04/11 02:13, 49F
→
04/11 02:15, , 50F
回uid88, 我是因為不了解, 才用這樣的笨方法呀...
04/11 02:15, 50F
推
04/15 16:57, , 51F
推詳細的實驗
04/15 16:57, 51F
‣ 更多 kkkmode 的文章
文章代碼(AID): #1JHBehAh (C_and_CPP)
‣ 更多 kkkmode 的文章
文章代碼(AID): #1JHBehAh (C_and_CPP)