Linux のプロセス管理を支える侵入型リンクリストの仕組み
Intrusive Linked Lists
侵入型リンクリストは、リンクをデータ構造自体に埋め込む方式で、通常のリンクリストに比べてメモリ割り当てが少なく、キャッシュ効率も優れています。Linux カーネルでは、この侵入型リンクリストを doubly circular linked list として実装し、プロセス管理やメモリ管理などに広く利用しています。本記事では、その基本概念から、Linux の task_struct における具体的な実装までを解説します。
侵入型リンクリストは、リストノードがリンク対象のオブジェクトに埋め込まれているため、データポインタを必要としません。
HNでの議論
49- el_pollo_diablo
記事が侵入型データ構造の利点として挙げている点よりも、さらに踏み込んで、リンクリストを例に考えてみよう。
記事でも述べられているように、侵入型データ構造は自然に間接参照を一つ減らすことができる。従来のリスト（リストノードがペイロードを所有する方式）で同じことをしようとすると、ペイロードの型ごとに異なるノード型が必要になる。これは、単相化されたジェネリクスを適切にサポートしていれば簡単で、C++ の std::list がその例だ。しかし C では、実装をマクロで生成しなければならず、厄介だ。C は自然に void * による間接参照へと向かうため、侵入型リストの方が魅力的になる。
侵入型データ構造のもう一つの利点は、間接参照なしでペイロードを複数の並列コレクションにリンクできることだ（従来のコレクションでは、例えば一つのコレクションがペイロードを所有し、他のコレクションはそれらへの非所有ポインタを保持するだけになるだろう）。
最後に、そして最も重要なことだが、侵入型データ構造の決定的な特性は、要素の割り当て責任をユーザーに委ねることだ。要素はヒープ上、スタック上、グローバル配列内（記事の「initholes」のように）、特別なアリーナ内など、どこにでも割り当てることができる。不均一な割り当て戦略を使うことさえ合理的だ。例えば、循環リストの場合、アンカーノードをスタックに割り当て、他のノード（ペイロードに埋め込まれたもの）をヒープに割り当てる、といった具合だ。
- pclmulqdq
侵入的リンクの主な利点が、ちょっとした補足のようにしか述べられていなかったのに驚いた。それは、データをコピーせずにリスト間（およびリスト内）で移動できることだ。また、オブジェクトへのポインタがどこか別の場所にあれば、リストの途中からの削除も O(1) で行える。その結果、大きな状態構造体を持っていて、リストの走査をあまり行わない場合、侵入的リンクはベクターのようなパック構造を使うよりもはるかに高速になる。
- flohofwoe
ふむ、興味深い。ここで紹介されている双方向リンクリストには、AmigaOS のエレガントな「オーバーラップしたリストヘッダ」のトリックが欠けている（少なくとも、私はそれをそこで最初に見た）。
例えば、AmigaOS のリストノードは conventional で、次のノードへのポインタ（succ）と前のノードへのポインタ（pred）の2つのポインタを持っている。
struct Node {
struct Node* ln_Succ;
struct Node* ln_Pred;
};
ほとんどの AmigaOS 構造体は、このような Node 構造体を先頭に埋め込んでいる。
...しかし、リストヘッダは3つのポインタを持ち、基本的に2つのオーバーラップした Node 構造体を形成している。
struct List {
struct Node* lh_Head;
struct Node* lh_Tail;
struct Node* lh_TailPred;
};
空のリストでは、lh_Head は &lh_Tail を指し、lh_TailPred は &lh_Head を指す。lh_Tail ポインタは常にヌルである（これが「終端マーカー」）。
要素が入ったリストでは、lh_Head は最初のリストノードの埋め込み Node 構造体を指し、lh_TailPred は最後のリストノードの埋め込み Node 構造体を指す。最後のノードの ln_Succ ポインタは、リストヘッダの lh_Tail ポインタのアドレスを指す（...これは常にヌル）。
このようにすれば、前方・後方への移動、ノードの挿入・削除には、既存のノードポインタだけが必要になる。succ または pred ポインタをたどってリストを走査するとき、ヌルポインタに遭遇すれば終端に達したことがわかる。
記事の Linux スタイルのリストでは、終端を検出するためにリストヘッダのアドレスを知る必要があるようだが、Amiga スタイルのリストではそれは不要だ（コス...）
- eventualcomp
ウェイター、ウェイター！ベンチマークなしの最適化記事をもっとください！
- zahlman
こういうことは、もう標準的なコンピュータサイエンスやソフトウェア工学の学部課程では教えられていないのだろうか？