行列のメモリレイアウト

行列のメモリレイアウトにはrow-majorとcolumn-majorの2種類がある。コンピュータのメモリ空間にデータを配置する以上2次元データをsequentialに並べる必要があるが、行を列数分並べるか列を行数分並べるかの違いがある。

$$A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix}$$

に対し

• row-major

$$\underrightarrow{ \begin{bmatrix} a_{11} & a_{12} & a_{13} \end{bmatrix} }\\ \underrightarrow{ \begin{bmatrix} a_{11} & a_{12} & a_{13} \end{bmatrix} }\\ \underrightarrow{ \begin{bmatrix} a_{31} & a_{32} & a_{33} \end{bmatrix} }\\$$

• colum-major

$$\begin{bmatrix} a_{11} \\ a_{21} \\ a_{31} \\ \end{bmatrix} \Bigg\downarrow \begin{bmatrix} a_{12} \\ a_{22} \\ a_{32} \\ \end{bmatrix} \Bigg\downarrow \begin{bmatrix} a_{13} \\ a_{23} \\ a_{33} \\ \end{bmatrix} \Bigg\downarrow$$

パフォーマンス

どちらのレイアウトを採用するかはライブラリごとに違う。また場合によっては別の型に分かれていたり、コンパイルオプション等で指定できたりする。

メモリレイアウトは実行性能に影響する。コンピュータの垂直方向の演算は高速だが水平方向の演算は遅い。

• 垂直方向

$$\begin{bmatrix} a_1 & a_2 & a_3 \end{bmatrix}\\ +\\ \begin{bmatrix} b_1 & b_2 & b_3 \end{bmatrix}\\$$

それぞれの演算は並列に処理できるため、1stepで計算できる

• 水平方向

$$a_1 + a_2 + a_3$$

演算に依存関係があるため、計算に2step必要となる。

したがって、行列とベクトルの積Axを計算する場合、内積をベクトル長分計算するより

$$\begin{bmatrix} a_1 & a_2 & a_3 \end{bmatrix}\\ \times\\ \begin{bmatrix} b_1 & b_2 & b_3 \end{bmatrix}\\$$

のようにベクトルの積を行列の列数分計算して足したほうが高速である。

すなわち、Axのように行列の右から垂直ベクトルをかけるときはcolumn-major、xAのように行列の左から水平ベクトルをかけるときはrow-majorの方が高速である。これらの計算は転置すれば同じである。

メリットとデメリット

column-majorのメリットは、高速な積の形Axが数式と同じことである。裏を返せばメリットはその程度しかない。

row-majorのメリットは、コードの見た目とメモリレイアウトが同じことである。

A = [
    [a11, a12, a13],
    [a21, a22, a23],
    [a31, a32, a33],
]

i,jのアクセス順も同じである。column-majorだと逆になる。

aij = A[i][j];

また、複合代入がシンプルに書けるのもメリットと言える。

x *= A

column-majorではこうは書けない。

x = A * x