メモリ効率の良いC構造体の作成

299日前原文(tomscheers.github.io)

概要

C言語のstructはデータ整理に便利だが、メモリ配置やパディングに注意が必要。構造体のサイズを最適化するためのテクニックを解説。フィールドの並び順や型選択、ビットフィールドやenumの活用が重要ポイント。実例を交えつつ、メモリ削減の効果を具体的に示す。パフォーマンスと可読性のバランスも考慮事項。

C言語構造体のメモリ最適化テクニック

C言語のstruct は、データを効率よく整理・管理するための基本手段。
フィールドの型や並び順によって、 構造体のサイズ が予想以上に大きくなる場合あり。
パディング（隙間） は、各メンバーのアライメント要件により自動で挿入される現象。
例：Monster構造体を定義し、各フィールドの型サイズを合計しても、 sizeofで得られる値が大きくなる 理由はパディングの存在。
アライメント要件により、 int型は4バイト境界、boolやcharは1バイト境界など、システム依存の違いもある。

Monster構造体例とパディングの発生

初期のMonster構造体例では、フィールド合計89バイトだが、sizeof(struct Monster)は 96バイト。
メモリレイアウトを表にすると、 パディング合計6バイト が追加されていることが分かる。
パディングは主に「アライメント調整」と「末尾パディング（tail padding）」の2種類。

パディング削減のためのフィールド再配置

アライメント値が同じフィールド をまとめて配置することで、パディングを減らせる。
一般的に「 大きい型から小さい型へ」並べるのが最適。
Monster構造体のフィールド順を最適化し、 92バイトに削減。

派生状態（Derived State）の活用

例： is_aliveフィールド はhealth > 0で判定できるため、フィールド自体を削除してサイズ削減。
この手法により、 88バイトに削減。

型の見直しによるサイズ削減

healthやspeedなどの値 は、int型よりも小さい型（uint8_tやuint16_t）で十分な場合が多い。
stdint.hの型を活用し、Monster構造体を 84バイト に削減。

ビットフィールドの活用

bool値 は1バイト消費するが、ビットフィールドを使えば 1ビット単位 で格納可能。
Monster構造体のbool系フィールドをビットフィールド化し、 80バイト に削減。

enumによる識別子の最適化

名前やモデル識別に 文字列を直接格納するのは非効率。
enumを使い、MonsterName型で識別すると、 20バイトまで削減 可能。
これにより、モンスター1000体分で96KB→20KBに大幅削減。

最適化のトレードオフと注意点

全ての構造体で極端な最適化を行う必要はない。
メモリ効率が特に重要なシステムや大量データを扱う場合に有効。
型を小さくし過ぎると オーバーフローや予期しない動作 のリスクもあるため、用途に応じてバランスを考慮。
可読性や保守性とのバランスも重要。

まとめ

構造体のサイズ削減 には、フィールド並び順・型の選択・ビットフィールド・enum活用が有効。
適切な最適化は メモリ削減やパフォーマンス向上 に直結。
ただし、 状況や目的に応じて最適化レベルを選択 することが大切。

タグ: blog ・ tutorial ・ C

Hackerたちの意見

paholeやドワーフについての言及はないの？ https://lwn.net/Articles/335942/ これはLinuxカーネル開発者たちが使ってる標準ツールだよ。

└

初心者が始めるとき、こういうツールのリストはどこで探せばいいの？

└

最近のclangdのバージョンでは、paholeみたいな構造体サイズ/アライメントのパディングオーバーヘッドの注釈が表示されるようになった。これがpaholeを使うよりもずっと便利だと思う。

└

paholeは素晴らしいツールだね。

完全性のために言うけど、このアライメントの説明は誤解を招くよね。 > 「さて、読者の皆さん、このパディングはCPUがメモリを4バイト単位でアライメントする必要があるから追加されているんです。」 > ... > つまり、構造体が4バイトにアライメントされているから、パディングなしで構造体のサイズが4の倍数なら、パディングは不要ってこと。個々のデータ型にはそれぞれアライメントがあって（例えば、boolやcharは1、shortは2、intは4、longは8など）、複合型（構造体みたいな）のアライメントはその構成要素の最大アライメントにデフォルトで設定される。この文では、struct Monsterのアライメントは4で、著者の設定ではintとfloatが4のアライメントを持ってるから。intの一つをlongに変えると、CPUによってはアライメントが8になるかもしれないし、intとfloatのフィールドを削除すると、ほとんどのCPUでアライメントが1に下がるよ。

└

それと、これはCPUやコンパイラに特有のことも覚えておいてね。あるコンパイラでは、すべてを4/8バイトでパックしてたけど、通常は8バイトだった。1/2/4/8ではなくてね。それは、データアクセスをうまくやらないとCPUがセグフォルトしちゃうからだった。コンパイラは、オフセットやメモリ移動、シフトを設定すると多くのことを隠してくれたけど、賢いけど遅かった。だから、デフォルトで余分な命令を排除するために十分広いパッキングを選んで、メモリを多く使うことになった。x86はその時一番許容度が高かったけど、ARMは一番厳しかった（少なくとも私が使ってたプラットフォームでは）。MIPSは場合によっては大丈夫だったけど、他のケースではそうでもなかった。

└

つまり、著者は間違ってる。struct s { char x; };は4バイトアラインされる必要はないんだ。1バイトのサイズを持つこともできるし、だからアラインメントもそうなる。

└

それに、boolは4バイトかもしれないし、charは2バイト（m68k）かもね！

└

知ってる限りでは、アライメントはもうあまり重要じゃない（少なくともCPUデータに関しては）。現代のCPUの「ワードサイズ」はキャッシュラインのサイズ（32バイトか64バイト？）だから、例えば32バイトや64バイトのブロック内での非アライメントアクセスは、アライメントされたアクセスと変わらないんだ。ただし、サイズに合わせてアライメントされたアイテムは隣接するキャッシュラインをまたぐことがないっていう利点はまだあるよ。それに、GPUデータを扱うときはまだたくさんの異なるアライメント要件があるし、面白いことにそのアライメント要件はCのアライメントルールとは異なることもあるから、手動でパディングを使ってパックされた構造体を明示的に使う必要があるかもしれない（これも標準Cの機能じゃないけど）。

└

個々のデータ型にはそれぞれのアライメントがある（例えば、boolやcharは1、shortは2、intは4、longは8など）。複合型（構造体のような）のアライメントは、その構成要素の最大アライメントにデフォルトで設定される。これは実装に依存することを付け加えておくよ。確か、標準が構造体のアライメントに課す唯一の制約は、ポインタがその最初のメンバーへのポインタでもあること、つまりアライメントは実質的に最初のフィールドの倍数でなければならないってことだよ。

著者は「speed」の後の未使用のパディングバイトにビットフィールドを収めることに依存してるけど、それは実装依存の動作なんだよね（ビットフィールドに関するほとんどのことが実装依存）。MSVCはunsignedビットフィールドをalignof(unsigned)にアライメントするけど、GCCやclangはパディングバイトを使う。構造体をポータブルにパックするには、unsigned整数を使ってフラグ（monster.flags & CAN_FLYのように）を使うといいよ。詳しくは https://c.godbolt.org/z/K7oY77KGj を見てね。

└

将来のCのリリースでビットフィールドの標準が定義されないのはなぜ？これは本当に使いたい機能の長年の議論されてきた欠点なんだよね。

└

ビットフィールドには他にも問題があるんだ。例えば、uint8_t型のビットフィールドが2つあって合計16ビットだとする。これって「2つのフィールド」だと思うかもしれないけど、コンパイラは好きなときにそれを「1つ」として扱うことができるんだ。もし片方をアトミックにアクセスして、もう片方をそうでない場合、同期が必要な方に非同期アクセスが発生する可能性があるから、これが問題になることがある。Cのビットフィールドは、コンパイラに過剰な振る舞いを任せすぎていて、定義されていないことも多い。ほんとに耐えられないよ。

パッキングを改善するためにできる他のこととしては、絶対ポインタの代わりに整数インデックスやオフセット、相対ポインタを使う（特に64ビットマシンでは）、ユニオンのフィールドを重ね合わせる（例えば、ユニオンの各メンバーで他のフィールドとビットを共有できるタグがあるかもしれない）、メモリ内の構造体の位置を使って情報をエンコードする（例えば、配列で割り当てられたノードの二分木があったら、右の子が常に親の後にメモリに続くように指定すれば、左の子のインデックスだけを保存すればいい）、そしてもちろん構造体パッキングのプラグマや属性を使うこと。

いい記事だね。次に本当に探求したいのは、構造体がどのように使われているかだ。小さい方がいいけど、時には速さが必要なこともある。そういう時は、よく一緒に読まれるフィールドをまとめるといいよ。例えば、x、y、speedはいつも一緒に読まれる可能性が高いから、これらのフィールドをまとめてキャッシュリードを最適化するのが理にかなってる。次に考えるべきは、あなたのモンスターが個別のものとして扱われるのか、グループとして扱われるのかってこと。もしグループとして扱われるなら、「配列の構造体」を作るのが理にかなってくるかも。例えば、すべての死んだモンスターを取り除くシステムがあると想像してみて。Monster構造体の配列を使うよりも、isAliveの配列をイテレートする方が速いだろうし。これでECSを再発明する道に進んでるね :)

C++に関する関連の考えをいくつか。メンバーがないラッピングクラスのコストは、空の基底クラス最適化を利用することで排除できるよ（つまり、基底クラスにメンバーを持たないことでEBCOを活用できるってこと）。C++では、未タグ付きの共用体を使って小さなオブジェクトの最適化を実装できる（未定義の動作に注意しながらね）。一般的な形としては、小さな構造体を共用体に格納して、大きな構造体の中でどちらかを判断するためにセンチネルを使うってアイデア。例えば、大きな構造体にゼロにしてはいけないフィールドがあったら、小さな構造体でそれをゼロにしておけば、タグなしで二つを区別できる。あと、個人的には「無効な状態を表現できないようにする」って考えが好きで、これを守ることで冗長性を減らしたり、余分なフィールドを排除できることが多いよ。

一般的に言えば、メンバーをアライメントの降順で並べると、非ポータブルなコンパイラ拡張に頼らずに最もタイトなパッキングができるよ。この降順は、メンバー間のパディングを排除して、最後のメンバーの最後のバイトのオフセットを最小にする。そうすることで、構造体の最後に必要なパディングも最小化できる。Cでは、基本型のアライメントはサイズに関連してる。型には、サイズと同じくらいのアライメント要件があることもある。例えば、8バイトのデータ型は、8で割り切れるアドレスに厳密にアライメントされることがある。配列のアライメントはその要素型のアライメントに従う。構造体のアライメントは、最も厳密にアライメントされたメンバーに従う。ポータブルなコーディングでは、正確にはわからないけど、最悪のケースを考えると、すべての基本型が最も厳しいアライメントを持つと仮定できる。つまり、そのサイズだね。すべての型のサイズもわからないけど、高いランクの整数は低いランクの整数と同じかそれ以上のサイズがあることはわかってる。例えば、sizeof(char)の構造体sは、void *p1, *p2, *p3, p4; short s1, s2, s3, s4; float f1, f2, f3, f4;。floatはほぼ確実にshortより大きくて、より厳しいアライメントを持つかもしれないけど、4つのメンバーがあるから関係ない。ポインタが16ビットの小さなシステムでも、4つあれば8バイトになるからね。だから、f1メンバーが構造体に配置されるとき、オフセットは少なくとも8バイトアライメントされてるから、パディングは期待しない。もし同じ型のメンバーを2の累乗サイズの塊で集めれば、システムの最も厳しいアライメントを満たすか超えるアライメントを簡単に作れるよ。だから、これが主な原則だね：同じ型のメンバーをまとめて、グループを保ちながらアライメントの厳しさで降順に並べる。

これがHNのフロントページに載ってるのを見てちょっと驚いてる。20年前の新入生のCSコースでこの内容が一回の講義で扱われたのをはっきり覚えてる。HNの初期にはこれがフロントページに載ることはなかったと思うし、今の業界では抽象化やAIエージェントに依存しすぎて、こういう基本的なことを教えるのが減ってきたのかなって思う。

└

プログラミングの面白いところの一つは、正式な教育なしでも高いスキルを身につけられることだよ。でも、そのせいで教育に特有の穴があるプログラマーも常にいるってことだ。個人的には、自分で学んだ人と正式に学んだ人が混ざっているのが好きで、自己学習者が正式教育を受けた人よりも得意なことが結構あると思ってる。両方の側面を尊重してるよ。ただ、HNにはこういうニーズが常にあったって言いたいだけ。

└

私は正式な場でCSを学んだことがないけど、プログラミングが雇用基盤を広げるにつれて、そういう人が増えている気がする。私が一緒に働いている人たちも、正式なCS教育を受けていない人が多い。だから、私はこれらのことをすべて独学で学ばなきゃいけなかった。こういう教育を重視するコミュニティもあるよ。私が言えるのは、Rustコミュニティがこの「低レベル」のことについてたくさん学ぶ手助けをしてくれたってこと。キャリアの初めはRubyをやってたけどね。

└

自分も同じくらいの時期にCSの学位を取得したけど、こういうトピックは全然扱わなかった。だから、学ぶ内容は人によってかなり違うと思うし、構造体のサイズについて知らないのは必ずしも現代的なことではないと思う。

アライメントとサイズはプラットフォーム特有だけど、実際には固定の順序を使うことでパディングを最小限にできることに注意してね：（さまざまなベクター型）int128_t long double long long, int64_t, int_fast64_t, double off_t time_t（32ビットプラットフォームではoff_tも64ビットである必要がある）register_t, int_fast16_t, int_fast32_t（例えばx32では64ビット）void *, void(*)(), intptr_t ptrdiff_t（完全にアライメントされていてポインタより大きい場合は理論的に間違い）size_t, ssize_t long（win64では32ビット; ポインタより大きい場合は一般的に16ビットのアライメントがある）int32_t, float int（16ビットの可能性がある）short, int16_t char, bool, int8_t, int_fast8_t（末尾の配列メンバーは最後に来る必要がある; 結合サイズを計算する際には、パディングを無駄にしないためにsizeofではなくoffsetofを使うべき）これに加えて、int_leastN_tはintN_tと一緒に使われ、すべての符号なし型はその符号あり型と一緒に使われる。id_tのような型は配置が難しいことに注意。ただし、サイズの順序でないプラットフォームも多く存在するけど、そういうプラットフォームでは一般的に大きな型は小さなアライメントを持つ。にもかかわらず、私はそういうプラットフォームを知らなくても行を分けることがある。

これは良い記事だけど、半分だけの話をしているようで気になる。なぜ構造体を小さくするの？おそらく「パフォーマンス」のためだよね。もし目標が単にメモリ使用量を減らすことなら、これは全然問題ない。小さなマイクロコントローラーで動かしていて、RAMがあまりないってこともあるだろうけど、今の時代、ほとんどの分野ではメモリは安くて豊富だよ。高価なのはCPUキャッシュ。もしそれに対してメモリ使用を最適化しているなら、本当に重要なのはランタイムの速度で、トータルのメモリ使用量ではない。キャッシュミスを減らして、CPUが待たされる時間を少なくするために小さくしようとしているわけだね。そういう場合、ここでのアドバイスは話の一部に過ぎない。ビットフィールドや小さな整数を使うとメモリを節約できるけど、それらのフィールドにアクセスして何かをするためには、レジスタにロードする必要がある。私は専門家ではないけど、ビットフィールドや小さな整数をワードサイズのレジスタにロードするのにはオーバーヘッドがあることがあるから、トレードオフに注意が必要だと思う。もし全体のランタイム速度を最適化しようとして構造体をパックすることを考えているなら、まずは良いプロファイリングとベンチマークを用意しておきたい。そうしないと、進展していると思っても実際には後退していることが簡単にあるからね。

└

パックされた構造体やビットフィールドの本当の問題は、同時実行が関わるときに起こるんだよね。現代のCPUキャッシュのほとんどはプライベートで、1つのコアだけがキャッシュラインを保持できるから、他のコアが別のコアのキャッシュラインにコンパクト化された情報を変更しようとすると、偽の依存関係が増えちゃうんだ。

└

すべてはマイクロアーキテクチャに依存するけど、一般的にはメモリサブシステムはサブワードのロードや書き込みを処理できるんだ。ただ、ビット単位の操作はうまくいかないことが多い。

└

侵入型データ構造を使っているなら、キーをポインタと同じキャッシュラインに置くことで、トラバーサルが速くなることがあるよ。パディングを減らすと、これがやりやすくなる。一般的に、よくアクセスされるものを同じキャッシュラインに置くのは良いアイデアだし、過剰なパディングを取り除くための作業は、これを実現するための作業と重なることが多いんだ。

└

最近では、ほとんどの分野でメモリは安くて豊富だから、次のマシンに128GのRAMを考えてるんだ。今は64G使ってて、よくOOMになるし、32Gじゃ使い物にならない。

└

もしそれに対してメモリ使用を最適化しているなら、実際にはランタイムの速度が重要で、トータルのメモリ使用量はあまり関係ないんだ。キャッシュミスを減らすために小さくしようとしているから、CPUが待たされる時間を減らせるんだよね。複雑なのは、キャッシュがグローバルリソースだってこと。データ構造が大きいコードは、たとえ速く動いても、他のコードの作業セットを大きくし、キャッシュミス率を少し上げることがある。これが「千の傷による死」のシナリオにつながることもあって、プロファイリングのときにしっかりしたデータを得るのが難しいんだ。でも、確かに小さい構造体が遅くなる方法はいくつかあって、実行時間で直接、または大きなコードが命令キャッシュのミスを増やすことで間接的に影響することがある。その他の要因としては、コンパイラがまとめてアクセスできるかどうかや、構造体が配列インデックスやベクトル化のために魔法の2の冪サイズに達するかどうかがある。だから、構造体を大きくすることでコードを速くできることもあるんだ。

└

構造体をパックするのは、パックされたレイアウトがハードウェアやネットワークの構造に合ってるからで、直接アクセスできるからなんだ。これは一般的なケースではないけど、存在するよ。

└

メモリは安くて豊富だ。高いのはCPUキャッシュだ。CPUキャッシュはメモリだし、メモリ自体も安くない、アクセスするのは比較的高い。CPUキャッシュの方がずっと安いよ。逆だよ。

└

すごく同意するけど、パフォーマンスは多くの要因によって決まるからね。このデータがキャッシュラインに収まっても、次のコードには何の影響もないか、逆に悪影響があるかもしれない。複雑なソフトウェアでは、変更後に速くなったとしても、実際に何が要因なのかを見極めるのは難しい。一度、最近のシステム研究会議でコードレイアウトを変更することがパフォーマンスに予期しない影響を与えるというシステム論文（名前は忘れた）を読んだことがある。個人的には、構造体が並行データ構造で、複数のコアで同期する必要があるときだけ、キャッシュラインとレイアウトに注意を払ってる。

└

もし本当にそのフィールドにアクセスしてるなら、全てのインスタンスで同じフィールドにアクセスしてる可能性が高いよ。アクセスパターンはこんな感じだね。monsters[0].health = //計算 monsters[1].health = //計算 monsters[2].health = //計算って感じで、monsters[0].health = //計算 monsters[1].name = //更新 monsters[2].is_poisoned = //チェックじゃない。モンスターの配列をストライドすると、1つのフィールドにアクセスするために各モンスターをロードしなきゃいけなくて、キャッシュがぶっ壊れちゃう。健康値を構造体の配列としてまとめる方がずっといいよ。エンティティ・コンポーネント・システムのアーキテクチャは、これを効率的に管理するための素晴らしいツールで、かなりのパフォーマンスを得られるんだ。

ハクソク