ListよりArrayListのほうが速いって本当？

結論：どちらも同じなので意味的に適切だと思う方を使ってよい

発端は以下のツイートだ。

たしかに、公式ドキュメントには以下のように書いてある。

On devices without a JIT, it is true that invoking methods via a variable with an exact type rather than an interface is slightly more efficient. (So, for example, it was cheaper to invoke methods on a HashMap map than a Map map, even though in both cases the map was a HashMap.) It was not the case that this was 2x slower; the actual difference was more like 6% slower. Furthermore, the JIT makes the two effectively indistinguishable.

JITのないデバイスでは、変数の型がインターフェイスではなく正確な型の場合、少し速いとある。しかし、Android 2.2よりDalvik VMにはJITが搭載されており、それを踏まえて読むと、現状はインターフェイス型でも十分に速いと書いているように読める。次のセクションのタイトルは「Always Measure」だし、気になったので測ってみた。

com.example.app.MainActivity

    private void startBenchmark() {
        final List<String> list = new ArrayList<>();
        final ArrayList<String> arrayList = new ArrayList<>();

        for (int i = 0; i < 100; ++i) {
            list.add(String.valueOf(i));
            arrayList.add(String.valueOf(i));
        }

        long t0 = System.currentTimeMillis();

        int sum = 0;
        for (int x = 0; x < 100000; ++x) {
            for (int i = 0; i < list.size(); ++i) {
                sum += list.get(i).length();

            }
        }

        final long t1 = (System.currentTimeMillis() - t0);

        t0 = System.currentTimeMillis();

        sum = 0;
        for (int x = 0; x < 100000; ++x) {
            for (int i = 0; i < arrayList.size(); ++i) {
                sum += arrayList.get(i).length();
            }
        }

        final long t2 = (System.currentTimeMillis() - t0);

        final TextView textView = (TextView) findViewById(R.id.textView);
        textView.setText(textView.getText() + String.format("List<T>: %dms, ArrayList<T>+ %dms\n", t1, t2));
    }

結果は以下のとおりで、変わらないように見える。

Android 4.2.2, Xperia A:

Android 4.4.2 ART, Nexus 4:

一般論として、メソッド呼び出しをコンパイル時に解決できる場合、インライン展開したりメソッドディスパッチをスキップする最適化を行う可能性がある*1。しかし、JITのある仮想マシンだと必ずしもそうでもないし、実際最近のDalvikVMは静的型にかかわらずきちんと最適化してくれるので、これは気にしなくてよさそうだ。

なおJITが絡む場合、正しくベンチマークを取るのは非常に難しい。このコードも絶対に正確かどうかは保証しない。ソースコードは以下にあるので、気になるなら追試してみてほしい。

• https://github.com/gfx/Android-ListBench

*1:実際JSXではそういう最適化をするし、C++でも仮想関数テーブルを介さないようにコードで工夫したりする。