ホーム » スタッフ » 斉藤徹 » メモリの使用効率

メモリの使用効率

投稿者: in 斉藤徹 投稿日:

次にメモリの利用効率の話について解説する。

配列宣言でサイズは定数

C言語では、配列宣言を行う時は、配列サイズに変数を使うことはできない。

最近のC(C99)では、実は下記のようなものは、裏で後述のalloca()を使って動いたりする。(^_^;

void foo( int size ) {
   int array[ size ] ;         // エラー
   for( int i = 0 ; i < size ; i++ )
      array[ i ] = i*i ;
}
void main() {
   foo( 3 ) ;
   foo( 4 ) ;
}

メモリ利用の効率

配列サイズには、定数式しか使えないので、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。

#define MEMBER_SIZE 50
#define NAME_LENGTH 20
char name[ MEMBER_SIZE ][ NAME_LENGTH ] ;

しかしながら、クラスに寿限無とか銀魂の「ビチグソ丸」のような名前の人がいたら、20文字では足りない。(C言語の普通の配列宣言では、”t-saitoh”くんは配列サイズ9byte、”寿限無”くんは配列220byte といった使い方はできない) また、クラスの人数も、巨大大学の学生全員を覚えたいとい話であれば、 10000人分を用意する必要がある。 ただし、10000人の”寿限無”ありを考慮して、5Mbyte の配列を準備したのに、与えられたデータ量が100件で終わってしまうなら、その際のメモリの利用効率は極めて低い。

このため、最も簡単な方法は、以下のように巨大な文字配列に先頭から名前を入れていき、 文字ポインタ配列に、各名前の先頭の場所を入れる方式であれば、 途中に寿限無がいたとしても、問題はない。

char array[2000] = "ayuka¥0mitsuki¥0t-saitoh¥0tomoko¥0....." ;
char *name[ 50 ] = {
   array+0 , array+6 , array+14 , array+23 , ...
} ;

この方式であれば、2000byte + 4byte(32bitポインタ)×50 のメモリがあれば、 無駄なメモリ空間も必要最低限とすることができる。

参考：
寿限無(文字数:全角103文字)


さる御方、ビチグソ丸(文字数:全角210文字)

引用Wikipedia

大きな配列を少しづつ貸し出す処理

// 巨大な配列
char str[ 10000 ] ;
// 使用領域の末尾(初期値は巨大配列の先頭)
char* sp = str ;
// 文字列を保存する関数
char* entry( char* s ) {
   char* ret = sp ;
   strcpy( sp , s ) ;
   sp += strlen( s ) + 1 ;
   return ret ;
}
int main() {
   char* names[ 10 ] ;
   names[ 0 ] = entry( "saitoh" ) ;
   names[ 1 ] = entry( "jugemu-jugemu-gokono-surikire..." ) ;
   return 0 ;
}
// str[] s a i t o h ¥0 t o m o k o ¥0
//       ↑             ↑
//     names[0]        names[1]

このプログラムでは、貸し出す度に、sp のポインタを後ろに移動していく。

スタック

この貸し出す度に、末尾の場所をずらす方式にスタックがある。

int stack[ 100 ] ;
int* sp = stack ;
void push( int x ) {
   *sp = x ;    // 1行で書くなら
   sp++ ;       // *sp++ = x ;
}
int pop() {
   sp-- ;
   return *sp ; // return *(--sp) ;
}
int main() {
   push( 1 ) ;
   push( 2 ) ;
   push( 3 ) ;
   printf( "%d¥n" , pop() ) ;
   printf( "%d¥n" , pop() ) ;
   printf( "%d¥n" , pop() ) ;
   return 0 ;
}


スタックは、最後に保存したデータを最初に取り出せる(Last In First Out)から、LIFO とも呼ばれる。
このデータ管理方法は、最後に呼び出した関数が最初に終了することから、関数の戻り番地の保存や、最後に確保した局所変数が最初に不要となることから、局所変数の管理に利用されている。

alloca() 関数

局所変数と同じスタック上に、一時的にデータを保存する配列を作り、関数が終わると不要になる場合には、alloca() 関数が便利である。alloca の引数には、必要なメモリの byte 数を指定する。100個の整数データを保存するのであれば、int が 32bit の 4byte であれば 400byte を指定する。ただし、int 型は16bitコンピュータなら2byteかもしれないし、64bitコンピュータなら、8byte かもしれないので、sizeof() 演算子を使い、100 * sizeof( int ) と書くべきである。

#include <alloca.h>
void foo( int size ) {
   int* p ;
   // 
   p = (int*)alloca( sizeof( int ) * size ) ;
   for( int i = 0 ; i < size ; i++ )
      p[ i ] = i*i ;
}
void main() {
   foo( 3 ) ;
   foo( 4 ) ;
}

alloca() は、指定された byte 数のデータ領域の先頭ポインタを返すが、その領域を 文字を保存するために使うか、int を保存するために使うかは alloca() では解らない。alloca() の返り値は、使う用途に応じて型キャストが必要である。文字を保存するなら、(char*)alloca(…) 、 intを保存するなら (int*)alloca(…) のように使う。

ただし、関数内で alloca で確保したメモリは、その関数が終了すると、その領域は使えなくなる。このため、最後に alloca で確保したメモリが、最初に不要となる…ような使い方でしか使えない。

タグ: ,