memorandums

日々の生活で問題解決したこと、知ってよかったことなどを自分が思い出すために記録しています。

2重ループの内外の入れ替えによるチューニング効果

授業資料を作るのにコードコンプリートの下巻のコードチューニングテクニック(第26章)を読んでいました。

CODE COMPLETE 第2版 下 完全なプログラミングを目指して

CODE COMPLETE 第2版 下 完全なプログラミングを目指して

富豪的プログラミングと対極ではありますが、モバイルデバイスや組み込み機器など、リソースや電力消費が話題になることがまだまだある世界ですので、知っておく価値はあるとは思います。

さて、この書籍の196ページに「26.2.6 最もビジーなループを内側に」という節がありまして、要は多重ループで処理する場合で、その繰り返し回数に大きな差がある場合に、どちらを外側、あるいは内側にするか?というチューニングになります。

チューニングが必要なコードとして以下が例として挙げられています。内側のループは5回繰り返し、そのループを100回繰り返します。for文では、それぞれカウンター変数(columnやrow)が指定された値を越えるかどうかの検査が行われ、さらに変数の値をインクリメントする命令も実行されます。ループ回数が多くなればなるほど、それら処理の回数が多くなります。

つまり、外100内5のパターンではfor文の処理が600回行われることになり、外5内100では505回に減らすことができるます。

■外100内5

for ( column = 0; column < 100; column++) {
  for ( row = 0; row < 5; row++ ) {
    sum = sum + table [ row ][ column ];
  }
}

■外5内100

for ( column = 0; column < 5; column++) {
  for ( row = 0; row < 100; row++ ) {
    sum = sum + table [ column ][ row ];
  }
}

この本では、計測結果も示されておりまして、具体的には以下のような表が掲載されていました。

言語 チューニング前 チューニング後 改善度
C++ 4.75 3.19 33%
Java 5.39 3.56 34%
PHP 4.16 3.65 12%
Python 3.48 3.33 4%

なかなかの差ですね。。。

で、実際に私の環境でも試してみました。

まず、Java。ほぼ上記のサンプルと同じですね。timeコマンドで計測したので差がわかるように1000000回繰り返して合計の処理時間をみました。

■外100内5

class Test {
  public static void main(String [] args) {
    int[][] table = new int [100][5];

    for (int times = 0; times < 1000000; times++) {
      int sum = 0;
      for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 5; j++) {
          sum = sum + table[i][j];
        }
      }
    }
  }
}

結果は以下です。傾向は同じでしたが、改善度が違いますね。。。なぜかなぁ?Javaのバージョンがあがって最適化されるようになったのか?

ちなみに表内の数値(改善度以外)の単位は秒です。

言語 チューニング前 チューニング後 改善度
Java1.8.0_91 0.63 0.52 17%

続いてRuby(2.3.1p112)も試してみました。ちなみにRubyのBenchmarkライブラリを使うべきと思いますがJavaにはないので測定方法を揃えるために使っていません。

■外100内5

table = Array.new(100){ Array.new(5,1) }

10000.times do
  sum = 0
  for i in 0..99 do
    for j in 0..4 do
      sum = sum + table[i][j]
    end
  end
end

結果は以下です。Rubyには繰り返しの書き方がいろいろあるので、ついでにその比較もしてみました。チューニングによる効果の傾向はコードコンプリートと同様ですね。改善率も

実装方法 チューニング前 チューニング後 改善度
for 5.30 4.38 17%
upto 4.99 3.95 21%
each 5.01 4.03 20%

Rubyはもちろんのこと、Java関数型プログラミングの機能が導入されて、ループで処理を実装する機会が減ってきたとは思いますが。。。一応、今でも使えるテクニックと言えると思います。