標題雖然是打 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 的頭像
edisonx

Edison.X. Blog

edisonx 發表在 痞客邦 留言(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 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼