副作用はあるが連続で呼んでも結果が変わらない関数の最適化

はじめに

コンパイラの最適化機能が、どこまで何を見抜くかに興味がある。特に、あるコンパイラができて、他のコンパイラができなかったりすることが見つかると楽しい。またそういうのを見つけたのでメモ。

コード

数字のペアが二つの配列a_i, a_jで表現されている。このペアの、値が小さい方をa_iに、大きい方をa_jに揃えたい。

単純に書けばこんな感じになろう。Kがペアの数。

void
naive(void){
  for(int k=0;k<P;k++){
    int i = a_i[k];
    int j = a_j[k];
    if(j>i){
      a_i[k] = j;
      a_j[k] = i;
    }
  }
}

これを最適化したり、アセンブラみたりしようと思ったが、一発だけだと時間測定があれかな、と思って100回呼ぶことにした。また、上記はインプレイスで書き換えているが、諸事情で二つ配列を用意した方が良いかと思い、入れ替え前と入れ替え後の配列を用意することにした。最終的にこういうコードになった。

test.cpp

//------------------------------------------------------------------------
#include <iostream>
#include <random>
#include <chrono>
const int N =  120000;
const int P = 8000000;
int a_i[P];
int a_j[P];
int a_i2[P];
int a_j2[P];
//------------------------------------------------------------------------
void
naive(void){
  for(int k=0;k<P;k++){
    int i = a_i2[k];
    int j = a_j2[k];
    if(j>i){
      a_i[k] = j;
      a_j[k] = i;
    }else{
      a_i[k] = i;
      a_j[k] = j;
    }
  }
}
//------------------------------------------------------------------------
int
main(void){
  static std::mt19937 mt(1);
  std::uniform_int_distribution<> ud(0, N-1);
  for(int k=0;k<P;k++){
    a_i2[k] = ud(mt);
    a_j2[k] = ud(mt);
  }
  auto start = std::chrono::system_clock::now();
  for(int i=0;i<100;i++){// ★インテルコンパイラがこのループを削除する
    naive();
  }
  auto end = std::chrono::system_clock::now();
  std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() << "[ms]" << std::endl;
}
//------------------------------------------------------------------------

0からN-1までの乱数を発生させ、a_i2とa_j2に入れて、その小さい方をa_iに、大きい方をa_jにいれましょう、という単純なコードである。これを実行すると、えらく実行時間が短い。

$ icpc -std=c++11 -O3 -xHOST test.cpp -o a.out
$ ./a.out
21[ms]

いや、いくらなんでも21[ms]はないだろ、と思ってコンパイラが吐いたアセンブリを見てみたら、100回ループするところ(★つけたところ)がバサッと落とされてしまっていた。すなわち「連続で実行されるかぎり、関数naiveは二度目以降は実行しなくても良い」とインテルコンパイラが見抜いたことになる。

同様なコードを、g++ 4.8.5, 5.1.0, clang++ 7.0.2, 8.0.0に食わせたが、こいつらはこのループを落とせると見抜くことができなかった。

どこまでいけるか

さて、関数naiveはグローバル変数を触っているので副作用はあるが、二度目以降結果が変わらないためにループが無視されてしまった。では、本質を変えずにいろいろ付け加えた時にコンパイラがどこまでがんばるか見てみる。

さっきの関数にstaticなカウンタをつけてみる。

void
naive(void){
  static int count = 0;
  count++;
  for(int k=0;k<P;k++){
    int i = a_i2[k];
    int j = a_j2[k];
    if(j>i){
      a_i[k] = j;
      a_j[k] = i;
    }else{
      a_i[k] = i;
      a_j[k] = j;
    }
  }
}

プログラムはこの他ではcountは参照していないので原理的にはループは落とせるのだが、インテルコンパイラはこの場合はループを落とさなかった。

インプレイスでやる

もともとのコードは、a_i2、a_j2という配列から、a_i、a_jという配列へのコピーだった。従って、次に呼ばれる時までのa_i2やa_j2が変更されていないことがわかればループを落とせる。では、インプレイスでやった場合はどうか？

test2.cpp

//------------------------------------------------------------------------
#include <iostream>
#include <random>
#include <chrono>
const int N =  120000;
const int P = 8000000;
int a_i[P];
int a_j[P];
//------------------------------------------------------------------------
void
naive(void){
  for(int k=0;k<P;k++){
    int i = a_i[k];
    int j = a_j[k];
    if(j>i){
      a_i[k] = j;
      a_j[k] = i;
    }
  }
}
//------------------------------------------------------------------------
int
main(void){
  static std::mt19937 mt(1);
  std::uniform_int_distribution<> ud(0, N-1);
  for(int k=0;k<P;k++){
    a_i[k] = ud(mt);
    a_j[k] = ud(mt);
  }
  auto start = std::chrono::system_clock::now();
  for(int i=0;i<100;i++){ //←落とせない
    naive();
  }
  auto end = std::chrono::system_clock::now();
  std::cerr << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() << "[ms]" << std::endl;
}
//------------------------------------------------------------------------

インテルコンパイラはこの場合も落とせない。ループの中で読み込み元となる領域と書き込み先となる領域が重なっており、実行の度に変更がある可能性を排除できないからだろう。もちろん、処理内容まで理解できればループは落とせることがわかるのだが、そこまでは理解できていない。

余計な処理をいれる

明らかに副作用が無いとわかるが、余計な処理が入るとどうなるか。たとえば無駄に(使われない)std::vectorを宣言してみる。

void
naive(void){
  std::vector<int> v;
  for(int k=0;k<P;k++){
    int i = a_i2[k];
    int j = a_j2[k];
    if(i<j){
      a_i[k] = j;
      a_j[k] = i;
    }else{
      a_i[k] = i;
      a_j[k] = j;
    }
  }

先程のstaticなカウンタと異なり、こちらはstatic宣言していないし、このvectorはどこにも使われていないので消せるはずなのだが、インテルコンパイラはこれを消さない。逆に、g++やclang++はループを消さない代わり、このvector宣言は消す。

これ、関数のインライン展開と関数内部の最適化の順序の違いかと思ったが、上記の関数を単体でコンパイルした場合もGCC/clangはvectorを消すが、インテルコンパイラは消さない。そのへんのポリシーはよくわからない。

まとめ

一般にグローバル変数が絡む最適化は面倒くさい。最低でもファイルスコープ全体に気を配らないといけなくなるため、大域最適化が必要になる。なので、多くのコンパイラはグローバル変数が絡むと最適化をあきらめてしまうのだが、なんかインテルコンパイラは伝統的にグローバル変数がからむ処理の最適化を積極的に行う気がする。

今回、対象となった関数はグローバル変数を触るから副作用は確実にあるはずだが「連続で呼んでも結果が変わらない」と看破したインテルコンパイラはたいしたものだと思う。たぶんこういう最適化は関数単位ではなくて、関数をインライン展開してから、一番外側のループに対して「やらなくて良い」と判断したのだと思われるが、それにしたってすごいなぁ、と思った(小並感)。