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

 

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 之工具還包含了 DrmempuriftyInsure++,其實還有更多,這裡只提幾個。

實作部份請看  下一篇之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;
}

 

這種 class 利用了 array in struct 之特性,有幾點必須注意。

(1) 由於 SIZE 是在編譯期 (compiler time)時就必須決定,所以不能放可變變數,也不能藉由 function 計算傳回 SIZE。 (所以上面的 arr<int, SIZE> arr2(arr1); 不能寫 arr<int, arr1.size()> arr2(arr1); )

(2) 在不考慮特偏化處理情況下,由於 arr<int, 10> 和  arr<int, 9> 被視為不同型別,所以這二個型別不能彼此做 assigned 。同樣的,arr<double, 10> 與 arr<int, 10> 也是不同型別。

(3) 也由於上一個原因,所以裡面的 struct Data 在做直接 assignment 時,不用擔心因 SIZE 不同而不能 assigned,因這個問題在編譯時便會出現錯誤。

(4) 由於 fixed array 是放在 stack 上,故上述之 class 並不適用於較大之 array。

 

此篇至此結束,其他議題可看下一篇

 

 *更新日期

初版 2012-03-27 21:09:19 

  • (0) VLA
  • (1) sizeof
  • (2) lookup memory leak
  • (3) allocate memory for 2d
  • (4) allocate memory for 3d
  • (5) spec. array index range
  • (6) fliexible array
  • (7) array in struct
  • (8) others

二版 2012-03-29 21:20:05 

  •  (1) add another article 
  •  (2) fix some descript about   " (7) array in struct "
  •  (3) " (8) others " section move to another article  , and re-code number as (A)
  •  (4) add c++ Array class sample in " (6) flixible array " 
  •  (5) add " (8) dbg_malloc " section in another article 
  •  (6) add " (9) alignment allocate memory " section in another article 
  •  (7) add " (B) Q & A " section in another article 
  •  (8) add " (C) referencesection in another article 

 

[ 註 1] 一開始只發一篇文章下來,鑑於篇幅過長,不易編輯,故後讀新增 [HFC] Hidden Features of Array Management in C (II) 。

[ 註 2] 此二篇文章為筆者自學 coding 、studying 來,所使用到、看過之一些技巧,同時必須感謝 novus 之意見與指導,指正了本文敘述不盡理想之處,也讓筆者看到更多關於 array 其它議題,也使文章之內容更為豐富,於此再次感謝。

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


留言列表 (4)

發表留言
  • novus
  • 你對「5. 指定陣列索引之範圍」的說明有沒有指出真正的問題。

    首先,不直接傳回 allocate 出來的位置是一個極常見的技巧。舉例來說帶有 debug 功能或者具備記憶體對齊功能的 alloc,都會配置超過使用者需求的記憶體,保留前後的幾個 byte 作為儲存資訊或者墊空間之用,然侯回傳位移後的位址給使用者。C 和 C++ 完全不禁止這種事,只要釋放的時候算得出當初配置的原址即可。

    對指標使用負數索引在 C 和 C++ 的規定中也是合法的。

    這個程式碼真正的問題在於,他算出來的 pool - low 不保證落在程式合法使用的範圍內,即使沒有對該位址 de-ref,*理論上*也仍然是未定義行為。


    「7. array in struct」儘管你認為無用,可是卻被收到 C++ library 當中的 std::array。
  • 謝謝 novus 指出不理想之處。

    關於第五點應該是我的誤解 (或是我真的沒說清楚)。 http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf

    摘錄 C99, 6.5.6 / 8,
    ... or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the
    behavior is undefined.

    前面相關的幾點我得到的結論是,確實可以進行 + - 法,可以指向「最後一個元素之後一個 (就是 C++ 的 iterator::end() ),妙的是它也沒再提到「往前」的問題。故我得到的訊息是,這應是在 dereference 前就有可能會出包 (再仔細看你的回覆,好像就是這條規則 Orz)。

    第七點我又覺得更神了,array in struct 在 C 裡必須指定 array size,進行 assignment 才會一次丟過去。 std::array 實作不很確定,但它在 constructor 時才決定 size ,所以推斷應是用 new 方式完成,對 struct 而言,有辦法自動 fill 嗎? ( 還是它在寫 constructor 時也是用 for loop 方式慢慢填?)

    edisonx 於 2012/03/28 19:42 回覆

  • novus
  • 我覺得你應該加一個配置記憶體對齊陣列的 section

    另外看你有沒有興趣實作一個 debug malloc,概念碼如下,缺漏處自己補:

    struct MemInfo {
    const char* filename;
    int lineno;
    MemInfo *prev, *next
    };


    void* dbg_malloc(size_t size, filename, lineno) {
    MemInfo* info = (MemInfo*) malloc(sizeof(MemInfo) + size);
    ** 指定 info->lineno 和 filename
    ** 將 info 加入 linked list
    return (void*) (info + 1);
    }

    dbg_free 只不過是把 info 移出 linked list 再 free 原址。

    如果 debug flag 被定義時:
    #define malloc(size) dbg_malloc(size, __FILE__, __LINE__)

    最後定義一個 dbg_report 函數,會印出在 linked list 當中的 info。另外你可以在頭尾加個 Guard byte 防止 overflow

    原理很簡單,VC 也只是這樣做而已,不過小細節要注意就是了。
    原理很簡單,VC 也只是這樣做而已,不過小細節要注意就是了。
  • 我看到讓我感到興奮的東西了,這份回覆提到的東西我之前連聽都沒聽過 (配置記憶體對齊陣列的 section 是?將起始位置 alignment 嗎?這好像 compiler 會做吧??),這份提到的有空會先查查資料再來實作,感謝提供 keyword !! ^^

    edisonx 於 2012/03/28 19:50 回覆

  • novus
  • std::array 的大小是由 template 給定的,應該很簡單就可以找到實作碼。
  • 我想到原因了, 我沒和 template 展開的時間點做聯結,現在總算知道為什麼了!感謝。

    edisonx 於 2012/03/29 16:26 回覆

  • 訪客
  • 3. allocate memory for 2d

    後兩個code 似乎將
    v[h][w] 誤視為 v[w][h]

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

    p = (int *)(v+w);
    p = (int *)(v+h);

    for(i=0; i<w; ++i)
    for(i=0; i<h; ++i)

    v[i]=p, p+=h;
    v[i]=p, p+=w;
  • 是我筆誤了沒錯。謝謝指正。

    edisonx 於 2012/04/10 06:23 回覆

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

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

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

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

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼