地平線に行く

2011-08-01

Java7 で String クラスがリファクタリングされていました

| 22:34 |

先日、ついに JavaSE 7 がリリースされました!

そこで、早速ダウンロードして、Java7 のソースコード(src.zip)を Java6と比較してみたところ、公表はされていないのですが、ちょこちょことリファクタリングされていることがわかりました。

そこで、そのうち String クラスについて調べてみました。


splitメソッド - 独自処理による高速化

いままでは、String#split(〜) は正規表現 (Patternクラス) に処理を移譲するだけでした。

// (Java6) Stringクラス、2291行目〜
public String[] split(String regex, int limit) {
    return Pattern.compile(regex).split(this, limit);
}

それが、単純な区切り文字なら正規表現を使わないで独自に処理をするようにリファクタリングされていました。

独自に処理をするのは、以下の条件にマッチするときです。

  1. regexが一文字。かつ、その文字列が正規表現メタ文字(.$|()[{^?*+\)ではない。
  2. regexが二文字。かつ、1文字目がバックスラッシュで、2文字目が数字やアルファベットではない*1
// (Java7) Stringクラス、2312行目〜
public String[] split(String regex, int limit) {
    /* fastpath if the regex is a
       (1)one-char String and this character is not one of the
          RegEx's meta characters ".$|()[{^?*+\\", or
       (2)two-char String and the first char is the backslash and
          the second is not the ascii digit or ascii letter.
    */
    char ch = 0;
    if (((regex.count == 1 &&
         ".$|()[{^?*+\\".indexOf(ch = regex.charAt(0)) == -1) ||
         (regex.length() == 2 &&
          regex.charAt(0) == '\\' &&
          (((ch = regex.charAt(1))-'0')|('9'-ch)) < 0 &&
          ((ch-'a')|('z'-ch)) < 0 &&
          ((ch-'A')|('Z'-ch)) < 0)) &&
        (ch < Character.MIN_HIGH_SURROGATE ||
         ch > Character.MAX_LOW_SURROGATE))
    {
    (…以下略…)

これは「文字をカンマで分割する」ときなどに大きな威力を発揮します。

"abc,def,ghi,jkl,mno".split(",");

計測してみたところ、このような場合に処理が約5倍速くなっていました*2


contentEqualsメソッド - たった一行の劇的変化

StringBuilder などと文字列比較を行うメソッド - String#contentEquals(CharSequence) に、「return true;」が追加されていました。

[#JDK-6355654] (str) String.contentEquals(CharSequence) calculates twice for AbstractStringBuilder - Java Bug System


たった一行の変更ですが、これによって3倍も速くなっていました*3

大抵の場合、CharSequence = StringBuffer, StringBuilder だと思うので、かなり効果的な変更だと思います。

// (Java7) Stringクラス、1069行目〜
public boolean contentEquals(CharSequence cs) {
    if (count != cs.length())
        return false;
    // Argument is a StringBuffer, StringBuilder
    if (cs instanceof AbstractStringBuilder) {
        char v1[] = value;
        char v2[] = ((AbstractStringBuilder)cs).getValue();
        int i = offset;
        int j = 0;
        int n = count;
        while (n-- != 0) {
            if (v1[i++] != v2[j++])
                return false;
        }
        return true;    // ここが追加になりました!!!
    }
    // Argument is a String
    if (cs.equals(this))
        return true;
    // Argument is a generic CharSequence
    char v1[] = value;
    int i = offset;
    int j = 0;
    int n = count;
    while (n-- != 0) {
        if (v1[i++] != cs.charAt(j++))
            return false;
    }
    return true;
}

コンストラクタ - 純粋なリファクタリング

Unicode コードポイントの配列から文字列を生成するコンストラクタ - String(int[] codePoints, int offset, int count) が、新たに書き直されていました。

// (Java7) Stringクラス、256行目〜
public String(int[] codePoints, int offset, int count) {
    (…中略…)
    final int end = offset + count;

    // Pass 1: Compute precise size of char[]
    int n = count;
    for (int i = offset; i < end; i++) {
        int c = codePoints[i];
        if (Character.isBmpCodePoint(c))
            continue;
        else if (Character.isValidCodePoint(c))
            n++;
        else throw new IllegalArgumentException(Integer.toString(c));
    }

    // Pass 2: Allocate and fill in char[]
    final char[] v = new char[n];

    for (int i = offset, j = 0; i < end; i++, j++) {
        int c = codePoints[i];
        if (Character.isBmpCodePoint(c))
            v[j] = (char) c;
        else
            Character.toSurrogates(c, v, j++);
    }
    (…中略…)

ざっと処理をまとめると・・・。

このコンストラクタは、引数 int[] codePoints から 内部の変数 char[] value へ詰め替えるのが主な処理です。

この処理でポイントになるのは、value の長さがどれだけ必要かという点です。単純に考えると codePoints.length == value.length ですが、Unicodeサロゲートペアを含む場合はそうなりません。これは、サロゲートペアを表すのに、int だと一つで済みますが、char だと二つ必要になるからです。

Java6では、この点をあまり考慮せず、いきなり char[] value に値をコピーしていって、不足したら配列を拡張するというやり方をとっていました。しかし、配列を拡張する = 新しく配列を生成し直すということなので、あまり効率がよくありません。

そこで、Java7では処理を2段階に分けるようになっていました。

  1. 文字列を格納するのに必要な配列長を計算
  2. 配列を割り当て、中身を詰める

こうすることで、配列を拡張する必要がなくなり、効率が良くなっていました。

また、コード自体も従来に比べ、単純でわかりやすくなっています。



その他

ほかにも、以下のような点がリファクタリングされていました。


感想

とても勉強になる、お手本のようなリファクタリングだと思います。

読んでいて、「ああ、こういう風にプログラムはよくなっていくんだ」と、とても感心しました。(もちろん、こういうリファクタリングをするにはテストが必須ですが…)

ほかのクラスも、Stringと同じようにリファクタリングされているみたいなので追ってみたいと思います。


関連記事

Java7 の try-with-resources で複数のリソースを扱うときの書き方が、C# の using と全然違う

一足早く、Java7でアプリを作ってみました!

eclipse が Java7 に対応するのは、2011年9月ごろの予定

Java7のObjectsクラス


速度調査に使ったプログラム

import java.util.Arrays;
import org.junit.Test;

public class StringTest {

    @Test
    public void contetEqualsTest(){
        String str = "abcdefg";
        StringBuilder cs = new StringBuilder("abcdefg");
        
        int loop = 11;
        long[] result = new long[loop];
        for(int i = 0; i < loop; i++){
            long start = System.nanoTime();
            for(int j = 0; j < 10000000; j++){
                str.contentEquals(cs);
            }
            long end = System.nanoTime();
            
            result[i] = end - start;
        }
        
        Arrays.sort(result);
        System.out.println(result[loop/2]);
        
        // java6 - 916,871,531ns
        // java7 - 299,915,409ns
    }

    @Test
    public void splitTest(){
        String str = "abc,def,ghi,jkl,mno";
        
        int loop = 11;
        long[] result = new long[loop];
        for(int i = 0; i < loop; i++){
            long start = System.nanoTime();
            for(int j = 0; j < 1000000; j++){
                str.split(",");
            }
            long end = System.nanoTime();
            
            result[i] = end - start;
        }
        
        Arrays.sort(result);
        System.out.println(result[loop/2]);
        
        // java6 - 1,546,249,382ns
        // java7 -   320,370,236ns
    }
}

*1:例えば、\[ が該当します。\は無視されるので、実質一文字です。

*2:手元の環境(Core i7 920 @2.67GHz)で str.split(","); を100万回ループした結果、Java6 が約1,550ms、Java7 が約320msでした。コードは、「続きを読む」に記載しています。

*3:手元の環境(Core i7 920 @2.67GHz)で str.contentEquals(cs); を1000万回ループした結果、Java6 が約920ms、Java7 が約300msでした。コードは、「続きを読む」に記載しています。