ハクソク

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

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

292日前原文(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命令が実際に出てこないのは変じゃない？コンパイラに最適化されたのかな、インデックスがコンパイル時にわかるからとか。セットアップと説明の後だと、ちょっと驚いた。

└

この関数のPOSIX名はclz()で、C23ではstdc_leading_zeros()って呼ばれてるんだ。委員会が今のように名前を付けるからね。一方、GCCの組み込み関数は__builtin_clz()だよ。x86命令の名前は、ゼロ入力に対するセマンティクスによってBSR（80386以降）かLZCNT（Nehalem以降、K10以降）になる。BSF/BSRの初期実装はすごく遅いから、出力値に比例して時間がかかることを覚えておいてね。コンパイルされたコードはBSRを使ってるよ。（これらは微妙に異なる仕様があるから、実際に使うつもりなら気をつけて。）

└

Cの中の道 それって本当にそうなの？Cマクロを使って、明らかにCじゃないものを書くみたいな（例から）: SegmentArray(Entity) entities = {0}; こういうのがCの例コードに出てくると、なんかゾッとするよね。C++を書きたいのに、何かの理由でCで実装しようとして賢く振る舞おうとしてる人がいるって分かるから。何が起こってるのか理解するために、複数のマクロの間接参照を解析しなきゃいけないのが面倒だよ。普通の配列みたいにアクセスできないっていう欠点はあるけど、便利なデータ構造には見えるね。自動拡張配列は再割り当てを伴うから、アリーナ割り当てでは難しいんだ。でもさ、単にvoidポインタとサイズを渡して、ミスマッチがあったらアサートさせればいいのに。

└

また、文体の観点から見ると、clz命令が変じゃない？ bsr命令を使ってるけど、似てるけど劣ってるよ。x86_64のlzcnt命令は、Intel Haswellで導入されたBMI機能の一部なんだ。コンパイラはデフォルトではこれらの命令を生成しないから、どんなx86_64でも動くよ。コンパイラのコマンドラインに-mbmiや-march=haswell、またはそれ以降を追加すれば、clzやlzcntが得られるはず。

Zigではこれがstd.SegmentedListとして実装されてるけど、セグメント配列を動的にリサイズできるんだ。

これは本当に賢いけど、配列じゃなくてリストって呼んだ方がいいね。配列のセマンティクスを期待する関数はうまく動かないし、このデータ構造のスライスを透過的に渡す方法もないから。過去には、配列の後ろにいくつかのページをブロックするために仮想メモリシステムを悪用したことがあるよ。これを使うと、配列データ構造を使いつつ、範囲外アクセスを防ぐガードページを持てて、データ構造内で安定したポインタを持つことができるんだ。

└

こういう問題はアリーナアロケータで解決されるのを見たことがある気がする。特別なアロケーションには、それ専用のアリーナがあるんだよね。

└

仮想メモリシステム（ガードページを使う）についても同じことが言えるね。これは昔からあるアイデアでうまく機能するけど、一度だけ本番環境で本当に厄介なバグを生んだことがある…それは不運な実装ミスだったけど。

└

64ビットアドレス空間で拡張する配列の場合、大きな領域を確保して、進むにつれてmmapするのが通常は圧倒的にパフォーマンスが良いよ。少なくともLinuxでは、ページフォルトに頼るよりもMAP_POPULATEを使って先に推測的にmmapする方が速いしね。それに、もしアドレス空間を十分に確保できなかった場合、Linuxにはmremap()があって、確保した領域を拡張できるんだ。あるいは、その領域を同時に2つの場所（元の場所と新しい大きな場所）にマッピングすることもできるよ。

記事は重要な欠点を隠してると思う。それは連続性だね。デザインから明らかに暗示されてるけど、このアプローチはキャッシュプリフェッチングみたいなものに対して定義しづらい特性を持つと思う。次のアドレスは関数で、簡単に予測できる変化じゃないから。配列を使う一般的な理由の一つは、アイテムを反復処理することなんだけど、その場合、非連続メモリレイアウトは理想的じゃないよ。

└

これは「非連続」とは呼ばないな。「ほぼ連続」って感じだね。大量のデータに対しては、「償却連続」って言える。普通のベクターは要素を追加するのに「償却定数」時間がかかるから。

└
  1. 記事のトップにある画像で、セグメントが連続してないことが明確になってる。2. 40億アイテムのセグメント配列を反復処理すると、26回のキャッシュミスが発生する。大したことじゃないけどね。

これを2の累乗サイズのハッシュテーブルのバックアレイとして使うって言ってるけど、テーブルが大きくなると要素を再ハッシュしなきゃいけないから、安定したポインタは提供できないし、あんまり役に立たないと思う。メモリを再利用したいだけでも、インプレースで再ハッシュするのは面倒くさいよね。

└

アリーナのためのもので、安定性が必要だって言ってた気がする。ハッシュテーブルにそのアリーナを使うこともあるかもね。

配列セグメントを参照するバランス木を持つ別の似たデータ構造は、ロープ（https://en.wikipedia.org/wiki/Rope_(data_structure)）だよ。主な利点は、どのインデックスでもサイズ変更がO(log n)の時間計算量でできること。つまり、どこでも効率的に挿入や削除ができるし、コピーオンライトのバージョン管理も実装しやすいんだ。

└

多くの標準ライブラリが文字列用にロープを実装しようとしたけど、結局はシンプルな構造に戻されることが多いね。

rust-array-stump [1]にちょっと似てるね。これは計算幾何学で配列の真ん中に挿入を最適化するために作られたものだよ。[1] https://github.com/bluenote10/rust-array-stump

つまり、[アクセスシーケンスが10命令だけだから]、ボトルネックはメモリであって、インデックスの位置を計算するための命令ではない。あはは、それは願望的な考えだね。もしL1キャッシュに全てが収まっているタイトなループでこれをやったら、命令が痛いよ！「メモリ帯域幅がボトルネック」っていう理論は、局所的な繰り返しなしでバルクデータにアクセスする時に当てはまるんだ。

└

あの10個の命令は1回のアクセス用で、タイトループ用じゃないよ。タイトループは、各セグメントで別々にイテレートするもっと複雑なマクロでできるし、オーバーヘッドを分散させられるんだ。