昨日は, 不思議な結果
昨日は
夜になって鳥乃が激しく嘔吐し、しまいには血の混じった胃液まで吐き出したので急遽近所の救急病院へ行きました。そこで吐き止めと失われた水分を補給するために点滴してもらっている間に鳥乃はすやすや眠ってしまい、0:00 過ぎに家に帰ってきました。
今日、かかりつけの病院に行って薬をもらってきたんですが、「今日一日は固形物は避けるように」と言われたのに早くもいつもの食い意地を発揮してヨーグルトやプリンをぱくぱく。元気になったのはいいけどちょっと心配だよ…。
不思議な結果
64bit 環境での性能向上率をいろいろ調べていた時のこと。
C で言う long long int、64bit 整数に関する演算速度を調べてみようと、下記のようなテストプログラムを作りました1。
#include <stdio.h>
int main()
{
long long int a, b, c, d;
int i;
a = b = c = d = 1;
for ( i=0; i<100000000; i++ )
{
a = d % 0xFFFFFFFFFFFFFFFLL;
b = a + a + 1LL;
c = b * 4LL;
d = c / 2LL;
}
printf("i:%d, a:%lld, b:%lld, c:%lld, d:%lld\n", i, a, b, c, d);
}
まず、このプログラムを今の僕の手元の環境でコンパイル、実行した時の結果は下記の通りとなりました2。
kazawa@tpx20:~$ uname -a
Linux tpx20 2.6.3 #1 Sat Mar 6 11:30:13 JST 2004 i686 unknown
kazawa@tpx20:~$ cat /proc/cpuinfo
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 8
model name : Pentium III (Coppermine)
stepping : 3
cpu MHz : 597.526
cache size : 256 KB
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 2
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 sep mtrr pge mca cmov pat pse36 mmx fxsr sse
bogomips : 1179.64
kazawa@tpx20:~$ gcc -v
Reading specs from /usr/lib/gcc-lib/i386-linux/2.95.4/specs
gcc version 2.95.4 20011002 (Debian prerelease)
kazawa@tpx20:~$ icc -V
Intel(R) C++ Compiler for 32-bit applications, Version 7.0 Build 20021021Z
Copyright (C) 1985-2002 Intel Corporation. All rights reserved.
FOR NON-COMMERCIAL USE ONLY
GNU ld version 2.12.90.0.1 20020307 Debian/GNU Linux
Supported emulations:
elf_i386
i386linux
/usr/lib/crt1.o: In function `_start':
/usr/lib/crt1.o(.text+0x18): undefined reference to `main'
kazawa@tpx20:~$ gcc -O3 -o multi_gcc multi.c
kazawa@tpx20:~$ time ./multi_gcc
i:100000000, a:436906, b:873813, c:3495252, d:1747626
real 0m19.619s
user 0m19.201s
sys 0m0.004s
kazawa@tpx20:~$ icc -O3 -mp1 -prec_div -fp_port -rcd -tpp6 -mcpu=pentiumpro -xiMK -o multi_icc multi.c
kazawa@tpx20:~$ time ./multi_icc
i:100000000, a:436906, b:873813, c:3495252, d:1747626
real 0m13.636s
user 0m13.346s
sys 0m0.003s
ここまでは、「ふむふむ、やっぱり Intel コンパイラの方が結構効率いいんだなぁ (最適化オプションが違い過ぎかも)」とか思いつつ普通に考えていました。
実際にはここでさらに 64bit バイナリを作ってテスト…という作業を行っていたのですが、その後戯れに、「Java だとどうだろう？」と思いつき、テストしてみることにしました。
まず、先程の C のプログラムとほぼ同じ内容の下記のようなプログラムを作成します。
public class multi {
public static void main(String[] args) throws Exception {
long a, b, c, d;
int i;
a = b = c = d = 1;
for (i = 0; i < 100000000; i++) {
a = d % 0xfffffffffffffffl;
b = a + a + 1l;
c = b * 4l;
d = c / 2l;
}
System.out.println("i:" + i + ", a:" + a + ", b:" + b + ", c:" + c + ", d:" + d);
}
}
Java の場合は long が 64bit なのでこれで OK なのです。さてその後、普通に javac でコンパイルして実行してみました3。
kazawa@tpx20:~$ java -server -version
java version "1.4.2_01"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_01-b06)
Java HotSpot(TM) Server VM (build 1.4.2_01-b06, mixed mode)
kazawa@tpx20:~$ javac multi.java
kazawa@tpx20:~$ time java -server multi
i:100000000, a:436906, b:873813, c:3495252, d:1747626
real 0m7.485s
user 0m7.223s
sys 0m0.033s
ちょっとびっくりなことに、VM の起動時間まで含まれてしまう time による計測にもかかわらず、icc による結果に比べても倍くらい高速です。なんじゃこりゃーって感じです。
１億回のループ中、中間結果をはしょったりしているんじゃなかろうか、と１千万回に１回中間結果を表示するようにしてみたりもしたんですが、結果は変わりませんでした。当然の如く、得られる数値も全て同一です。
これほど小さなプログラム、それも計算主体のものでこんなに差が出る理由がはっきり言って謎です。なお興味深いことに、テストプログラム中の *4 を *6 に、/2 を /3 に変更して試してみた結果が下記です。
kazawa@tpx20:~$ time ./multi_icc
i:100000000, a:-384307168202464939, b:-768614336404929877, c:-4611686018429579262, d:-1537228672809859754
real 0m31.510s
user 0m30.825s
sys 0m0.007s
kazawa@tpx20:~$ time java -server multi
i:100000000, a:-384307168202464939, b:-768614336404929877, c:-4611686018429579262, d:-1537228672809859754
real 0m32.544s
user 0m31.778s
sys 0m0.027s
icc 版は２倍、java 版は4倍くらい遅くなって、どちらもほとんど変わらない結果となりました (Java が１秒ほど遅いのは VM 起動時のラグだとすると体感的にはちょうどな感じ)。つまりあれですか、かけ算をシフト命令で置き換えられるような時の 64bit 計算の効率が激しく良い、ってこと？しかし、いくら HotSpotVM が動的最適化して効率の良いネイティブコードを生成する、と言ったって、icc が静的に生成するコードよりも効率のいいものを作れるものなんでしょうかね。しかもこんな単純なコードで。
おまけ。HotSpot Server VM でなく Client VM では、
kazawa@tpx20:~$ time java multi
i:100000000, a:436906, b:873813, c:3495252, d:1747626
real 0m58.071s
user 0m56.676s
sys 0m0.040s
てな感じになります。また IBM VM でも
kazawa@tpx20:~$ /usr/local/IBMJava2-141/bin/java -version
java version "1.4.1"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1)
Classic VM (build 1.4.1, J2RE 1.4.1 IBM build cxia32141-20030522 (JIT enabled: jitc))
kazawa@tpx20:~$ time /usr/local/IBMJava2-141/bin/java multi
i:100000000, a:436906, b:873813, c:3495252, d:1747626
real 0m56.422s
user 0m54.605s
sys 0m0.093s
と、あまり変わらない結果となります。こう見てくると、HotSpot Server VM だけが異常に (C と比べても) 速いことがわかります。なんでなんだろう…？
コメント
- SAK (Wed, 24 Mar 2004 12:18:56)
-
64bit版JavaVMの結果きぼんぬ。
- Digitune (Wed, 24 Mar 2004 21:12:42)
-
書き忘れたけど、SPARC 版の VM でも同じような傾向だったんだよね。それなりに 64bit VM vs. 32bit VM の速度差よりも、Server VM vs. Client VM の差の方が大きかった気がするがよく覚えてない。
ちなみにウチの環境では 64bit 版 VM は動かない、っつーかそもそもそんなものはないがなー(笑。
- Digitune (Wed, 24 Mar 2004 21:14:07)
-
あうち。上のコメント中の「それなりに」は「そういえば」に変換して読んでくらはい。
- かぴさん (Wed, 24 Mar 2004 22:35:34)
-
同じところを１億回も実行するからＶＭでもほとんどネーティブコードと変わらなかろうと思う。
ループ内は
a = ((a << 1) + 2) % 0xfffffffffffffffLL;
のレベルまで圧縮でき、ミクロに見ても畳み込めるぐらいの簡単コードなので如実に最適化パワーが出るコードだと考えられる。
千回に一回内容を見るとしても、
b = a + a + 1;
c = b << 2;
d = c >> 1;
の関係が判明していればこれらを千回に一回実行すればいいだけのことだな。で、この関係を見抜くのは変数の簡単な依存関係を調べるだけでできる。
あとはループ回数が固定値ではっきりしているのでループ展開とかすれば完璧。1000個ごとに１回ループ。
- Digitune (Thu, 25 Mar 2004 01:59:21)
-
かぴの行った解析は静的にも可能なものなような気がするんだが、とすると単に icc ですら Server VM がランタイムに行っている最適化に追いついていない、って言うこと？それはないようにも思うんだが…。
ちなみに、1000 回分づつ unroll、みたいな最適化をコンパイラはするんかね？icc では unroll しきい値は設定できるけど、そういう細かい指定は出来ないみたいだった。
- かぴ３ (Thu, 25 Mar 2004 22:16:56)
-
静的に可能でないとはまったくゆっていないが・・。
動的解析でもこれだけ単純なループならネーティブコードなやつとほとんど差はないだろーことと、たまに計算内容を表示するにしても参照のときだけ真面目に計算する方法を取れば畳み込みが阻害されないことを示したっつーこと。
コンパイラやVMの最適化戦略にも一長一短あるだろーから、たまたま特定の短いコードにクリティカルヒットするものもあるだろーよ。ベンチのときだけそこそこ速いクルーソーみたいなもん。オプションにもよるのかもしれないが、ｉｃｃなんか常識的な２の乗数積のシフト置き換えすらやっていないように見えるし。
- Digitune (Thu, 25 Mar 2004 22:40:45)
-
JITC がランタイムに行う最適化処理に使えるステップ数と、icc などの静的コンパイラが最適化処理に使えるステップ数には雲泥の差があるもんだと思っていたんだが…。
つまり、実行時情報が使えるような場合は本質的に JITC の方がより優れた結果を生む可能性はあるけれど、逆に言えばそれ以外の部分については敵いっこない、と思っていた、ってだけの話。
最近の JITC は最適化処理を裏 thread で回したりもするようだから、それほど処理量に対する制約は大きくないのかもね。
- Digitune (Thu, 25 Mar 2004 22:59:51)
-
違うか、敵いっこない、ってのはあながち間違っていないとしても、今回くらい簡単なプログラムに対する最適化ならば利用可能なステップ数はほとんど問題にならず、単にオプティマイザとコードの相性が効いてくる、って話か。
それは確かにそうだね。どーもです。
- かぴ３ (Fri, 26 Mar 2004 18:36:34)
-
ＶＭの最適化も処理頻度が大きいところほど最適化度を上げるような最適化度の最適化、イヒシオンの４段階ＣＭＳとかのような漸近的最適化処理といった近代的な仕組みがあれば割とこってりした最適化も無理なく可能だと考えられる。１億回も実行するんなら多少時間かけてでもより良く最適化した方が得そうだし。
ＶＭレベルだとコンパイラレベルと比べて大域的最適化が困難なわけだがー、これもjavacが吐いたことを前提としたコードのクセを踏まえて行えばソースがあるに等しいレベルで可能。トータルでの最適化時間は掛かるものの漸近的に詰めていけば実害は少なくて済む。
以前に大学の課題でコンパイラの最適化に取り組んだことがあって、そのとき他の連中はソースレベルで重厚な最適化処理を書いていたのに対して、俺はいったんバイナリコードを吐いて畳み込む方式で遥かに簡潔に性能の高い最適化を実現したことがある。局所的なレベルならバイナリコードでも簡単に強力な最適化が行えるもんだよ。分配則とかをＶＭレベルで見抜くのは難しそうなんで、この辺りで評価をするとiccの良さが出るかも。
- しゅどう (Fri, 02 Apr 2004 13:35:07)
-
iccが、2べきの乗算のシフトへの置換をしないように見えたのは、Pentium 4では相対的にシフト演算のコストが高くなったから。手元のicc 7.1でPentium 4向け(デフォルト)にコンパイルすると、x 128までは加算の繰り返し、x 256になって初めて左シフトにコンパイルする。