第2回 コンピュータサイエンスを学ぼう: メモリ領域と配列の関係

こんにちは、@binarytaです。

突然ですが、Cで記述された以下2パターンの2次元配列の初期化に関してパフォーマンスがいいのはどちらかご存知でしょうか。
( 両者の違いは初期化時の添字ijが入れ替わっていることです )

int array[256][256];

  /* ... */

  for (i = 0; i < 256; i++) {
    for( j = 0; j < 256; j++) {
      array[j][i] = i*j;
    }
  }

  /* ... */
int array[256][256];

  /* ... */

  for (i = 0; i < 256; i++) {
    for( j = 0; j < 256; j++) {
      array[i][j] = i*j;
    }
  }

  /* ... */

もし両者のパフォーマンスについて違いがわからない場合は本エントリを読むとメモリ領域に関して少しだけ理解が深まると思います。
問いの解説は目次の最後のリンクに設置しています。

配列はプログラミング言語において最も一般的な複合データ型ですが、配列のメモリ配置や効率に関して深く理解して使っている若手のプログラマはそこまで多くないでしょう。
本エントリでは配列に関するメモリ配置の挙動と効率の良い配列へのアクセス方法を紹介します。
また、エントリ内で説明のために使用する言語はC/C++をメインとします。

配列の基本

ここで説明するのは一般的な配列の概念です。
多くのプログラマは既に知っている内容ばかりだと思いますので、次の節へ進んでも構いません。

C/C++の配列は複合データ型の一種です。構造体や共用体、ポインターも複合データ型に当たります。C++におけるclassもすべて複合型です。

配列は同一の型の要素からなる集合を表すデータ型です。
128個の要素を持つ配列は一般的に次のように宣言します。

  int array[128];

この宣言によりメモリ領域に512 Byteの領域が確保されます。
  ※ int型は4 Byteなので 4 x 128 = 512 Byte
C/C++では自動変数として宣言した配列は初期化されず、メモリ内に存在するビットパターンに対応する値を持つようになります。

自動記憶域期間を持つオブジェクトが明示的に初期化されていない場合、その値は不定となる
[ISO/IEC 9899:2011]

配列は添字(インデックス)により任意の要素へアクセスできます。
宣言した変数には配列の先頭要素のアドレスが格納され、先頭要素のアドレスは占有したメモリ領域内の最も下位のメモリ位置に存在します。
そのため、配列とポインタの関係を使った場合、変数名に対して1を加算することで添字1の要素アドレスにアクセスでき、2を加算することで添字2の要素アドレスにアクセスでき、以降も同様にアクセスできます。
また自動変数(通常の変数)の宣言では配列は不定な値で初期化されトラップ表現になる場合がありますが、静的変数の宣言の場合は全て0で初期化されます。
これは次の簡単なプログラムからでも確認できます。

#include <stdio.h>

/* 配列の各要素のアドレスと、ポインタによるアクセスで要素の値を出力する */
int main(void) {
  int array[5] = {1,2,3,4,5};
  printf("array[0]: { value: %d, address: %p }\n", *array      , array    );  
  printf("array[1]: { value: %d, address: %p }\n", *(array + 1), array + 1); 
  printf("array[2]: { value: %d, address: %p }\n", *(array + 2), array + 2); 
  printf("array[3]: { value: %d, address: %p }\n", *(array + 3), array + 3); 
  printf("array[4]: { value: %d, address: %p }\n", *(array + 4), array + 4); 

  static int sArray[5];
  printf("sArray[0]: { value: %d, address: %p }\n", *sArray      , sArray    ); 
  printf("sArray[1]: { value: %d, address: %p }\n", *(sArray + 1), sArray + 1); 
  printf("sArray[2]: { value: %d, address: %p }\n", *(sArray + 2), sArray + 2); 
  printf("sArray[3]: { value: %d, address: %p }\n", *(sArray + 3), sArray + 3); 
  printf("sArray[4]: { value: %d, address: %p }\n", *(sArray + 4), sArray + 4);
}

/* output
array[0]: { value: 1, address: 0x7ffee8a02440 }
array[1]: { value: 2, address: 0x7ffee8a02444 }
array[2]: { value: 3, address: 0x7ffee8a02448 }
array[3]: { value: 4, address: 0x7ffee8a0244c }
array[4]: { value: 5, address: 0x7ffee8a02450 }

sArray[0]: { value: 0, address: 0x105114030 }
sArray[1]: { value: 0, address: 0x105114034 }
sArray[2]: { value: 0, address: 0x105114038 }
sArray[3]: { value: 0, address: 0x10511403c }
sArray[4]: { value: 0, address: 0x105114040 }
*/

上記の例により、メモリ配置が下位から順に4Byteずつ連続して配置されていることがわかりますね。

配列のメモリ配置

1次元配列のメモリ配置

配列は同一の型を持つ要素の集合なので特定の型のバイト列が連続して配置されています。
まず一次元配列について見ていきます。

先の例のプログラム上では、宣言時にint型要素を5個持つ配列を初期化していました。
これは図にすると次のようなイメージです。

f:id:AdwaysEngineerBlog:20180614215633j:plain

薄枠で表現した長方形1つは1Byteを表わします

この図は容易に想像できるでしょう。
メモリは1Byteごとにアドレスが割り当てられます。
配列arrayの各(int型)要素は4Byteずつメモリを占有していて、記憶領域(メモリ)上に連続して配置しています。

多次元配列のメモリ配置

1次元配列の場合、配列内の各要素は隣接して記憶領域を占有し、連続してメモリが割り当てられていました。
多次元配列の場合、各次元をどのようにメモリ上で表現(割り当て)するのかは言語処理系によって異なります。そのため、要素に簡単にアクセスできるアドレス指定方法は存在しません。
多次元配列に実行時に効率よくアセセスするためには行優先順列優先順という配列操作について知る必要があります。

行優先順と列優先順

行優先順は各次元の要素ごとにメモリを割り当てます。
列優先順は各次元の添え字(インデックス)を優先してメモリ割り当てを行います。
多くの静的型付言語では行優先順の方式が使われています。行優先順方式は実装が単純でマシン命令で簡単に使用できます。
図の上側が行優先順、下側が列優先順のメモリ上のマッピングイメージです。
ちなみに列優先順を使用する言語としてFortranを例にあげています。

f:id:AdwaysEngineerBlog:20180615150401j:plain

多次元配列へのアクセス

1次元配列に関しては連続したメモリ配置となるのでパフォーマンスの問題は起きません。(多次元)配列へ効率良くアクセするために多くの言語で共通して使われるアルゴリズムがあります。
配列が保持するバイト数は、(配列内の各要素の数) x (要素ごとのバイト数)になりますが、多くの言語処理系では配列の末尾にパディングバイトを追加して配列の合計の長さがちょうど良い値(4など)の倍数になるようします。また、最適化コンパイラは2Byte, 4Byte, 8Byteなどの共有サイズの倍数のメモリアドレスを開始位置として配列を記憶領域に割り当てようとします。これにより、その配列の直前の記憶領域に対してパディングバイトを追加することになります。例えば、直前に存在するオブジェクトがchar型の1Byteオブジェクトだった場合、その1Byteの直後に3Byteのパディングバイトを追加し、割り当てようとしている配列の先頭要素が4Byte境界に位置するようにアラインメントします。

1次元配列内の任意の要素のアドレスを取得するのはとても簡単です。
任意の要素のアドレス = 配列のベースアドレス + (インデックス x 要素のByte数)
となります。多次元配列の場合は、先に説明した行優先順と列優先順のようにそれぞれメモリ配置が違うのでアドレスの取得方法はそれぞれ異なります。

2次元配列、3次元配列、そして4次元配列のアドレスを取得する計算式はそれぞれ次のように表せます。

2次元配列
行優先の場合
任意の要素のアドレス = 配列のベースアドレス + (行インデックス x 列サイズ + 列インデックス) x 要素ごとのByte数

列優先の場合
任意の要素のアドレス = 配列のベースアドレス + (列インデックス x 行サイズ + 行インデックス) x 要素ごとのByte数
 

3次元配列
行優先の場合
任意の要素のアドレス = 配列のベースアドレス + ((奥行インデックス x 行サイズ + 行インデックス) x 列サイズ + 列インデックス) x 要素ごとのByte数

列優先の場合
任意の要素のアドレス = 配列のベースアドレス + ((列インデックス x 行サイズ + 行インデックス) x 奥行サイズ + 奥行インデックス) x 要素ごとのByte数
 

4次元配列
言葉では説明しづらいため、次のようなCの宣言を例に考えます。

int array[bounds0][bounds1][bounds2][bounds3];

行優先のCでは要素array[ i ][ j ][ k ][ m ]にアクセスするときの計算は次のようになります。

int* address = ***array + (((i * bounds1 + j) * bounds2 + k) * bounds3 + m) * sizeof(int);
/* or */
int* address = &array[0][0][0][0] + (((i * bounds1 + j) * bounds2 + k) * bounds3 + m) * sizeof(int);

冒頭質問の解説

後者の方が効率的にアクセスが可能です。
Cでは多次元配列操作に行優先順が使用されます。そのため、配列の各要素に連続的にアクセスしているので前者よりもキャッシュラインを効率的に使用してアクセスしています。
前者の場合、配列arrayは256 x 256行列のint型要素にアクセスする際に、2番目の要素には1024, 3番目には2048, 以降3076, 4096....といった1024 * jを係数として、係数倍されたアドレスにアクセスすることになります。 これは記憶領域内で1024 * j[bit]の距離があるアドレスを逐次的に操作しているのでスラッシングを引き起こします。