Wikipedia

データ構造アライメント

データ構造アライメント（データこうぞうアライメント、英語: data structure alignment）は、コンピュータのメモリ（主記憶装置）内のデータにアクセス（読み書き）する際に、メモリ上の位置の調整を行うことである。

そこには、別々だが関連する2つの問題、すなわち、データ整列とデータ構造パディングがある。最新のコンピュータがメモリアドレスを読み書きする場合には、ワードサイズのチャンク（32ビットシステムの場合は4バイトのチャンク）単位で実行される。データ整列とは、ワードサイズの倍数に等しいメモリアドレスにデータを配置することであり、CPUがメモリを処理する方法によってシステムのパフォーマンスが向上する。データを整列させるには、最後のデータ構造の終端部分と次のデータ構造の開始部分の間に未使用のバイトを挿入する必要があり、これを「データ構造パディング」という。

例えば、コンピュータのワードサイズが4バイトの場合（バイトは、ほとんどのコンピュータで8ビットを意味するが、一部のシステムでは異なる可能性がある）、読み取るデータは4の倍数のメモリアドレスにある必要がある。例えば、データが16番地ではなく14番地から開始する場合、コンピュータは、4バイトのチャンクを2つ以上読み取り、要求されたデータが読み出される前に何らかの計算を実行しなければならないか、アライメントエラーを生成する可能性がある。よって、その前のデータ構造の終端が13番地にあったとしても、次のデータ構造は16番地から始める必要がある。そのため、2つのパディングバイトが2つのデータ構造の間の14番地と15番地に挿入される。

データ構造のアライメントは現代の全てのコンピュータにとって基本的な問題であるが、多くのコンピュータ言語およびコンピュータ言語の実装がデータ整列を自動的に処理する。Ada[1][2]、PL/I、C言語（C11以降[3]）・C++（C++11以降[4]）[5]、D言語[6]、Rust[7]、アセンブリ言語は、特定の特殊な状況で有用なデータ構造のパディングを少なくとも部分的に制御することを可能にしている。

定義

編集

メモリアドレス a は、a が n バイトの倍数（n は2の累乗）であるときに、「n バイトアライメント」と呼ばれる。この場合、バイトはメモリアクセスの最小単位である。つまり、各メモリアドレスは異なるバイトを指定する。二進数で表現した場合、n バイトアライメントされたアドレスの下位の桁は、最小で log2(n) 桁がゼロになる。

「b ビットアライメント」は、「b/8 バイトアライメント」とも表現できる（例えば、64ビットアライメントは8バイトアライメント）。

アクセスされるデータが n バイト長であり、データアドレスが n バイトアライメントされている場合、メモリアクセスは「アラインされている」(aligned) という。メモリアクセスがアライメントされていない場合は、「アラインされていない」(misaligned) という。定義上、バイトメモリアクセスは常にアラインされている。

n バイト長のプリミティブ・データを参照するメモリポインタは、nバイトアライメントされたアドレスのみを含むことが許可されていれば、「アラインされている」という。データ集合体（構造体または配列）を参照するメモリポインタは、集合体内の各プリミティブデータがアラインされている場合かつその場合にのみ、アラインされている。

上記の定義は、各プリミティブデータが2の累乗バイトの長さであると仮定している。これが当てはまらない場合（x86の80ビット浮動小数点の場合など）、コンテキストはデータがアラインされているとみなされる条件に影響する。

構造体は、スタックに静的なサイズで、またはヒープ上に動的なサイズで格納できる。

問題

編集

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

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

単一のメモリワードにアクセスするとき、その動作はアトミックである。すなわち、メモリワード全体が一度に読み書きされ、その処理が完了するまでは他のデバイスによるアクセスはできない。これは、複数のメモリワードへのアライメントされていないアクセスの場合は当てはまらない。例えば、あるデバイスが最初のワードを読み込み、別のデバイスが両方のワードに書き込み、その後、1つ目のデバイスが2つ目のワードを読み込んだとき、読み込まれた値は更新前の値とも更新後の値とも異なる。このような失敗はまれだが、識別するのが非常に難しい場合がある。

アーキテクチャ

編集

RISC

編集

ほとんどのRISCプロセッサは、ロード命令やストア命令でアラインされていないアドレスにアクセスすると、アライメントフォールトを生成する。これにより、オペレーティングシステムは、他の命令を使用してアラインされていないアクセスをエミュレートできる。例えば、アライメントフォールトハンドラは、大きなロード命令やストア命令をエミュレートするために、バイト単位のロードやストア（常にアラインされている）を使用する場合がある。

MIPSなどのいくつかのアーキテクチャでは、特別なアラインされていないロード命令とストア命令がある。1つのアライメントされていないロード命令は、最も低いバイトアドレスを持つメモリワードからバイトを取得し、別のロード命令は、最も高いバイトアドレスを持つメモリワードからバイトを取得する。同様に、ストア・ハイ命令およびストア・ロー命令は、それぞれ上位および下位メモリワードに適切なバイトを格納する。

Alphaアーキテクチャでは、アライメントされていないロードおよびストアに対する2段階のアプローチがある。第1のステップは、上位および下位のメモリワードを別々のレジスタにロードすることである。第2のステップは、MIPS命令と同様の特別なロー/ハイ命令を使用してメモリワードを抽出または修正することである。アラインされていないストアは、変更されたメモリワードをメモリに戻すことによって完了される。この複雑さの理由は、オリジナルのAlphaアーキテクチャでは、32ビットまたは64ビットの値しか読み書きできないためである。これは、しばしばコードが膨らんでパフォーマンスが低下する重大な制限となることが判明した。この制限に対処するために、元のアーキテクチャにByte Word Extensions (BWX) という拡張機能が追加された。これは、バイトとワードのロード・ストアのための命令で構成されている。

これらの命令は、通常のメモリロード・ストア命令よりも大きく、遅いため、必要なときにのみ使用するべきである。CおよびC++のコンパイラの中には、アライメントの合っていない命令を必要とするポインタに適用できる“unaligned”属性がある[8]。

x86

編集

x86アーキテクチャは本来、アライメントされたメモリアクセスを必要とせず、またそれなしでは動作するが、x86 CPUのSSE2命令の中には、データを128ビット（16バイト）にアライメントさせる必要があるものがあり、これらのアーキテクチャでアライメントされたデータを使用することにより、パフォーマンス上の大きな利点が得られる。ただし、MOVDQUなどのアラインされていないアクセスのための命令もある。さらに、ロードとストアの操作は、通常、正しくアラインされていればアトミックである。

互換性

編集

アラインされていないアクセスをサポートする利点は、アクセスを遅くするという犠牲を払ってでも、メモリを調整する必要のないコンパイラを書くほうが簡単だということである。生のパフォーマンスを最大にするように設計されたRISCプロセッサのパフォーマンスを向上させる1つの方法は、データの自然な境界にデータをロードまたは格納することである。従って、メモリは一般に8ビットのバイトで扱われるが、32ビットマシンで32ビット整数をロードするには32ビットごとに開始し、64ビットマシンで64ビット整数や浮動小数点数をロードするには64ビットごとに開始する必要がある。このような境界にない数値をロードするように要求された場合、プロセッサはフォールトにフラグを立てることができる。しかし、これは、どのワードがデータを含んでいるか把握し、同等の値を抽出する必要があるルーチンへの呼び出しを遅くすることになる。

データ構造パティング

編集

コンパイラ（またはインタプリタ）は、通常、アラインされた境界上に個々のデータ項目を割り当てるが、データ構造はしばしば異なるアライメント要件を有するメンバーを有する。適切なアライメントを維持するために、トランスレータは通常、追加の無名のデータメンバーを挿入して、各メンバーが適切にアライメントされるようにする。さらに、データ構造全体には、終端に名前のないメンバーが埋め込まれている場合がある。これにより、構造体配列の各メンバを適切にアラインすることができる。

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

CとC++では、コンパイラがスペースを節約するために構造体メンバを並べ替えることはできないが、他の言語では可能である。また、大部分のC/C++コンパイラでは、構造体のメンバを一定のアラインレベルで「パック」することもできる。例えば、"pack（2）"は、バイトよりも大きいデータメンバを2バイト境界にアラインメントさせることを意味する。全てのパッディングメンバは最大で1バイト長である。

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

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

パディングの計算

編集

次の式は、データ構造の開始位置をアラインメントするのに必要なパディングバイト数を示す（modは剰余演算子）。 

padding = (align - (offset mod align)) mod align
aligned = offset + padding
        = offset + ((align - (offset mod align)) mod align)

例えば、4ビットアライメントの構造体のオフセット0x59dに追加するパディングは3である。構造体は0x5a0（4の倍数）番地から開始する。ただし、offset のアライメントが align のアライメントと既に等しい場合、(align - (offset mod align)) mod align の2つ目の剰余演算はゼロを返すので、元の値は変更されない。

定義によりアライメントは2の累乗であるため、剰余演算はビット単位のAND演算に置き換えられる。

次の数式はアラインしたオフセットを生成する（& はビット単位のAND、~ はビット単位のNOT）。 

padding = (align - (offset & (align - 1))) & (align - 1)
        = (-offset & (align - 1))
aligned = (offset + (align - 1)) & ~(align - 1)
        = (offset + (align - 1)) & -align

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

編集

構造体のメンバは、メモリに順番に格納されるため、以下の構造体では、メンバData1は常にData2の前に、Data2は常にData3の前に配置される。 

struct MyData
{
    short Data1;
    short Data2;
    short Data3;
};

short型が2バイトのメモリに格納されている場合、上記の構造体の各メンバは2バイトでアラインされる。Data1はオフセット0、Data2はオフセット2、Data3はオフセット4になる。この構造体のサイズは6バイトになる。

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

  • 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 C++では8バイトアライメント、GCCでは4バイトアライメント
  • ポインタ（4バイト） - 4バイトアライメント

LP64モデルの64ビットシステムは次の通りである。

  • long（8バイト） - 8バイトアライメント
  • double（8バイト） - 8バイトアライメント
  • long long（8バイト） - 8バイトアライメント
  • long double（GCCでは16バイト） - GCCでは16バイトアライメント
  • ポインタ（8バイト） - 8バイトアライメント

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

次に挙げる構造体は、様々な型のメンバを有しており、そのバイト数を単純に合計すると8バイトになる。 

struct MixedData
{
    char Data1;
    short Data2;
    int Data3;
    char Data4;
};

コンパイル後、構造体にはパディングバイトが追加され、各メンバの適切なアライメントが保証される。 

struct MixedData  /* After compilation in 32-bit x86 machine */
{
    char Data1; /* 1バイト */
    char Padding1[1]; /* 次のshort型を2バイト境界にアラインするための1バイトのパディング。
 構造体が始まるアドレスが偶数であると仮定。 */
    short Data2; /* 2バイト */
    int Data3;  /* 4バイト - 最も大きな構造体メンバ */
    char Data4; /* 1バイト */
    char Padding2[3]; /* 構造体のサイズを12バイトにするための3バイトのパディング */
};

構造体のコンパイルされたサイズは12バイトになる。最後のメンバの後にもパディングバイトが追加されていることに留意されたい。この場合、構造体の合計サイズは、構造体メンバの最大のアライメントの倍数となる。上の例では、構造体を12バイトのサイズにパディングするために最後のメンバの後に3バイトが追加される。 

struct FinalPad
{
    float x;
    char n[1];
};

上記の例では、sizeof演算子により算出される FinalPad 構造体のサイズ sizeof(FinalPad) は5ではなく8（floatのアライメントの倍数）になる。 

struct FinalPadShort
{
    short s;
    char n[3];
};

上記の例では、FinalPadShort 構造体のサイズ sizeof(FinalPadShort) は5や8ではなく6（shortのアライメントの倍数）になる。

構造体メンバの順序を変更したり、構造体メンバのコンパイラのアライメントを変更（パッキング）して、必要なメモリを減らす（または既存の形式に準拠させる）ために、構造体のアライメントを変更することができる。前述の MixedData 構造体にこれを適用すると、次のようになる。 

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

これにより、構造体のコンパイル後のサイズが、メンバのバイト数を単純に合計したサイズである8バイトと一致するようになった。Padding1[1] は Data4 によって置き換えられ（従って排除され）、構造体は既にlong wordのサイズにアラインされているので、 Padding2[3] はもはや必要ではない。

MixedData 構造体を1バイト境界にアライメントさせる別の方法は、プリプロセッサに構造体メンバの所定のアライメントを破棄させ、これによりパディングバイトを挿入しないようにすることである。

C11およびC++11よりも前の規格では、構造体メンバのアライメントを定義する標準的な方法はないが、コンパイラの中には #pragma ディレクティブを使用してソースファイル内のパッキングを指定するものがある。次にその例を示す。 

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

struct MyPackedData
{
    char Data1;
    long Data2;
    char Data3;
};

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

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

もう1つの例: 

struct MyPackedData
{
    char Data1;
    long Data2 __attribute__((packed));
    char Data3;
};

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

編集

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

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

編集

キャッシュメモリのラインに合わせてメモリを割り当てることは有益である。配列が複数のスレッドが動作するようにパーティション化されている場合、サブ配列の境界をキャッシュラインとアラインさせないとパフォーマンスが低下する可能性がある。次に、64バイトのキャッシュにアライメントされたメモリ（サイズ10の倍精度配列）の例を示す。 

#include <stdlib.h>
double *foo(void) {
    double *var; /* サイズ10の配列を作成 */

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

    if (ok != 0) {
        return NULL;
    }

    return var;
}

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

編集

アライメントの問題は、ハードウェアアドレス変換メカニズム（PCIリマッピング、MMUで実施）によるその領域の効率的なマッピングが目的である場合、C構造体よりもはるかに大きな領域に影響を与える可能性がある。

例えば、32ビットオペレーティングシステムでは、4 KBページは、任意の4 KBのデータチャンクだけではない。通常は、4 KB境界にアラインされたメモリ領域である。これは、ページをページサイズの境界にアラインすると、複雑な算術演算ではなくアドレスの上位ビットを置換することで、ハードウェアが物理アドレスに仮想アドレスをマップできるためである。

例: 物理アドレス0x12345000に仮想アドレス0x2cfc7000のTLBマッピングがあるとする（これらのアドレスは両方とも4 KB境界でアラインされている）。仮想アドレスva = 0x2cfc7abcにあるデータにアクセスすると、0x2cfc7〜0x12345のTLB分解能で、pa = 0x12345abcへの物理アクセスが行われる。ここで、20/12ビットの分割は幸いなことに、5/3桁の16進表現の分割に一致する。ハードウェアは、物理アドレス（0x12345）の最初の20ビットと仮想アドレス（0xabc）の最後の12ビットを単純に組み合わせることによって、この変換を実装できる。これは、仮想インデックス（abc）物理的タグ付け（12345）とも呼ばれる。

サイズ 2^(n+1)-1 のデータのブロックは、常に 2^n バイトにアラインされたサイズ 2^n の1つのサブブロックを有する。

以下は、アライメントの知識のない動的アロケータを使用して、スペースロスの2倍を犠牲にして、アラインしたバッファを提供する方法である。 

Example: get a 12-bit aligned 4 KBytes buffer with malloc()

// unaligned pointer to large area
void *up=malloc((1<<13)-1);
// well-aligned pointer to 4 KBytes
void *ap=aligntonext(up,12);

where aligntonext() is meant as:
move p to the right until next well-aligned address if
not correct already. A possible implementation is

// PSEUDOCODE assumes uint32_t p,bits; for readability
// --- not typesafe, not side-effect safe
#define alignto(p,bits) (p>>bits<<bits)
#define aligntonext(p,bits) alignto((p+(1<<bits)-1),bits)

関連項目

編集

脚注

編集
  1. ^ “Ada Representation Clauses and Pragmas”. GNAT Reference Manual 7.4.0w documentation. http://docs.adacore.com/gnat_rm-docs/html/gnat_rm/gnat_rm/representation_clauses_and_pragmas.html 2015年8月30日閲覧。 
  2. ^ “F.8 Representation Clauses”. SPARCompiler Ada Programmer's Guide. http://docs.oracle.com/cd/E19957-01/802-3641/802-3641.pdf 2015年8月30日閲覧。 
  3. ^ _Alignas - cppreference.com
  4. ^ alignas specifier (since C++11) - cppreference.com
  5. ^ いくつかのC/C++の実装（処理系）では、これらの規格が標準化される以前から、独自拡張としてアライメント指定をサポートしている。
  6. ^ “Attributes - D Programming Language: Align Attribute”. 2012年4月13日閲覧。
  7. ^ “The Rustonomicon - Alternative Representations”. 2016年6月19日閲覧。
  8. ^ __unaligned | Microsoft Docs
  9. ^ pack pragma | Microsoft Docs
  10. ^ 6.58.8 Structure-Packing Pragmas
  11. ^ “Working with Packing Structures”. MSDN Library. Microsoft (2007年7月9日). 2011年1月11日閲覧。

参考文献

編集
  • Bryant, Randal E.; David, O'Hallaron (2003). Computer Systems: A Programmer's Perspective (2003 ed.). Upper Saddle River, NJ: Pearson Education. ISBN 0-13-034074-X. http://csapp.cs.cmu.edu/ 

外部リンク

編集
「https://ja.wikipedia.org/w/index.php?title=データ構造アライメント&oldid=85636523」から取得