Loading article…
データ構造のアライメントとは、コンピュータのメモリ内でデータがどのように配置され、アクセスされるかを示すものです。これは、データアライメント、データ構造のパディング、パッキングという、互いに関連しながらも独立した3つの要素から構成されます。
現代のコンピュータハードウェアにおけるCPUは、データが自然に整列している場合に、メモリへの読み書きを最も効率的に実行します。これは一般的に、データのメモリアドレスがデータサイズの倍数であることを意味します。例えば、32ビットアーキテクチャでは、データが連続する4バイトに格納され、最初のバイトが4バイト境界にある場合、データは整列していると言えます。
データアライメントとは、要素をその自然なアライメントに従って整列させることです。自然なアライメントを確保するには、構造体の要素間、または構造体の最後の要素の後にパディングを挿入する必要がある場合があります。たとえば、32ビットマシンでは、16ビット値の後に32ビット値が続くデータ構造の場合、32ビット値を32ビット境界に整列させるために、16ビット値と32ビット値の間に16ビットのパディングを挿入することができます。あるいは、パディングを省略して構造体をパックすることもできます。この場合、アクセス速度は低下する可能性がありますが、16ビットのメモリを節約できます。
データ構造のアライメントは現代のすべてのコンピュータにとって基本的な問題ですが、多くのプログラミング言語とプログラミング言語の実装はデータアライメントを自動的に処理します。Fortran 、 Ada 、 [ 1 ] [ 2 ] PL /I、[ 3 ] Pascal、[ 4 ]特定のCおよびC++実装、D、[ 5 ] Rust、[ 6 ] C#、[ 7 ]およびアセンブリ言語は、データ構造のパディングを少なくとも部分的に制御することができ、これは特定の特殊な状況で役立つ場合があります。
メモリ アドレスaは、 a がnの倍数( nは 2 のべき乗) である場合にnバイト境界にアラインされていると言われます。この文脈では、バイトはメモリ アクセスの最小単位であり、つまり各メモリ アドレスは異なるバイトを指定します。nバイト境界にアラインされたアドレスは、バイナリで表現すると、少なくともlog 2 ( 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バイトの構造体（例えばchar）と4バイトの整数（例えば）を含む構造体は、3バイトのパディングを追加で必要とします。このような構造体の大きな配列は、パックすることでメモリ使用量を37.5%削減できますが、各構造体へのアクセスには時間がかかる場合があります。この妥協点は、空間と時間のトレードオフuint32_tの一種と考えることができます。
「パック」構造はメモリ容量を節約するために最も頻繁に使用されますが、標準プロトコルを使用して送信するためのデータ構造のフォーマットにも使用できます。ただし、この場合、構造体メンバーの値がプロトコルで要求されるエンディアン（多くの場合、ネットワークバイトオーダー）で格納されるように注意する必要があります。これは、ホストマシンが本来使用するエンディアンとは異なる場合があります。
以下の式は、データ構造の先頭を整列させるために必要なパディングバイト数を示します（modは剰余演算子です）。
パディング = (アライン - (オフセット mod アライン)) mod アライン 整列 = オフセット + パディング = オフセット + ((アライン - (オフセット mod アライン)) mod アライン)
例えば、4バイトアラインメントされた構造体の場合、オフセット0x59dに追加するパディングは3です。すると、構造体は4の倍数である0x5a0から始まります。ただし、オフセットのアラインメントが既にアラインメントと等しい場合、 (align - (offset mod align)) mod alignの2番目の剰余演算はゼロを返すため、元の値は変更されません。
アライメントは定義上2のべき乗であるため、[ a ]剰余演算はビットごとのAND演算に簡略化できます。
以下の式は正しい値を生成します（&はビットごとの AND、~はビットごとの NOTを表します）。ただし、オフセットが符号なしであるか、システムが2 の補数演算を使用している場合に限ります。
padding = (align - (offset & (align - 1))) & (align - 1) = -offset & (align - 1) 整列 = (オフセット + (整列 - 1)) & ~(整列 - 1) = (オフセット + (アライン - 1)) & -アライン
データ構造のメンバーはメモリに順番に格納されるため、以下の構造では、メンバーはdata1常にdata2; の前にあり、メンバーはdata2常に : の前にありますdata3。
struct MyData { short data1 ; short data2 ; short data3 ; };型がshort2バイトのメモリに格納される場合、上記のデータ構造の各メンバーは2バイト境界にアラインされます。data1はオフセット 0、data2はオフセット 2、 はdata3オフセット 4に配置されます。この構造のサイズは6 バイトになります。
構造体の各メンバーの型には通常、デフォルトのアライメントが設定されています。つまり、プログラマが特に指定しない限り、あらかじめ決められた境界にアライメントされます。Microsoft ( Visual C++ )、Borland / CodeGear ( C++Builder )、Digital Mars (DMC)、およびGNU ( GCC ) のコンパイラで 32 ビット x86 用にコンパイルする場合、以下の典型的なアライメントが有効です。
charは1バイト境界に揃えられます。short（2バイト）は2バイト境界に揃えられます。int4バイト境界に揃えられます。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 バイト境界にそれぞれ配置されます。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 バイトです。
struct MixedData { char c1 ; short s ; int i ; char c2 ; };コンパイル後、データ構造にはパディングバイトが追加され、各メンバーの適切なアライメントが確保されます。
// 32ビットx86マシンでコンパイル後struct MixedData { char c1 ; // 1バイト//構造体の開始アドレスが偶数であると仮定して、次の 'short' を 2 バイト境界にアラインするための 1 バイトchar padding1 [ 1 ]; short s ; // 2 バイトint i ; // 4 バイト - 最大の構造体メンバーchar c2 ; // 1 バイトchar padding2 [ 3 ]; // 構造体の合計サイズを 12 バイトにするための 3 バイト};コンパイル後の構造体のサイズは12 バイトになりました。
最後のメンバーは、構造体の合計サイズが構造体メンバーの最大アライメントの倍数になるように必要なバイト数だけパディングされます（この場合はalignof(int)、linux-32bit/gcc では = 4）。
この場合、 構造体を12バイトのサイズにパディングするために、最後のメンバーに3バイトが追加されます （alignof(int) * 3）。
struct 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 c1 ; char c2 ; short s ; int i ; };コンパイル後の構造体のサイズは、コンパイル前のサイズである8 バイトと一致します。なお、padding1[1]はdata4に置き換えられ（したがって削除され）、構造体は既にロングワードのサイズにアラインされているため、 padding2[3]は不要になりました。
MixedData構造体を1バイト境界にアラインメントさせる代替方法を用いると、プリプロセッサは構造体メンバーの事前決定されたアラインメントを破棄するため、パディングバイトは挿入されません。
構造体メンバーの配置を定義する標準的な方法はありませんが（C および C++ ではalignas指定子を使用できますが、これはより厳密な配置を指定する場合にのみ使用できます）、一部のコンパイラは#pragmaディレクティブを使用してソース ファイル内のパッキングを指定します。以下に例を示します。
#pragma pack(push) // 現在のアライメントをスタックにプッシュする#pragma pack(1) // アライメントを1バイト境界に設定するstruct MyPackedData { char c1 ; long l ; char c2 ; };#pragma pack(pop) // スタックから元の配置を復元するこの構造は、 32 ビット システムではコンパイル後のサイズが6 バイトになります。上記のディレクティブは、 Microsoft [ 9 ] 、 Borland、GNU [ 10 ]など、多くのコンパイラで利用可能です。
別の例：
struct MyPackedData { char c1 ; long l ; char c2 ; } __attribute__ (( packed ));Microsoft コンパイラの一部、特に RISC プロセッサ向けでは、プロジェクトのデフォルト パッキング (/Zp ディレクティブ) と#pragma packディレクティブの間に予期しない関係があります。#pragma packディレクティブは、構造体のパッキング サイズをプロジェクトのデフォルト パッキングから縮小するためにのみ使用できます。 [ 11 ] このため、プロジェクトのパッキングがこれより小さい場合、たとえば#pragma pack(8)を使用するライブラリ ヘッダーとの相互運用性の問題が発生します。このため、プロジェクトのパッキングをデフォルトの 8 バイト以外の値に設定すると、ライブラリ ヘッダーで使用される#pragma packディレクティブが壊れ、構造体間のバイナリ互換性の問題が発生します。この制限は、x86 用にコンパイルする場合にはありません。
キャッシュラインにアラインされたメモリを割り当てると効果的です。配列を複数のスレッドで操作するために分割する場合、サブ配列の境界がキャッシュラインにアラインされていないと、パフォーマンスが低下する可能性があります。以下に、 64バイトのキャッシュにアラインされたメモリ（サイズ10のdouble型配列）を割り当てる例を示します 。
#include <stdlib.h>// サイズ10の配列を作成するdouble * foo ( void ) { double * a ; if ( posix_memalign (( void ** ) &a ) a 、64、10 * sizeof ( double ) ) == 0 ) { return a ; }return NULL ; }ハードウェアアドレス変換メカニズム（PCIリマッピング、 MMUの動作）を介してその領域を効率的にマッピングすることが目的の場合、アライメントの問題はC構造体よりもはるかに大きな領域に影響を与える可能性があります。
例えば、32ビットオペレーティングシステムでは、4 KiB（4096バイト）のページは、単なる任意の4 KiBのデータチャンクではありません。実際には、通常は4 KiB境界にアラインされたメモリ領域です。これは、ページをページサイズの境界にアラインすることで、ハードウェアが複雑な算術演算を行うのではなく、アドレスの上位ビットを置き換えることで仮想アドレスを物理アドレスにマッピングできるためです。
例: 仮想アドレス0x2CFC7000から物理アドレス0x12345000への TLB マッピングがあるとします。(これらのアドレスは両方とも 4 KiB 境界にアラインされています。) 仮想アドレス va=0x2CFC7ABC にあるデータにアクセスすると、 0x2CFC7から0x12345への TLB 解決が行われ、{{{1}}}への物理アクセスが発行されます。ここで、20/12 ビットの分割は、5/3 桁で分割された 16 進数表現と幸運にも一致します。ハードウェアは、物理アドレス ( 0x12345 ) の最初の 20 ビットと仮想アドレス ( 0xABC ) の最後の 12ビットを組み合わせるだけで、この変換を実装できます。これは、仮想インデックス ( ABC ) 物理タグ ( 12345 )とも呼ばれます。
サイズ 2 (n+1) − 1のデータブロックには、常に 2 nバイトにアラインされたサイズ 2 nのサブブロックが 1 つ含まれます。
このように、アライメントに関する知識を持たない動的アロケータを使用しても、スペース損失が2倍になるという代償を払うことで、アライメントされたバッファを提供することができます。
// 例: malloc() を使用して 4096 バイトのバッファ上に 4096 バイトをアラインメントする// 大きな領域へのアラインメントされていないポインタvoid * up = malloc (( 1 << 13 ) - 1 ); // 4 KiB へのアラインメントされたポインタvoid * ap = ALIGN_TO_NEXT ( up , 12 );ここで、は、整列した増分を加算し、次にの最下位ビットをクリアすることによって機能します。考えられる実装は次のとおりです。ALIGN_TO_NEXT(p, r)rp
// 読みやすさのために `uint32_t p, bits;` と仮定します#define ALIGN_TO(p, bits) (((p) >> bits) << bits) #define ALIGN_TO_NEXT(p, bits) ALIGN_TO(((p) + (1 << bits) - 1), bits)[…] セグメントには、5 つのアライメント属性のうち 1 つ (inpage 属性の場合は 2 つ) を指定できます。 […] バイト。これは、セグメントが任意のアドレスに配置できることを意味します。 […] ワード。これは、セグメントがアドレス 0H から始まる 2 の倍数のアドレスにのみ配置できることを意味します。 […] 段落とは、セグメントがアドレス 0 から始まる 16 の倍数のアドレスにのみ配置できることを意味します。 […] ページとは、セグメントがアドレス 0 から始まる 256 の倍数のアドレスにのみ配置できることを意味します。 […] インページとは、セグメントが上記の属性のいずれかに配置されることが可能であり、かつページ境界をまたがらないように配置される必要があることを意味します。 […] 配置コードは次のとおりです。 […] B – バイト […] W – ワード […] G – 段落 […] xR – インページ […] P – ページ […] A – 絶対 […] インページ配置コードの x は、他の任意の配置コードにすることができます。 […] セグメントは、インページ属性を持つことができ、これはセグメントが 256 バイトのページ内に存在しなければならないことを意味します。また、ワード属性を持つことができ、これはセグメントが偶数バイト上に存在しなければならないことを意味します。 […]