Javaはできる子です

Javaと聞くと、遅くね？と拒否反応を示す人は多いはず。就職して以降、弊社の戦略的事情から（本当だろうか）もっぱらプログラムはJavaで書いています。Javaは適当に遊んでいた程度でしたが、だいぶ慣れてきました。チューニング的な意味で。最近、大規模データや構造化データを扱うことが増えたので、ちょっと気を抜くと動かなくなります。同じインターフェースで5回くらい実装し直すのはざらです。

さて、Javaはインタプリタだから遅いと思われがちですが、本当でしょうか。最近の経験を鑑みるに、JIT最適化はかなりがんばっているという印象を受けます。経験的に（CPU実験の）、もっとも効く最適化の一つはインライン展開（とそれに伴う定数伝搬など）なんですが、そちらは実はだいぶがんばっているように思います。遅い原因は、そこではなくてメモリ馬鹿食いから来るキャッシュミスと、それに伴う速度低下が原因の用に思います。Javaは仕様上（たしか）オブジェクトやら配列やら、何を作るにも余計にメモリを食います。Arrayなんて最悪にメモリ食うので、絶対にvectorに勝てません。可変長配列を自作することをお勧めします。HashMapもひどいことになるので、byte[]を作って2分探索をお勧めします。しかし、一方でJITでしかできない最適化もあるので、それを検証。テーマは仮想関数。

仮想関数は一般にはインライン展開できません。当然です。実行時まで呼ばれる関数がわからないから。C++では、手続きを抽象化して、かつ速度も出したいときはtemplateと関数オブジェクトを使うのが常套手段になっていますが、これは非常に生産性を落とします。一方のJavaはどうでしょう。Javaの最適化は実行時にかかるので、原理的には呼ばれる関数が途中でわかればインライン展開できるはずです。本当に速くなるのか試してみました。

public class InlineTest {
  
  private static interface I {
    public int f(int x);
  }

  private static class F implements I {
    public int f(int x) {
      return x * 2;
    }
  }

  public static void main(String[] args) {
    {
      long begin = System.currentTimeMillis();
      
      I f = new F();
      int n = 0;
      for (int j = 0; j < 10000;j++)
        for (int i = 0; i < 100000; i++)
          n += f.f(i);

      long end = System.currentTimeMillis();
      System.out.println((double)(end - begin) / 1000 + " sec: " + n);
    }

    {
      long begin = System.currentTimeMillis();
      
      F f = new F();
      int n = 0;
      for (int j = 0; j < 10000;j++)
        for (int i = 0; i < 100000; i++)
          n += f.f(i);

      long end = System.currentTimeMillis();
      System.out.println((double)(end - begin) / 1000 + " sec: " + n);
    }


    {
      long begin = System.currentTimeMillis();
      int n = 0;
      for (int j = 0; j < 10000;j++)
        for (int i = 0; i < 100000; i++)
          n += i * 2; 
      
      long end = System.currentTimeMillis();
      System.out.println((double)(end - begin) / 1000 + " sec: " + n);
    }

  }
}

#include <iostream>
#include <time.h>

using namespace std;

class I {
public:
  virtual int f(int x);
};

class F : public I {
public:
  int f(int x) { return x * 2; }
};

int main() {
  {
    double begin = (double)clock() / CLOCKS_PER_SEC;
    I *f = new F();
    int n = 0;
    for (int j = 0; j < 10000;j++)
      for (int i = 0; i < 100000; i++)
        n += f->f(i);

    double end = (double)clock() / CLOCKS_PER_SEC;
    cout << end - begin << " sec: " << n  << endl;
  }

  {
    double begin = (double)clock() / CLOCKS_PER_SEC;
    F *f = new F();
    int n = 0;
    for (int j = 0; j < 10000;j++)
      for (int i = 0; i < 100000; i++)
        n += f->f(i);

    double end = (double)clock() / CLOCKS_PER_SEC;
    cout << end - begin << " sec: " << n  << endl;
  }
  
  {
    double begin = (double)clock() / CLOCKS_PER_SEC;
    I *f = new F();
    int n = 0;
    for (int j = 0; j < 10000;j++)
      for (int i = 0; i < 100000; i++)
        n += i * 2;

    double end = (double)clock() / CLOCKS_PER_SEC;
    cout << end - begin << " sec: " << n  << endl;
  }

  {
    double begin = (double)clock() / CLOCKS_PER_SEC;
    int n = 0;
    for (int j = 0; j < 10000;j++)
      for (int i = 0; i < 100000; i++)
        n += F().f(i);

    double end = (double)clock() / CLOCKS_PER_SEC;
    cout << end - begin << " sec: " << n  << endl;
  }
}

実行結果

% javac InilieTest.java
% java InlineTest
1.578 sec: -723552768
1.078 sec: -723552768
1.078 sec: -723552768
% g++ -O2 inlinetest.cc
% ./a
5.75 sec: -723552768
5.75 sec: -723552768
0.531 sec: -723552768
0.532 sec: -723552768

やったことは単純で、親クラスI, 子クラスFとして、1番上が型Iで関数呼び出し、2番目が型Fで関数呼び出し、3番目が手動展開、C++だけ4番目が値渡し。手動展開で比べるとC++が2倍速ですが、関数呼び出しにするとC++よりJavaの方が断然速くなります！　この速度差を考えるとJITでインライン展開していると予想できます。ちょっとおもしろいのが、型Fで呼び出してもC++は速くなりません。ポインタで呼び出しているので、実際の型が何なのかわからないためでしょう。値で呼べばインライン展開されます。逆に、Javaなら型をちゃんと指定すればインライン展開されることがよくわかります。ところで、親クラス指定だと微妙にパフォーマンスが劣る（といっても、足し算1回分の半分くらいですが）のは気になります。なんか、実行型のチェックとかの分岐でも入ってるんじゃないかなぁ、とか邪推しますがどういうバイナリを生成しているのか気になりますね。