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

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

作者: スティーブマコネル,Steve McConnell,クイープ
出版社/メーカー: 日経BP社
発売日: 2005/03/26
メディア: 単行本
購入: 16人クリック: 193回
この商品を含むブログ (164件) を見る

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

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

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

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

■外１００内５

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

■外５内１００

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回繰り返して合計の処理時間をみました。

■外１００内５

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にはないので測定方法を揃えるために使っていません。

■外１００内５

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