[C&++] 怎避開一直重覆 check allocate success ?? @ Edison.X. Blog

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

問題敘述

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

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

Code Snippet
const size_t DCNT = 1000;  // #data
const size_t DIM  = 3;     // #dim of data
const size_t K    = 12;    // #clustering
 
double data[DCNT][DIM];    // source data
 
double center[K][DIM];     // each center of clustering
size_t center_cnt[K];      // #pt in each center
double tmp_sum[DIM];       // temp. variable
 
double center_mse[K];      // mse in each clustering
size_t pt_belongs_K[DCNT]; // each pt belongs which clustering

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

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

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

Code Snippet
const size_t DCNT = 1000;  // #data
const size_t DIM  = 3;     // #dim of data
const size_t K    = 12;    // #clustering
 
double **data, **center, *center_mse;
size_t *center_cnt, *pt_belongs_K;    
size_t k, dim, dcnt;
 
//////////////////////////////////////////////////////////////////////////
// allocate double data[DCNT][DIM];
if(! (data = (double**)malloc(sizeof(double*) * DCNT)))
    return 0; // fail
for(dcnt=0; dcnt<DCNT; ++dcnt)
    if( !(data[dcnt] = (double*)malloc(sizeof(double) * DIM))) break;
 
if(dcnt!=DCNT){ // allocate in for loop
    for(--dcnt; (int)dcnt>=0; --dcnt)
        free((void*)data[dcnt]);
    free(data);
    return 0;
}
 
//////////////////////////////////////////////////////////////////////////
// allocate double center[K][DIM];
if(! (center = (double**)malloc(sizeof(double*)*K))) {
    for(dcnt=0; dcnt<DCNT; ++dcnt) free((void*)data[dcnt]);
    free((void*)data);
    return 0; // fail
}
/* ... other allocate... */

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

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

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

Code Snippet
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void * new1d(const size_t Count, const size_t SizeOfEle){
    return malloc(Count*SizeOfEle);
}
void** new2d(const size_t H,const size_t W,const size_t SizeOfEle)
{
    char *space1d, **space2d;
    size_t i;
 
    space2d = (char **)malloc(sizeof(char*)*H+SizeOfEle*H*W);
    if(!space2d)  return NULL;
 
    space1d = (char *)(space2d+H);
    for(i=0; i<H; ++i){
        space2d [i] = space1d;
        space1d += (SizeOfEle * W);
    }
    return (void**)space2d;    
}
 
 
int main()
{
    const size_t DCNT = 1000;  // #data
    const size_t DIM  = 3;     // #dim of data
    const size_t K    = 12;    // #clustering
 
    double **data, **center, *center_mse;
    size_t *center_cnt, *pt_belongs_K;    
 
    // double data[DCNT][DIM]
    if (!(data = (double**)new2d(DCNT, DIM, sizeof(double)))) return 0;
    // double center[K][DIM]
    if( !(center = (double**)new2d(K, DIM, sizeof(double)))) {
        free((void*)data); return 0;
    }    
    // double center_mse[K]
    if( !(center_mse = (double*)malloc(sizeof(double) * K))){
        free((void*)data); free((void*)center); return 0;
    }
    // size_t center_cnt[K]
    if( !(center_cnt = (size_t*)malloc(sizeof(size_t) * K))){
        free((void*)data); free((void*)center);
        free((void*)center_mse); free((void*)center_mse);
        return 0;
    }
    // size_t pt_belongs_K[DCNT]
    if( !(pt_belongs_K = (size_t*)malloc(sizeof(size_t) * DCNT))){
        free((void*)data); free((void*)center);
        free((void*)center_mse); free((void*)center_mse);
        free((void*)center_cnt);
        return 0;
    }    
    /* do sometihing */
    return 0;
}

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

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

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

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

Code Snippet
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main()
{
    const size_t DCNT = 1000;  // #data
    const size_t DIM  = 3;     // #dim of data
    const size_t K    = 12;    // #clustering
 
    double **data, **center, *center_mse;
 
    char   *pool;
    double *trunk_double;
 
    size_t data_size, center_size, center_mse_size;
    size_t t, k, dcnt;
 
    size_t offset[100]={0}, offset_n=1;
    
    //////////////////////////////////////////////////////////////////////////
    // bytes of double data[DCNT][DIM]
    t = (data_size = sizeof(double*)*DCNT + sizeof(double)*DCNT*DIM)>>2;
    if(t<<2 != data_size) data_size = (t+1)<<2;
    offset[offset_n] = data_size;
    ++offset_n;
 
    // bytes of double center[K][DIM]
    t = (center_size = sizeof(double*)*K + sizeof(double)*K*DIM)>>2;
    if(t<<2 != center_size) center_size = (t+1)<<2;
    offset[offset_n] = offset[offset_n-1] + center_size;
    ++offset_n;
 
    // bytes of double center_mse[K]
    t = (center_mse_size = sizeof(double) * K) >> 2;
    if(t<<2 != center_mse_size) center_mse_size = (t+1)<<2;
    offset[offset_n] = offset[offset_n-1] + center_mse_size;
    ++offset_n;
 
    /* other calculation */
    /*... */
 
    //////////////////////////////////////////////////////////////////////////
    /* allocate memory */
    pool = (char*)malloc(offset[offset_n-1]);    
    if(!pool) return 0; // fail
 
    // double data[DCNT][DIM]
    data = (double**)(pool+offset[0]);
    trunk_double = (double*)(data+DCNT);
 
    printf("data : %08x\n", data);
    printf("trunk_double : %08x\n", trunk_double);
    for(dcnt=0; dcnt<DCNT; ++dcnt)
        data[dcnt] = trunk_double, trunk_double+=DIM;
 
    // double center[K][DIM]
    center = (double**)(pool+offset[1]);
    trunk_double = (double*)(center+K);
    for(k=0; k<K; ++k)
        center[k] = trunk_double, trunk_double+=DIM;
 
    // double center_mse[K]
    center_mse = (double*)(pool+offset[2]);
 
    //////////////////////////////////////////////////////////////////////////
    // test
    memset((void*)*data, 0, DCNT*DIM*sizeof(double));
    memset((void*)*center, 0, K*DIM*sizeof(double));
    memset((void*)center_mse, 0, K*sizeof(double));
 
    /* others...release */
    free((void*)pool);
    //////////////////////////////////////////////////////////////////////////
    return 0;
}

它是做出來了，雖然避開了一直重覆判斷 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 ，把記憶體徹底清空。至於有沒有辦法像上述去掉碎片化問題的話...，嗯，再說吧。