標題雖然是打 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 較特殊用法，這篇文章所提只是冰山一角，但限於主題關係，探討於此打住。
留言列表
開發手札 (2)
{{ article.title }}