StringBuilderを使ったクソコードはどこまで遅いか

※ 4/9 11:25 いろいろ計測しなおしてます。こちらも参照


Javaで文字列連結する場合には+演算子よりもStringBuilderを使うべき、という話があるのですが、よく

sb.append("[" + data + "]");

みたいなコードをみかけて、あんまり意味ないなーと思ったりします。
あと、

sb.append("title:");
sb.append("[" + data + "]");

みたいに、+演算子を使った一行の式にして

sb = "title:" +
  "[" + data + "]";

としておけば「title:」と「[」はコンパイル時点で最適化されたのに、ってコードもあります。


ということでTwitter

Javaでの文字列連結は+を使うべき、ってやったほうが、StringBuilder使ったsb.append("[" + data + "]")みたいなクソコードが量産されるよりも、世の中全体のJava文字列連結は速くなる可能性がある。

ということを書いてみたのだけど、ほんとにクソコードは遅いのか。
試してみました。
あ、適当に試してみただけなので、実際に速度が必要なときの指針にするときは、まじめに調べてから計測しなおしてください。


それでは、まず、文字列の配列を用意します。

strarray = IntStream.range(0, 1000).map(i -> (i % 9) + 1)
  .mapToObj(len -> IntStream.range(0, len).mapToObj(i -> "a").collect(Collectors.joining()))
  .toArray(size -> new String[size]);

「a」「aa」「aaa」という1文字から10文字までの文字列が1000個用意されることが一目でわかりますね!
これを連結して「[a],[aa],[aaa],[aaaa],...」という文字列を作ってみます。


StringBuilderを使うとこう。

    public static String stringBuilderJoin(){
        StringBuilder s = new StringBuilder("[");
        for(int i = 0; i < strarray.length; ++i){
            if(i != 0){
                s.append(",[");
            }
            s.append(strarray[i]).append("]");
        }
        return s.toString();
    }

5万回実行すると1579msでした。実行時最適化してもらうために計測前に100回ほど空ループもさせています。


さて、これをStringBufferにしてみます。StringBufferはappendがいちいちsynchronizedされているので遅いです。

    public static String stringBufferJoin(){
        StringBuffer s = new StringBuffer("[");
        for(int i = 0; i < strarray.length; ++i){
            if(i != 0){
                s.append(",[");
            }
            s.append(strarray[i]).append("]");
        }
        return s.toString();
    }

1692msになりました。やっぱちょっと遅いですね。


StringBuilderでのクソコードはどうでしょう?

    public static String stringBuilderFuckingJoin(){
        StringBuilder s = new StringBuilder();
        for(int i = 0; i < strarray.length; ++i){
            if(i != 0){
                s.append(",");
            }
            s.append("[" + strarray[i] + "]");
        }
        return s.toString();
    }    

「s.append("[" + strarray[i] + "]");」とかやってます。カンマのつけ方も、洗練されてない感じにしてクソコード感を出してみました。
1712msになって、StringBufferよりもStringBuilderのクソコードのほうが遅くなってます。


では、+演算子での文字列連結はどうでしょう?

    public static String plusArrayJoin(){
        String s = "[";
        for(int i = 0; i < strarray.length; ++i){
            if(i != 0){
                s += ",[";
            }
            s += strarray[i] + "]";
        }
        return s;
    }

あれ、帰ってこない子になりました。
110182ms。当社比100倍。
話にならないくらい遅いですね。これなら、「速度が気になるときにはクソコードでもいいからStringBuilder使え」という結論になりそうです。


ついでに同じことをStreamでやってみましょう。

    public static String streamArrayJoin(){
        return Arrays.stream(strarray)
                .flatMap(s -> Stream.of(",", "[", s, "]"))
                .skip(1).collect(Collectors.joining());
    }

コード短くなった。
でも4720ms。StringBuilderよりも3倍くらいかかってますね。
残念。これが速ければ世の中全部Streamでいけたのに。


これを、あらかじめListに変換してやってみます。

        strlist = Arrays.asList(strarray);


こんな感じ。

    public static String streamListJoin(){
        return strlist.stream()
                .flatMap(s -> Stream.of(",", "[", s, "]"))
                .skip(1).collect(Collectors.joining());
    }

4668ms。
微妙に速い。


んで、","と"["が別々になってるのがもったいないので、がんばって最適化してみます。

    public static String streamListJoinOpt(){
        return Stream.concat(
                strlist.stream().limit(1).flatMap(s -> Stream.of("[", s, "]")),
                strlist.stream().skip(1)
                .flatMap(s -> Stream.of(",[", s, "]")))
                .collect(Collectors.joining());
    }

4004ms。
おぉ、ちょっと速くなったけど、普通にStringBuilder使ったほうがいいですね。


さて、せっかくStreamなので、並列化してみましょう。ちなみに4コア8スレッドのCore i7です。

    public static String streamListParallelJoinOpt(){
        return Stream.concat(
                strlist.stream().limit(1).flatMap(s -> Stream.of("[", s, "]")),
                strlist.stream().skip(1).parallel()
                    .flatMap(s -> Stream.of(",[", s, "]")))
            .collect(Collectors.joining());
    }        

2586ms。
速くなったけど、StringBuilderのほうがいいですね。
ちなみに、concatしたものをparallelにしても、実行結果かわりませんでした。joiningは並列化きかないっぽい。


あと、concat使わないコードもparallelStreamにしてみました。

    public static String streamListParallelJoin(){
        return strlist.parallelStream()
                .flatMap(s -> Stream.of(",", "[", s, "]"))
                .skip(1).collect(Collectors.joining());
    }

3760ms。
なんか、あんまり並列がきいてないですね。


全体の結果はこんな感じです。

stringBuilderJoin:1579ms
stringBufferJoin:1692ms
stringBuilderFuckingJoin:1712ms
plusArrayJoin:110182ms
streamArrayJoin:4720ms
streamListJoin:4668ms
streamListJoinOpt:4004ms
streamListParallelJoinOpt:2586ms
streamListParallelJoin:3760ms


ということで、結論としては、+演算子じゃなくてStringBuilder/Bufferにしておけばだいぶ速くなるしそれ以上はそこまでかわらない、Streamで小細工してもムダ、みたいな、「高速化ではちょっとのがんばりですごく速くなるけどあとはあんまり速くできない」っていう法則を実証した感じになりました。


文字列連結などはEffective Javaに載ってますけど、Stream対応版が欲しいところです。
と思ったら、準備中だそうな。「楽しみにしてます」「翻訳楽しみにしてます」っていう柴田さんとのやりとりもいいですね。
https://twitter.com/enefem/status/428834489519722497

EFFECTIVE JAVA 第2版 (The Java Series)

EFFECTIVE JAVA 第2版 (The Java Series)


ということで、コード全体

public class StringJoinBench {
    static String[] strarray;
    static List<String> strlist;
    
    public static void main(String[] args) {
        strarray = IntStream.range(0, 1000).map(i -> (i % 9) + 1)
                .mapToObj(len -> IntStream.range(0, len).mapToObj(i -> "a").collect(Collectors.joining()))
                .toArray(size -> new String[size]);
        strlist = Arrays.asList(strarray);
        
        bench("stringBuilderJoin", StringJoinBench::stringBuilderJoin);
        bench("stringBufferJoin", StringJoinBench::stringBufferJoin);
        bench("stringBuilderFuckingJoin", StringJoinBench::stringBuilderFuckingJoin);
        bench("plusArrayJoin", StringJoinBench::plusArrayJoin);
        bench("streamArrayJoin", StringJoinBench::streamArrayJoin);
        bench("streamListJoin", StringJoinBench::streamListJoin);
        bench("streamListJoinOpt", StringJoinBench::streamListJoinOpt);
        bench("streamListParallelJoinOpt", StringJoinBench::streamListParallelJoinOpt);
        bench("streamListParallelJoin", StringJoinBench::streamListParallelJoin);
    }
    
    public static String stringBuilderJoin(){
        StringBuilder s = new StringBuilder("[");
        for(int i = 0; i < strarray.length; ++i){
            if(i != 0){
                s.append(",[");
            }
            s.append(strarray[i]).append("]");
        }
        return s.toString();
    }
    public static String stringBufferJoin(){
        StringBuffer s = new StringBuffer("[");
        for(int i = 0; i < strarray.length; ++i){
            if(i != 0){
                s.append(",[");
            }
            s.append(strarray[i]).append("]");
        }
        return s.toString();
    }
    public static String stringBuilderFuckingJoin(){
        StringBuilder s = new StringBuilder();
        for(int i = 0; i < strarray.length; ++i){
            if(i != 0){
                s.append(",");
            }
            s.append("[" + strarray[i] + "]");
        }
        return s.toString();
    }    
    public static String plusArrayJoin(){
        String s = "[";
        for(int i = 0; i < strarray.length; ++i){
            if(i != 0){
                s += ",[";
            }
            s += strarray[i] + "]";
        }
        return s;
    }
    public static String streamArrayJoin(){
        return Arrays.stream(strarray)
                .flatMap(s -> Stream.of(",", "[", s, "]"))
                .skip(1).collect(Collectors.joining());
    }

    public static String streamListJoin(){
        return strlist.stream()
                .flatMap(s -> Stream.of(",", "[", s, "]"))
                .skip(1).collect(Collectors.joining());
    }
    public static String streamListJoinOpt(){
        return Stream.concat(
                strlist.stream().limit(1).flatMap(s -> Stream.of("[", s, "]")),
                strlist.stream().skip(1)
                .flatMap(s -> Stream.of(",[", s, "]")))
                .collect(Collectors.joining());
    }
    public static String streamListParallelJoinOpt(){
        return Stream.concat(
                strlist.stream().limit(1).flatMap(s -> Stream.of("[", s, "]")),
                strlist.stream().skip(1).parallel()
                    .flatMap(s -> Stream.of(",[", s, "]")))
            .collect(Collectors.joining());
    }        
    public static String streamListParallelJoin(){
        return strlist.parallelStream()
                .flatMap(s -> Stream.of(",", "[", s, "]"))
                .skip(1).collect(Collectors.joining());
    }

    public static void bench(String name, Supplier<String> proc){
        bench(name, 50_000, proc);
    }
    public static void bench(String name, int count, Supplier<String> proc){
        if(!streamArrayJoin().equals(proc.get())) throw new RuntimeException(name + " is defferent with array join.");
        for(int i = 0; i < 100; ++i){
            proc.get();
        }
        long s = System.currentTimeMillis();
        for(int i = 0; i < count; ++i){
            proc.get();
        }
        System.out.printf("%s:%dms%n", name, System.currentTimeMillis() - s);
    }
}