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

フリー百科事典ウィキペディアより
ナビゲーションにジャンプ 検索にジャンプ

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

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

データの配置は、自然な配置に従って要素を配置することです。自然な位置合わせを確保するために、構造体要素の間または構造体の最後の要素の後にパディングを挿入する必要がある場合があります。たとえば、32 ビット マシンでは、16 ビット値の後に 32 ビット値が続くデータ構造では、16 ビット値と 32 ビット値の間に 16 ビットのパディングを配置して、32 ビット値を整列させることができます。 32 ビット境界上の値。または、パディングを省略して構造体をパックすることもできます。これにより、アクセスが遅くなる可能性がありますが、メモリの使用量は 4 分の 3 になります。

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

定義

メモリ アドレスaは、a がnの倍数( nは 2 の累乗) の場合nバイトアラインされていると言われます。このコンテキストでは、バイトはメモリアクセスの最小単位です。つまり、各メモリアドレスは異なるバイトを指定します。nバイトでアラインされたアドレスは、 2 進数で表すと、少なくともlog 2 ( n )の最下位ゼロを持ちます。

b-bit 整列という別の言い回しは、b/8 バイト整列アドレスを示します (例: 64 ビット整列は 8 バイト整列です)。

アクセスされるデータの長さがn バイトで、データム アドレスがnバイトでアラインされている場合、メモリ アクセスはアラインされていると言われますメモリー・アクセスがアライメントされていない場合、ミスアライメントと呼ばれます。定義により、バイト メモリ アクセスは常に整列されることに注意してください。

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

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

データ構造は、 bounded と呼ばれる静的サイズのスタックまたはunboundedと呼ばれる動的サイズのヒープのメモリに格納できます

問題

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

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

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

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

データ構造パディング

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

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

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

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

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

パディングの計算

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

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

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

アラインメントは定義上2 のべき乗であるため、[a]モジュロ演算はビットごとのブール AND 演算に減らすことができます。

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

パディング = (整列 - (オフセット & (整列 - 1))) & (整列 - 1)
        = -オフセット & (整列 - 1)
整列 = (オフセット + (整列 - 1)) & ~(整列 - 1)
        = (オフセット + (整列 - 1)) & -整列

x86 での C 構造体の典型的なアライメント

データ構造体のメンバーはメモリに順番に格納されるため、以下の構造体では、メンバー Data1 が常に Data2 より前になります。そして、Data2 は常に Data3 より前になります。

 MyData構造体
{
    短いData1 ; 
    短いData2 ; 
    短い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 バイト) は 4 バイトでアラインされます。
  • long double ( C++Builder と DMC では 10 バイト、Visual C++ では 8 バイト、GCC では 12 バイト) は、C++Builder では 8 バイト、DMC では 2 バイト、Visual では 8 バイトになります。 C++、および GCC に合わせた 4 バイト。
  • 任意のポインター(4 バイト) は 4 バイトでアラインされます。(例: char*、int*)

32 ビット システムと比較した場合のLP64 64 ビット システム のアラインメントにおける注目すべき唯一の違いは次のとおりです。

  • 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 バイトになる、さまざまな型のメンバーを含む構造体です。

struct  MixedData
{
    char Data1 ; 
    短いData2 ; 
    intデータ 3 ; 
    char Data4 ; 
};

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

struct  MixedData /* 32 ビット x86 マシンでのコンパイル後 */  
{
    char Data1 ; /* 1 バイト */  
    char Padding1 [ 1 ]; /*構造体が始まるアドレスが偶数であると仮定して、次の「short」が 2 バイト境界に整列するための 1 バイト*/  

    短いData2 ; /* 2 バイト */  
    intデータ 3 ; /* 4 バイト - 最大の構造体メンバー */   
    char Data4 ; /* 1 バイト */  
    char Padding2 [ 3 ]; /* 構造体の合計サイズを 12 バイトにするために 3 バイト */  
};

構造体のコンパイル済みサイズは 12 バイトになりました。構造体の合計サイズが任意の構造体メンバーの最大アラインメントの倍数になるように、最後のメンバーに必要なバイト数が埋め込まれていることに注意することが重要です (この場合は、alignment(int) = 4 on linux-32bit/gcc) [要出典] .

この場合、最後のメンバーに 3 バイトが追加され、構造体が 12 バイトのサイズ (alignment(int) × 3) になるまでパディングされます。

struct  FinalPad { 
  フロートx ; 
  char n [ 1 ]; 
};

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

struct  FinalPadShort { 
  ショート; _ 
  char n [ 3 ]; 
};

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

構造体メンバーを並べ替えるか、構造体メンバーのコンパイラーの配置 (または「パッキング」) を変更することにより、構造体の配置を変更して必要なメモリを減らす (または既存の形式に準拠させる) ことができます。

struct  MixedData /* 並べ替え後 */  
{
    char Data1 ; 
    char Data4 ; /* 並べ替えました */    
    短いData2 ; 
    intデータ 3 ; 
};

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

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

構造体メンバーのアラインメントを定義する標準的な方法はありませんが、一部のコンパイラは#pragmaディレクティブを使用してソース ファイル内のパッキングを指定します。以下に例を示します。

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

構造体 MyPackedData
{
    char Data1 ; 
    長いData2 ; 
    char Data3 ; 
};

#pragma pack(pop)    /* スタックから元のアライメントを復元 */

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

もう一つの例:

構造体 MyPackedData
{
    char Data1 ; 
    長いData2 ; 
    char Data3 ; 
} __attribute__ (( pack )); 

デフォルトのパッキングと#pragma pack

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

キャッシュ ラインに合わせてメモリを割り当てる

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

#include <stdlib.h> 
double * foo (ボイド) {  
   ダブル*変数; // サイズ 10 の配列を作成int ok ; 
        

   ok = posix_memalign (( void ** ) & var , 64 , 10 * sizeof ( double ));    

   もし(大丈夫!= 0 )   
     NULLを返します 

   変数を返します。 
}

アライメント要件のハードウェアの重要性

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

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

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

サイズ 2 (n+1) - 1 のデータのブロックには、常に 2 n バイト  に整列されたサイズ 2 nの 1 つのサブブロックがあります。

これは、アラインメントの知識を持たない動的アロケーターを使用して、2 分の 1 のスペース損失を犠牲にして、アラインメントされたバッファーを提供する方法です。

// 例: malloc() を使用して 4096 バイトのバッファに整列された 4096 バイトを取得します

// 大領域へのアラインされていないポインタ
void * up = malloc (( 1 << 13 ) - 1 );       
// 適切に配置された 4 KiB へのポインター
void * ap = aligntoext ( up , 12 );    

ここで、 aligntoext( p , r ) は、アラインされたインクリメントを追加してから、 pのr 個の最下位ビットをクリアすることによって機能します可能な実装は

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

注意事項

  1. ^ ターゲット アラインメントが 2 のべき乗である最新のコンピューター。これは、たとえば、9 ビット バイトまたは 60 ビット ワードを使用するシステムでは当てはまらない場合があります。

参考文献

  1. ^ "Ada 表現句とプラグマ" . GNAT リファレンス マニュアル 7.4.0w ドキュメント2015 年 8 月30 日閲覧
  2. ^ "F.8 表明条項". SPARCompiler Ada プログラマーズ ガイド(PDF) 2015 年 8 月30 日閲覧
  3. ^ IBM System/360 オペレーティング システム PL/I 言語仕様(PDF) . IBM1966 年 7 月。55 ~ 56 ページ。C28-6571-3.
  4. ^ Niklaus Wirth (1973 年 7 月). 「プログラミング言語Pascal(改訂版レポート)」(PDF) . p。12.
  5. ^ "属性 - D プログラミング言語: 属性の整列" . 2012年 4 月 13 日閲覧
  6. ^ 「ラストノミコン - 別の表現」. 2016 年6 月 19 日閲覧
  7. ^ "LayoutKind Enum (System.Runtime.InteropServices)" . docs.microsoft.com 2019-04-01取得
  8. ^ Kurusa, Levente (2016-12-27). 「ARM でのアラインされていないアクセスの奇妙なケース」 . ミディアム2019-08-07取得
  9. ^ パック
  10. ^ 6.58.8 構造パッキング プラグマ
  11. ^ "パッキング構造の操作" . MSDN ライブラリ. マイクロソフト。2007-07-09 . 2011 年1 月 11 日閲覧

さらに読む

  • ブライアント、ランダル E .; デビッド、オハラロン(2003)。コンピューター システム: プログラマーの視点(2003 年版)。米国ニュージャージー州アッパーサドルリバー:ピアソン教育ISBN 0-13-034074-X.
  • 「1. はじめに: セグメントの配置」. 8086 ファミリ ユーティリティ - 8080/8085 ベースの開発システムのユーザー ガイド (PDF)リビジョン E (A620/5821 6K DD 版)。米国カリフォルニア州サンタクララ:インテル コーポレーション1982 年 5 月 [1980 年、1978 年]。pp.1-6、3-5。注文番号: 9800639-04。2020-02-29 にオリジナルからアーカイブ (PDF) . 2020-02-29取得[…] セグメントは、5 つのアラインメント属性のうちの 1 つ (ページ内属性の場合は 2 つ) を持つことができます: […] バイト。これは、セグメントが任意のアドレスに配置できることを意味します。[…] ワード、つまりセグメントは、アドレス 0H から始まる 2 の倍数のアドレスにしか配置できないことを意味します。[…] 段落。セグメントは、アドレス 0 から始まる 16 の倍数のアドレスにのみ配置できることを意味します。 […] ページ。セグメントは、256 の倍数のアドレスにのみ配置できることを意味します。 、アドレス 0 から開始。[…] B - バイト […] W - 単語 […] G - 段落 […] xR - ページ内 […] P - ページ […] A - 絶対 […] ページ内位置合わせコードの x はその他の任意の値にすることができます整列コード。[…] セグメントは inpage 属性を持つことができます。つまり、256 バイトのページ内に存在する必要があり、word 属性を持つことができます。つまり、偶数バイトに存在する必要があります。[…]

外部リンク