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

[WeBurn (燒)]

這比memcpy快 可以快個三到四倍，調用方法與memcpy一樣

不做restricted保護


#include <emmintrin.h> /*SSE2*/

#define DIV16(VAL)              ((VAL)>>4)
#define MUL16(VAL)              ((VAL)<<4)

#define MEMCPY( PDST, PSRC, SIZE)
                          sse2_memcpy( (PDST), (PSRC), (SIZE))


void sse2_memcpy(void *pDst, void *pSrc, size_t size)
{
        if(pDst == pSrc)
                return ;

        unsigned int i;
        unsigned int nLoops;

        char *pcDst, *pcSrc;
        __m128i *pMovSrc, *pMovDst;


        pMovDst = (__m128i*)(pDst);
        pMovSrc = (__m128i*)(pSrc);

        nLoops = DIV16((unsigned int)size);

        __m128i _miTemp;
        for(i = 0; i < nLoops; i++){
                _miTemp = _mm_loadu_si128(pMovSrc);
                _mm_storeu_si128( pMovDst, _miTemp);
                pMovDst++;
                pMovSrc++;
        }


        pcDst = (char*)(pMovDst);
        pcSrc = (char*)(pMovSrc);

        for(i = MUL16(nLoops); i< size; i++)
                *pcDst++ = *pcSrc++;

}/*sse_memcpy*/


※ 引述《tropical72 (藍影)》之銘言：
: ※ 引述《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 還是有可改善空間，希望這些意見能給你一些幫助。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.176.120.10
→ tropical72:這方法..不就和 cpy3 相仿？
→ jackace:差很多好嗎 他用到的是sse 128-bit暫存器
→ jackace:你用到甚麼struct 其實compiler都還是用32 bit暫存器copy
→ jackace:同樣copy 16個byte用128 bit站存器就是只要1個指令
推 tropical72:原來如此,謝謝j大說明。
→ jackace:不過就像我前一篇推文說的 用xmm有啟動時間的 若不是大區
→ jackace:塊 還是得用general purpose暫存器搬最快
※ 編輯: WeBurn          來自: 180.176.120.10       (03/19 03:45)
推 tropical72:#define MUL16(V) ((V)<<4) 一起補上吧。
※ 編輯: WeBurn          來自: 180.176.120.10       (03/19 04:12)
→ WeBurn:已補上
→ WeBurn:若要再狠一點，用匯編的LOOP指令
→ WeBurn:編譯器出來，都是用CMP + JZ, 用LOOP可以少個指令
→ WeBurn:該說每圈少個指令
推 heymei0421:謝謝大大們的熱心Orz
推 Slither:just curious: is loop faster than cmp/jcond?
→ Bencrie:幫翻譯：匯編 == 組語
→ jackace:那cmp+jz跟loop的差別其實已經不大 指令多少有時不是重點
→ jackace:每顆不同型號的cpu 每個指令所需的cycle都未必相同
→ jackace:如果真的在意那一點點差異的話 可以上intel把spec抓回來看
推 littleshan:要用 aligned move 才會快吧
→ WeBurn:輸入輸出的內存指針在能控制的情況下 當然要用對齊指令
→ WeBurn:若處理沒對齊的指針 還用了對齊的指令 一定當機
→ WeBurn:cmp + JZ會有分支 這樣會浪廢一些亂序運行引擎
→ WeBurn:LOOP就一直幹下去 沒分支 對CPU來說(core以後的)
→ WeBurn:算有差那一些
推 littleshan:截頭截尾 然後中間部份使用aligned access吧
→ littleshan:branch prediction對於這類loop有良好的表現
→ littleshan:所以cmp+jz與loop不會差太多
推 tropical72:多請教一問題，若暫存器是 16 bytes，那是不是先
→ tropical72:aligment 到 16 倍數，再處理，效果好些？
推 freelancer:work copy, alignment check, sse enhance，為什麼要
→ freelancer:搞一些明明glibc的memory copy 都已經用上的技巧呢？
→ freelancer:我相信vc 帶的library 也都幫你做完了
→ WeBurn:樓上 不要亂下斷言 VC是要在汎用下盡可能優化
→ WeBurn:但SSE2是 pentium3 所沒有的指令
→ WeBurn:測過就知道我所言是否為真 編譯器是程式 不是人
→ WeBurn:還是有極多眉角可以手工優化的
→ WeBurn:tropical72: 沒對齊用_mm_loadu_si128 指令
→ WeBurn:對齊用_mm_load_si128 效能更好
推 tropical72:謝謝 ^^
推 freelancer:ms 自已說的
→ freelancer:http://msdn.microsoft.com/en-us/library/26td21ds.as
→ freelancer:px
→ freelancer:另一篇vc 2005 就可以做到的事
→ freelancer:http://blog.codingnow.com/2005/10/vc_memcpy.html
→ freelancer:不是說去optimize memcpy 無用，是說應該從上層的架構
→ freelancer:先去看有沒有refine的機會，會比你在那optimize一個
→ freelancer:library 本來就做的很不錯的function 來的有價值
→ freelancer:當然最後沒招了，要改memcpy也是方法一，但不是一開始
→ WeBurn:MOVSD只有一次複製4byte......
→ WeBurn:我這是一次復製16byte.....