What's the fastest way to concatenate two Strings in Java?

Question

What's the fastest way to concatenate two Strings in Java?

i.e

String ccyPair = ccy1 + ccy2;

I'm using cyPair as a key in a HashMap and it's called in a very tight loop to retrieve values.

When I profile then this is the bottleneck

java.lang.StringBuilder.append(StringBuilder.java:119)  
java.lang.StringBuilder.(StringBuilder.java:93)

Solution 1

The reason why these routines show up in the benchmark is because that is how the compiler implements your "+" under the covers.

If you really need the concatenated string, you should let the compiler do its magic with the "+". If all you need is a key for map lookup, a key class holding both strings with suitable equals and hashMap implementations might be a good idea as it avoids the copying step.

Solution 2

Lots of theory - time for some practice!

private final String s1 = new String("1234567890");
private final String s2 = new String("1234567890");

Using plain for loops of 10,000,000, on a warmed-up 64-bit Hotspot, 1.6.0_22 on Intel Mac OS.

eg

@Test public void testConcatenation() {
    for (int i = 0; i < COUNT; i++) {
        String s3 = s1 + s2;
    }
}

With the following statements in the loops

String s3 = s1 + s2; 

1.33s

String s3 = new StringBuilder(s1).append(s2).toString();

1.28s

String s3 = new StringBuffer(s1).append(s2).toString();

1.92s

String s3 = s1.concat(s2);

0.70s

String s3 = "1234567890" + "1234567890";

0.0s

So concat is the clear winner, unless you have static strings, in which case the compiler will have taken care of you already.

Solution 3

I believe the answer might have already been determined, but I post to share the code.

Short answer, if pure concatenation is all you are looking for, is: String.concat(...)

Output:

ITERATION_LIMIT1: 1
ITERATION_LIMIT2: 10000000
s1: STRING1-1111111111111111111111
s2: STRING2-2222222222222222222222

iteration: 1
                                          null:    1.7 nanos
                                 s1.concat(s2):  106.1 nanos
                                       s1 + s2:  251.7 nanos
   new StringBuilder(s1).append(s2).toString():  246.6 nanos
    new StringBuffer(s1).append(s2).toString():  404.7 nanos
                 String.format("%s%s", s1, s2): 3276.0 nanos

Tests complete

Sample Code:

package net.fosdal.scratch;

public class StringConcatenationPerformance {
    private static final int    ITERATION_LIMIT1    = 1;
    private static final int    ITERATION_LIMIT2    = 10000000;

    public static void main(String[] args) {
        String s1 = "STRING1-1111111111111111111111";
        String s2 = "STRING2-2222222222222222222222";
        String methodName;
        long startNanos, durationNanos;
        int iteration2;

        System.out.println("ITERATION_LIMIT1: " + ITERATION_LIMIT1);
        System.out.println("ITERATION_LIMIT2: " + ITERATION_LIMIT2);
        System.out.println("s1: " + s1);
        System.out.println("s2: " + s2);
        int iteration1 = 0;
        while (iteration1++ < ITERATION_LIMIT1) {
            System.out.println();
            System.out.println("iteration: " + iteration1);

            // method #0
            methodName = "null";
            iteration2 = 0;
            startNanos = System.nanoTime();
            while (iteration2++ < ITERATION_LIMIT2) {
                method0(s1, s2);
            }
            durationNanos = System.nanoTime() - startNanos;
            System.out.println(String.format("%50s: %6.1f nanos", methodName, ((double) durationNanos) / ITERATION_LIMIT2));

            // method #1
            methodName = "s1.concat(s2)";
            iteration2 = 0;
            startNanos = System.nanoTime();
            while (iteration2++ < ITERATION_LIMIT2) {
                method1(s1, s2);
            }
            durationNanos = System.nanoTime() - startNanos;
            System.out.println(String.format("%50s: %6.1f nanos", methodName, ((double) durationNanos) / ITERATION_LIMIT2));

            // method #2
            iteration2 = 0;
            startNanos = System.nanoTime();
            methodName = "s1 + s2";
            while (iteration2++ < ITERATION_LIMIT2) {
                method2(s1, s2);
            }
            durationNanos = System.nanoTime() - startNanos;
            System.out.println(String.format("%50s: %6.1f nanos", methodName, ((double) durationNanos) / ITERATION_LIMIT2));

            // method #3
            iteration2 = 0;
            startNanos = System.nanoTime();
            methodName = "new StringBuilder(s1).append(s2).toString()";
            while (iteration2++ < ITERATION_LIMIT2) {
                method3(s1, s2);
            }
            durationNanos = System.nanoTime() - startNanos;
            System.out.println(String.format("%50s: %6.1f nanos", methodName, ((double) durationNanos) / ITERATION_LIMIT2));

            // method #4
            iteration2 = 0;
            startNanos = System.nanoTime();
            methodName = "new StringBuffer(s1).append(s2).toString()";
            while (iteration2++ < ITERATION_LIMIT2) {
                method4(s1, s2);
            }
            durationNanos = System.nanoTime() - startNanos;
            System.out.println(String.format("%50s: %6.1f nanos", methodName, ((double) durationNanos) / ITERATION_LIMIT2));

            // method #5
            iteration2 = 0;
            startNanos = System.nanoTime();
            methodName = "String.format(\"%s%s\", s1, s2)";
            while (iteration2++ < ITERATION_LIMIT2) {
                method5(s1, s2);
            }
            durationNanos = System.nanoTime() - startNanos;
            System.out.println(String.format("%50s: %6.1f nanos", methodName, ((double) durationNanos) / ITERATION_LIMIT2));

        }
        System.out.println();
        System.out.println("Tests complete");

    }

    public static String method0(String s1, String s2) {
        return "";
    }

    public static String method1(String s1, String s2) {
        return s1.concat(s2);
    }

    public static String method2(String s1, String s2) {
        return s1 + s2;
    }

    public static String method3(String s1, String s2) {
        return new StringBuilder(s1).append(s2).toString();
    }

    public static String method4(String s1, String s2) {
        return new StringBuffer(s1).append(s2).toString();
    }

    public static String method5(String s1, String s2) {
        return String.format("%s%s", s1, s2);
    }

}

Solution 4

You should test with a String generated at run time (like UUID.randomUUID().toString()) not at compile time (like "my string"). My results are

plus:     118 ns
concat:    52 ns
builder1: 102 ns
builder2:  66 ns
buffer1:  119 ns
buffer2:   87 ns

with this implementation:

private static long COUNT = 10000000;

public static void main(String[] args) throws Exception {
    String s1 = UUID.randomUUID().toString();
    String s2 = UUID.randomUUID().toString();
    for(String methodName : new String[] {
            "none", "plus", "concat", "builder1", "builder2", "buffer1", "buffer2"
    }) {
        Method method = ConcatPerformanceTest.class.getMethod(methodName, String.class, String.class);
        long time = System.nanoTime();
        for(int i = 0; i < COUNT; i++) {
            method.invoke((Object) null, s1, s2);
        }
        System.out.println(methodName + ": " + (System.nanoTime() - time)/COUNT + " ns");
    }
}

public static String none(String s1, String s2) {
    return null;
}

public static String plus(String s1, String s2) {
    return s1 + s2;
}

public static String concat(String s1, String s2) {
    return s1.concat(s2);
}

public static String builder1(String s1, String s2) {
    return new StringBuilder(s1).append(s2).toString();
}

public static String builder2(String s1, String s2) {
    return new StringBuilder(s1.length() + s2.length()).append(s1).append(s2).toString();
}

public static String buffer1(String s1, String s2) {
    return new StringBuffer(s1).append(s2).toString();
}

public static String buffer2(String s1, String s2) {
    return new StringBuffer(s1.length() + s2.length()).append(s1).append(s2).toString();
}

Solution 5

For the question in the title: String.concat will typically be the fastest way to concat two Strings (but do note nulls). No [oversized] intermediate buffer or other object is involved. Strangely + gets compiled into relatively inefficient code involving StringBuilder.

However, the body of you question points to other problems. String concatenation to generate keys for a map is a common "anti-idiom". It is a hack and error-prone. Are you sure that the generated key is unique? Will it remain unique after your code is maintained for some as yet unknown requirement? The best approach is to create an immutable value class for the key. Using a List and generic tuple class is a sloppy hack.

View more solutions

Comments

[Bozho]

bottleneck in string concatenation? That would mean all java programs are having preformance issues. Don't microoptimize.

[Duncan McGregor]

But he has profiled the code, and this is the bottleneck. This isn't micro-optimization, nor premature optimization, it's just optimization.

[bestsss]

@Duncan, actually that's one of the issues. The real issues the ccy code generation into the loop. It contains multiple allocations+memory barriers, +not so fast hash code (14 mul+add; assuming ccy pairs are like "eur/usdusd/jpy"), and then equals. Using a holding pair w/ references to the 2 strings will be a lot better solution.

[Deepak]

@KitsuneYMG,Can you post a complete working example so that it is handy for tackling such issues in futures.

[Stephen C]

That doesn't help for a regular hashmap.

[Deepak]

do you have any sample code to prevent the bottleneck since you might know the implementation part

[Axel]

StringBuffer will definitely not perform better here since StringBuilder is its not threadsafe counterpart, avoiding the unnecessary synchronisation overhead.

[matbrgz]

@Deepak, I don't believe this to be a bottleneck, but the easiest way to create such a class in Eclipse 3.6 is to create a new class, give it the fields ccy1, and ccy2, ask Eclipse to create an constructor based on fields, and to generate the hashCode() and equals() methods.

[KitsuneYMG]

@Deepak see edits. It you need a triple, quad, etc, it's very easy to use this as a base to add more.

[Paŭlo Ebermann]

Is the StringBuilder variant really much more inefficient than concat?

[Deepak]

@KitsuneYMG,can you post the public static void main method for you pair class so that it can be handy for further reference

[Duncan McGregor]

Do you have any evidence for "you cannot improve String concatenation per se"?

[Duncan McGregor]

Indeed - StringBuilder is significantly faster

[Duncan McGregor]

I'd be interested to know if this is actually quicker in use, as it doesn't cache the Pair's hashCode, whereas the concatenated string's hashCode is cached.

[KitsuneYMG]

@Duncan you could easily cache the hashcode and discard it upon set*. This should be faster than concatenating two strings which requires two memcpy's (unless the particular JVM uses ropes).

[bestsss]

the code will be dead optimized, so you are effectively testing not-optimized code. This is how you dont write micro-benchmarks. Nonetheless, String.contact should be the fastest for 2 strings.

[bestsss]

@Stephen, look at String.concat() impl. there is NO surprise and it has been the best method for concatenating 2 strings ONLY. It allocates exactly as needed char[] and copies via System.arrayCopy (so one char[] alloc, 2 memcpy, one string alloc, cant beat that ever), but most of all, it's the only way to create a String w/o extra copy of the char array (as of now, back in the day StringBuffer didn't copy either)

[Stephen C]

The surprise is that they can't use s.concat(s2) for s + s2. But it makes sense; see above.

[bestsss]

@Stephen, yes, it doesn't work if any of the strings is null. But consider this: String.valueOf(s1).contact(String.valueOf(s2)); actually I'd swear I have seen JBuilder does it (but it was at least 8 years ago, so I'd not swear for real)

[bestsss]

actually - you end up w/ "ccy1ccy2" always.

[bestsss]

side notes: the eclipse generated hashcode/equals suck (esp. visually), you probably want the class serializable; hashcode caching may not be needed (due to how hashmap works). Also declaring T1 and T2 String will help the compiler to statically link equals and hashcode (now it will probably fall back to inline caches though, not so shabby but still)

[bestsss]

@Stephen, the custom map (2 value map) is the best solution to the problem. I guess I can post one.

[Duncan McGregor]

I am guilty of not further examining the results as they were exactly what I expected! But I don't understand how I am testing not optimised code. If Hotspot were removing code with no side effects all these loops would take the same time, and if it isn't, then I am testing the time to run the statements (plus the loop). The thing that we don't know is the time taken by the loops, but not having too much time on my hands I didn't account for that ;-)

[Duncan McGregor]

@Stephen C - you can't have it both ways - saying that I have too much time on my hands and then complain that I only give results for one VM and set of input strings!

[Stephen C]

@Duncan McGregor - I'm not complaining. I'm just noting that the results may not be valid across the board ... which is something that you neglected to mention.

[Duncan McGregor]

@Stephen C - indeed, but I did give the conditions that I did use. I'd wager good odds that you'd find the similar odds for other VMs and strings - probably better for concat with longer strings - but I don't have reliable evidence for that hunch ;-)

[Redandwhite]

Can you provide details on the JVM you tested these with?

[leoismyname]

@Redandwhite java version "1.6.0_31" Java(TM) SE Runtime Environment (build 1.6.0_31-b05) Java HotSpot(TM) Client VM (build 20.6-b01, mixed mode, sharing)

[Martin Podval]

Nice comment. I've been looking for speed of string.format and now I see that it's little bit slow :-) I'll use concat instead.

[matbrgz]

@DuncanMcGregor It takes a while before the JVM optimizes the code.

[Georgi Peev]

StringBuilder is a way to fast with big strings ,but is slow with small.