Java と JIT と Iterable と RandomAccess

タイトルがいい加減である。いまさらだが、Tiger というと generics というイメージが強かったせいで、foreach が使えるようになったことを忘れていたのだが、これが便利。便利というか、ループさせるのに変数がいるというのは正直ださい。仕組みとしては、Iterable インターフェースに iterator メソッドがあって、foreach 構文をかくといわゆる Iterator を使った for 文として解釈される寸法。

すると気になるのは、というかいろいろなところでかかれているのが、RandomAccess な Collection は iterator ループよりインデックスで get した方が速いよということらしい。C++ なら実質ただの ++ になって同等の速度だと思われるので、その辺 JIT どうなってるのよと言うのが気にかかるところ。いかんせん、未だに JIT コンパイラに信用がおけない。

だらだらソースをみせるほどのものでもないんですけど。単に Vector と Integer と int で、全部にアクセスするような処理書いただけ。

import java.util.Vector;

public class VecTest {
    static final int SIZE = 1000000;
    static final int N = 100;
    public static void main(String args) {
	Vector v = new Vector();
	for (int i = 0; i < SIZE; i++)
	    v.add(i);

	long t = System.currentTimeMillis();
	int sum = 0;
	for (int j = 0; j < N; j++)
	    for (int i = 0, s= v.size(); i < s; i++)
		sum += v.get(i);
	long e = System.currentTimeMillis();
	System.out.println("Random access: " + (e-t) + " ms");
	
	t = System.currentTimeMillis();
	for (int j = 0; j < N; j++)
	    for (int x: v)
		sum += x;
	e = System.currentTimeMillis();
	System.out.println("Iterative access: " + (e-t) + " ms");

	Integer a = new Integer[SIZE];
	for (int i = 0; i < a.length; i++)
	    a[i] = new Integer(i);

	t = System.currentTimeMillis();
	for (int j = 0; j < N; j++)
	    for (int i = 0; i < a.length; i++)
		sum += a[i];
	e = System.currentTimeMillis();
	System.out.println("Random access (Object Array): " + (e-t) + " ms");
	t = System.currentTimeMillis();
	for (int j = 0; j < N; j++)
	    for (int x: a)
		sum += x;
	e = System.currentTimeMillis();
	System.out.println("Iterative access (Object Array): " + (e-t) + " ms");

	int[] b = new int[SIZE];
	for (int i = 0; i < b.length; i++)
	    b[i] = i;
	
	t = System.currentTimeMillis();
	for (int j = 0; j < N; j++)
	    for (int i = 0; i < b.length; i++)
		sum += b[i];
	e = System.currentTimeMillis();
	System.out.println("Random access (Array): " + (e-t) + " ms");
	t = System.currentTimeMillis();
	for (int j = 0; j < N; j++)
	    for (int x: b)
		sum += x;
	e = System.currentTimeMillis();
	System.out.println("Iterative access (Array): " + (e-t) + " ms");
    }
}

はい。実行結果。

Random access: 5747 ms
Iterative access: 9108 ms
Random access (Object Array): 1580 ms
Iterative access (Object Array): 1515 ms
Random access (Array): 280 ms
Iterative access (Array): 281 ms

Iterator 使ってせいぜい２倍ですね。これを見て２倍も遅いのか、使うのやめよと考えるのは早計。これが内積計算のようにループの中が関数呼び出しに比べて、メモリアクセスに比べて、ものすごく軽い処理ならいざ知らず、たかが get 呼び出すよりはるかに重いのが普通。ループコストはふつう無視できる。JIT でがんばれないのかと思うが、うーむ。
逆に内積計算やベクトル加算みたいなのをするなら、ループコストが大半になってしまうのでそのまま２倍時間かかるよと。むしろ気になるのは、配列で３倍、int にするとさらに６倍速なところ。これって、JIT 効いてないんじゃ・・・。この手の JIT が効いてくれないと安心して眠れない。配列に対する foreach は速度差ないみたいですね。

ちなみに、C++ と比較。

#include 
#include 
#include 

using namespace std;

int main()
{
  const int N = 100;
  vector v;
  for (int i = 0; i < 1000000; i++)
    v.push_back(i);
  boost::timer t;
  int sum = 0;
  for (int j=0;j

実行

80 ms

こうしてみると Java の配列はがんばっている方なのかもしれない。多分、配列境界チェックなどがいちいち入っていると想像できるので（確認してないけど）。