最近CPythonのメモリ管理のコード (obmalloc.c) を読んでいたのだが、いろいろなところで連結リストが使われていた。教科書的な連結リストの実装と比べていくつか工夫が見られて面白かったのでメモしておく:

  1. ノードを配列としてまとめて確保
  2. ソートされた連結リストへの挿入のためのインデックス

arena_objectの説明

CPythonはメモリを管理する単位は色々あるのだが、一番大きい単位がアリーナである。アリーナはデフォルトで256KiBある。ただのメモリのかたまりであるアリーナの情報を管理しているのがarena_objectという構造体で、これが連結リストのノードになっている。

arena_objectは以下の3つの状態をもつ:

  1. アリーナが割り当てられていない
  2. アリーナが割り当てられていて、空きがある
  3. アリーナが割り当てられているが、空きがない

1の状態のarena_objectはunused_arena_objectsという単連結リストにつながれていて、2の状態のarena_objectはusable_arenasという双連結リストにつながれている。

usable_arenasはnfreepoolsという値について昇順になるようにソートされていて、空きの少ないアリーナほど前に来るようになっている。その結果、リストの後方にある空きの多いアリーナが解放される可能性を高めているのである。

実装の工夫

すべてのarena_objectはarenasというグローバルな配列で確保されている。この配列の長さは最初16で、新たなarena_objectが必要になったときはreallocして配列の長さを2倍にするという実装になっている。教科書的な連結リストの実装だとノードを追加するたびにmallocするが、ここではJavaのArrayListのような仕組みになっている。

これによってノード追加時の最悪計算量がO(n)になってしまうが、そのかわり空間局所性が高くキャッシュが効きそうだ。

他の工夫としてusable_arenasへの挿入がある。ソートされた連結リストの適切な場所に新たなノードを挿入するにはO(n)の時間がかかるが、nfp2lasta[MAX_POOLS_IN_ARENA + 1]という配列をルックアップすることによってどこに挿入すればいいかO(1)で分かるようになっている。