javaが懐かしくなってきたので、ちょっと読んでみました。
今回は割とよく使うであろうInteger#toString(int i)について。これも割と（俺にとっては）ややこしいコードになってました。
まずは冒頭部分
switch(i) {
case Integer.MIN_VALUE: return "-2147483648";
case -3: return "-3";
case -2: return "-2";
case -1: return "-1";
case 0: return "0";
case 1: return "1";
case 2: return "2";
...小さい数字は頻出しやすいためにこういう「手抜き」状態になってるのかなぁと思います。Integer#MIN_VALUEを特別扱いしてるのは、intから文字列への変換アルゴリズムがInteger#MIN_VALUEを正常に扱えないためです。
焦点となるのはgetChars(int, char)。メソッド名のとおり、intで与えられた数値をcharのバッファに格納します。
private static int getChars(int i, char buf) {
int q, r;
int charPos = 12;
char sign = 0; if (i < 0) {
sign = '-';
i = -i;
}
// Generate two digits per iteration
while (i >= 65536) {
q = i / 100;
// really: r = i - (q * 100);
r = i - )((q << 6) + (q << 5) + (q << 2))(;
i = q;
buf [--charPos] = DigitOnes[r];
buf [--charPos] = DigitTens[r];
}
// Fall thru to fast mode for smaller numbers
// assert(i <= 65536, i);
for (;;) {
q = (i * 52429) >>> (16+3);
r = i - )((q << 3) + (q << 1))(; // r = i-(q*10) ...
buf [--charPos] = digits [r];
i = q;
if (i == 0) break;
}
if (sign != 0) {
buf [--charPos] = sign;
}
return charPos;
}
見た目には何やってんだかサッパリです。
とりあえず、下のような前処理をやるのでInteger#MIN_VALUEを特別扱いしてることはわかります。
if (i < 0) {
sign = '-';
i = -i;
}このメソッド理解のヒントはクラス内部のコメントに書いてあります。Division by Invariant Integers using Multiplicationという論文？を元に invariant division by multiplication という"trick"を使用してパフォーマンス向上を図っているようです。特に10による除算を避けるのが狙いらしいです。
さらにコメントによると、.remや.divコールを避けるとコードパスが長くなり、ディスパッチオーバーヘッドが大きくなるが、JITではディスパッチオーバーへッドは存在しないので、"trick"は古いInteger#toStringコードより早くなる･･･らしい。
Invariant Integers using Multiplication が日本語だと何て訳せばいいかわからないけど、要は割り算を乗算で置き換えることによって高速化を図るため、ややこしいコードになってるようです。
さて実際のコード。とりあえず、大きく分けて2つのループになってます。まず、65536より大きい場合は最初のループに入って、65536より小さくなるまで何かしら処理をします。で、65536より小さい場合は「Fall thru to fast mode for smaller numbers」の通り、専用の高速ルーチンを使っています。
というわけで一つ目のループ。
// Generate two digits per iterationやってることは大したことなくて、iの下2桁を取り出してcharに変換してiを2桁繰り下げる、の繰り返し。やってることは↓のよーなコードと同じです。modが遅いんでしょうね、おそらく。
while (i >= 65536) {
q = i / 100;
// really: r = i - (q * 100);
r = i - )((q << 6) + (q << 5) + (q << 2))(;
i = q;
buf [--charPos] = DigitOnes[r];
buf [--charPos] = DigitTens[r];
}
div = a / 10; // aを1桁下げる
mod = a % 10; // aの下1桁を取得する
そこで、modを乗算で実現するわけです。実際にはシフト演算を使いますが。
qとrに入る計算結果の内容は、qにiを2桁下げたものが入り、rにiの下2桁が入ります。「q = i / 100」はまぁそーいうもんだとして。rの計算はコメントにあるとおりの計算になりますが、これによって何故に下2桁が取れるか見てみます。
q = i / 100;
// really: r = i - (q * 100);
r = i - )((q << 6) + (q << 5) + (q << 2))(;
q * 100をシフト演算でどう表現してるかなんですが、xビットの左xビットシフトは2^x乗倍を利用します。まぁとりあえず100 * xを分解してみると
100 * x
= (64 + 32 + 4) * x
= (2^6 + 2^5 + 2^2) * x
= 2^6*x + 2^5*x + 2^2*x
となり、xの100倍 は xを6ビット左シフト + xを5ビット左シフト + xを2ビット左シフトになります。んで、そいつを i から引いてやることで下2桁が取得できます。
例えばi = 12345678 とすると･･･
q = i / 100;
= 123456
r = i - )((q << 6) + (q << 5) + (q << 2))(;
= 12345678 - (123456 * 100)
= 12345678 - (12345600)
= 78
こんな感じで下2桁を取り出します。あとはこの2桁をcharに変換するわけなんですが、ここもまた面白いことやってます。
buf [--charPos] = DigitOnes[r];言ってみれば2桁の数値専用のint-char変換テーブルです。添え字に対して、添え字の1の位 or 10の位の数字を配列要素にいれることで変換します。テーブル駆動プログラミングの一種ってことですかねぇ、これも。
buf [--charPos] = DigitTens[r];final static char DigitTens = {
'0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
'1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
'2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
'3', '3', '3', '3', '3', '3', '3', '3', '3', '3',
'4', '4', '4', '4', '4', '4', '4', '4', '4', '4',
'5', '5', '5', '5', '5', '5', '5', '5', '5', '5',
'6', '6', '6', '6', '6', '6', '6', '6', '6', '6',
'7', '7', '7', '7', '7', '7', '7', '7', '7', '7',
'8', '8', '8', '8', '8', '8', '8', '8', '8', '8',
'9', '9', '9', '9', '9', '9', '9', '9', '9', '9',
} ;final static char [] DigitOnes = {
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
} ;
次に2つ目のループです。
// Fall thru to fast mode for smaller numbersやってることは1つ目のループと変わりません。下1桁を取り出してcharに変換していきます。
// assert(i <= 65536, i);
for (;;) {
q = (i * 52429) >>> (16+3);
r = i - ((q << 3) + (q << 1)); // r = i-(q*10) ...
buf [--charPos] = digits [r];
i = q;
if (i == 0) break;
}
問題はこの部分。
q = (i * 52429) >>> (16+3);rの計算は上と同じ理屈なのでいいとして、qの計算は非常に謎。結果としては1桁下げる（i / 10する）のと同じことをやっているんだけど･･･。割り算を乗算（とシフト）で置き換えてる、ってのはわかるんだけど。うーん･･･。
r = i - ((q << 3) + (q << 1)); // r = i-(q*10) ...
