ペイロードの後にタグを格納する利点
構造体のアライメント制約により、フィールドの配置順序によってメモリ使用量が大きく変わる場合がある。
通常、構造体のサイズは最も大きいフィールドのアライメントに合わせて調整されるが、入れ子構造になると無駄なスペースが生じやすい。
Swiftのような、サイズとストライドを分離したレイアウトアルゴリズムを用いることで、この無駄を減らせる。
特に、Sum Type（Optionなど）において、タグをペイロードの後に格納することで、メモリ効率を大幅に向上させることができる。
Swiftはこの実装を採用しており、他の言語でも同様のアプローチが検討されるべきである。
プログラミングにおけるメモリ効率化は、システムのパフォーマンスやリソース消費に直結する重要な課題です。今回注目されるのは、データ構造、特に「和型（Sum Type）」のメモリレイアウトに関する技術的な考察です。具体的には、タグ情報（どのバリアントかを示す情報）をペイロード（実際のデータ）の後に配置することで、驚くほどメモリ使用量を削減できるという手法が提案されています。
データ構造のメモリ配置の基礎知識
コンピュータのCPUは、データを読み書きする際、特定の「アライメント（整列）」要件を満たす必要があります。例えば、4バイトの値を読み込むには4バイト境界に配置されている必要があり、8バイトの値を読み込むには8バイト境界が必要です。この要件を満たさないと、パフォーマンスが低下したり、最悪の場合プログラムがクラッシュしたりします。
構造体（struct）をメモリに配置する際、コンパイラは各フィールドのサイズとアライメント要件を考慮し、最適な配置を決定します。この配置方法が、最終的な構造体のサイズとアライメントを決定づけることになります。
ネストされた構造体におけるメモリの浪費
構造体をネスト（入れ子）にしていくと、メモリの浪費が顕著になるケースがあります。一般的な言語のレイアウト方式では、配列のサイズを構造体の最大アライメントに合わせて丸め上げる（パディングする）処理が行われます。
例えば、ある構造体がサイズ9バイトでアライメント8が必要な場合、配列として扱う際はサイズが16バイトに丸められます。これをさらにネストさせると、必要なサイズ以上に多くのパディングが発生し、メモリの無駄が蓄積してしまうという問題があります。これは、特にSwiftのような言語が採用している「サイズ」と「ストライド（配列の要素間の間隔）」を分離するアプローチで改善されることが知られています。
和型におけるタグ配置の最適化
このメモリ効率化の考え方を「和型（enumなど）」に応用することが本記事の核心です。和型は通常、「タグ（どのバリアントか）」と「ペイロード（実際のデータ）」の順で配置されます。この標準的な配置では、ネストが深くなるにつれてメモリの浪費が大きくなります。
しかし、タグをペイロードの後に配置し直すことで、構造体のように効率的なレイアウトが可能になります。これにより、ネストが深くなっても、メモリの無駄を大幅に削減できることが示されています。この手法はSwiftで採用されているものと類似していますが、その詳細な実装は未解明であると述べられています。
まとめ
タグをペイロードの後に配置するというシンプルな変更が、データ構造のネストが深くなる際のメモリ効率を劇的に改善する可能性を示しています。これは、低レイヤーのメモリ管理やコンパイラの最適化に関わる、非常に興味深い技術的知見と言えるでしょう。
原文の冒頭を表示（英語・3段落のみ）
The short version of this shower thought: storing the tags for sum types after the payload rather than before can save a surprising amount of space.
The long version needs some context.
A pointer has alignment A if ptr % A == 0. Eg a pointer to address 564 has alignment 4, because 564 % 4 == 0. But it does not have alignment 8 because 564 % 8 == 4.
※ 著作権に配慮し、引用は冒頭3段落までです。続きは元記事をご覧ください。