行列のメモリレイアウト

ATY — Wed, 10 Apr 2024 06:53:14 +0000

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

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

に対し

\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} }\\

[a11a21a31]↓[a12a22a32]↓[a13a23a33]↓\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

パフォーマンス

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

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

[a1a2a3]+[b1b2b3]\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