データ構造のアライメント

データ構造のアライメントとは、コンピュータのメモリ内でデータを配置してアクセスする方法です。これは、データのアライメント、データ構造のパディング、パッキングという 3 つの別個だが関連する問題から構成されます。

現代のコンピュータ ハードウェアのCPUは、データが自然に整列している場合にメモリの読み取りと書き込みを最も効率的に実行します。これは通常、データのメモリ アドレスがデータ サイズの倍数であることを意味します。たとえば、32 ビット アーキテクチャでは、データが 4 つの連続したバイトに格納され、最初のバイトが 4 バイト境界にある場合、データは整列している可能性があります。

データ アラインメントとは、要素を自然なアラインメントに従ってアラインメントすることです。自然なアラインメントを確保するには、構造体の要素間または構造体の最後の要素の後にパディングを挿入する必要がある場合があります。たとえば、32 ビット マシンでは、16 ビット値の後に 32 ビット値が続くデータ構造体では、16 ビット値と 32 ビット値の間に 16 ビットのパディングを挿入して、32 ビット値を 32 ビット境界に揃えることができます。または、パディングを省略して構造体をパックすることもできます。この場合、アクセス速度は低下しますが、メモリ使用量は 4 分の 3 になります。

データ構造のアライメントは現代のすべてのコンピュータにとって基本的な問題ですが、多くのコンピュータ言語とコンピュータ言語の実装では、データアライメントを自動的に処理します。Fortran 、 Ada 、 [ ^{1] [2]} PL/I、^[3] Pascal、^[4]特定のCおよびC++実装、D、^[5] Rust、^[6] C#、^[7]およびアセンブリ言語では、データ構造のパディングを少なくとも部分的に制御できるため、特定の特殊な状況では役立つ場合があります。

メモリ アドレスaがnの倍数( nは 2 の累乗) である場合、そのメモリ アドレス a はnバイト境界に揃えられていると言われます。この文脈では、バイトはメモリ アクセスの最小単位です。つまり、各メモリ アドレスは異なるバイトを指定します。nバイト境界に揃えられたアドレスは、 2 進数で表現すると、最下位のゼロが少なくともlog ₂ ( n )個になります。

代替表現である「b ビット アラインメント」は、b/8 バイト アラインメントアドレスを指定します(例: 64 ビットアラインメントは 8 バイト アラインメントです)。

アクセスされるデータがn バイト長で、データ アドレスがnバイトに揃えられている場合、メモリ アクセスは整列されていると言われます。メモリ アクセスが整列されていない場合は、不整列であると言われます。定義により、バイト メモリ アクセスは常に整列されていることに注意してください。

n バイト長のプリミティブ データを参照するメモリ ポインターは、nバイトでアラインされたアドレスのみを含むことができる場合はアラインされていると言われ、それ以外の場合はアラインされていないと言われます。データ集合 (データ構造または配列) を参照するメモリ ポインターは、集合内の各プリミティブ データがアラインされている場合 (その場合のみ) アラインされています。

上記の定義では、各プリミティブ データの長さが 2 バイトの累乗であると想定していることに注意してください。そうでない場合 ( x86の 80 ビット浮動小数点など)、コンテキストによって、データが整列されているかどうかが判断されます。

データ構造は、静的なサイズ（境界付き）でスタック上のメモリに格納することも、動的なサイズ（境界なし）でヒープ上に格納することもできます。

CPU は、一度に 1 つのメモリ ワードでメモリにアクセスします。メモリ ワード サイズがコンピューターでサポートされている最大のプリミティブ データ型と同じかそれ以上の大きさであれば、アラインされたアクセスでは常に 1 つのメモリ ワードにアクセスします。アラインされていないデータ アクセスの場合は、この限りではありません。

データの最上位バイトと最下位バイトが同じメモリ ワード内にない場合、コンピューターはデータ アクセスを複数のメモリ アクセスに分割する必要があります。これには、メモリ アクセスを生成して調整するための複雑な回路が多数必要になります。メモリ ワードが異なるメモリ ページにある場合に対処するには、プロセッサは命令を実行する前に両方のページが存在することを確認するか、命令実行中にメモリ アクセスで発生するTLBミスまたはページ フォールトを処理できる必要があります。

一部のプロセッサ設計では、このような複雑さを意図的に回避し、代わりに、不整列メモリ アクセスが発生した場合に代替の動作を生成します。たとえば、ARMv6 ISA より前の ARM アーキテクチャの実装では、すべてのマルチバイト ロードおよびストア命令に対して、強制的に整列メモリ アクセスが必要です。^[8]発行された特定の命令に応じて、不整列アクセスの試行の結果、問題のあるアドレスの最下位ビットが切り捨てられて整列アクセスに変換されるか (場合によっては追加の注意事項があります)、MMU例外がスローされるか (MMU ハードウェアが存在する場合)、その他の予測できない結果が暗黙的に生成されます。ARMv6 以降のアーキテクチャでは、多くの状況で非整列アクセスがサポートされていますが、必ずしもすべての状況でサポートされるわけではありません。

単一のメモリ ワードにアクセスする場合、操作はアトミックです。つまり、メモリ ワード全体が一度に読み取られるか書き込まれるため、他のデバイスは読み取りまたは書き込み操作が完了するまで待機して、そのメモリ ワードにアクセスする必要があります。これは、複数のメモリ ワードへの非整列アクセスには当てはまらない場合があります。たとえば、最初のワードが 1 つのデバイスによって読み取られ、両方のワードが別のデバイスによって書き込まれ、次に 2 番目のワードが最初のデバイスによって読み取られる場合、読み取られた値は元の値でも更新された値でもありません。このような障害はまれですが、特定が非常に困難な場合があります。

コンパイラ(またはインタープリタ) は通常、個々のデータ項目を境界に揃えて割り当てますが、データ構造には異なる境界揃え要件を持つメンバーが含まれることがよくあります。適切な境界揃えを維持するために、トランスレータは通常、各メンバーが適切に境界揃えされるように、追加の無名データ メンバーを挿入します。さらに、データ構造全体に、最後の無名メンバーが埋め込まれる場合があります。これにより、構造体の配列の各メンバーが適切に境界揃えされます。

パディングは、構造体メンバーの後に、より大きなアラインメント要件を持つメンバーが続く場合、または構造体の最後にある場合にのみ挿入されます。構造体のメンバーの順序を変更することで、アラインメントを維持するために必要なパディングの量を変更することができます。たとえば、メンバーが降順のアラインメント要件で並べ替えられている場合、最小限のパディングが必要です。必要な最小限のパディングの量は、常に構造体の最大アラインメントよりも小さくなります。必要な最大パディングの量の計算はより複雑ですが、常に、すべてのメンバーのアラインメント要件の合計から、構造体メンバーの最もアラインメントの少ない半分のアラインメント要件の合計の 2 倍を引いた値よりも小さくなります。

C および C++ では、スペースを節約するためにコンパイラが構造体メンバーを並べ替えることはできませんが、他の言語では可能です。ほとんどの C および C++ コンパイラに、構造体のメンバーを特定のレベルの配置に「パック」するように指示することもできます。たとえば、「pack(2)」は、1 バイトを超えるデータ メンバーを 2 バイト境界に揃え、パディング メンバーが最大 1 バイトの長さになるようにすることを意味します。同様に、PL/Iでは、ビット文字列の周囲を除くすべてのパディングを削除するように構造体を宣言できますUNALIGNED。

このような「パックされた」構造体の用途の 1 つは、メモリを節約することです。たとえば、1 バイト (char など) と 4 バイトの整数 (uint32_t など) を含む構造体には、さらに 3 バイトのパディングが必要です。このような構造体の大規模な配列をパックすると、メモリ使用量が 37.5% 削減されますが、各構造体へのアクセスに時間がかかる場合があります。この妥協は、空間と時間のトレードオフの一種と見なすことができます。

「パックされた」構造体は、メモリ空間を節約するために最もよく使用されますが、標準プロトコルを使用して送信するためのデータ構造体をフォーマットするためにも使用できます。ただし、この使用法では、構造体メンバーの値がプロトコルで必要なエンディアン(多くの場合、ネットワーク バイト オーダー) で保存されるように注意する必要があります。このエンディアンが、ホスト マシンでネイティブに使用されるエンディアンと異なる場合があります。

次の式は、データ構造の開始を揃えるために必要なパディング バイトの数を示します ( modはモジュロ演算子です)。

パディング = (align - (offset mod align)) mod align
整列 = オフセット + パディング
        = オフセット + ((整列 - (オフセット mod 整列)) mod 整列)

たとえば、4 バイトの境界整列構造体のオフセット 0x59d に追加するパディングは 3 です。構造体は 4 の倍数である 0x5a0 から始まります。ただし、offsetの境界整列がalignの境界整列とすでに等しい場合、 (align - (offset mod align)) mod alignの 2 番目のモジュロは0 を返すため、元の値は変更されません。

アライメントは定義により 2 の累乗であるため、^[a]モジュロ演算はビット単位の AND演算に簡略化できます。

次の数式は、オフセットが符号なしであるか、システムが2 の補数演算 を使用している場合に、正しい値を生成します (ここで、 &はビット単位の AND で、~はビット単位の NOTです)。

パディング = (align - (offset & (align - 1))) & (align - 1)
        = -オフセット & (整列 - 1)
整列 = (オフセット + (整列 - 1)) & ~(整列 - 1)
        = (オフセット + (位置合わせ - 1)) & -位置合わせ

データ構造のメンバーはメモリ内に順番に格納されるため、以下の構造ではメンバー Data1 は常に Data2 の前にあり、Data2 は常に Data3 の前にあります。

構造体MyData { short Data1 ; short Data2 ; short Data3 ; }; 

     
     
     

「short」型が 2 バイトのメモリに格納される場合、上に示したデータ構造の各メンバーは 2 バイトに揃えられます。Data1 はオフセット 0、Data2 はオフセット 2、Data3 はオフセット 4 になります。この構造のサイズは 6 バイトになります。

構造体の各メンバーの型には通常、デフォルトのアラインメントがあります。つまり、プログラマーが別途要求しない限り、事前に決められた境界にアラインメントされます。次の一般的なアラインメントは、32 ビットx86 用にコンパイルする場合、 Microsoft ( Visual C++ )、Borland / CodeGear ( C++Builder )、Digital Mars (DMC)、およびGNU ( GCC ) のコンパイラーで有効です。

• char (1 バイト)は1 バイトに揃えられます。
• short (2 バイト)は2 バイトに揃えられます。
• int (4 バイト)は4 バイト境界に揃えられます。
• long (4 バイト)は4 バイトに揃えられます。
• float (4 バイト)は4 バイト境界に揃えられます。
• double (8 バイト)は、Windows では 8 バイト境界に揃えられ、Linux では 4 バイト境界に揃えられます ( -malign-doubleコンパイル時オプションで 8 バイト)。
• long long (8 バイト) は、Windows では 8 バイト境界に配置され、Linux では 4 バイト境界に配置されます (コンパイル時オプション-malign-doubleを使用すると 8 バイトになります)。
• long double (C++Builder および DMC では 10 バイト、Visual C++ では 8 バイト、GCC では 12 バイト) は、C++Builder では 8 バイト境界に、DMC では 2 バイト境界に、Visual C++ では 8 バイト境界に、GCC では 4 バイト境界に揃えられます。
• すべてのポインタ(4 バイト) は 4 バイト境界に揃えられます。 (例: char*、int*)

LP64 64 ビット システムと 32 ビット システムを比較した場合 のアライメントの唯一の顕著な違いは次のとおりです。

• long (8 バイト)は8 バイトに揃えられます。
• double (8 バイト)は8 バイト境界に揃えられます。
• long long (8 バイト) は 8 バイト境界に揃えられます。
• long double (Visual C++ では 8 バイト、GCC では 16 バイト) は、Visual C++ では 8 バイト境界に揃えられ、GCC では 16 バイト境界に揃えられます。
• すべてのポインタ(8 バイト) は 8 バイト境界に揃えられます。

一部のデータ型は実装に依存します。

以下は、コンパイル前の 合計8 バイトのさまざまなタイプのメンバーを持つ構造体です。

構造体MixedData { char Data1 ; short Data2 ; int Data3 ; char Data4 ; }; 

     
     
     
     

コンパイル後、データ構造にはパディング バイトが追加され、各メンバーの適切な配置が確保されます。

struct MixedData /* 32 ビット x86 マシンでコンパイルした後 */ { char Data1 ; /* 1 バイト */ char Padding1 [ 1 ]; /*構造体が始まるアドレスが偶数であると仮定して、後続の 'short' が 2 バイト境界に揃えられるための 1 バイト*/ short Data2 ; /* 2 バイト */ int Data3 ; /* 4 バイト - 最大の構造体メンバー */ char Data4 ; /* 1 バイト */ char Padding2 [ 3 ]; /* 構造体の合計サイズを 12 バイトにするための 3 バイト */ };   

      
      

      
       
      
      

構造体のコンパイルされたサイズは 12 バイトになりました。

最後のメンバーには、構造体の合計サイズが構造体メンバーの最大アラインメントの倍数（この場合はalignof(int)、linux-32bit/gcc では 4）になるように、必要なバイト数が埋め込まれます^{[引用が必要]}。

この場合、構造体のサイズを 12 バイト ( alignof(int) * 3 ) にするために、最後のメンバーに 3 バイトが追加されます。

構造体FinalPad { float x ; char n [ 1 ]; };  
   
   

この例では、構造体の合計サイズはsizeof (FinalPad) == 8 であり、 5 ではありません (したがって、サイズは 4 の倍数になります ( alignof(float) ))。

struct FinalPadShort { short ;​文字n [ 3 ]; };  
   
   

この例では、構造体の合計サイズはsizeof (FinalPadShort) == 6 であり、5 ではありません (8 でもありません) (したがって、サイズは 2 の倍数になります ( linux-32bit/gcc ではalignof(short) == 2 ))。

構造体メンバーの順序を変更したり、コンパイラの構造体メンバーのアラインメント (または「パッキング」) を変更したりすることで、構造体のアラインメントを変更して、必要なメモリを削減したり、既存の形式に準拠したりすることができます。

struct MixedData /* 並べ替え後 */ { char Data1 ; char Data4 ; /* 並べ替え後 */ short Data2 ; int Data3 ; };   

     
        
     
     

構造体のコンパイルされたサイズは、プリコンパイルされた8 バイトのサイズと一致します。Padding1 [1]はData4に置き換えられ (したがって削除され) 、構造体は既にロング ワードのサイズに揃えられているため、 Padding2[3] は不要になっていることに注意してください。

MixedData構造体を 1 バイト境界に揃える別の方法では、プリプロセッサが構造体メンバーの事前に決定された揃えを破棄するため、パディング バイトは挿入されません。

構造体メンバーのアラインメントを定義する標準的な方法はありませんが (C および C++ ではこの目的でalignas指定子を使用できますが、より厳密なアラインメントを指定する場合にのみ使用できます)、一部のコンパイラでは#pragmaディレクティブを使用してソース ファイル内のパッキングを指定します。次に例を示します。

#pragma pack(push)   /* 現在のアラインメントをスタックにプッシュします */ 
#pragma pack(1)      /* アラインメントを 1 バイト境界に設定します */

構造体MyPackedData { char Data1 ; long Data2 ; char Data3 ; }; 

     
     
     


#pragma pack(pop)    /* スタックから元の配置を復元します */

この構造体は、32ビットシステムではコンパイル後のサイズが6バイトになります。上記のディレクティブは、Microsoft、^[9] 、Borland、^[10]など のコンパイラで使用できます。

別の例:

構造体 MyPackedData { char Data1 ; long Data2 ; char Data3 ; } __attribute__ (( packed )); 

     
     
     
 

一部の Microsoft コンパイラ、特に RISC プロセッサでは、プロジェクトのデフォルト パッキング (/Zp ディレクティブ) と#pragma packディレクティブの間に予期しない関係があります。#pragma packディレクティブは、プロジェクトのデフォルト パッキングから構造体のパッキング サイズを減らすためにのみ使用できます。 ^[11] これにより、プロジェクト パッキングがこれより小さい場合、たとえば#pragma pack(8) を使用するライブラリ ヘッダーとの相互運用性の問題が発生します。このため、プロジェクト パッキングをデフォルトの 8 バイト以外の値に設定すると、ライブラリ ヘッダーで使用される#pragma packディレクティブが壊れ、構造体間のバイナリの非互換性が発生します。この制限は、x86 用にコンパイルする場合は存在しません。

キャッシュ ラインに揃えてメモリを割り当てると便利です。配列が複数のスレッドで操作できるように分割されている場合、サブ配列の境界がキャッシュ ラインに揃えられていないと、パフォーマンスが低下する可能性があります。以下は、64 バイトのキャッシュに揃えてメモリ (サイズ 10 の double 配列) を割り当てる例です。

#include <stdlib.h> double * foo ( void ) { // サイズ 10 の配列を作成double * array ; if ( 0 == posix_memalign (( void ** ) & array , 64 , 10 * sizeof ( double ))) return array ; 
   
    
        
      

   NULLを返します。 

ハードウェアアドレス変換メカニズム (PCI 再マッピング、MMUの操作)を通じてその領域を効率的にマッピングすることが目的である場合、アライメントに関する懸念は C 構造体よりもはるかに大きな領域に影響を与える可能性があります。

たとえば、32 ビット オペレーティング システムでは、4  KiB (4096 バイト) ページは単なる任意の 4 KiB のデータ チャンクではありません。通常は、4 KiB 境界に揃えられたメモリ領域です。これは、ページをページ サイズの境界に揃えると、ハードウェアが複雑な演算を行うのではなく、アドレスの上位ビットを置換して仮想アドレスを物理アドレスにマップできるためです。

例: 仮想アドレス 0x2CFC7000 から物理アドレス 0x12345000 への TLB マッピングがあるとします。(これらのアドレスは両方とも 4 KiB 境界に揃えられていることに注意してください。) 仮想アドレス va=0x2CFC7ABC にあるデータにアクセスすると、TLB 解決により 0x2CFC7 から 0x12345 になり、pa=0x12345ABC への物理アクセスが発行されます。ここで、20/12 ビットの分割は、5/3 桁で分割された 16 進表現と一致します。ハードウェアは、物理アドレスの最初の 20 ビット (0x12345) と仮想アドレスの最後の 12 ビット (0xABC) を組み合わせるだけで、この変換を実装できます。これは、仮想インデックス (ABC)、物理タグ (12345) とも呼ばれます。

^{サイズが 2 (n+1)} − 1のデータ ブロックには、常に 2 ⁿ バイト  に揃えられたサイズ 2 ⁿのサブブロックが 1 つあります。

このように、アライメントを認識しない動的アロケータを使用して、スペース損失が 2 倍になるという代償を払って、アライメントされたバッファを提供できます。

// 例: malloc() を使用して 4096 バイトのバッファに 4096 バイトを配置する

// 大きな領域へのアラインされていないポインタ
void * up = malloc (( 1 << 13 ) - 1 ); // 4 KiB へのアラインされたポインタvoid * ap = aligntonext ( up , 12 );       

    

ここで、aligntonext( p , r )は、整列した増分を追加し、次にpの最下位rビットをクリアすることによって機能します。可能な実装は次のようになります。

// 読みやすくするために `uint32_t p, bits;` と仮定します
#define alignto(p, bits) (((p) >> bits) << bits) 
#define aligntonext(p, bits) alignto(((p) + (1 << bits) - 1), bits)

• Bryant, Randal E. ; David, O'Hallaron (2003)。『コンピュータシステム: プログラマの視点』(2003 版)。アッパーサドルリバー、ニュージャージー州、米国: Pearson Education。ISBN 0-13-034074-X。
• 「1. 概要: セグメント アラインメント」。8086 ファミリ ユーティリティ – 8080/8085 ベース開発システム ユーザーズ ガイド(PDF)。リビジョン E (A620/5821 6K DD 版)。米国カリフォルニア州サンタクララ: Intel Corporation。1982年 5 月 [1980、1978]。pp. 1-6、3-5。注文番号: 9800639-04。2020-02-29にオリジナルからアーカイブ(PDF)されました。2020-02-29に取得。[…] セグメントには、次の 5 つのアラインメント属性のうち 1 つ (inpage 属性の場合は 2 つ) を設定できます。[…] バイト。セグメントは任意のアドレスに配置できます。[…] ワード。セグメントは 0H から始まる 2 の倍数のアドレスにのみ配置できます。 […] 段落: セグメントは、アドレス 0 から始まる 16 の倍数のアドレスにのみ配置できます。 […] ページ: セグメントは、アドレス 0 から始まる 256 の倍数のアドレスにのみ配置できます。 […] インページ: セグメントは、前述の属性のいずれかに該当する場所に配置できますが、ページ境界を越えないように配置する必要があります。 […] 配置コードは次のとおりです。 […] B – バイト […] W – ワード […] G – 段落 […] xR – インページ […] P – ページ […] A – 絶対 […] インページ配置コードの x は、他の任意の配置コードにすることができます。 […] セグメントは、インページ属性を持つことができます。インページ属性は、256 バイトのページ内に存在する必要があることを意味し、ワード属性を持つことができます。ワード属性は、偶数バイトに存在する必要があることを意味します。 […]

• データアライメントに関する IBM Developer の記事
• データの調整とパフォーマンスに関する記事
• データの配置に関する Microsoft Learn の記事
• データの整合とデータの移植性に関する記事
• バイトの整列と順序
• Wayback Machineの 64 ビット呼び出し規約におけるスタック アライメント(2018-12-29 アーカイブ) – x86-64 呼び出し規約のスタック アライメントについて説明します。
• エリック・S・レイモンド著「構造パッキングの失われた芸術」