ハクソク

世界を動かす技術を、日本語で。

C言語における安定ポインタを持つ高速で成長可能な配列

2025年8月7日原文(danielchasehooper.com)

概要

  • Segment Array は、動的配列の代替として使えるデータ構造
  • 安定したポインタ を保証し、アリーナアロケータと相性が良い
  • 各セグメントは前の2倍のサイズで、必要時のみ確保
  • 高速なランダムアクセス と高いメモリ効率を両立
  • 実装はシンプルで120行未満、C言語のシングルヘッダとして提供

セグメント配列（Segment Array）の概要

  • Segment Arrayは、 動的配列 の代替として利用可能なデータ構造
  • ポインタの安定性 を確保し、アイテムの移動が発生しない設計
  • 各セグメントは 前のセグメントの2倍のアイテム数 を保持
  • 必要な時だけ新しいセグメントを 動的確保 する方式
  • アリーナアロケータ との高い親和性

構造とメモリレイアウト

  • Segment Arrayは、 固定長のポインタ配列 （segments）を持つ
  • 各ポインタは個別のセグメント領域を指し、 セグメントサイズは2のべき乗
  • 先頭6セグメント（1,2,4,8,16,32）は省略し、 64アイテムから開始
  • 26セグメントで 最大約42億個 のアイテムを格納可能（u32インデックス対応）
  • セグメント配列自体が キャッシュ効率 を高める役割

インデックス計算と高速アクセス

  • インデックスから該当セグメントとオフセットを ビット演算 で高速算出
    • log2i関数で セグメント番号 を決定
    • capacity_for_segment_countで 累積容量 を計算
  • アクセスは 定数時間 で実現
  • 順次アクセス時は、 各セグメントを直接ループ 可能

アイテム追加と容量管理

  • 新規アイテム追加時、 必要に応じてセグメントを確保
  • セグメントサイズはslots_in_segmentで計算
  • 容量を2のべき乗に揃える調整 も可能（ハッシュテーブル用途向け）

ジェネリクス（型安全な利用）

  • マクロを用いて 任意の型 に対応
    • SegmentArray(type)で型付き共用体を宣言
    • sa_get, sa_alloc等のマクロで 型安全なアクセス を提供
  • typeofやマクロが不要な場合は 省略可能

使用例

  • シングルヘッダ（segment_array.h）をインクルードし、 簡単なAPI で利用可能
    • アイテム追加、取得、全件ループ、解放（arena未使用時のみ）

他データ構造との比較

  • 固定長配列 ：拡張不可、ランダムアクセス・連続性・効率良
  • 動的配列 ：拡張可、アイテム移動あり、ランダムアクセス良
  • チャンク付きリスト ：拡張可、ランダムアクセス不可、メモリ効率高
  • ハイブリッド方式 ：一括生成時に有効、最終的に固定長配列へ
  • 仮想メモリアレイ ：巨大な仮想空間予約、組込み等では利用不可
  • Segment Array ：拡張可、アリーナ親和性・ランダムアクセス良、連続性なし

メモリ効率（平均値）

  • 固定長配列： 100%
  • 動的配列： 75～83% （成長率による）
  • チャンクリスト： ほぼ100%
  • ハイブリッド： 100%
  • 仮想メモリアレイ： 100%
  • Segment Array： 75%

適用場面とまとめ

  • アイテム数が事前に不明 かつ アリーナアロケータ を使う場面で有用
  • 例：プロファイラ等で 動的生成される大量データ の管理
  • 高速・安定・アリーナ親和性 の三拍子
  • シングルヘッダ実装は 120行未満 で完結
  • 詳細実装やダウンロードは ニュースレター登録 で入手可能

参考情報

  • Per Vognsen による名称「Segment Array」
  • Zig では「Segmented List」と呼称
  • C++のstd::deque は類似だが設計思想が異なる
  • アリーナアロケータ 利用時に特に真価発揮

結論

  • Segment Arrayは、 拡張性・速度・安定性・メモリ効率 をバランス良く実現
  • C言語で簡潔に実装可能 な汎用データ構造
  • 特定用途（アリーナ・動的生成）で 他構造より優位性 あり
  • 実装や利用に関するフィードバック歓迎

Hackerたちの意見

今日のコンピュータは、アイスレイクで導入されたポインタの64ビット中48ビットしか使ってないんだって。https://en.wikipedia.org/wiki/Intel_5-level_paging でも、これって結局std::dequeのバリエーションじゃないの？ https://en.cppreference.com/w/cpp/container/deque.html

└

256 TiB以上のRAMを使うセットアップって、どんなのがあるの？

└

std::dequeはランダムアクセスに対応してるの？

└

原則的にはdequeとそんなに違わないけどね。 (1) dequeは固定サイズのブロックを使ってて、サイズが増えるブロックじゃない。 (2) dequeueは前に追加することができて、内部的にもう一つの間接レベルが加わる。

└

C++でのdequeの実装の詳細は正確には知らないけど、最も人気のあるスタックオーバーフローの説明を考えると、いくつかの即座の落とし穴があるね。T*マップ自体が無制限に聞こえるし、各チャンクが固定のサイズしか割り当てないなら、フラグメンテーションやオーバーアロケーションにはひどいかも。インデックスも割り算に依存してるみたい。2の累乗のアプローチだと、配列の前から本当に削除することはできないけど、保存するポインタの数は一定で、メモリのフラグメンテーションは良くなる。 (OPはdequeの動作をサポートしたいとは言ってなかったけど、修正するのはそんなに難しくないはず。ただ、インデックスはまた計算を通る必要がありそう) OPの配列は使ったことないけど、std::dequeのメモリアロケーションパターンで何度も痛い目にあったから、生の配列とポインタ追跡で書き直さなきゃいけなかった。

└

std::dequeの詳細は実装によって異なり、MSVCではほとんど使えないと考えられてるよ。MSVCはブロックサイズが小さすぎて、役に立たないんだ。libc++のブロックサイズは16要素か4096バイトだよ。実装の詳細を理解して制御できるコンテナを使う方が一般的には良いね。自分はこれをstd::dequeのバリアントとは呼ばないかな。間違ってはいないけど、あまり役に立つ観察とは思わないな。

└

5レベルのページングを示す図にあるアイコンって、雪の結晶や三角形みたいなの、何なんだろう？

└

残念ながら、Microsoftの実装ではstd::dequeが制約されてるんだ。ブロックサイズが8バイトを超えるTだと、リンクリストに落ちちゃうし、バイナリ互換性のために修正できないんだ。 https://github.com/microsoft/STL/issues/147 それに対して、GNUの実装は512バイトのブロックサイズを持ってる。幸いなことに、高性能システムでは無制限のキューが必要な場面は限られてるよ。

安定したサイズ変更可能なベクターの実装には、仮想メモリも使えるよ。最初に予約した仮想メモリの量に基づいて最大長さが決まって、その後必要に応じて物理的な容量を増やすためにコミットする感じ。

└

そうだね、ランタイムオーバーヘッドが少ないから、約4kBの最小割り当てサイズで問題なければ。

└

記事ではこの代替案に言及していて、埋め込みコンテキストやWASMでは機能しないことも指摘してるよ。

いいね、ただマクロの「トリック」がちょっと多すぎる気がする。Cではそういうやり方が一般的なのは理解してるけど（30年Cを書いてきたから）、あんまりやりたくないな。あと、厳密に言うと、インデックス関数の10命令の逆アセンブルにclz命令が実際に出てこないのは変じゃない？コンパイラに最適化されたのかな、インデックスがコンパイル時にわかるからとか。セットアップと説明の後だと、ちょっと驚いた。

Hacker Newsで議論の続きを見る