Integer.getCharsが面白い

　JavaのIntegerクラスgetCharsメソッドがおもしろい。このメソッド自体はpackage privateなので直接呼び出すことはできないが、Integer.toStringのメイン処理が実装されている。

メソッドのシグネチャはgetChars(int i, int index, char[] buf)で整数iを表す文字列をbufに格納するというもの。このとき文字列はindexから0の方向にLSB -> MSBの順で埋められていく。
これだけ聞くと簡単そうに聞こえるが、高速化のためにおもしろい処理がされている。

とりあえず実装を載せておく。

static void getChars(int i, int index, char[] buf) {
        int q, r;
        int charPos = index;
        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;
        }
    }

まず第一段の処理としてiが65536以上の場合は2桁（10進数で）ずつ処理していく。
コメントを見ると、
r = i - ((q << 6) + (q << 5) + (q << 2))
と
r = i - (q * 100)
が等価であることが分かる。確かに100 = 64 + 32 + 4なのでそのとおり。DigitOnesとDigitTensはそれぞれ2桁の数字の1桁目と2桁目をO(1)で取り出すためのテーブル。これはハードコーディングされている。

まあここまでは分かる。

問題は次の第二段目の処理。

q = (i * 52429) >>> (16+3);
r = i - ((q << 3) + (q << 1));

何ですか、これは。。
何ですか、これは。∑(￣Д￣；)

先ほどの100倍と同じように、
r = i - ((q << 3) + (q << 1));

は、r = i - (q * 10)のこと。

ということは逆算して考えると、

q = (i * 52429) >>> (16+3);

ってのは、

q = i / 10ですか？試してみると確かにそうなっている。

でも何で52429と(16+3)なの？他の数字じゃだめなの？？

ということで、いろいろ試行錯誤して「52429」が唯一使える数字ということを確認したコードが以下。

package com.kenjih.test;

public class Clazz {
    public void run() {
        // 割り算をシフト演算にしたいので、２の冪乗のみ
        for (int i = 0 ; i < 32 ; i++) {
            int x = 1<<i;
            
            // 10 * y / x == 1となるようなyが候補。
            int y = x/10;
            if (y++ == 0)
                continue;
            
            // 65535を掛けたとき0xffffffffを越えないか？
            //（シフト演算が>>>なのでCでいうところのunsigned intの範囲までなら扱える）
            if (y * 65535L > 0x0ffffffffL)
                continue;
            
            // 60009 * y - 6000 * x < xか？
            // 上式が成り立たない場合は、60009 * y % x = 6001（以上）になってしまう。
            if (x * 6001 > 60009 * y)
                System.out.println(y);
        }
    }
    
    public static void main(String[] args) {
        new Clazz().run();
    }
}

以下が実行結果。

$ 52429

まさにシフト演算のマジックやぁ～～。(ﾉ￣□￣)ﾉｵｵｵｫｫｫｫ!

コイツはしびれますね。

で結局これってほんとに速いの？？
ということで高速化を考えず書いた普通の処理と比べてみる。

package com.kenjih.test;

public class MyInteger {
    private static char[] digits = {
        '0', '1', '2', '3', '4',
        '5', '6', '7', '8', '9'
    };
    
    public static String toString(int i) {
        char[] buf = new char[16];
        boolean minus = i < 0;
        int pos = 16;
        while (i > 0) {
            buf[--pos] = digits[i % 10];
            i /= 10;
        }
        if (minus)
            buf[pos] = '-';
        return new String(buf, pos, (16 - pos));
    }
}

普通に書くとまあこんなもんでしょっ。
桁数が大きい方が高速化が生きて来そうなので、1,000,000,000 - 1,100,000,000までを変換する処理も用いて比べてみた。

比較結果。
Integer = 0m4.499s
MyInteger = 0m5.681s

2割くらい速い！（微妙っ。いや、この違いは結構大きいのか？）