はい。C++17を使っている人はnewが全部やってくれるようになったので不要な話です。C++17以前のコードのため。
Introduction
アライメントとは、ざっくり言うとメモリ上の位置調整であり、普段は気にしなくていい（コンパイラやmallocがちゃんとやってくれる）。だが、SIMDなどの特殊用途や、キャッシュ効率の最適化などの際は考慮する必要がある。SIMDは、例えば一度に256bit分の長さの値（double x4とか、std::int32_t x8とか）を足し算するとかいう感じの命令だが、この256bitの値（普通は何かの配列）がメモリ上で32byte境界にぴったり乗っている（メモリアドレスが32の倍数になっている）と読み書きが楽だったりする。あるいは、CPUキャッシュは大抵64byte境界から64byteを一単位として持ってくるのだが、キャッシュされて欲しいデータが一つのキャッシュラインに収まっていれば効率がよくなる。"false sharing"などでググってみると面白い話が出てくる。
値がスタックに乗る場合、スタックメモリはコンパイラの管理下にあるので、そのアドレスはコンパイラが制御できる。だが、ヒープアロケーションを伴う場合、普通のmallocやnewにはアライメント情報を渡せないので（newに関してはC++17以前の話）、適切なアライメントになっている保証はない。これを解決する方法は大きく分けて3つある。コンパイラを新しくしてC++17を使うか、posix_memalignや_mm_alloc（intel製CPUのみ）、_aligned_alloc（Windows）などの環境依存な関数を使うか、多めにメモリを確保してアライメントが満たされる領域を使うかだ。
std::alignはこの第三の選択肢を実装するためにもってこいだ。これは、あるメモリ領域の中に、指定したアライメントを満たす指定したサイズの領域があれば、その領域の先頭を返す。
今回の記事は、これを使えばposix_memalignと_aligned_allocを使い分けなくていいじゃん！ と思ったものの意外と難しかったという記録だ。できたっぽいけど。
Method
まず、void* malloc(size_t)の変種みたいなものvoid* aligned_alloc(align, size)を作る以上、void aligned_free(void*)できる必要がある。これがあとで結構色々な制限に繋がってくる。
基本的なアイデアを少し詰めていこう。まず、大きめの領域を確保して、そこからアライメントがあっている箇所を抜き出してくる。常に満たされるアライメントをmin_alignとすると、要求されたアライメントがreq_alignとして、req_align - min_alignだけ広く取れば、必ずアラインされている（req_alignの倍数になるメモリアドレスから始まる）領域があることになる。例えば、常に16byteアラインが満たされる時、64byteアライメントを満たすには、48byteだけ広く取っておけば大丈夫だ。
,_____________allocated size _________, | ,____ required size ____, | | | | padding ... | aligned memory region | ^ min_align ^ req_align
ここまではいい。だが、正しくメモリを解放しようと思うと、これでは足りない。というのも、アライメントされた領域のポインタを返すと、もともと確保されたメモリ領域がどこまでだったかわからなくなるからだ。最初のアライメントはmin_alignの保証しかないことを考えると、何バイトにアラインされているかがわかっても、絞り込めないケースが出てくる（例えばreq_align = 64byteでmin_align = 16byteだったとすると、パディングのサイズは16, 32, 48の3通りあり得、先頭ポインタからはその情報は消えている）。つまり、パディングの量か、本来の先頭へのポインタを覚えておく必要があるのだ。
ではどちらを覚えておくべきだろうか。パディングの量だとメモリ消費が少なくなりそうだが、よく考えると要求されるアライメントのサイズが不明なので結局ptrdiff_tを使うことになりそうだ。するとポインタを覚えておくのと特に変わりない。また、パディングに「パディングのサイズ」自体を含めるかどうかが曖昧で、こういうミスが許されないところで使うのは怖い（いや、プログラムは大抵どこでもミスは許されないのだが）。となると、本来の先頭を指すvoid*を覚えておくのが楽だろう。
,_____________allocated size _________, | ,____ required size ____, | | | | padding ... | aligned memory region | ^ +-- ここを覚えておきたい
ではどこにそのvoid*を置くか。今後使う領域に置くわけには行かないので（早晩書き換えられてしまうだろう）、選択肢は概ね3つだ。真の先頭、アラインされた領域の直前、アラインされた領域の直後だ。
|void*| padding ... | aligned memory region |
| padding ... |void*| aligned memory region |
| padding ... | aligned memory region |void*|
だが、実際にfreeする時のことを考えると、取り得る選択肢は1つに絞られる。上の図では真ん中にある、「アラインされた領域の直前」しかない。まず、最初の選択肢は、先に述べてある「パディングのサイズが不明」という問題を解決できない。なので、そもそもこのvoid*を取りに行けない。よって却下。次に、最後の選択肢、最後尾に置くというものだが、往々にして人はインデックスを溢れさせてこの値が書き換えられるだろうから、ではなく、aligned_free(void*)は領域のサイズを受け取らないので、aligned memory regionがどれくらいの長さかわからず、結局これも取りに行けないのだ。
というわけで、aligned_free(void*)からvoid*をsizeof(void*)バイトだけ一つ後ろにずらすだけで必ず取りに行ける、真ん中の選択肢が唯一生き残る。その場合、aligned_freeの実装は以下のようになるだろう。まず、受け取ったvoid*をvoid**だと思い込み、一つ後ろを見る（これでvoid*一つぶん後ろに動く）。そこの内容を取ってきて、std::freeに渡す。
void aligned_free(void* ptr) { if(ptr) { std::free(*(reinterpret_cast<void**>(ptr) - 1)); return; } }
ここまでの議論があれば、わりかしシンプルな実装に落ち着いたように思えるが、いきなりこれを見ると驚くかもしれない。
というわけでメモリ解放ができるようになったので、アロケーションの方をちゃんと実装しよう。アライメントされた領域を確保するには、パディングと、freeするためのvoid*分だけ大きな領域を取らなければならない。さて、min_alignだが、mallocはany scalar typeに対して正しくアラインされたものを返すらしいので、void*のためのアライメントは保証される。以降もvoid*は使うので、これを保証されたアライメントの値ということにしよう。
void* aligned_alloc(std::size_t req_align, std::size_t size) { constexpr std::size_t min_align = alignof(void*); const auto offset = req_align - min_align + sizeof(void*); void* const ptr = std::malloc(size + offset); // ... }
この領域からstd::alignを使ってアライメント要求に合う領域を取り出すのだが、その前に、最低限void*を格納できる領域を先に確保しておく必要がある。
void* aligned_alloc(std::size_t req_align, std::size_t size) { // ... void* const ptr = std::malloc(size + offset); // void* 1つ分後ろにずらす void* aligned_ptr = reinterpret_cast<void*>( reinterpret_cast<void**>(ptr) + 1); std::size_t space = size + offset - sizeof(void*); // アライメント要求に合う領域を探す std::align(req_align, size, aligned_ptr, space); // ... }
この時点でaligned_ptrの値が欲していた領域の先頭を指すポインタになっている。なので、忘れずその一つ前に本当の先頭ポインタをメモしておいて、完了だ。
void* aligned_alloc(std::size_t req_align, std::size_t size) { // ... void* const ptr = std::malloc(size + offset); // ... std::align(req_align, size, aligned_ptr, space); // aligned_ptrの直前にメモしておく *(reinterpret_cast<void**>(aligned_ptr) - 1) = ptr; return aligned_ptr; }
こっちはまあ、想像通りの複雑さになった。加えて、本当はここに「req_alignがmin_alignと同じかそれより小さい場合」の対応を入れる必要がある。それは普通にmalloc使えよって話で、assertすればよくね？ と思ったが、using aligned_vector = std::vector<T, aligned_allocator<T, alignof(T)>>;みたいな使い方する時は普通にあり得るんだよな……。
Result
valgrindでリークチェックとかしたけど大丈夫そうでした、まる。
Conclusion
std::alignとstd::mallocでaligned_alloc作ろうとすると超絶面倒くさいから、環境依存の関数をマクロで使いわけましょう。
