Java7 で ArrayList の foreach が速くなった理由を調べてみました。

Java7でList/TreeMap/TreeSetのIteratorがかなり早くなって、
ArrayListのforeach文（拡張for文）も、普通のfor文より早くなりました。

コレクションの細かい話、だが面白い！ - 谷本 心 in せろ部屋

そうなんですか！？
…と思って試してみたところ、ArrayList の foreach文（拡張for文）が Java6 → Java7 で約2.5倍速くなっていました。
手元の環境では、普通の for 文より速くなることはなかったものの、ほとんど気になならないぐらいの差でした。

• • • -

2011年11月26日 訂正：
速くなっていたのは ClientVM で実行した場合のみで、ServerVM では変わっていませんでした。
詳しくは、Javaの実行速度を調べるなら、ClientVM/SeverVM の違いを考慮しておくべきでした。 - 地平線に行く をご覧ください。

• • • -

速くなった理由

何が変わったんだろう？ ということで、APIのソースコードを確認してみたところ、Java7 で ArrayList の Iterator がリファクタリングされていました。

Java6 の場合、ArrayList は Iterator を実装せず、AbstractList の汎用的な実装を使用していました。
この AbstractList の実装は、 各要素を get(int) で取得して、その時に発生する例外を try-catch で捕まえて、Iterator 用の例外に変換するようになっていました。

// Java6, AbstractList - 342行目〜
public E next() {
    checkForComodification();
    try {
        E next = get(cursor);
        lastRet = cursor++;
        return next;
    } catch (IndexOutOfBoundsException e) {
        checkForComodification();
        throw new NoSuchElementException();
    }
}

一方、Java7 では、ArrayList が AbstractList の Iterator をオーバーライドしていました。
そして、このオーバーライドした Iterator では、get(int) を使用せず、直接チェックと例外のスローを行うようになっていました。

// Java7, ArrayList - 790行目〜
@SuppressWarnings("unchecked")
public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

この差、つまり try-catch を使用しなくなったことが、スピードアップの秘訣のようです。
試しに、Java6 のソースから try-catch を抜いてみると*1、for文でアクセスした場合と同じ速度になりました。

try-catch を使ったからといってものすごく遅くなるわけではないと思いますが、やはりループの中で何度も出たり入ったりを繰り返すとそれなりに影響が出てしまうようです。

実験

ArrayList(要素10,000個) × 1,000回ループで試してみました。*2 *3。

• foreach でループ
  • Java6 : 339ms
  • Java7 : 133ms
• for と List.get(i) でループ
  • Java6 : 194ms
  • Java7 : 116ms

これなら、foreach(String str : list) と安心して書けます。

テストプログラム

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import org.junit.BeforeClass;
import org.junit.Test;

public class SpeedTest {
    private static List<String> list;
    
    @BeforeClass
    public static void beforeClass(){
        Random random = new Random();
        
        list = new ArrayList<String>();
        for(int i = 0; i < 10000; i++){
            list.add(Integer.toString(random.nextInt()));
        }
    }
    
    @Test
    public void listForeachTest(){
        long start = System.nanoTime();
        
        for(int i = 0; i < 1000; i++){
            for(String str : list){
                str.isEmpty();
            }
        }
        
        long end = System.nanoTime();
        System.out.println("List & foreach : " + ((end - start) / 1000000.0) + "ms");
    }
    
    @Test
    public void listForTest(){
        long start = System.nanoTime();
        
        for(int i = 0; i < 1000; i++){
            for(int j = 0; j < list.size(); j++){
                list.get(j).isEmpty();
            }
        }
        
        long end = System.nanoTime();
        System.out.println("List & for : " + ((end - start) / 1000000.0) + "ms");
    }
}

*1:当然、バグった実装なので使い物にはならないですが…

*2:バージョンは Java1.6.0 Update29 と Java1.7.0。PCスペックは、Core i7 920(2.67MHz)、メモリ3GBです。

*3:テストプログラムは「続きを読む」に記載しています