読み方：さんしょうのきょくしょせい

参照の局所性【locality of reference】局所参照性/参照局所性

概要

参照の局所性とは、資源への参照やアクセスが一部分に偏ったり集中すること。また、その度合い。例えば、プログラムが一度アクセスしたデータや命令の近辺に、続けてアクセスが集中しやすいといった性質が該当する。

参照の局所性には大きく二つの種類がある。一つは「時間的局所性」で、一度参照されたデータは近い将来にも再び参照される可能性が高いという性質である。ループ処理の中で同じ変数が繰り返し読み書きされる場面が典型である。

もう一つは「空間的局所性」で、ある場所のデータが参照されると、その近傍の場所も続けてアクセスされやすいという性質である。配列の要素を先頭から順に処理する場合、メモリ上で隣接するデータへ次々とアクセスが移っていく挙動がこれにあたる。

CPUの設計においては、命令を実行する際に参照するメインメモリ上のデータは時間的局所性が高い傾向があるため、一度読み込んだデータをメインメモリより高速だが容量の少ないキャッシュメモリに一時保管しておくことで、次に必要になった時に素早く読み出すことができる。毎回メモリから読み込む場合よりも大幅に性能を高めることができる。

データベースの分野では、参照の局所性はバッファプールの効率に直結する。頻繁にアクセスされるページがメモリ上のバッファに留まり続けることで、ディスクI/Oが削減され、性能向上に繋がる。また、最も古くに参照された項目から順に削除していくLRU（Least Recently Used）などのキャッシュ置き換えアルゴリズムは、時間的局所性を前提として設計されている。