Unrolled linked list

Unrolled linked listは連結リストの変種で、各ノードに格納する要素を複数個にしたものである。CPUキャッシュの利用効率を劇的に向上させるとともに、リストのメタデータ（参照など）によるメモリ消費のオーバーヘッドを削減できる。B木とも関連がある。

概要

典型的なUnrolled linked listの実装は以下のようになる。

record node {
    node next        // リストの次のノードへの参照
    int numElements  // このノード中の現在の要素数。最大maxElements個
    array elements   // 要素の配列。maxElements個の領域にnumElements個の要素が格納されている
}

各ノードはある一定の最大個数（maxElements個）まで要素を格納できる。maxElementsの大きさは、1つのノードが1から数個程度のキャッシュラインに乗るように設定する。リスト中の要素の位置は、ノードへの参照と配列中の位置のペアで識別される。上記の実装に、リストの一つ前のノードへの参照を追加して、双方向のUnrolled linked listとすることもできる。

新しい要素を挿入する際は、要素が配置されるべきノードを探した上で、elements配列に要素を挿入し、numElementsをインクリメントすればよい。配列がすでに一杯だった場合は、まず現在のノードの前か後ろのいずれかに新しいノードを挿入し、現在のノードの配列の内容の半分を新しいノードへ移動した上で、要素を配列へ追加する。

要素を削除する場合も同様で、削除されるべき要素が入っているノードを探し、elements配列から要素を削除し、numElementsをデクリメントする。numElementsがmaxElements÷2より小さくなった場合は、隣接ノードから現在のノードへ要素を移動させる。隣接ノードの要素もmaxElements÷2より少なかった場合は、要素を移動させてノードをひとつにまとめる。これにより、使用領域の無駄を省くことができる。

性能

Unrolled linked listの最大の利点は、使用領域を削減できることにある。たかだか1つのノードを除けば、それ以外の全てのノードは常に最低でも半分以上埋まっている状態になる。要素の挿入や削除がランダムに行われたとすると、各ノードは平均3/4まで埋まっている計算になる。

リストのパラメータを

* m = maxElements, 各elements配列の最大長
* v = 要素数や参照の保存によって発生する、ノードあたりのオーバーヘッド
* s = 要素一つのサイズ

とすると、n個の要素を格納するために消費される領域のサイズは $(v+sm)\lceil n/m\rceil$ （おおよそ $(v/m+s)n$ ）からその2倍の間となる。これと比較として、通常の連結リストで消費される領域は（vは一般に小さいとしても） $(v+s)n$ であり、また最もコンパクトなデータ構造である配列の場合は $sn$ の領域を必要とする。Unrolled linked listではリスト中の要素数に対するvのオーバーヘッドを効果的に削減しており、maxElementsが大きい場合や、要素一つのサイズが小さい場合などにオーバーヘッドの削減効果がより大きくなる。

要素一つのサイズが特に小さい場合（例えば1ビットなど）、データに対するオーバーヘッドのサイズは（データモデルにもよるが）最大64倍にもなる。その上、多くのメモリアロケータではメモリも割り当ての度に少量のメタデータを作成するため、オーバーヘッドvがその分増加する。これらの理由により、Unrolled linked listはより魅力的となる。

また、Unrolled linked listを使用することでCPUキャッシュの利用効率を向上させることもできる。各ノードが一杯の状態で、キャッシュラインのサイズをbとすると、リスト全体の走査はおよそ $n/B$ 回のキャッシュミスで行える^[1]。さらに、各要素一つあたりのサイズがキャッシュラインのサイズと比較して小さければ、通常の連結リストと比較して少ない回数のキャッシュミスでリスト中を走査することができる。いずれの場合でも、操作に必要な時間はリストのサイズに比例して増加する。