[HFC] Hidden Features of Array Management in C (I) @ Edison.X. Blog

這裡講的陣列管理並不非常深入，主要只探討幾個主題

0. VLA

1. sizeof

2. defect memory leak

3. allocate memory for 2d

4. allocate memory for 3d

5. spec. array index range ( ex : arr[-2:3] )

6. flexible array

7. array in struct

避免篇幅過長，另外之議題於下一篇提出。

8. dbg_malloc

9. alignment allocate memory

A. others

B. Q & A

C. Reference

* 0. VLA

VLA 全名為 Variable-Length Array，中文譯名大概有二、三種，較習慣譯為「可變長度陣列」，它在 C99 以後才有的。也由於 C99 以後才規定，你可以使用這種寫法

int n=10;
int x[n] = {0};

早期在 C99 出現時，這都是被禁止的。但 VLA 的出現卻引出來一些爭議，
特別我也是不建議用 VLA 的一群。為何？再測以下程式碼

#include <iostream>
using namespace std;
int main()
{
     int N=1000000;
     int i, sum;
     int x[N];
     for(i=0; i!=N; ++i) x[i]=i;
     for(i=0; i!=N; ++i) sum+=x[i];
     cout << "sum=" << sum << '\n';
     delete [] x;
     return 0;
}

雖只有 4MB 記憶體大小，但很遺憾的， VLA 沒辦法配置出來。我沒確切的資料能說明，VLA 實際上是在 heap 或是 stack 上，但我的確相信， VLA 是配置在 stack 上而非 heap，上面程式只是一個推斷的例子而已。

同時 VLA 我認為它的名稱真的取得不是很好 - 可變長度陣列，但一旦我用了 int x[N] 時，在 x 生命週期結束之前，它所有可用元素都只有 N 個，沒辦法變大，沒辦法變小，我認為直接稱它 semi-dynamic array (半動態陣列) 可能還比較合適。

若拿動態陣列與 VLA 做比較，大致上有幾點是可注意的

a. VLA 可宣告的範圍與 Static Array 無二異，甚至會少一點。
( 有另一說，VLA 會配置比實際用得元素還多，但那些多配置的就浪費了。)

b. 都是 run time 時配置

c. 並非所有 compiler 都支援 VLA，但所有 compiler 都支援 Dynamic Array

d. Dynamic Array 在配置、釋放時花時間，VLA、Static Array 無此問題。

光是 a. 與 c. ，我便主張不用 VLA，Dynamic Array 在 d. 缺點上之表現，
實際上仍有些技巧可改善一直重覆配置的問題，於此便不多談。

* 註 : 如果發現這段和這篇文章第四段與第五段長得一模一樣，別懷疑了，那份文章是我寫的，只是該論壇需要閱讀權限，故直接引來 blog 裡。

1. sizeof

(0) 識別字 or 運算子

筆者不願再做這口舌之爭，但這二種說法都有人說。

早期有人認為它是識別字，但後來 C++ 裡是把它納到運算子裡面去。

有人提出它是單元運算子的證明是：

int a, b=10;
a = ~b;
a = ~(b);
a = sizeof(b);
a = sizeof b;

結果以這方式證明的人，一度被圍勦，認為邏輯能力不夠清楚。其他的口水就不再多敘述。

(1) sizeof(void)

切記，無論如何不要出現這東西，這是 undefined behavior，有些 compiler 可能會給 1，有些 compiler 可能會給 0，總之程式碼裡絕不要出現這種東西。

(2) sizeof(char)

規格書裡有定義，sizeof(char) == 1 怛成立，代表 char 資料型態一定是 1 byte，

而 1 byte = ??? bits，是要去查 limits.h (climit) 裡之 CHAR_BITS。

所以害怕 sizeof(char) 不等於 1 這種想法是多餘的。

但在 malloc 情形下，下面這段 code 又有所爭議了。

char *str = (char*)malloc(strlen(ss)+1);

該不該寫成

char *str = (char*)malloc( (strlen(ss) + 1) * sizeof(char) );

可以討論很久，討論的點不外乎圍繞在維護性上，筆者較建議這種寫法。

char *str = (char*) malloc ( (strlen(ss) + 1 ) * sizeof(*str) );

在 str 更換 type 時會好些。

(3) sizeof(int*)、sizeof(int**)... etc

事實上 C language 在表達 pointer 大小時，只有一種寫法：sizeof(void *)。但有時在教學的時候，

int **a = (int**)malloc(sizeof(int*) * 20);

這種寫法反而讓大多人認為較為清楚，同時基於一些 pointer 加法問題等，有時反而不會強調一定要用 void** a 、sizeof(void*) 等用法。

2. defect memory leak

目前，沒有任何一套完整的 library ，可以抓「所有」的memory leak，但的確可以抓出「大多」之memory leak。

在查 memory leak 時，目前大多都是用現有之工具下去做輔助，這部份不得不推 Visual C++ 。另外 valgrind 也是查 memory leak 之工具，但它主要是用在 linux 底下。

若為新手，建議直接學 Visual C++ 裡面怎麼查，這裡只做淺述。

(1) 一定要是在 C++ 底下才能用 (extension filename : .cpp)

(2) 在 main.cpp 最開頭加上 #define _CRTDBG_MAP_ALLOC

(3) 引入#include <crtdbg.h>

(4) 在 main 結束前呼叫 _CrtDumpMemoryLeaks();

(5) 執行時一定要在 Debug Mode 底下，且必須是「偵錯 (F5) 」方式執行。

這部份在 codeproject 已經有人研究了相關之 API，封裝成 class，有興趣可自行查看。

其他在 windows 下查 memory leak 之工具還包含了 Drmem、purifty、Insure++，其實還有更多，這裡只提幾個。

實作部份請看下一篇之dbg_malloc。

3. allocate memory for 2d

(1) 文中提到的「碎片化」該不該考量已被爭議一段時日，這裡不重覆爭議。筆者持向「考慮」碎片化問題，原因為 arr[w][h]，能不能使用 memset、memcpy 等管理函式，碎片化時必須調用 w 次；沒碎片化時只需調用 1 次。

(2) malloc \ free，new \ delete 需要一點點時間，有些人很在意這個，但一般而言應不會是瓶頸問題。

在 C++ 中，要配置二維陣列很容易，同時也較建議直接用 vector < > 即可。

以二維 int v[h][w] 為例，所有方法均可推到三維去。一般初學寫的動態記憶體配置

/* allocate */

int** v = (int**)malloc(sizeof(int*)*h);

for(i=0; i<h; ++i)
    v[i] = (int*)malloc(sizeof(int)*w);
/* release */
for(i=0; i<h; ++i) free(v[i]);
free(v);

呼叫 malloc / free 需要 1+h 次，且造成記憶體碎片化問題，一種解法方式是以一維代替多維。

size_t i, j, h=2, w=3, cnt=0;
/* allocate */
int *v = (int*)malloc(sizeof(int)*h*w);
/* index transform */
for(i=0; i<h; ++i)
    for(j=0; j<w; ++j)
        v[i*w+j] = ++cnt;
/* release */
free(v);

malloc / free 只需一次，在計算 index 轉換時稍嫌麻煩。是有一點技巧可降低 malloc 使用次數。

/* allocate */    
    int *trunk = (int*)malloc(sizeof(int)*h*w);
    int **v = (int **)malloc(sizeof(int*)*h);
    for(i=0; i<h; ++i)
        v[i] = trunk, trunk+=w;
    /* set value */
    memset(v[0], 0, sizeof(int)*w*h);
    /* release */
    free(*v);
    free(v);

另一種作法相似，其作法是把額外的 pointer 也塞到 heap 裡去，使其 malloc 次數少一次。

size_t h=2, w=3;
// allocate and link address
int **p  = (int **)malloc(sizeof(int*)*h + sizeof(int)*h*w);
int *trunk = (int*)(p + h);
for(i=0; i<h; ++i)
    p[i]=trunk, trunk+=w;
// write
memset((void*)*p, 0, sizeof(int)*h*w);
// read
for(i=0; i<h; ++i) for(j=0; j<w; ++j)
    printf("%d", p[i][j]);
// release
free((void*)p);

根據上述技巧，可包 function 出來，參考。

void** new2d(size_t H, size_t W, size_t SizeOfEle)
{
    size_t i;
    char **p    = (char**)malloc(sizeof(*p)*H);
    char *trunk = (char*)malloc(SizeOfEle*H*W);
    for(i=0; i<H; ++i)
        p[i] = trunk, trunk+=(SizeOfEle*W);
    return (void**)p;
}

一樣也可以用成 macro 型式，但不適合，不再以範例碼示之。

4. allocate memory for 3d

3d 之動態記憶體配置技巧觀念上與上面一樣，也分成配置三次與配置 1 次之方法，這裡不再 po code 加版面，有興趣請到這裡下載 ArrayManagement.rar ，裡面相關之說明提一下

new1.c : p[x][y][z]， allocate / free 次數 = (1+x+x*y)，具碎片化問題，不可直接調用 memset / memcpy。
new2.c : p[x][y][z]，三個維度， allocate / free 次數 = 3 次，不具碎片化問題，可直接調用 memset / memcpy。
new3.c : p[x][y][z]， allocate / free 次數 = 1 次，不具碎片化問題，可直接調用 memset / memcpy。

xnew_ver1 資料夾 : O (n) 之 allocate 方式包成 function，及調用範例。
xnew_ver2 資料夾 : O (1) 之 allocate 方式包成 function，及調用範例。

Challenge : 了解多維配置技巧後，有種想法是，N 維全都是從 N-> N-1 -> ... -> 1 ，慢慢配置、接上 pointer，照理說可實現任意維度之陣列配置。這部份筆者目前實作出來並不完全正確，於此不再野人獻暴。

關於 saw array 請看下一篇文章之 Q & A 部份。

5. spec. array index range

我不推薦這種技巧，日後出包機會太大，不是很好的設計。

曾在某本原文之數值分析書上看到類似下面的程式碼。

int main()
{
    int i, j, cnt=0;
    const int low=-2, up=2;
    float* v = create_vec(low, up);

    for(i=low; i<=up; ++i) // set value
        v[i]=(float)(++cnt);
    
    for(i=low; i<=up; ++i) // display
        printf("v[% d]=%.0f, ", i, v[i]);
    delete_vec(v, low);
    /* output :
     * v[-2]=1, v[-1]=2, v[ 0]=3, v[ 1]=4, v[ 2]=5,
     */
    return 0;
}

原始是用在 matrix，是寫成二維，這裡改成一維簡化說明而已。

它特別的地方在於，arr 可指定 index 範圍，上述便是指定了 index 範圍為 -2 : +2。

但關鍵的 create_vec 卻沒附上，於是有心想看完這本數值分析的人便開始猜想，

create_vec 、delete_vec 到底怎麼完成的。

最後想了一下，應是利用了 *(ptr + i ) = 以 ptr 為 base，移動 i 個 data type = ptr[i] 的概念，

推斷大概長這樣

float* create_vec(int low, int up)
{
    float* pool = (float*)malloc(sizeof(float)*(up-low+1));
    return pool - low;
}
void delete_vec(float* v, int low)
{
    free( (void*)(v+low));
}

這份 code 有個要命的地方，在將 pointer 指向了不是 allocate 出來的位置，

實際上是 undefined behavior，也就是 return pool - low; 這行為本身是 undefined.

另足標裡面是不允許放負值，實際會怎麼做又是一個 undefined 。(錯誤更正)

無論如何，這種寫法別用，它必須有太多的前提假設才可以正常作用。

最後那份數值分析的 code ，我也還是不知道最後他是怎麼做的，只是臆測而已，所以也沒辦法驗證，但推測應是有多 allocate 一些 memory 出來就是。

6. Flexible Array

這技巧並不實用，但在寫底層時常用，這種作法筆者其實看不出優點。

早期用到 flexible array 主要原因在於：少malloc 一次、解決記憶體碎片化問題，但筆者實在是看不出有這些優點。

Flexible Array 在 C language 一般較少讓人討論，早期較常使用在寫通訊之類的程式碼上。

若將簡單的 array 管理封裝成 struct

typedef struct tagArr{
    size_t size;
    int *arr;
}Arr;

Arr v = {10,NULL};
v.arr = (int*)malloc(sizeof(int) * v.size);
/* do something */
free(v.arr);

而 flexible array 利用了 C 本身不會 check bound 特性，去產生一組 array 出來。

typedef struct tagArr{
    size_t size;
    int arr[];
}Arr;
/* caller */
size_t i, size = 10;
// allocate
Arr *pv = (Arr *)malloc(sizeof(Arr) + (size) * sizeof(int));
// setter
for(i=0; i<size; ++i) pv->arr[i] = i;
// display
for(i=0; i<size; ++i) printf("%d", pv->arr[i]);
// release
free(pv);

在 struct 裡面有人寫 int arr[0]，但這種作法較不具可攜性，也不合標準，一些 compiler 會因此而出包。

flexible array 在 C99 裡使用不完整之類型去實作出來，它在 struct 裡之宣告，即 arr 必須為 struct 中之最後一個成員，且不可指定元素個數。

7. array in struct

這招奇淫怪技非常冷僻，且用到的時機幾乎是零。

我們在做 array assigned 時必須逐一 assigned，

但固定大小的 array ，可放在 struct 裡一次做 assignment，

/************************************************************************/
/* */
/* filename : ArrayInStruct.c */
/* author : Edison.Shih. / EdisonX */
/* compiler : Visual C++ 2010 */
/* date : 2012.03.31 */
/* */
/************************************************************************/

#include <stdio.h>
#define N 5

struct tagArray{
    int arr_[N];
};
typedef struct tagArray Array;

void print(Array x)
{
    size_t i;
    for(i=0; i<N; ++i)
        printf("%d", x.arr_[i]);
    puts("");
}

int main()
{
    size_t i;
    Array arr1={0,1,2,3,4};
    Array arr2={0};
    /* display arr2 */
    print(arr2);
    /* arr1 assigned to arr2, display arr2 */
    arr2 = arr1, print(arr2);

    getchar();
    return 0;
}

沒很推用這種方式處理原因為

(1) 只能用於 assignment 一個固定大小的 array，不能用在 heap 上。

(2) 它還是不能以簡單的方式完成 compare 功能。

(3) 它對於 array 實體的存取顯得麻煩，但可綁定一個 const pointer to object 方式綁在 data member (array) of struct 上面，詳情可看這篇，裡面提到的第三點有提出。

(4) 底層上它還是一筆一筆慢慢搬，好一點的會用 memcpy 方式搬過去，故較建議直接用 memcpy 這個去做就好。

由於在實務上，array 放在 stack 機會上少到可憐，幾乎都是放在 heap 上，故這種方法基本上是不怎麼可能派得上用場的。

< 以下感謝 novus 提示 >

在 C++ 裡之 template 有份特性， template 裡之引數將在編譯期時被展開 (這點也不贅述)，利用這特性，array in struct 也可被利用於此。一份簡易之程式碼供參考，欲下載請至這下載 small_array.cpp

#include <iostream>
using namespace std;
#define SIZE_ 5
//////////////////////////////////////////////////////////////////////////

template<typename T, const size_t SIZE>
class arr{
private:
    /* we can use anonymous struct */
    /* struct { T data[SIZE]; }Data; */
    struct tagData { T  data[SIZE]; }Data; 
public:
    
    // constructor
    /* (!) It is not essential to check bounding, */
    /* (!) because compiler will check same size for us. */
    arr(arr &rhs) {Data = rhs.Data;} 
    arr(){}    
    arr(T *carr, size_t size) {    
        for(size_t i=0; i<size; ++i)
            Data.data[i] = carr[i];
    }
    
    // member function
    inline size_t size() {return SIZE;}
    // operator []
    inline const T& operator[](const size_t idx) const 
    {
        return Data.data[idx];
    }
    inline const T& operator[](size_t idx)
    {
        return Data.data[idx];
    }
    // friend, operator <<
    template<typename T, const size_t SIZE>
    friend ostream& operator<<(ostream& out ,arr<T,SIZE> obj)
    {
        for(size_t i=0; i<obj.size(); ++i)
            out << obj.Data.data[i] <<  ' ';
        return out;
    }
};

//////////////////////////////////////////////////////////////////////////
int main()
{

    int carr[SIZE_] ;
    for(size_t i=0; i<SIZE_; ++i) 
        carr[i] = i;

    arr<int, SIZE_> arr1(carr, SIZE_);
    arr<int, SIZE_> arr2(arr1);

    cout << "arr1 : " << arr1 << endl;
    cout << "arr2 : " << arr2 << endl;
    
    cin.get();
    return 0;
}