アライメント解説

しばらく放置してしまっていた。中々書くべきことが見つからなかったので。Nintendo Switchを購入してしまい、遊んでいたというのもあるが。

今回は、ちょっと普段気にしないアライメントのことについて話してみようと思う。

以前、C++17でのアライメント指定付き動的メモリ確保の話をした時少し話した気がするが、CPUはメモリのどんな位置にでも好き勝手にアクセスできるわけではない。例えば、一回のメモリアクセスでは16バイト分のデータを16の倍数のアドレスからしか読み込めない、というような感じの制限がある（数字は適当）。なので、以下のようになって困ることがある。

メモリアクセス
 v v v v
| | |d|a|t|a| | |

というわけで、メモリ上でのデータの配置には守るべきルールが存在し、型Tはalignof(T)（例えば8バイト）の倍数にあたるメモリアドレスから始まる領域にしか置くことができない。

これは、以下のようなコードを書くときに問題になってくる。

バイナリファイルを読み書きする場合
何らかの理由でデータのビット表現を取得する必要があるとき
普通でないアライメント指定をして動的メモリ確保するとき

他にもあるかもしれない。何にせよ、例えばバイナリファイルを読み書きしている時、以下のようなことをすると一発で地雷を踏みぬいてしまう。

const char* stream;
const double d = *reinterpret_cast<const double*>(stream);

ここで、streamの位置はバイト単位で変わる。例えばデータ型のタグとして1バイト使っていたとすると、その次からdoubleのデータが始まったりするだろう。すると、メモリ上に確かにsizeof(double)分の領域があり、そこにdoubleのビット列が入っているのだが、メモリアドレスがalignof(double)の倍数になっていないという状況になりかねない。その場合、上のコードでデリファレンスしているポインタは、アライメント要求を満たさない不適切なポインタになってしまう。つまりこうだ。

0x0000
 v
| |d|a|t|a| | |
   ^ 0x0001 (8の倍数でないため、`double`のポインタにできない)

ではどうするか。C規格では(unsigned|signed) charとならどんな型でも変換可能ということになっている。C++17ではstd::byteもここに仲間入りした。これは、char*からT*への変換が常に成立するという意味ではなく（これは常には成立しない）、T*をcharの配列へのポインタへ再解釈して構わないということである。charのアライメント要求が最小ということなのだろう。なので、より安全なコードは以下のようになる。

const char* stream;
double d;
std::memcpy(reinterpret_cast<void*>(std::addressof(d)),
            reinterpret_cast<void*>(stream), sizeof(double));

上記コードではdoubleへのポインタを(memcpyは内部でunsigned charへのポインタに変換するので)unsigned charへのポインタに変換し、両方をunsigned char[N]だと思ってデータをコピーしている。まったく、面倒この上ない。

他に、データのビット表現を取得するとき、というのは、例えばfloatの値をuint32_tへビットをそのままに変換するという意味だ。なぜそんなことをするのかというと、謎のビット演算によっていくつかの高コストな浮動小数点演算が近似できるからだ。このテクニックは以下によくまとまっている。

GitHub - keon/awesome-bits: A curated list of awesome bitwise operations and tricks

この場合、以下のようにしたくなる。

float f = /**/;
std::uint32_t i = *reinterpret_cast<std::uint32_t*>(&f);

実際、以前このブログでも書いてしまった気がする。だがこれは通らない（大抵動くのだが、間違ったコードなので動く保証はない）。これは、floatとstd::uint32_tのアライメント要求が一致している前提で書かれたコードだが、そんな保証はない。保証されているのは前述の通りcharかstd::byteへの変換のみである。

なので、正しくは以下だ。

float f = /**/
std::uint32_t i;
std::memcpy(reinterpret_cast<void*>(std::addressof(f)),
            reinterpret_cast<void*>(std::addressof(i)),
            sizeof(float));

よく考えると、floatが4バイトなのは定義されているのだろうか? std::uint32_tはその点便利で、これは2の補数表現でピッタリ32ビットであることが保証されている。そのような型をサポートしていないアーキテクチャでは、この型が定義されない。なので知らずにコンパイルしてもエラーになってくれる。

ちょっと見てみたが、IEEE754準拠は必須ではない（__STDC_IEC_559__が１ならIEEE 754に対応しているとわかる）。ということは、floatの中身については何も仮定できない。まあintがそうなのだから当たり前か。

（ため息）

さて、上記の３つの状況の最後のものは、普通でないアライメントを指定して何かする時だ。

まず、なぜそんなことをする必要があるのかというと、これもいくつか理由がある。

SIMDなどの特殊な命令を使う
パフォーマンス最適化

まず、SIMDとはSingle Instruction Multiple Dataの略で、一つの命令を複数のデータに同時に適用することで速度向上を図るものだ。例えば、レジスタに4つの数値をロードしておいて、その全てに加算命令を発行して同時に処理すれば、1命令で4つ分の計算ができ、速度が理論上4倍になる。このとき、ロードするデータが通常より大きなアライメントを満たしていれば、ロード速度が向上する。そうでなければ複数回のメモリアクセスが発生し、少し時間がかかってしまう。

他に、キャッシュの更新を抑える目的でアライメントを調整することがある。根本に立ち戻ると、現代のアーキテクチャではメモリはCPUに比べると遅い。なので、CPUの計算よりもメモリアクセスが律速になってしまうことが多い。それをなんとか隠蔽しようとして、CPUは内部に高速にアクセスできるが容量の少ないメモリを持っておき、メモリ上の使いそうなものをそこに先に持ってきておくようになった。CPUは一回につきある決まった量のデータをキャッシュしておくのだが、これはキャッシュラインと呼ばれている。

賢い戦略ではあるのだが、やはり面倒なことはある。例えば並列化で複数のCPUが同じメモリ領域を見ているとすると、一つのCPUでのキャッシュへの書き込みが他のCPUのキャッシュに同期されなければ、データがおかしくなってしまう。なので書き込みが生じた場合、全CPUとメインメモリでデータを同期する必要がある（キャッシュコヒーレンシ）。さて、もし一つのキャッシュライン上に凄まじく頻繁に更新される値が一つと、全く更新されないとわかっている値が沢山乗っていたらどうだろう。ほとんどの値は変更されないのに、同じキャッシュラインに乗っているたった一つの値のせいでキャッシュライン全体の動機が発生する（false sharing）。これを回避する方法はいくつかある。キャッシュラインサイズに沿ったアライメント指定をして別のラインに乗るようにするものと、構造体にダミーデータでパディングして別のキャッシュラインに入るようにするというものだ。

他に外部デバイスと通信するときに気をつけないといけないという話を聞いたことがあるが、あまり書いたことがないのでよくわかっていない。GPUのテクスチャメモリ（か、別の特殊なメモリだったかもしれない）だと何か要求されていたような気がする。

さて、上記のようなコードを書く場合は同時にアライメントについて調べると思うので、あまり変な事にはならないのではないかと思う。ただ、落とし穴があるのは動的にメモリ確保をする時だ。通常、mallocやnewはメモリ領域のサイズしか知らされず、アライメントまでは指定されない。mallocにアライメント値を渡した記憶のある方はいるだろうか？　受け取らないのだからいるはずがない。ではどうしているのかというと、デフォルトのアライメントが決まっており、それに合わせたメモリ領域が返ってくるのだ。このデフォルト値は大抵、基本型の要求するアライメントのうち最大のものになっている。アライメントは何かの倍数のアドレスに置くことを要求するものなので、最大の値の倍数（最大公倍数と言えばいいのだが、大抵全て2のN乗なので最大の値に等しい）は他のものを満たすという便利な性質がある。ではデフォルト値より大きな値を設定するとどうなるか？　どうにもならない。mallocもnewもそんなことは知らない。なのでアライメントは単に無視されてしまう。

このために、C11ではaligned_allocが、C++17ではアライメント指定されたデータの動的メモリ確保が入った。これらはアライメント要求を受け取り、それに適した領域をアロケートして返す。これ以前だと、大きめにアロケートして先頭ポインタが要求を満たすところまでずらすか、posix_memalignや_aligned_mallocなどの処理系定義関数を使う必要があった。

面倒この上ない。だが、これらは計算機科学の奥底に眠っている問題ではなく、バイナリファイルを読もうとしたりちょっとした最適化をしようとしたときにすぐに首をもたげる問題なので、意識しておくのもいいかもしれない。