連続アクセスと1次元データ

数値計算では、長い1次元配列を順に読む処理が頻繁に出てきます。同じ要素数を読む場合でも、メモリ上で連続して読むか、飛び飛びに読むかで実行時間が変わることがあります。

論理メモリ番地は1次元

プログラムから見るメモリ番地は、基本的に1次元の並びです。プログラムは通常、連続した論理アドレス空間の中にデータが置かれているように扱えます。

address:  ... 1000 1008 1016 1024 1032 1040 ...
value:        a[0] a[1] a[2] a[3] a[4] a[5]

Vec<f64> の要素は、この1次元のアドレス空間の中で連続して並びます。 f64 は8バイトなので、隣の要素へ進むことは、典型的にはアドレスを8バイト進めることに対応します。

連続アクセス

次のように Vec<f64> を先頭から順に読むと、メモリ上でも隣の要素へ進みます。

fn sum_contiguous(x: &[f64]) -> f64 {
    let mut s = 0.0;
    for value in x {
        s += *value;
    }
    s
}

CPUはメモリから1個の f64 だけを読むのではなく、周辺のデータをまとめて cache line に載せます。連続して読むと、cache line に載ったデータを無駄なく使いやすくなります。

飛び飛びアクセス

一方、次のように一定間隔で要素を読むと、実際に使わないデータも cache line に載ることがあります。

fn sum_every_k(x: &[f64], k: usize) -> f64 {
    let mut s = 0.0;
    let mut i = 0;
    while i < x.len() {
        s += x[i];
        i += k;
    }
    s
}

このようなアクセスでは、読んだバイト数のわりに使う値が少なくなり、メモリ帯域やcacheの効率が悪くなることがあります。ここでいう「何要素ごとに読むか」が、1次元データでのstrideの直感です。

実際には

実際には、論理アドレスはOSやMMUによってページ単位で物理メモリに対応づけられます。ただし、配列をどの順序で読むかを考える段階では、まず論理アドレス空間での連続性を見れば十分です。

第4章への接続

多次元配列では、数学的な添字が2個以上あっても、実データは1次元bufferに置かれます。 row-major、column-major、stride、loop order は、多次元配列とメモリレイアウトで扱います。

Keyboard shortcuts