std::pairをmemcpyすることについて

g++-8で追加された-Wclass-memaccessの警告を有効にしている場合、以下のコードはコンパイル時に警告が出ます。-Wclass-memaccessの警告は、-Wallに含まれるため、単にコンパイラをg++-8に変更しただけでこの警告に出くわすこともあると思います。

#include <utility>
#include <cstring>

std::pair<double, double> p, q;

int main() {
    ::memcpy(&q,&p,sizeof q);
}

これは、どのような警告かというと、「std::pair<T, U>には非自明なコピー代入演算子がある。本当にmemcpyでバイト列をコピーするだけで大丈夫?」という警告です。

ここで、非自明なコピー代入演算子とは、何も書かなかった時の自動定義と= defaultでの定義を除く、ソースコード中に明示的に書かれたコピー代入演算子のことです。

普通に考えるとstd::pair<T, U>のコピー代入演算子は非自明なことをするはずはないのですが、定義されているので仕方がないです。

以下、TUはPlain Old Data (POD)であることを前提として話を進めます。

LLVMコンパイルするとこの警告が出た

どうもg++-8でLLVMコンパイルするとこの警告が出ます。 LLVMC++で書かれており、コンパイル速度が速いことを売りにしているようですが、スピード狂がいるのでしょうか。

警告メッセージによれば、llvm::SmallVector<T, N>Tとしてstd::pairを使ったことが原因のようです。llvm::SmallVector<T, N>TがPODのようなものである場合、具体的にはllvm::isPodLike<T>::valuetrueの時、特殊化されており、memcpyを使った高速実装を用いるようです。

問題のllvm::isPodLike<T>ですが、大体以下のような感じに定義されています。

template<typename T>
struct isPodLike {
  static const bool value = std::is_trivially_copyable<T>::value;
};

llvm/type_traits.h at 425788d8b599aef1e77092228423e0bb641df359 · llvm-mirror/llvm · GitHub

これならばmemcpyを用いても問題は発生しそうにありません。しかし、その下に定義されている特殊化がまずいです。

// std::pair's are pod-like if their elements are. 
template<typename T, typename U> 
struct isPodLike<std::pair<T, U>> { 
  static const bool value = isPodLike<T>::value && isPodLike<U>::value; 
}; 

ちなみに、現在LLVMをg++-8でコンパイルしてもこの警告は出なくなっています。どうやって解決したのかというと、

Fix few g++ 8 warning with non obvious copy object operations · llvm-mirror/llvm@425788d · GitHub

reinterpret_cast<void*>を使って、単に警告を黙らせるという姑息な解決法だったようです。

正しい方法

正しい方法は、以下の二通りです。

1 自明にコピー可能なstruct Pair<T, U>を自分で定義する。

2 std::copyなどを用いてコピーする。

1 の方法を使う場合、std::pairとの互換性のため、std::pair<T1, U1>からの変換コンストラクタ等を定義した方が良いでしょう。= defaultによる定義を用いることで、自明にコピー可能であることと両立可能です。

2 の方法を使う場合、memcpyよりも遅くなってしまうという欠点があります。

std::copymemcpyよりおそいのか

現代の最適化コンパイラ、clang++やg++をもってしても、std::copymemcpyよりも遅いです(x86のように幅広なレジスタを持たないアーキテクチャなら互角になるかもしれません)。

memcpyを使った場合

memcpyを使った場合は限界までチューニングされた関数が呼び出されます。たぶん、一番幅広なレジスタ(私の環境では256bit幅のymmレジスタ)に乗っけてコピーしているのだと思われます。

std::copyを使った場合

以下はstd::pair<int, double>[10000000]std::copyするコードを、clang5.0.1で-O3コンパイルした時のアセンブリです。注意すべき点として、この構造体にはパディングが含まれているという点があげられます。パディングが含まれている構造体をmemcmpで比較するのはまずいですが、memcpyでコピーすること自体は問題ありません(実際はstd::pairは自明にコピー可能なわけではないのでこの議論は根本がまちがっているわけですが)。

.LBB0_3:
  mov eax, [rbx+src]
  mov [rbx+dst], eax
  mov rax, [rbx+src+8]
  mov [rbx+dst+8], rax
  mov eax, [rbx+src+16]
  mov [rbx+dst+16], eax
  mov rax, [rbx+src+24]
  mov [rbx+dst+24], rax
  mov eax, [rbx+src+32]
  mov [rbx+dst+32], eax
  mov rax, [rbx+src+40]
  mov [rbx+dst+40], rax
  mov eax, [rbx+src+48]
  mov [rbx+dst+48], eax
  mov rax, [rbx+src+56]
  mov [rbx+dst+56], rax
  mov eax, [rbx+src+64]
  mov [rbx+dst+64], eax
  mov rax, [rbx+src+72]
  mov [rbx+dst+72], rax
  lea rax, [r15+5]
  and r15, -2
  add rbx, 80
  cmp r15, 4
  mov r15, rax
  jne .LBB0_3

単に五倍ループアンローリングされること以外はごく普通のコードになっています。パディングのところに触らないようにeax(4Byteレジスタ)やrax(8Byteレジスタ)を使っているため、命令数がかさみ、コピーに時間がかかるようになってしまうようです。

パディングがあるのは意地悪な例のようにも思えますが、std::pair<double, double>のようなものの場合でも、movsd命令(16Byteレジスタの下半分だけ使う命令)を使っているため、結局コピーに時間がかかる点は同じです。

g++の場合はもう少し速いコードを生成するようですが、実行速度はmemcpyより有意に一割ほど遅かったです(wandboxを使ったためアセンブリは確認していません)。

おわりに

最適化はコンパイラに任せろと言われて久しいですが、現代のコンパイラをもってしてもstd::copyを自動でmemcpyに変換するような高級なことはできず、いまだにこの手の最適化はプログラマの責任の範囲となってしまっています。 一方で最近のコンパイラは想像を絶するような最適化も行うため、うっかり未定義挙動を踏まないようにするのも、最適化プログラマの責任となってしまっています。

現代のスピード狂プログラマは、速いコードを書くための知識だけではなく、言語仕様の熟知も必要条件となりつつあります。 コンパイラを黙らせるのではなく、コンパイラの有用な指摘をありがたく受け取れるようにしたいものです。

そもそも、今回の問題はstd::pairの設計に問題があることが原因のような気がしますが。