Re: [問題] 怎麼提高效率?

看板C_and_CPP作者tropical72 (藍影)時間12年前 (2012/03/18 23:43)推噓11(11推 0噓 22→)

留言33則, 8人參與討論串2/3 (看更多)

※ 引述《heymei0421 (heymei)》之銘言： : 小弟目前用ubuntu為作業系統 : 用google所提供的工具來量測performance : 好不容易搞了一個下午總算把程式中各函式所執行的時間百分比弄出來 : 如下圖: : http://ppt.cc/ueyv 我看不到這東西，請釋放權限。 : void : my_memcpy (void *target, void *source, int size) : { : int i; : unsigned char *target_ptr = target; : unsigned char *source_ptr = source; : for (i = 0; i < size; i++) : { : *(target_ptr + i) = *(source_ptr + i); : } : } 如果你可以用 memcpy 的話就用它，它的速度正常的話會比自己寫快上2~3倍不是問題，它放在 memory.h / string.h 裡面，不行調用的話才有必要自己寫。一般而言在寫低階動作時，若「去掉 compiler 優化能力」，有幾個部份是值得注意的， (i) 盡可能使用前置 (ii) 另一為盡可能減少陣列索引之計算 (iii) 程式碼可以展開的話就盡可能展開 (很可笑對吧 ? 但它是事實..) 所以你的程式碼暫修如下 typedef unsigned char byte; void cpy1(void* target, void* source, int size) { byte *Src=(byte*)source; byte *Des=(byte*)target; while(size) { *Des++ = *Src++; --size; } } 這樣就避開了計算 Des[i] / Src[i] 所需時間，如果要再快一點點的話，「考慮」要不要弄個非標準的做法。 void cpy2(void* target, void* source, int size) { byte *Src = (byte*)source; byte *Des = (byte*)target; byte *Src_End = (byte*)source + size; while(Src!=Src_End) /* 使用比較運算子取代了遞減運算子 */ *Des++ = *Src++; } 非標準的地方在於 byte *Src_End = (byte*)source + size; 正常而言，指標 + size 這動作並不保證，但大多 compiler (一些面試題也基於此假設) 是從 source 移動 size 個 byte 大小。會不會更快不一定，要去查「比較」和「遞減」所使用的週期數。截至目前為止，其實改的都只是小部份，但有個較大的部份沒改到，如果可以一次 4 bytes / 8 bytes 複制，速度會更快，多出來的部份再慢慢 1 bytes / 1 bytes 複制。這裡演示基於標準作法，要非標準的作法可再自己嚐試 void cpy3(void* target, void* source, size_t size) { word *Wsrc_s = (word*)source; word *Wdes_s = (word*)target; byte *Bsrc_s; byte *Bdes_s; // 處理 4 bytes while(size>4){ *Wdes_s++ = *Wsrc_s++; size-=4; } // 處理 < 4 bytes Bsrc_s = (byte*)(Wsrc_s); Bdes_s = (byte*)(Wdes_s); while(size) { *Bdes_s++ = *Bsrc_s++; --size; } } 基本上用到 4bytes 一次複製觀念速度就夠快了，另外有個比較 kuso 的方式你可以參考先建立一個 struct, 裡面直接丟 byte trunk[256], byte trunk[1024] 等 struct 做 assigned 時，裡面的 trunk 會直接複制，但速度怎樣將會相依於 compiler 實作之能力，會不會比較快不得而知，但以我手中 vc2010 , debug mode 下測，這方式是最快的 (開 256)，在 size 較大情況下，速度比你原本方式快 5 倍以上 (看 N 值)，但最終還是打不過 memcpy (記得它 "應" 是用組語寫的！) 完整的測試程式碼參考如連結 http://ppt.cc/a;Bv 結果如下參考。 N 787654321 cpy1 : 453 arr2=arr1 (check) --> memcpy cpy2 : 3610 arr2=arr1 (check) --> 逐一 copy cpy3 : 938 arr2=arr1 (check) --> 4 bytes 處理 cpy4 : 531 arr2=arr1 (check) --> struct 256 bytes 處理 cpy5 : 500 arr2=arr1 (check) --> struct 1024 + 256 + 4 bytes 處理。 vc 開 option 測時會很不準，懶得再用 gcc 測 (其實也懶得再看 .asm) 其實上面的 cpy4 / cpy5 還是有可改善空間，希望這些意見能給你一些幫助。 -- 2012.3.19 補充 (1) struct 裡面可以用 unsigned int trunk[] 取代 unsigned char turnk[], 速度理應會更快。 (2) struct trunk[size], size 大小其實可以調大一點，上面 1024 + 256 其實是不智的二個數字 (因為 256 最多也跑 4 次而已)，可以試試 4096 + 256，甚至試 8192 + 256, 最大調多大為佳, 和硬體 cache size, compiler 對於 struct member assigned 實作相依。 (3) 開 O2/O3 後 (gcc,vc都一樣), 其實逐一 assigned 和 memcpy 差不了多了。 2012.3.22 補充 (1) trace 結果發現 struct in C 有幾個特性, 一般 compiler 實作 struct S mem={0}，其實是呼叫 memset。 (2) 合理原因猜測，以 struct 包 array, 做 assigned 動作時，實際上 compiler 是自己再去呼叫 memcpy 出來做，故其實和直接呼叫 memcpy 沒什麼太大差別。 (3) 由於測時到近 1 G 時，測時時間也不到 1 秒，精度測時使用 clock() 過於不精準，換較高精度做計數。同時測時時，memcpy 不該再另包一層 function。另會看 asm 的人會發現，struct 包 array 方式，翻成組語後實際上還是在調用 mov 這東西，沒什麼太多技巧。補上較完整之結果與測試碼。 http://ppt.cc/5sid xmemcpy2.rar 。心得在裡面的文字檔有說明，特別是關於 duff's device 部份。 (4) 強調，本文並沒有針對 alignment 問題做處理，意思是如果沒 alignment 的話，程式碼會出包。即使不出包，效能也會變差。 -- 我知道 ~ 但別說出來 , 說出來讓人感到特別難過... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.195.165.40

推

heymei0421

03/18 23:47, , 1^F

03/18 23:47, 1^F

→

heymei0421

03/18 23:47, , 2^F

03/18 23:47, 2^F

推

QQ29

03/18 23:57, , 3^F

03/18 23:57, 3^F

→

QQ29

03/18 23:57, , 4^F

03/18 23:57, 4^F

推

heymei0421

03/18 23:59, , 5^F

03/18 23:59, 5^F

→

heymei0421

03/18 23:59, , 6^F

03/18 23:59, 6^F

測 profile 我記得有兩套常被拿來用, vs 有 performance Tool，intel 有 VTune 如果都不會用的話~分析一下演算法本身能不能將複雜度降低，降不下來的話~ 只有 300 行而已，將可以包出 function 的部份都用 clock() 做 wall time test, 不就知道效能卡在哪了嗎？話說剛 vc / gcc 開 O2 之後，其實你原本的寫法和 memcpy 根本差不了多少 (1G，859 / 1141)，要再改善的話能力有限。

推

littleshan

03/19 00:01, , 7^F

03/19 00:01, 7^F

推

QQ29

03/19 00:02, , 8^F

03/19 00:02, 8^F

考慮移植與速度問題後， memcpy 流傳的 code 基本上就是 cpy3， cpy4 / cpy5 目前我沒看別人用過，有問題的話也只可能是它們而已 (目前我是看不出有什麼問題)，「轉型」的話... 我想是在 caller 那裡處理的，和 memcpy 本身沒太大關係吧 Orz

推

littleshan

03/19 00:31, , 9^F