効率のよいメモリ使用と動的メモリ/スタック/malloc+free

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

配列宣言でサイズは定数

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

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

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

メモリ利用の効率

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

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

しかしながら、クラスに寿限無とか銀魂の「ビチグソ丸」のような名前の人がいたら、20文字では足りない。(“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(2020年5月リンク切れてる…)

• ピカソの本名もなかなか(英字109文字)。参考：長い名前

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

// 巨大な配列
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 j u g e m u - .... ¥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 ;
}
int main() {
   foo( 3 ) ;
   foo( 4 ) ;
   return 0 ;
}

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

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

malloc()とfree()

malloc() は、動的(ヒープ領域)にメモリを確保する命令で、データを保存したい時に malloc() を実行し、不要になった時に free() を実行する。

malloc() では、alloca() と同じように、格納したいデータの byte 数を指定する。また、malloc() は、確保したメモリ領域の先頭を返すが、ヒープメモリが残っていない場合 NULL ポインタを返す。処理が終わってデータ領域をもう使わなくなったら、free() で解放する必要がある。

基本的には、確保したメモリ領域を使い終わった後 free() を実行しないと、再利用できないメモリ領域が残ってしまう。こういう処理を繰り返すと、次第にメモリを食いつぶし、仮想メモリ機能によりハードディスクの読み書きで性能が低下したり、最終的にOSが正しく動けなくなる可能性もある。こういった free() 忘れはメモリーリークと呼ばれ、malloc(),free()に慣れない初心者プログラマーによく見られる。

ヒープメモリは、プロセスの起動と共に確保され、プログラムの終了と同時にOSに返却される。このため、malloc()と処理のあとすぐにプロセスが終了するようなプログラムであれば、free() を忘れても問題はない。授業では、メモリーリークによる重大な問題を理解してもらうため、原則 free() は明記する。

文字列を保存する場合

#include <stdlib.h>
char* names[ 10 ] ;
char  buff[ 1000 ] ;

// 名前を10件読み込む
void inputs() {
   for( int i = 0 ; i < 10 ; i++ ) {
      if ( fgets( buff ,
                  sizeof( buff ) ,
                  stdin ) != NULL ) {
         names[ i ]
            = (char*)malloc( strlen(buff)+1 ) ;
         if ( names[ i ] != NULL )
            strcpy( names[ i ] , buff ) ;
      }
   }
}
// 名前を出力する
void prints() {
   for( int i = 0 ; i < 10 ; i++ )
      printf( "%s" , names[ i ] ) ;
}
int main() {
   // 文字列の入力＆出力
   inputs() ;
   prints() ;
   // 使い終わったら、free() で解放
   for( int i = 0 ; i < 10 ; i++ )
      free( names[ i ] ) ;
   return 0 ;
}

文字列を保存する場合には、上記の names[i] への代入のような malloc() と strcpy() を使うことが多い。
このための専用の関数として、strdup() がある。基本的には、以下のような機能である。

char* strdup( char* s ) {
   char* p ;
   if ( (p = (char*)malloc( strlen(s)+1 )) != NULL )
      strcpy( p , s ) ;
   return p ;
}

また、入力した文字列をポインタで保存する場合、以下のようなプログラムを書いてしまいがちであるが、図に示すような状態になることから、別領域にコピーする必要がある。

char  buff[ 1000 ] ;
char* name[10] ;
for( int i = 0 ; i < 10 ; i++ ) {
   if ( fgets( buff , sizeof(buff) , stdin ) != NULL )
      name = buff ;
}

配列に保存する場合

任意サイズの配列を作りたい場合には、malloc() で一括してデータの領域を作成し、その先頭アドレスを用いて配列として扱う。

#include <stdlib.h>
void main() {
   int size ;
   int* array ;
   // 処理するデータ件数を入力
   scanf( "%d" , &size ) ;

   // 整数配列を作る
   if ( (array = (int*)malloc( sizeof(int) * size )) != NULL ) {
      int i ;
      for( i = 0 ; i < size ; i++ )
         array[i] = i*i ; // あんまり意味がないけど
      for( i = 0 ; i < size ; i++ )
         printf( "%d¥n" , array[i] ) ;

      // mallocしたら必ずfree
      free( array ) ;
   }
}

構造体の配列

同じように、任意サイズの構造体の配列を作りたいのであれば、配列サイズに「sizeof( struct Complex ) * データ件数」を指定すればいい。

#include <stdlib.h>
struct Complex {
   double re , im ;
} ;

// 指定した場所にComplexを読み込む。
int input_Complex( struct Complex* p ) {
   return scanf( "%f %f" ,
                 &(p->re) , &(p->re) ) == 2 ;
}

// 指定したComplexを出力
void print_Complex( struct Complex* p ) {
   printf( "%f+j%f¥n" , p->re , p->im ) ;
}
void main() {
   int size ;
   struct Complex* array ;
   // 処理する件数を入力
   scanf( "%d" , &size ) ;
   // 配列を確保して、データの入力＆出力
   if ( (array = (struct Complex*)malloc(
                    sizeof(struct Complex) * size )) != NULL ) {
      int i ;
      for( i = 0 ; i < size ; i++ )
         if ( !input_Complex( &array[i] ) )
            break ;
      for( i = 0 ; i < size ; i++ )
         print_Complex( &array[i] ) ;

      // mallocしたら必ずfree
      free( array ) ;
   }
}