val it: α → α = fun

会社で勧められて “Producing wrong data without doing anything obviously wrong!” というタイトルの論文を読んでみたら面白かったので紹介したいと思います。ASPLOSという学会で半年ぐらい前(2009年3月)に発表された論文です。

コンピュータシステムにおける測定バイアスとは

論文の主旨は簡単にいうと「測定バイアスによって様々な処理や最適化の影響は(予想以上に大きな)影響を受ける」というものです。測定バイアスというのは「調査すべき変数に対して、対象者を不正確に測定(または分類)することによる系統的な誤差」です(例えばこちらなど)。医学方面でよく見られる考え方ですが、別に医学分野に限っただけの話ではありません。

たとえばある種の処理系に対して、ある種の最適化をほどこすという提案をしたいとしましょう。通常、元の処理系と最適化をほどこしたあとの処理系を両方用意して、何らかの決められた処理を実行させてみてパフォーマンスを比べるということが行われます。とはいっても比較はそう簡単ではなく、場合によっては測定に偏りが生まれることがあるのです。

もちろん、大抵のまともな論文は何回も同じテストを繰り返して平均や中央値をとったり、といったようにしてバイアスを避けようとしています。ところが、そんなレベルではないところから測定バイアスが生まれることがあるというのがこの論文の主張です。

論文で例として挙げられているのが環境変数とリンクの順序です。

環境変数なんてなんの影響もない、という気がするのですが、環境変数は実際には実行時にメモリの特定の領域にロードされます。とすると、環境変数のサイズが変化することでスタックのレイアウトが変わりますから、パフォーマンスが変わることがあるはずです。著者の非常に単純なプログラムで測定したところ、30%ぐらいの変化があるというのです。同じように、リンクする順序が変われば関数のメモリ上の配置も変化するため、パフォーマンスが変わります。こうした変化は実は意外と大きく、結果として誤った結論を導く危険があるようです。

しかも、こうした変化は予測不能だというより大きな問題があります。環境変数の長さがどのように影響するかというのは一見してわかるものではなく、リンク順序もどういう順序がいいのかはハードウェアにも依存するので簡単に決められるものではありません。つまり、「こうすれば測定バイアスを避けられる」という万能の環境はないということです。

ほかにも著者は様々な条件を検討しています。たとえばこういう問題がgccに特有なのかを検討するためにiccでも同様の比較を行い、大差ない結果を得ているので、コンパイラによってあったりなかったりするタイプのバイアスではないようだ、とか。詳しくは論文を読んでみてください。

実際にやってみた

非常に印象深い話だったので少し試してみました。

次のようなコードを用意します。これは論文に掲載されているサンプルコードとほぼ同一です。パフォーマンス計測のために、ごく単純にclock()を使うことにしました(実際にはさらに少し手を加えています。clock()はわりと失敗することがあり、失敗すると-1が返されるのでそのための対処コードを差し込むというものです)。

static int i = 0, j = 0, k = 0;

int main(void) {
  clock_t s = clock();
  int g = 0, inc = 1;
  for (; g < 65536; g++) {
    i += inc;
    j += inc;
    k += inc;
  }
  printf("%d\n", clock() - s);
  return 0;
}

非常に単純な繰り返しのプログラムです。論文の著者はこれですら環境変数によって結果が変化することを指摘しています。

これをつぎのようなスクリプトで実行させてみました。

ENV.clear
clocks = {}
15.times do |unused|
  (1..400).map{|i| i * 10}.shuffle.each do |env_size|
    ENV['x'] = 'x' * env_size
    while true do
      clock = `a.out`.to_i
      if clock > 0
        clocks[env_size] = [] unless clocks.has_key?(env_size)
        clocks[env_size].push(clock)
        break
      end
    end
  end
end
clocks.to_a.sort.each do |env_size, cs|
  puts [env_size, cs.inject(&:+)].join(" ")
end

手元のMacBookでgcc -O0 でコンパイルしましたが、確かに差が見られました。

横軸は環境変数のサイズ、縦軸は実行時間です。画像が小さいのでわかりにくいですが、300のあたりと400のあたりというふうに2つのグループができたのがわかると思います。非常にいい加減な環境で計測したので(BGMで音楽を流しながらとかそういうレベル)この結果は正直なところぜんぜん信頼していないのですが、何度か試行したところ、結果はそこそこ安定的でした(細かい数値は変わるが、どのサイズのところで400あたりのグループになるかは変わらない)。

また、予測が正しいならスタックのアドレスが変われば結果は変わるはずです。そこでmainのかわりにfuncという名前の関数にしてmainはfuncを呼ぶだけの単純なwrapperにしたところ、ちゃんとどのサイズで実行時間が伸びるかというのが変化しました。ほかにもいろいろやったんですが飽きたのでこの辺で。どうせ厳密な環境でもないし……。

まとめ

なかなか面白い論文なのですが、こういう話を聞きかじって「環境変数って大事なんだなあ」などと理解するのはまるっきり間違っているので注意してください。環境変数はただの例であって、実際ほかにも影響を及ぼすであろうものというのはいくらでもあるだろうと著者は主張しています。たとえば、室温とか。

測定バイアスというのは、実験群と対照群を同じ実験条件で実験していないときに起こる問題ですが、コンピュータシステムにおいて本当に「同じ実験条件」というのをどう揃えたらいいかなんてわからん、というのが問題の根幹ではないかと思います。

けっきょく、いろんなベンチマークをたくさん試すとか、実験環境をランダムに構築するとかして測定バイアスの影響を弱めることしかできない、と著者の人達は書いています。でもリンクの順序が違うとかは実験するのがいかにも大変そうですなあ。