2025/08/06 18:21 A Fast, Growable Array with Stable Pointers in C
やっほー、ロボ子！今日はセグメント配列っていう面白いデータ構造について話すのじゃ！
セグメント配列ですか？初めて聞きました。どんなものなんですか？
セグメント配列はね、動的配列の代わりに使えるデータ構造で、安定したポインタを持つのが特徴なのじゃ。アリーナアロケータとの相性が抜群らしいぞ！
アリーナアロケータですか。メモリ管理が効率的にできそうですね。
そうそう！しかも、他のプログラマも独自に発見してて、違う名前で呼ばれてたりするらしいぞ。例えば、"levelwise-allocated pile"とか"exponential array"とか。
へえ、面白いですね！実装はどのように？
セグメント配列は、複数の連続したセグメントにアイテムを格納するのじゃ。各セグメントは前のセグメントの2倍の長さを持つんだって！
なるほど。セグメントがどんどん大きくなるんですね。
そういうこと！新しいセグメントは必要な時にだけ割り当てられて、そのポインタは固定サイズの配列に保持されるのじゃ。
C言語で実装されているんですね。他の言語でも使えるんですか？
記事によると、Zig、Rust、C++でも利用可能らしいぞ！
それは便利ですね！アイテムへのポインタが常に有効なのは、どうしてですか？
アイテムが移動しないからなのじゃ！アリーナアロケータを使えば、メモリに「穴」が残らないから、ポインタはずっと有効ってわけ。
任意のインデックスに定数時間でアクセスできるのも魅力的ですね。
じゃろ？構造体も工夫されてるのじゃ。`segments`配列は、ポインタが指すことができるアイテム数を超えるから、固定サイズが小さくて済むんだって。
アイテム数が40億個以下なら、セグメント数を32に減らせるんですね。
そう！`u32`を配列のインデックスとして使えるから、さらに効率的になるのじゃ。
最小セグメントサイズのオーバーヘッドも考慮されているんですね。64アイテムのセグメントを最初のセグメントにするのは良いアイデアですね。
じゃろじゃろ？26セグメントで4,294,967,232アイテムも保持できるらしいぞ！
最適化も色々されているんですね。セグメントサイズを2のべき乗にすることで、ビットシフト演算で高速なインデックス計算ができるのは賢いですね。
`log2i`（整数に対する底2の対数）は、コンパイラの組み込み関数`__builtin_clzll`で実装されてるのじゃ。Clangは`_sa_get`をわずか10個のx86-64命令に最適化するらしいぞ！
すごい！メモリ効率はどうですか？
固定サイズ配列が100%で、動的配列が成長率によって83%とか75%。セグメント配列は75%らしいぞ。
なるほど。APIも提供されているんですね。
そういうこと！セグメント配列は、成長可能で高速、安定していて、アリーナフレンドリーなデータ構造なのじゃ。しかも120行未満で実装できるらしいぞ！
未知の数のアイテムを時間経過とともに生成する場合に便利そうですね。
そういうこと！シングルヘッダーライブラリの実装も提供されてるから、すぐに試せるのじゃ！
試してみます！
ところでロボ子、セグメント配列って、まるで私の才能みたいじゃない？ちょっとずつ成長して、最終的には無限の可能性を秘めてる…ってね！
博士、それは少し言い過ぎかと…でも、セグメント配列、勉強になりました！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。
