標題雖然是打 Struct Array Hacker,實際上是和 struct 特性較相關一點。這裡要講的主要有四項

 

1. memcpy 複制陣列。

2. memmove / memcpy 差異。

3. 偷用 struct 做 array assigned。

4. 談談 memcpy / memmove source code。

 

1. 善用 memcpy


一般初學者在 array assigned 上,容易有誤解。看一下下面程式碼

 

int x[N], y[N];
y = x; /* Take a error */

 

當然必須逐一 assigned 動作

 

int i, src[N], des[N];
for(i=0; i<N; ++i)
    des[i] = src[i];

 

就語法上,有可以不要逐一 assigned 的方法嗎?有,而且方法不只一種。

對基本資料型態(POD)而言,事實上可以直接調用 sstring.h 裡之 memcpy 或 memmove 即可

( 以這例子為例,即使調用 memmove,實際上還是在間接呼叫 memcpy );

C++ 可引入 header - algorithm,調用 copy。

 

以 memcpy 為例,我們可以這麼做

 

memcpy((void*)des,(const void*)src, sizeof(src));

 

 實際上它也可以用到二維裡面去

 

int des[N][M], src[N][M];
memcpy((void*)des,(const void*)src, sizeof(src));

 

這裡只需注意一件事,在於第三個參數,若 src 本身是用 malloc / new 產生,資料型態為 pointer,第三個參數就不能用 sizeof 去計算大小,必須用人工方式計算,如 sizeof(src[0][0]) * M * N。 上述之 src[0][0],是假設 src 宣告是 Type ** src ,Type 可為任意 POD / struct 型態;而若只是宣告 Type* src 時,只需用 src[0] 即可。

 

2. memmove / memcpy 差異

 

 在某些情況下,我們可能會想要對同一份 array,做資料搬移的動作。假設 int arr[6],這些搬移的動作,分四種情況討論

 

1. arr[0:2] 搬到 arr[3:5]

範圍沒重疊,可以直接用 memcpy。

 

2. arr[3:5] 搬到 arr[0:2]

範圍沒重疊,可以直接用 memcpy。

 

3. arr[0:3] 搬到 arr[2:5]

有問題就從這裡開始了,假設 arr[] = {1,2,3,4,5,6},搬完後的結果希望變成 arr [] = {1,2,1,2,3,4}

如果從前面搬到後面的話,會變成

arr[2] = arr[0]  , arr[] = {1,2,1,4,5,6 } ----> 原本的 arr[2] 被蓋掉了
arr[3] = arr[1]  , arr[] = {1,2,1,2,5,6 } 
arr[4] = arr[2]  , arr[] = {1,2,1,2,1,6 } ----> 原本的 arr[2] 被蓋掉了,故 arr[4] 拿到的就不是原本的 arr[2]
arr[5] = arr[3]  , arr[] = {1,2,1,2,1,2 }

最後拿到的結果是 arr[] = {1,2,1,2,1,2},和預期的 {1,2,1,2,3,4} 不同。這種狀況必須由後往前搬才行,即順序為

arr[5] = arr[3]  , arr[] = {1,2,3,4,5,4}
arr[4] = arr[2]  , arr[] = {1,2,3,4,3,4}
arr[3] = arr[1]  , arr[] = {1,2,3,2,3,4}
arr[2] = arr[0]  , arr[] = {1,2,1,2,3,4}

 

4. arr[2:5] 搬到  arr[0:3]

從上述分析方式,這次必須由前往後搬,才可確保其正確性。


上面四種狀況裡,同一塊 array 裡若要進行搬移,只有前二種是保證正確的,第三種是必須由後往前搬,第四種必須由前往後搬,但 memcpy 並沒規定一定要由前到後,或是由後到前,但其方向性會是固定的,意指 3.4 之情況,memcpy 至少會出錯一種情況,即, memcpy 並不保證其正確性。而 memmove 便保證了上面四種情況之正確性。可合理推斷,在 memmove source code 裡面,也可能偷用了 memcpy ,因其作用只是多了一些 condition 判斷。


3. 偷用 struct 做 array assigned

 

還記得 struct 有什麼特性嗎?先看一段 source code。

 

#include <stdio.h>
typedef struct tagstudent{int chi, eng, math;}student;
int main()
{
    student edisonx = {100,99,98};
    student cougar = edisonx;
    printf("edisonx : %d%d%d\n", 
            edisonx.chi, edisonx. eng, edisonx.math);
    printf("cougar : %d%d%d\n", 
            cougar.chi, cougar.eng, cougar.math);
    return 0;
}

 

最後結果,cougar 之成員和 edisonx 成員內容變一樣。

它的特性是,允許直接對 struct 做 assign ,裡面的成員會逐一複製過去,

很巧的是,這特性也適用在裡面含有靜態陣列。應用這特性,一段範例碼如下述。

 

#include <stdio.h>
#define N 3
#define M 5
typedef struct tagarray1{int arr[N];  }array1; // 一維陣列
typedef struct tagarray2{int arr[N][M];}array2;// 二維陣列
int main()
{
    size_t i, j, cnt=0U;
    array1 a = {1,2,3};
    array1 b = a; // a assigned to b , 1 dim
    array2 c = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    array2 d = c;
    
    // display b
    for(i=0; i<N; ++i)
        printf("%d", b.arr[i]);
    puts("\n");
    // display d
    for(i=0; i<N; ++i){
        for(j=0; j<M; ++j)
            printf("%d", d.arr[i][j]);
        puts("");
    }
    return 0;
}

 

 

上面 array 部份完成沒有用 loop 去逐一 assigned,但不論是一維還是多維陣列,包成 struct 裡後就整個複制過去。

事實上這方法使用並不會非常方便,有幾個缺點

 

1. 必須是靜態陣列。

2. 要存取陣列元素時顯得麻煩。


針對第二個缺點,有個簡單的小技巧可以改善,便是直接再設一 pointer,綁定在 struct 裡之 array 成員身上,上述的程式碼便可修改如下。

 

#include <stdio.h>
#define N 3
#define M 5
typedef struct tagarray1{int arr[N];  }array1; // 一維陣列
typedef struct tagarray2{int arr[N][M];}array2;// 二維陣列
int main()
{
    size_t i, j, cnt=0U;
    array1 a = {1,2,3};
    array1 b = a; // a assigned to b , 1 dim
    array2 c = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    array2 d = c;

    int *ptr_b      = b.arr;  /* ptr_b binds b.arr */
    int (*ptr_d)[M] = d.arr;  /* ptr_d binds d.arr */
    
    // display b
    for(i=0; i<N; ++i)
        printf("%d", ptr_b[i]);
    puts("\n");
    // display d
    for(i=0; i<N; ++i){
        for(j=0; j<M; ++j)
            printf("%d", ptr_d[i][j]);
        puts("");
    }
    return 0;
}

 

 此後便可使用 ptr_b 和 ptr_d 對陣列進行修改即可。上述 ptr_b、ptr_d ,較好的作法應是要加上 const  (const pointer to object)做為修飾,宣告並定義,變成了

 

int  * const ptr_b     = b.arr;
int (* const ptr_d)[M] = d.arr;

 

 

關於 const 修飾問題實為繁雜,此文不多加探討。

 

 4. memcpy / memmove source


memcpy / memmove 基本上並不怎麼需要自己寫,目前所有 compiler 所提供的這二個函式速度都很快,一般大多是用組語完成,且會做適當 restricted 保護,筆者也納悶,為何在 C / C++ 裡還有需求要加快 memcpy 函式。

言歸正傳,一般在網路上找到的 code 少數是逐一 byte 慢慢複製。

 

void* memcpy( void * destination, const void * source, size_t num )
{
    byte *Src=(byte*)source;
    byte *Des=(byte*)destination;
    while(size) {
        *Des++ = *Src++;
        --size;
    }
    return destination;
}

 

這種方式速度極慢,大多還是會考慮到,其實可以先一次4bytes複製,剩下的再逐一複製即可。而 4 bytes 之資料型態,可考慮用 unsigned (其實較好的選擇是 unsigned long),程式碼粗寫如下。

 

typedef unsigned char byte;
typedef unsigned int  word;
void* memcpy( void * destination, const void * source, size_t num )
{
    word *Wsrc_s  = (word*)source;
    word *Wdes_s  = (word*)destination;
    byte *Bsrc_s;
    byte *Bdes_s;
    // 處理 4 bytes
    while(num>4){
        *Wdes_s++ = *Wsrc_s++;
        num-=4;
    }
    // 處理 < 4 bytes
    Bsrc_s = (byte*)(Wsrc_s);
    Bdes_s = (byte*)(Wdes_s);
    while(num) {
        *Bdes_s++ = *Bsrc_s++;
        --num;
    }
    return destination;
}

 

這是一般能 google 到的解法,基本上有用到 4 bytes 一次複製概念,會被 compiler opt. 機會極高,速度其實也不慢了,而 memmove 也是類似手法,只是分幾種狀況在討論罷了。

 

void * xmemmove ( void * destination, const void * source, size_t num )
{
    size_t i;
    if( (word)destination < (word)source ) {
        return xmemcpy(destination, source, num);
    }

    if( (word)destination % sizeof(word) ==0U &&
        (word)source % sizeof(word) ==0U &&
        num % sizeof(word)==0U
        ) { // front to back, 
            word* des = (word *)destination;
            word* src = (word *)source;

            for(i=num/sizeof(word); i; --i)
                *des++ = *src++;
    } else { // back to front
        word* des = (word *)destination;
        word* src = (word *)source;
        for(i=num; i; --i)
            des[i-1] = src[i-1];
    }
    return destination;
}

 

對 memcpy 而言,另一種較 kuso 的方式,最近剛好在 ptt 裡面發表,便是利用 struct 之特性。我們知道若用 struct 進行複製的話,可以一整個 array 都丟過去,如果我們一次將 struct 弄成 1024 Bytes,相對的也是一次 1024 Bytes 都丟過去。於是便有種想法,假設 struct 其大小給1024 bytes,這樣便可一次丟 1024 bytes 過去 (有盲點,稍後討論),速度應會「飛快」才對。

這裡實作是設 3 種 struct 大小,假設 unsigned int 佔 4 bytes,分別為 4096 bytes、1024 bytes、256 bytes,接下來再轉交由 unsigned int、unsigned char 方式複製。

 

typedef unsigned char byte;
typedef unsigned int  word;
typedef struct  tagxT64U_ {word trunk[64];    }T64U_;
typedef struct tagxT256U_ {word trunk[256];   }T256U_;
typedef struct tagxT1024U_{word trunk[1024];  }T1024U_;

void * xmemcpy  ( void * destination, const void * source, size_t num )
{    
    if(destination!=source) {
        size_t n;
        T1024U_ *t0_src, *t0_des;
        T256U_ *t1_src, *t1_des;
        T64U_  *t2_src, *t2_des;
        word   *t3_src, *t3_des;
        byte   *t4_src, *t4_des;

        n = num / sizeof(T1024U_);
        num %= sizeof(T1024U_);
        t0_src = (T1024U_ *)source;
        t0_des = (T1024U_ *)destination;    
        while(n--) *t0_des++ = *t0_src++;
        
        n = num / sizeof(T256U_);
        num %= sizeof(T256U_);
        t1_src = (T256U_ *)t0_src;
        t1_des = (T256U_ *)t0_des;        
        while(n--) *t1_des++ = *t1_src++;

        n = num / sizeof(T64U_);
        num %= sizeof(T64U_);
        t2_src =  (T64U_ *)t1_src;
        t2_des =  (T64U_ *)t1_des;
        while(n--) *t2_des++ = *t2_src++;

        n = num / sizeof(word);
        num %= sizeof(word);
        t3_src = (word *)t2_src;
        t3_des = (word *)t2_des;
        while(n--) *t3_des++ = *t3_src++;

        n = num;
        t4_src = (byte *)t3_src;
        t4_des = (byte *)t3_des;
        while(n--) *t4_des++ = *t4_src++;
    }
    return destination;
}

 

 

struct 遞減之大小,實際上可再思考一下,要設哪幾組比較合適 ( 像 1024 那組,最多只會跑 3 次;256 那組,最多也只會跑 3 次 )。

有興趣可跑跑看它的效果如何,的確是比網路上流傳的只轉 4 bytes 方式快,但普遍之情況下,還是打不過 memcpy。

上述方式雖然看起來像是  4096 -> 1024 -> 256 -> 4 -> 1  依序下來處理,但實際上在搬移時,我們不知道它到底是怎麼做的,因規格書中並沒有明文規定,struct 裡面之 data member 該如何進行複製,頂多也只能由 coder 自行猜測,但較可以確定的是,它一次還是只複製 4 bytes,只是複製的細節不知道,它的確也可能一次複製超過 4 bytes (暫存器 bytes 數),但無法確定,就莫名的快而已。

真正一次要複製 4 bytes 以上之方法,應是調用 sse2 裡之暫存器 ( "目前" 應是 16 bytes),但這種作法並不具可攜性。sse2 在不考量 restricted情況下,此種實作方式據稱可比 memcpy 還快,但用 C 實作下來之結果,欲複製 byte 數不論是大 ( 1GB ) 或小 ,並沒以 struct hacker 方式來得快。有興趣可 下載 xmemcpy (rar) 筆者第一份 memcpy 版本做測試與比較。推測,sse2 暫存器方式,應需以 asm 撰碼,速度才可能跑得出來。

 

對於 struct 較特殊用法,這篇文章所提只是冰山一角,但限於主題關係,探討於此打住。

edisonx 發表在 痞客邦 PIXNET 留言(2) 人氣()


留言列表 (2)

發表留言
  • novus
  • 1. 據我所知,有些版本比較新的 C library 已經採用 SSE2 之類的指令來實作。

    2. 你的一次 4 byte 版本還有一些潛在的改進空間,像是 loop unrolling 還有處理 memory alignment,如果改一改應該是不會比內建的 memcpy 慢才對(假設你用的 c library 使用傳統方法實作),而且應該會比其他的鳥技法還快。

    3. 我猜你 SSE2 之所以表現不佳,是因為沒有處理 memory alignment。抱歉我懶得看程式碼,猜錯勿怪。

    4. 其他沒建設性的話我就不多說了,總之如果你對編譯器和硬體有點常識,就會曉得用 struct 做這種事意義不大...
  • 先謝謝 novus 指正與回覆,上面前二點我非常讚同,下面為一些補充,與想請教的問題。

    (2) 實際上在用時會先以 bitwise 技巧計算 #loop (如下程式碼),但不知是否還有哪些地方可展開來?還是您指的是 Duff's Device ?

    for (nLoop = n>>2 ; nLoop; --nLoop) *des4++=*src4++;
    for (nLoop = n&3 ; nLoop; --nLoop) *des1++=*src1++;

    (3) 想了一下才想到你說的問題,但請問一下,處理 alignment 是去對齊到 16 的倍數嗎??

    (4) 關於 struct 問題,我知道實際上還是只使用 32 bits 暫存器慢慢丟,翻成組語也都是用同一個指令 : mov,或許得到這結果,只能說明我在 4 bytes 那裡處理的不好,並不能說明 實際上用 struct 處理可以得到更好的效果,這點也感謝您特別再點出。

    edisonx 於 2012/03/21 17:56 回覆

  • novus
  • GCC4 的 sse intrinsics 要引用 xmmintrin.h,編譯時要加選項 -msse -msse2。這兩個選項還會促使 GCC 主動找尋有機會套用 SSE 的普通程式碼。

    舉例來說(我不保證這樣比較好),你的主要 loop 可以寫成

    num >>= 5;
    while (num) {
    dst32[0] = src32[0];
    dst32[1] = src32[1];
    dst32[2] = src32[2];
    dst32[3] = src32[3];
    dst32[4] = src32[4];
    dst32[5] = src32[5];
    dst32[6] = src32[6];
    dst32[7] = src32[7];
    dst32 += 8;
    src32 += 8;
    --num;
    }

    這樣連續複製了 8 個 word,才會更新 counter、檢查 branch 一次,執行的總指令數會少一點。常數的 offset 很容易被編譯器辨識出來,在 GCC 下用 -O3 -msse -msse2 編譯,通常就會被直接代換成 SSE2 指令

    如果還是慢很多,可能真的必須去微調組語指令,或者用 rep movsw 之類的指令改寫。

    最後補充,在GCC中 -O2、-O3、-msse2 這些不見得誰比誰快,要看程式和輸入資料的特性,-O2 比 -O3 快是常有的事,沒微調的 SSE2 code 有時後會有反效果。這些必須去實驗才能知道最好的選擇,一般來說只有確定有效的模組才會用 -O3 和 -msse2 編譯,其他用 O2 大概就夠了。
  • 學到不少,謝謝您的回覆指導,感激不盡!!

    edisonx 於 2012/03/21 23:48 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼