code 有點長,這篇只是點出,有時大量 allocate 時可以考慮挖 pool 出來,但未必比較好用,比較難維護是真的,減少碎片化問題也是真的。

 

問題敘述 

 

這問題是網友提出的,原問題是問 C,範例拿掉用我舉的例子。 

我要舉的例子是 KMeans 演算法。假設有 DCNT 筆資料,每筆資料有 DIM 維度的屬性(屬性都是 double,沒有名目尺度這種東西),想要分成 K-clustering。所以要 allocate 的大概有下面這些東西。

 

Code Snippet
  1. const size_t DCNT = 1000;  // #data
  2. const size_t DIM  = 3;     // #dim of data
  3. const size_t K    = 12;    // #clustering
  4.  
  5. double data[DCNT][DIM];    // source data
  6.  
  7. double center[K][DIM];     // each center of clustering
  8. size_t center_cnt[K];      // #pt in each center
  9. double tmp_sum[DIM];       // temp. variable
  10.  
  11. double center_mse[K];      // mse in each clustering
  12. size_t pt_belongs_K[DCNT]; // each pt belongs which clustering

 

以上希望全都用 malloc 生成,另二維 heap 不以一維示之 (所以會有 pointer overhead)。

 

雖然它是一份 Solution, 但千千萬萬別這麼做

 

初始化 allocate 時,最最初學、最糟的寫法大概長如此。

 

Code Snippet
  1. const size_t DCNT = 1000;  // #data
  2. const size_t DIM  = 3;     // #dim of data
  3. const size_t K    = 12;    // #clustering
  4.  
  5. double **data, **center, *center_mse;
  6. size_t *center_cnt, *pt_belongs_K;    
  7. size_t k, dim, dcnt;
  8.  
  9. //////////////////////////////////////////////////////////////////////////
  10. // allocate double data[DCNT][DIM];
  11. if(! (data = (double**)malloc(sizeof(double*) * DCNT)))
  12.     return 0; // fail
  13. for(dcnt=0; dcnt<DCNT; ++dcnt)
  14.     if( !(data[dcnt] = (double*)malloc(sizeof(double) * DIM))) break;
  15.  
  16. if(dcnt!=DCNT){ // allocate in for loop
  17.     for(--dcnt; (int)dcnt>=0; --dcnt)
  18.         free((void*)data[dcnt]);
  19.     free(data);
  20.     return 0;
  21. }
  22.  
  23. //////////////////////////////////////////////////////////////////////////
  24. // allocate double center[K][DIM];
  25. if(! (center = (double**)malloc(sizeof(double*)*K))) {
  26.     for(dcnt=0; dcnt<DCNT; ++dcnt) free((void*)data[dcnt]);
  27.     free((void*)data);
  28.     return 0; // fail
  29. }
  30. /* ... other allocate... */

 

如上所見,由於每進行一次 allocate 時都要判斷是否成功,換句話說,如果失敗的話,要把之前所配置的記憶體全都清掉。上述用了很糟的方式,所以在 allocate 失敗、清記憶體時,會愈寫愈長。

 

我想這種 Solution 應可應付大多情況了吧

 

說到底這其實是源自於二維配置不佳的原因,二維配置之前小弟在  [HFC] Hidden Features of Array Management in C (I) 裡的 3. allocate memory for 2d 已有給出了一份已算是不錯的 solution,包含副函式後,大概可以這麼解決。

 

Code Snippet
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. void * new1d(const size_t Count, const size_t SizeOfEle){
  6.     return malloc(Count*SizeOfEle);
  7. }
  8. void** new2d(const size_t H,const size_t W,const size_t SizeOfEle)
  9. {
  10.     char *space1d, **space2d;
  11.     size_t i;
  12.  
  13.     space2d = (char **)malloc(sizeof(char*)*H+SizeOfEle*H*W);
  14.     if(!space2d)  return NULL;
  15.  
  16.     space1d = (char *)(space2d+H);
  17.     for(i=0; i<H; ++i){
  18.         space2d [i] = space1d;
  19.         space1d += (SizeOfEle * W);
  20.     }
  21.     return (void**)space2d;    
  22. }
  23.  
  24.  
  25. int main()
  26. {
  27.     const size_t DCNT = 1000;  // #data
  28.     const size_t DIM  = 3;     // #dim of data
  29.     const size_t K    = 12;    // #clustering
  30.  
  31.     double **data, **center, *center_mse;
  32.     size_t *center_cnt, *pt_belongs_K;    
  33.  
  34.     // double data[DCNT][DIM]
  35.     if (!(data = (double**)new2d(DCNT, DIM, sizeof(double)))) return 0;
  36.     // double center[K][DIM]
  37.     if( !(center = (double**)new2d(K, DIM, sizeof(double)))) {
  38.         free((void*)data); return 0;
  39.     }    
  40.     // double center_mse[K]
  41.     if( !(center_mse = (double*)malloc(sizeof(double) * K))){
  42.         free((void*)data); free((void*)center); return 0;
  43.     }
  44.     // size_t center_cnt[K]
  45.     if( !(center_cnt = (size_t*)malloc(sizeof(size_t) * K))){
  46.         free((void*)data); free((void*)center);
  47.         free((void*)center_mse); free((void*)center_mse);
  48.         return 0;
  49.     }
  50.     // size_t pt_belongs_K[DCNT]
  51.     if( !(pt_belongs_K = (size_t*)malloc(sizeof(size_t) * DCNT))){
  52.         free((void*)data); free((void*)center);
  53.         free((void*)center_mse); free((void*)center_mse);
  54.         free((void*)center_cnt);
  55.         return 0;
  56.     }    
  57.     /* do sometihing */
  58.     return 0;
  59. }

 

然後問題又來了,是不是只能那麼麻煩,每次 malloc 失敗後,又要從前面逐一 release 回來?

嗯,截至目前為止,我大概也會像上面寫成這樣吧,唯一有可議的情況是:記憶體需求很吃緊,這時候才會「考慮」使用下面手法。

 

我希望以後暫時別有機會寫到這種 "沒碎片化 (??)" 的Code

 

直接挖一大塊 pool,把所有該配置的都計算好,另需考慮每個 pointer alignment 到 4 的倍數。為避免程式碼太過於流水,只做前三項配置。

 

Code Snippet
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int main()
  6. {
  7.     const size_t DCNT = 1000;  // #data
  8.     const size_t DIM  = 3;     // #dim of data
  9.     const size_t K    = 12;    // #clustering
  10.  
  11.     double **data, **center, *center_mse;
  12.  
  13.     char   *pool;
  14.     double *trunk_double;
  15.  
  16.     size_t data_size, center_size, center_mse_size;
  17.     size_t t, k, dcnt;
  18.  
  19.     size_t offset[100]={0}, offset_n=1;
  20.     
  21.     //////////////////////////////////////////////////////////////////////////
  22.     // bytes of double data[DCNT][DIM]
  23.     t = (data_size = sizeof(double*)*DCNT + sizeof(double)*DCNT*DIM)>>2;
  24.     if(t<<2 != data_size) data_size = (t+1)<<2;
  25.     offset[offset_n] = data_size;
  26.     ++offset_n;
  27.  
  28.     // bytes of double center[K][DIM]
  29.     t = (center_size = sizeof(double*)*K + sizeof(double)*K*DIM)>>2;
  30.     if(t<<2 != center_size) center_size = (t+1)<<2;
  31.     offset[offset_n] = offset[offset_n-1] + center_size;
  32.     ++offset_n;
  33.  
  34.     // bytes of double center_mse[K]
  35.     t = (center_mse_size = sizeof(double) * K) >> 2;
  36.     if(t<<2 != center_mse_size) center_mse_size = (t+1)<<2;
  37.     offset[offset_n] = offset[offset_n-1] + center_mse_size;
  38.     ++offset_n;
  39.  
  40.     /* other calculation */
  41.     /*... */
  42.  
  43.     //////////////////////////////////////////////////////////////////////////
  44.     /* allocate memory */
  45.     pool = (char*)malloc(offset[offset_n-1]);    
  46.     if(!pool) return 0; // fail
  47.  
  48.     // double data[DCNT][DIM]
  49.     data = (double**)(pool+offset[0]);
  50.     trunk_double = (double*)(data+DCNT);
  51.  
  52.     printf("data : %08x\n", data);
  53.     printf("trunk_double : %08x\n", trunk_double);
  54.     for(dcnt=0; dcnt<DCNT; ++dcnt)
  55.         data[dcnt] = trunk_double, trunk_double+=DIM;
  56.  
  57.     // double center[K][DIM]
  58.     center = (double**)(pool+offset[1]);
  59.     trunk_double = (double*)(center+K);
  60.     for(k=0; k<K; ++k)
  61.         center[k] = trunk_double, trunk_double+=DIM;
  62.  
  63.     // double center_mse[K]
  64.     center_mse = (double*)(pool+offset[2]);
  65.  
  66.     //////////////////////////////////////////////////////////////////////////
  67.     // test
  68.     memset((void*)*data, 0, DCNT*DIM*sizeof(double));
  69.     memset((void*)*center, 0, K*DIM*sizeof(double));
  70.     memset((void*)center_mse, 0, K*sizeof(double));
  71.  
  72.     /* others...release */
  73.     free((void*)pool);
  74.     //////////////////////////////////////////////////////////////////////////
  75.     return 0;
  76. }

 

它是做出來了,雖然避開了一直重覆判斷 malloc 是否成功,但所付出之開發成本反而更為龐大,同時還不能忘記在 pool 裡當初給的順序 ( alignment 會影響)。至於它能不能包成較易使用之副函式?我想是可以的 (恕筆者目前沒強烈需求,沒再完整實作,有時間再附上),只是在呼叫端並不會顯得較容易,使用上「可能」不會讓人感到較便利。

 

我想可能有更好的方式

 

筆者,小弟不才,認為碎片化問題在此例,用一次 malloc 方式是有點走火入魔,下面是一些心得。

 

(1) 最麻煩的地方...

最麻煩的是在於有不斷的為 double** 這種東西建立起第一層 double * ,導致沒辦法用 for-loop 一次到位。若以一維表示二維時,pointer over-head 情況消除,上述問題可用簡單的一個 for-loop 完成,但計算每段 heap 所需大小之前置作業還是省不了。

另由於筆者還沒包副函式 (估用 struct 包會漂亮些),在 allocate 記憶體後,指來指去時,維護蠻不易的 (特別是筆誤的時候...)

 

(2) 有好處嗎?

通常用上述「建議」的程式碼,已可降低碎片化問題;但為了徹底解決碎片化問題,有沒有必要做成這樣,筆者是覺得,代價似乎有些高。但,畢竟這種 code 大概不會開出來給別人看,如果不是 team work ,個人當作練習倒是無妨。

 

(3) C++?

STL 原理剖析沒啃完,但對於這種判斷 malloc 失敗後續處理的問題, C++ vector 應已提供了一份不錯之 solution (bad_alloc),另外也可以自己弄出一份 struct,裡面包 vector< T > mVal,透過一些手法還可以直接操作 mVal[row][col],這裡就不再多述了。

不過對於一些 龜毛 coder,在 vector 丟出 bad_alloc 之後,會要求之前 resize 好之 vector,再用 vector::swap ,把記憶體徹底清空。至於有沒有辦法像上述去掉碎片化問題的話...,嗯,再說吧。

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


留言列表 (2)

發表留言
  • novus

  • 這裡的 cleanup 部分可以用 goto 來解決,包含 linux kernel 在內,很多軟體都有使用類似的手法。

    通常把原始函數分解成多個單一責任的函數會是更好的選擇,但這並不總是容易達成,也不一定更好理解或維護。

    由於 C 語言提供的機制比較原始,不管怎麼做都會發現維護上的難處。如果 goto 在某個場合是缺點最少的一種做法,就應該使用。

  • 看到你提到的 goto 我才想到 windows batch 常用到的 goto 技巧,這裡的 cleanup 想想,的確用 goto 會方便許多。

    以前在 C 看到的 goto 有兩種情況:一種是硬跳出深層回圈(不過這個不知道為什麼,很多人寧可設個 flag,每個 loop 加一個判斷,也不用 goto);另一種是 C 語言 state machine 之實作,一個 state 一個 label,goto 代表狀態轉移,缺點是只能實作較簡易之 state machine,維護不易,現在又看到第三種用法了。 謝謝您的指教 :)

    edisonx 於 2012/12/10 02:55 回覆

  • novus
  • 原始的程式語言就只有各種 goto (jump),後來為了避免不受限制的 goto 所帶來的危害,人們才發明各種高階控制結構來取代 goto。理論上分支、迴圈、副程式已經足以完全取代 goto 的功能,但所有實際寫過程式的人都知道,程式碼除了正確完成功能之外還有一大堆考量。

    有些高階語言還會提供 labeled break、異常處理流程等等,已經沒有太多理由使用 goto。

    但在純 C 底下有時候你就是沒有太多選擇,有時候你就是必須使用被別的程式語言認為很糟糕的東西,例如缺乏 type safety 的 void*、指標算數、不定引數函數、union 等等。先放下對 goto 的成見,會發現 C 語言的 goto 和這些東西類似,他們通常都可以被更好機制取代,但還是可以明智地納入選項。

    至於從深層迴圈跳出,有一個做法是將迴圈獨立出來變成函數,然後用 return。某種程度上只是把 goto 換個名稱而已。

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

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

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

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

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼