はじめに
多次元配列のメモリレイアウト方式について調べた内容を記事にしました。
多次元配列要素のメモリレイアウト方式
1次元配列は各要素がメモリ上の連続したアドレスに格納されますが、多次元配列の場合実装方式は主に3つの種類があり、言語によって異なります。
以下では、2次元配列Aを例に実装方式の違いを説明しています。
A[i][j] \quad (i = 0, 1 \quad j = 0, 1, 2)
Row-major order
Row-major order方式では配列Aの各要素とメモリ上の値の対応は以下の表のようになります。
簡単のため、配列Aの最初の要素のメモリアドレスを0としています。
この方式では配列を各行ごとに順にアクセスすることでメモリ上でのシーケンシャルアクセスなアクセスが可能となります。
| アドレス | 値 |
|---|---|
| 0 | A[0][0] |
| 1 | A[0][1] |
| 2 | A[0][2] |
| 3 | A[1][0] |
| 4 | A[1][1] |
| 5 | A[1][2] |
Column-major order
Column-major order方式ではRow-major order方式とは反対に各列ごとに順にアクセスすることでメモリ上でのシーケンシャルアクセスなアクセスが可能となります。
配列Aの各要素とメモリ上の値の対応は以下です。
| アドレス | 値 |
|---|---|
| 0 | A[0][0] |
| 1 | A[1][0] |
| 2 | A[0][1] |
| 3 | A[1][1] |
| 4 | A[0][2] |
| 5 | A[1][2] |
Iliffe vectorを用いた方式
Iliffe vectorとは多次元配列を実装する際に用いられるデータ構造の１種で、N次元配列に対し、(N-1)次元配列のポインタで構成された1次元配列です。
この方式は上の２方式とは若干異なっており、2次元配列の各行のポインタからなる配列と各行データの配列からなります。
| アドレス | 値 |
|---|---|
| 0 | $p_0$ |
| 1 | $p_1$ |
| アドレス | 値 |
|---|---|
| $p_0$ | A[0][0] |
| $p_0 + 1$ | A[0][1] |
| $p_0 + 2$ | A[0][2] |
| アドレス | 値 |
|---|---|
| $p_1$ | A[1][0] |
| $p_1 + 1$ | A[1][1] |
| $p_1 + 2$ | A[1][2] |
メモリレイアウトを意識したコーディング
メモリ上のデータにアクセスする場合はシーケンシャルにアクセスしたほうが処理時間が短くなります。その理由は以下の２つです。
したがって
- Row-major order方式、Iliffe vector を用いた方式
⇒ 行ごとにアクセスする (A[0][0], A[0][1], A[0][2], A[1][0], ...) - Column-major order方式
⇒ 列ごとにアクセスする (A[0][0], A[1][0], A[0][1], A[1][1], ...)
のようにアクセスすることで、処理時間を最小限に抑えることができます。
言語ごとの実装方式
いくつかの言語について実装方式の違いを表にまとめました。
| 実装方式 | 言語 |
|---|---|
| Row major | C, C++, Go, Python(Numpy) |
| Column major | Fortran, MATLAB, R |
| Iliffe vector | Java, C#, Scala, Swift |
参考
- 本記事全般についての参考
https://en.wikipedia.org/wiki/Row-_and_column-major_order - Iliffe vectorについて
https://en.wikipedia.org/wiki/Iliffe_vector - Go言語の配列メモリレイアウト
https://stackoverflow.com/questions/39561140/how-is-two-dimensional-arrays-memory-representation - DRAMアクセス速度について
https://www.quora.com/Is-sequential-access-to-RAM-faster-than-random - SIMD, キャッシュ
プロセッサを支える技術 (Hisa Ando) https://www.amazon.co.jp/dp/4774145211/
-
DRAMは2次元的に並んだコンデンサとトランジスタからなっており、メモリの読み出し時は目的アドレスのコンデンサを含むコンデンサ列全体を放電させて電圧値を読み取るのでシーケンシャルアクセスのほうが速く読み取れる。 ↩
-
SIMD(Single Instruction Multiple Data) 1つのCPU命令を複数のデータに対して同時に実行する仕組み。通常よりもサイズの大きいレジスタに複数のデータをロードし、それらに対し同一の演算を実行する。データのアドレスが連続している場合、1回のSIMDロード命令でレジスタ1個分のデータをロードできるが、アドレスが不連続の場合、複数回のロード命令が必要となる。 ↩