よく使うデータへのアクセスを高速化するために、そういったデータを高速な記憶媒体に保持しておくことを、キャッシュすると言ったりします。
高速な記憶媒体はそれ相応に高い*1ので、大容量と両立することはできません。
そこで、よく使うデータを選別して、それだけをキャッシュにおいておくことが全体の高速化につながります。
具体的にどのデータが頻繁にアクセスされるかが事前にわかっている場合は、選別を最適化することができます。 しかし、オンライン的にアクセスがくる場合、未来予知をする必要があるため、最適解を求めることは不可能です。
最適解を近似するアルゴリズムに、LRUアルゴリズムがあります。 これは、キャッシュに入っていないデータへのアクセスが来た時、最も古いデータは捨てて代わりにそれを入れるというものです。
最近使っていないデータへのアクセスは、今後も来ないだろうと考えるのが常識的であり、それを採用したアルゴリズムになっています。 LRUというのは、least recent usedの略で、「最近使っていない」（ものを捨てる）という意味合いになっています。
実際には、一定数のデータを巡回的にアクセスする、などのパターンで最悪の性能を示すという弱点があります。 改善案が日々研究されているようですが、ここでは単純なLRUアルゴリズムを使うことにします。
実際にデータの順序を変更する方法
std::array<T, N> cacheについて、データが来るたびにそのデータを先頭に移動させるという方法です。
if( const auto it = std::find_if( cache.begin(), cache.end(), cond ); it != cache.end() ) {
// cache hit
std::rotate( cache.begin(), it, it + 1 );
return cache[0];
} else {
// cache miss
// ....
}
のように、std::rotate関数を使うと非常に簡潔に書けます。
また、頻繁に使われるデータが先頭付近に存在する可能性が高くなるため、先頭からの線形探索は思ったより高速に動作する可能性が高いです（連結リスト - Wikipedia）。
この方法は、sizeof(T)が大きい場合に大量のコピーが発生するために非効率です。
LRUオーダーを持つ方法
std::array<std::pair<T, size_t>, N>あるいは、std::pair<std::array<T, N>, std::array<size_t, N>>のような構造にする方法です。
前者はarray of struct (AoS, 構造体の配列)、後者はstruct of array (SoA, 配列の構造体）になっており、どちらが適切かは微妙なところです。
データの位置は変更せず、追加されたsize_t（実際にはもっと小さな型で十分であることが大半です）に順番（LRUオーダー）を記録します。
- キャッシュに入っているデータにアクセスが来た場合、現在のLRUオーダーより小さい値のLRUオーダーを一ずつインクリメントし、自分のLRUオーダーを0にする
- キャッシュに入っていないデータにアクセスが来た場合、LRUオーダーがN-1である要素を新たなデータで上書きし、LRUオーダーを0にする。他のLRUオーダーは一ずつインクリメントする
データの移動がないため、参照が無効になることがないのはうれしい点です。 どれを捨てるのかの判断にも線形探索が必要な点は「実際にデータの順序を変更する方法」に劣ります。
CPUのキャッシュは普通この方法で実装されています。
タイムスタンプを持つ方法
「LRUオーダーを持つ方法」では、アクセスのたびにLRUオーダーの書き換えが大量発生していましたが、代わりにタイムスタンプを持つ方法です。
アクセスがあるたびにタイムスタンプを更新し、どれを捨てるかの判断は単なる最小値の線形探索をすることによります。
タイムスタンプがオーバーフローしないようにするため、タイムスタンプ領域のサイズは「LRUオーダーを持つ方法」より大きくなります。
そのため、sizeof(T)が小さい場合にはそのオーバーヘッドが無視できなくなります。
以上の三手法は、sizeof(T)の大きさによって使い分けるとよいです。
sizeof(T)が小さい場合は「実際にデータの順序を変更する方法」が簡単です。一方、タイムスタンプ領域が無視できるほどsizeof(T)が大きいのであれば「タイムスタンプを持つ方法」が便利です。
なお、「タイムスタンプを持つ方法」は、タイムスタンプが最も古いものがどこにいるのかを判別するために最小ヒープを用いることで計算量を改善することが可能です。
ところで、「実際にデータの順序を変更する方法」は追加の領域が必要になっておらず一見不思議です。
これは、集合としておなじ配列に内在する冗長性（順番成分）がlog_2(N)ビット存在することが原因です。 LRUオーダーを覚えるためにこの情報量をかつようしているために追加の領域が必要になっていないのです。
連想配列に適用する方法
先の3つの手法は、キャッシュにデータがあるかの探索は線形検索でした。 しかし、通常の用途では連想配列を用いることが多いです。
さきの3つの手法のうち、「LRUオーダーを持つ方法」と「タイムスタンプを持つ方法」はそのまま連想配列に適用できます。 「実際にデータの順序を変更する方法」は連想配列の場合には使えません。
ところで、ECMAScript 2015で追加されたMapは、挿入順でイテレートするという動作をします。
これを利用すると、追加の記憶なしに「最近使ったことにする」touch（LRUオーダーを0にする）や「古いのを捨てて挿入する」insert関数が以下のように書けます。
性能がベストなのかはよくわかりませんが、それほど悪くないように思われます。
class FullAssociativeLRUTable extends Map {
constructor(size) {
super();
this.maxSize_ = size;
}
touch(tag) {
if (this.has(tag)) {
// いったん削除して再挿入で、MRU position に移動
let data = this.get(tag);
this.delete(tag);
this.set(tag, data);
} else {
console.log(`${tag}は含まれていないのにtouchした`);
}
}
insert(tag, data) {
if (this.has(tag)) {
console.log(`${tag}は含まれているのにinsertした`);
} else if (this.size < this.maxSize_) {
this.set(tag, data);
return null;
} else {
// keys().next()は最初の要素 (LRU position)
let minTag = this.keys().next().value;
let data = this.get(minTag);
this.delete(minTag);
this.set(tag, data);
return data;
}
}
}
