Unrolled linked list

アンローリング連結リストとは

アンローリング連結リスト（Unrolled linked list）は、従来の連結リストの拡張版であり、各ノードに複数の要素を格納できる点が特徴です。この構造により、メモリ使用量の効率化とCPUキャッシュの利用率向上が期待できます。

基本構造

アンローリング連結リストのノードは、以下の要素で構成されます。

next: 次のノードへの参照
numElements: 現在ノードに格納されている要素数
elements: 要素を格納する配列（最大`maxElements`個）

各ノードは最大で`maxElements`個の要素を保持できます。`maxElements`の値は、ノードが数個のキャッシュラインに収まるように調整されます。リスト内の要素の位置は、ノードへの参照と配列内の位置のペアで特定されます。また、双方向リストとして実装する場合は、前のノードへの参照も保持します。

要素の挿入と削除

挿入:

1. 要素を挿入するノードを特定します。
2. ノードの`elements`配列に要素を追加し、`numElements`をインクリメントします。
3. 配列が満杯の場合、新しいノードを現在のノードの前または後ろに挿入します。
4. 現在のノードの要素の半分を新しいノードに移動し、新しい要素を追加します。

削除:

1. 削除する要素があるノードを特定します。
2. `elements`配列から要素を削除し、`numElements`をデクリメントします。
3. `numElements`が`maxElements/2`より小さくなると、隣接ノードから要素を移動させます。
4. 隣接ノードの要素も`maxElements/2`より少ない場合は、ノードを統合します。

これらの処理により、メモリ使用効率を最適化します。

アンローリング連結リストの利点

アンローリング連結リストの主な利点は、メモリ使用量の削減です。ほとんどのノードが常に半分以上埋まっている状態を維持できるため、メモリの浪費を抑えられます。要素の挿入や削除がランダムに行われても、各ノードは平均して3/4程度まで埋まっていると考えられます。

メモリ使用量の計算

以下のパラメータを定義します。

`m`: `elements`配列の最大長（`maxElements`）
`v`: ノードあたりのオーバーヘッド（参照など）
`s`: 要素1つのサイズ

n個の要素を格納する場合、アンローリング連結リストが消費するメモリサイズは概ね

`(v/m + s)n`からその2倍の間になります。

従来の連結リストでは`(v + s)n`、配列では`sn`のメモリが必要となるため、特に`maxElements`が大きい場合や、要素のサイズが小さい場合に、アンローリング連結リストのオーバーヘッド削減効果が大きくなります。要素サイズが1ビットのような極端に小さい場合、オーバーヘッドが最大で64倍になることもあります。

また、メモリアロケータが追加するメタデータもオーバーヘッド`v`を増加させるため、アンローリング連結リストの利用はさらに魅力的になります。

キャッシュ効率

アンローリング連結リストはCPUキャッシュの効率も向上させます。各ノードが満杯の状態で、キャッシュラインのサイズを`B`とすると、リスト全体の走査は概ね`n/B`回のキャッシュミスで完了します。要素サイズがキャッシュラインサイズより小さい場合、従来の連結リストよりもキャッシュミスを減らすことができます。いずれの場合も、操作時間はリストのサイズに比例して増加します。

関連技術

CDRコーディング: アンローリング連結リストと同様に、連結リストのオーバーヘッドを削減し、キャッシュ局所性を向上させる手法です。
スキップリスト: 高速な走査を可能にする連結リストの変種ですが、挿入・削除の面ではアンローリング連結リストに劣ります。
B木・T木: アンローリングされた二分木とみなせる点で、アンローリング連結リストと類似しています。
XOR連結リスト: 双方向リストにおいて、2つのポインタをXOR処理した1つのポインタで表現することで、メモリ使用量を削減します。

まとめ

アンローリング連結リストは、メモリ効率とキャッシュ効率の両面で優れたデータ構造であり、特に大量のデータを扱う場合に有効です。要素の挿入や削除も効率的に行えるため、さまざまなアプリケーションでの利用が期待されます。

もう一度検索