StringBuilder and string-building performance

Building a 100,000-character string with s += "x" in a loop copies about 5 billion characters, and the recorded run below allocated 5 GB to do it. Each round creates a new String and copies everything built so far into it, so the work grows with the square of the length, while a StringBuilder appends into one buffer that grows only now and then. A + that joins a few values in one expression is fine: javac compiles it to a single call that builds one result.

You will measure both ways on JDK 25, read the bytecode javac writes for each, and step through a builder as it grows and as its methods edit it in place. Then come StringJoiner for lists with separators, three traps, and what StringBuffer does and does not do for threads. The exercise is a run-length encoder that must handle 400,000 characters within a second.

Concatenating in a loop copies every char again

A String is an immutable objectimmutable object: An object whose state can never change once it exists, such as a String. Methods that seem to change it, like toUpperCase(), return a new object, so one object can be shared safely by many variables and threads. More in “Strings: first look and equality”, so s += "x" cannot add a character to s. It builds a new string from the old one and "x", and the old one becomes garbageAn object that no variable or other object refers to any more. The garbage collector reclaims its memory, and making and collecting such objects is part of what += in a loop costs.. The first round copies 1 character, the second 2, and round n copies n: n(n + 1) / 2 characters in all, a quadraticquadratic growth: Work that grows with the square of the input: twice the input, about four times the work. Building a string of n chars with += in a loop copies n(n + 1) / 2 chars, which is quadratic. amount. A StringBuilder writes each new character into unused space in its buffer, and copies its contents only when the buffer is full, into a new buffer about twice the size:

Step through the first rounds of both loops, and the round where the builder’s 16 slots run out. Watch the left column, where every round leaves one more string behind:

The program below builds the same string both ways for four sizes and asks the JVM how much memory each loop allocated:

import java.lang.management.ManagementFactory;

// Builds the same text, n copies of "x", with += and with a StringBuilder, as n doubles. For each way it prints the
// memory the loop allocated, which is the same on every run, and the time it took, which is not. A rough
// measurement (one run, a short warm-up); the performance module measures properly with JMH.
String withPlus(int n) {
    String s = "";
    for (int i = 0; i < n; i++) {
        s += "x";
    }
    return s;
}

String withBuilder(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        sb.append("x");
    }
    return sb.toString();
}

// Bytes allocated so far by this thread (a HotSpot extension of ThreadMXBean).
long allocated() {
    return ((com.sun.management.ThreadMXBean) ManagementFactory.getThreadMXBean()).getCurrentThreadAllocatedBytes();
}

void main() {
    IO.println("processors available to the JVM: " + Runtime.getRuntime().availableProcessors());
    withPlus(1_000);
    withBuilder(1_000);
    boolean same = true;
    for (int n = 25_000; n <= 200_000; n *= 2) {
        long bytes0 = allocated();
        long time0 = System.nanoTime();
        String a = withPlus(n);
        long time1 = System.nanoTime();
        long bytes1 = allocated();
        String b = withBuilder(n);
        long time2 = System.nanoTime();
        long bytes2 = allocated();
        same &= a.equals(b);
        IO.println(String.format("n = %,7d: += allocated %,8.1f MB in %,5d ms; StringBuilder %.3f MB in %.1f ms",
                n, (bytes1 - bytes0) / 1e6, (time1 - time0) / 1_000_000, (bytes2 - bytes1) / 1e6, (time2 - time1) / 1e6));
    }
    IO.println("both ways built the same strings: " + same);
}

processors available to the JVM: 18
n =  25,000: += allocated    313.6 MB in   219 ms; StringBuilder 0.100 MB in 0.8 ms
n =  50,000: += allocated  1,252.2 MB in   203 ms; StringBuilder 0.199 MB in 1.6 ms
n = 100,000: += allocated  5,004.4 MB in   669 ms; StringBuilder 0.396 MB in 1.1 ms
n = 200,000: += allocated 20,008.8 MB in 2,160 ms; StringBuilder 0.791 MB in 1.0 ms
both ways built the same strings: true

The memory column is the one to read, because it is the same on every run. Each time n doubles, += allocates four times as much, and StringBuilder twice as much: one curve grows with n², the other with n. The numbers also match the arithmetic. Strings whose characters all fit in one byte are stored with one byte per character (JEP 254, compact stringscompact strings: How the JVM stores a String since JDK 9 (JEP 254): one byte per char when every char fits in Latin-1, and two bytes per char, as UTF-16, otherwise.), so for n = 100,000 the copies alone come to 100,000 × 100,001 / 2 = 5,000,050,000 bytes, about 5,000 MB. The measured 5,004.4 MB adds a few dozen bytes of object headers for each of the 100,000 strings. To build a 100 KB string, the loop allocated 5 GB, and every string but the last became garbage one round after it was made.

The times tell the same story less precisely: they include the garbage collector and the JIT compilerJIT compilation: Just-in-time compilation: while a program runs, the JVM compiles the methods that run often from bytecode to native machine code, so a Java program gets faster after a short warm-up. The option -Xint switches it off. More in “What Java is, how it runs and where it is used”, which changes the loop’s code while it runs. On the computer of the recorded run, += was hundreds of times slower than StringBuilder at the larger sizes, while the builder’s time hardly changed from one size to the next. A careful measurement needs a benchmark harness such as JMH, which the performance module uses.

A single concatenation expression compiles to one call

The rule of thumb “never use +, always use StringBuilder” comes from older JDKs. The compiler’s output shows why it no longer holds for a single expression, and why it still matters in a loop. javac compiles the class below, and javap -c prints its bytecodebytecode: The instructions that javac writes into class files: the instruction set of the Java Virtual Machine, a computer that exists only as a specification, so the same bytecode runs on any system that has a recent enough JVM. More in “What Java is, how it runs and where it is used”:

// Two uses of +, compiled and then disassembled with javap to see what javac made of them.
class Concat {
    // One expression that joins three values.
    static String label(String city, int pin) {
        return city + " - " + pin;
    }

    // += inside a loop.
    static String repeatX(int n) {
        String s = "";
        for (int i = 0; i < n; i++) {
            s += "x";
        }
        return s;
    }
}

from session import run

run("""
javac -d out Concat.java
javap -c out/Concat.class
""")

$ javac -d out Concat.java
$ javap -c out/Concat.class
Compiled from "Concat.java"
class Concat {
  Concat();
    Code:
         0: aload_0
         1: invokespecial #1                  // Method java/lang/Object."<init>":()V
         4: return

  static java.lang.String label(java.lang.String, int);
    Code:
         0: aload_0
         1: iload_1
         2: invokedynamic #7,  0              // InvokeDynamic #0:makeConcatWithConstants:(Ljava/lang/String;I)Ljava/lang/String;
         7: areturn

  static java.lang.String repeatX(int);
    Code:
         0: ldc           #11                 // String
         2: astore_1
         3: iconst_0
         4: istore_2
         5: iload_2
         6: iload_0
         7: if_icmpge     23
        10: aload_1
        11: invokedynamic #13,  0             // InvokeDynamic #1:makeConcatWithConstants:(Ljava/lang/String;)Ljava/lang/String;
        16: astore_1
        17: iinc          2, 1
        20: goto          5
        23: aload_1
        24: areturn
}

javap -c disassembles a class file into its bytecode instructions. In label, the whole expression city + " - " + pin became one invokedynamicinvokedynamic: A bytecode instruction whose target the JVM links the first time it runs, by calling a bootstrap method. Since JDK 9 javac compiles each string concatenation expression to one, which StringConcatFactory links. instruction that names makeConcatWithConstants (JEP 280, JDK 9). Before JDK 9, javac wrote a chain of StringBuilder.append calls instead. Either way, one expression builds one result each time it runs, so a single + expression was never the problem. Step through the life of that instruction, from javac to every later call of label:

On the first call, the JDK’s StringConcatFactory links the instruction to concatenation code of the JDK’s own choosing, so the strategy can improve with each JDK without recompiling your classes. In repeatX, the same instruction sits inside the loop: the goto 5 at offset 20 jumps back to the loop’s test, and every round runs the invokedynamic at offset 11 again, producing a new string from s and "x". javac does not turn the loop into one buffer for you, because each new string is assigned to s, where the next statement could read it, and the 5 GB that the same loop allocated in Growth.java show that the running JVM did not either. That is the case for StringBuilder.

A builder grows to twice its capacity plus 2

A builder’s capacitycapacity: How many chars a StringBuilder can hold before it needs a bigger buffer: 16 for new StringBuilder(), and the text's length plus 16 for new StringBuilder(text). length() is how many it holds now. is how many chars it can hold before it needs a bigger buffer, and its length is how many it holds now. This program appends 300 chars one at a time, prints the capacity each time it changes, and counts the chars that growing moved:

// How a StringBuilder grows: it starts with room for 16 chars and, when an append does not fit, moves its chars to a
// bigger buffer. The capacities printed here are this JDK's choices; the Javadoc of ensureCapacity documents the rule.
void main() {
    StringBuilder sb = new StringBuilder();
    int capacity = sb.capacity();
    int copied = 0;
    IO.println("length 0, capacity " + capacity);
    for (int i = 0; i < 300; i++) {
        sb.append('x');
        if (sb.capacity() != capacity) {
            copied += sb.length() - 1;                   // the chars that were in the old buffer moved across
            capacity = sb.capacity();
            IO.println("length " + sb.length() + ", capacity " + capacity);
        }
    }
    IO.println("300 appends: " + copied + " chars copied while growing");
    StringBuilder sized = new StringBuilder(300);
    IO.println("new StringBuilder(300): capacity " + sized.capacity() + " before any append");
    IO.println("new StringBuilder(\"idli\"): length 4, capacity " + new StringBuilder("idli").capacity());
}

length 0, capacity 16
length 17, capacity 34
length 35, capacity 70
length 71, capacity 142
length 143, capacity 286
length 287, capacity 574
300 appends: 548 chars copied while growing
new StringBuilder(300): capacity 300 before any append
new StringBuilder("idli"): length 4, capacity 20

The builder started with room for 16 chars. Appending the 17th moved the contents into a buffer of 34, the 35th into one of 70, and so on: each new capacity is twice the old one plus 2, the rule the Javadoc of ensureCapacity gives. Follow one append that finds room and one that does not:

• Growing copied 16 + 34 + 70 + 142 + 286 = 548 chars for 300 appends, as the run counted. Each copy is about twice the one before, so all of them together stay below twice the final length, which is why n appends cost about n.
• When you know the final size, new StringBuilder(300) allocates it at once and nothing is ever copied.
• new StringBuilder("idli") starts with the text and room for 16 more chars: capacity 20, the length of the argument plus 16, as the constructor’s Javadoc says.

Editing methods change the builder in place

A StringBuilder is a mutable sequence of chars. Its methods change it in place and return the builder itself, so calls can be chained. Editing.java builds a list of seats in a loop, then edits it six times:

// A StringBuilder is a buffer of chars that you can change in place. Each method below edits the same builder.
void main() {
    StringBuilder sb = new StringBuilder();
    for (String seat : new String[] {"34", "35", "36"}) {
        sb.append("B2-").append(seat).append(", ");      // append returns the builder, so calls chain
    }
    IO.println("after the loop:      [" + sb + "]");

    sb.setLength(sb.length() - 2);                        // drop the last ", "
    IO.println("setLength(len - 2):  [" + sb + "]");

    sb.insert(0, "Seats: ");
    IO.println("insert(0, ...):      [" + sb + "]");

    sb.replace(7, 9, "A1");                              // chars 7 and 8 become "A1"
    IO.println("replace(7, 9, \"A1\"): [" + sb + "]");

    sb.setCharAt(sb.length() - 1, '7');
    sb.deleteCharAt(5);                                   // the ':'
    IO.println("setCharAt, deleteCharAt: [" + sb + "]");

    IO.println("reverse():           [" + new StringBuilder("stressed").reverse() + "]");

    sb.setLength(0);                                      // empty it, keep its buffer
    IO.println("setLength(0):        [" + sb + "], capacity still " + sb.capacity());
}

after the loop:      [B2-34, B2-35, B2-36, ]
setLength(len - 2):  [B2-34, B2-35, B2-36]
insert(0, ...):      [Seats: B2-34, B2-35, B2-36]
replace(7, 9, "A1"): [Seats: A1-34, B2-35, B2-36]
setCharAt, deleteCharAt: [Seats A1-34, B2-35, B2-37]
reverse():           [desserts]
setLength(0):        [], capacity still 34

Step through the same edits, with the builder’s length and capacity after each one:

• setLength(sb.length() - 2) is the tidy way to drop the separator after the last item; setLength(0) empties the builder but keeps its buffer, so a loop can reuse one builder.
• insert(offset, text) and replace(start, end, text) take positions like substring: the start is included and the end is not. setCharAt overwrites one char and deleteCharAt removes one, moving the rest left.
• reverse() reverses the chars, so "stressed" becomes "desserts".

Every edit after the loop ran in the 34 slots the builder already had, so none of them allocated a buffer.

StringJoiner puts separators only between items

A loop that appends an item and a comma, then removes the last comma, is common and easy to get wrong. StringJoiner remembers a separator, a prefix and a suffix and adds the separator only between items, so there is nothing to delete afterwards:

// StringJoiner remembers a separator, a prefix and a suffix, and what to print when nothing was added.
void main() {
    StringJoiner seats = new StringJoiner(", ", "[", "]");
    seats.setEmptyValue("(no seats)");
    IO.println("before any add: " + seats);
    seats.add("B2-34").add("B2-35");
    seats.add("B2-36");
    IO.println("after three:    " + seats + ", length " + seats.length());

    StringJoiner wait = new StringJoiner(", ", "Waiting list: ", ".");
    IO.println("no setEmptyValue: \"" + wait + "\"");

    IO.println(Stream.of("WL 1", "WL 2").collect(Collectors.joining(", ", "Waiting list: ", ".")));
    IO.println(String.join(", ", List.of("B2-34", "B2-35", "B2-36")));
}

before any add: (no seats)
after three:    [B2-34, B2-35, B2-36], length 21
no setEmptyValue: "Waiting list: ."
Waiting list: WL 1, WL 2.
B2-34, B2-35, B2-36

setEmptyValue decides what an empty joiner prints: without it, the result is the prefix and the suffix with nothing between them, "Waiting list: .", which reads like a bug. The three ways of joining suit three situations, and the run printed one line for each:

Three traps: a char, equals and half an emoji

Each trap compiles without a warning and fails only when the program runs. The program shows all three:

// Three ways a StringBuilder surprises people.
void main() {
    // 1. There is no constructor that takes a char: 'a' is widened to the int 97 and becomes the capacity.
    StringBuilder fromChar = new StringBuilder('a');
    fromChar.append("bc");
    IO.println("new StringBuilder('a').append(\"bc\") is \"" + fromChar + "\", capacity was " + new StringBuilder('a').capacity());

    // 2. StringBuilder does not override equals: two builders with the same chars are not equal.
    StringBuilder x = new StringBuilder("idli");
    StringBuilder y = new StringBuilder("idli");
    IO.println("x.equals(y): " + x.equals(y) + ", x.compareTo(y) == 0: " + (x.compareTo(y) == 0)
            + ", \"idli\".contentEquals(x): " + "idli".contentEquals(x) + ", x.toString().equals(y.toString()): " + x.toString().equals(y.toString()));

    // 3. deleteCharAt removes one char, which is half of an emoji.
    StringBuilder thanks = new StringBuilder("Thanks 🙏");
    thanks.deleteCharAt(thanks.length() - 1);
    String left = thanks.toString();
    IO.println("after deleteCharAt: length " + left.length() + ", last char U+" + Integer.toHexString(left.charAt(left.length() - 1)).toUpperCase()
            + ", a lone surrogate: " + Character.isHighSurrogate(left.charAt(left.length() - 1)));
}

new StringBuilder('a').append("bc") is "bc", capacity was 97
x.equals(y): false, x.compareTo(y) == 0: true, "idli".contentEquals(x): true, x.toString().equals(y.toString()): true
after deleteCharAt: length 8, last char U+D83D, a lone surrogate: true

1. A char is not text here. StringBuilder has constructors for an int capacity, a String and a CharSequence, but none for a char. So new StringBuilder('a') widens 'a' to the int 97 and makes an empty builder with capacity 97, and the "a" never appears. Write new StringBuilder("a").
2. Two builders are never equal. StringBuilder does not override equals, so x.equals(y) compares identities and is false for two builders with the same chars. Compare contents with x.compareTo(y) == 0 (Java 11), "idli".contentEquals(x) or x.toString().equals(y.toString()), and never use a builder as a key of a HashMap.
3. One char is not one character. deleteCharAt removes a single char, and the emoji 🙏 takes two of them, a surrogate pairsurrogate pair: Two UTF-16 code units, a high one from D800 to DBFF and a low one from DC00 to DFFF, that together encode one character beyond U+FFFF, such as an emoji. length() counts both; codePointCount counts one. More in “char, boolean, casting and conversions”, so deleting the last char left half of it: a lone high surrogate, U+D83D. reverse() takes care to keep such pairs together, but it reverses everything else char by char, which still breaks emoji with skin tones and words in Indian scripts. The module’s lesson on Unicode and Indian scripts shows how to work with what a reader sees as one character.

The last chars of "Thanks 🙏" show the third trap, position by position:

StringBuffer locks each call, not each line

StringBuffer is the original class from Java 1.0 and has the same methods, but it synchronisesDeclared synchronized: a thread must hold the object's lock to run the method, so calls on one object from different threads run one at a time. Each call is protected on its own; a sequence of calls is not. them, so that the calls made on one buffer behave as if they ran one after another, whichever threads make them. StringBuilder arrived in Java 5 for the usual case of one thread: its documentation says outright that it is not safe for use by several threads at once, and recommends StringBuffer when synchronisation is needed.

That recommendation is rarely the right design, though. Synchronising each call does not make a sequence of calls atomic: two threads that each run buf.append(name).append(", ") can still interleave their calls and produce "AshaRavi, , ". Step through that order, then the fix:

Interleave.java runs the same two threads for real. Three latchesA java.util.concurrent counter that threads wait on with await() until other threads have called countDown() enough times. Here each one makes a thread wait for the call before it. force the order of the figure, which a busy computer can also produce by itself, then the second half hands over finished lines:

import java.util.concurrent.CountDownLatch;

// Two threads each add one line, "name, ", to a shared StringBuffer. Every call of a StringBuffer is synchronised,
// but a line built with two appends is two calls. The latches below force the order a busy computer sometimes
// produces on its own: A's name, B's name, A's ", ", B's ", ". Then the same order, with whole lines.
void main() throws InterruptedException {
    StringBuffer shared = new StringBuffer();
    CountDownLatch aNamed = new CountDownLatch(1);
    CountDownLatch bNamed = new CountDownLatch(1);
    CountDownLatch aDone = new CountDownLatch(1);
    Thread a = Thread.ofPlatform().start(() -> {
        shared.append("Asha");
        aNamed.countDown();
        await(bNamed);
        shared.append(", ");
        aDone.countDown();
    });
    Thread b = Thread.ofPlatform().start(() -> {
        await(aNamed);
        shared.append("Ravi");
        bNamed.countDown();
        await(aDone);
        shared.append(", ");
    });
    a.join();
    b.join();
    IO.println("two appends per line, one shared StringBuffer: [" + shared + "]");

    // The fix: each thread builds its line in a StringBuilder of its own, then hands over the finished line in one call.
    StringBuffer lines = new StringBuffer();
    CountDownLatch aLine = new CountDownLatch(1);
    Thread c = Thread.ofPlatform().start(() -> {
        String line = new StringBuilder().append("Asha").append(", ").toString();
        lines.append(line);
        aLine.countDown();
    });
    Thread d = Thread.ofPlatform().start(() -> {
        String line = new StringBuilder().append("Ravi").append(", ").toString();
        await(aLine);
        lines.append(line);
    });
    c.join();
    d.join();
    IO.println("one append per finished line:                [" + lines + "]");
}

void await(CountDownLatch latch) {
    try {
        latch.await();
    } catch (InterruptedException e) {
        throw new IllegalStateException(e);
    }
}

two appends per line, one shared StringBuffer: [AshaRavi, , ]
one append per finished line:                [Asha, Ravi, ]

Give each thread its own StringBuilder and combine the finished strings, or hand complete lines to something built for sharing, such as a concurrent queue or a logging library. The concurrency module covers both.

Practise: run-length encoding

compress("aaabcc") should return "a3b1c2": each run of one character becomes the character and the length of the run, which is called run-length encodingrun-length encoding: Writing each run of one repeated character as the character and the length of the run, so aaabcc becomes a3b1c2. It shortens text with long runs and lengthens text without them.. The last check compresses 400,000 characters and must finish within a second. As it starts, compress returns an empty string, so every check fails except the one for empty input:

// Your turn: run-length encoding. compress("aaabcc") is "a3b1c2": each run of one character becomes the character and
// the length of the run. Build the result with a StringBuilder, so that the method stays fast on long inputs.
String compress(String s) {
    return "";   // Write your code here.
}

int failed = 0;
int total = 0;

void check(String input, String expected) {
    total++;
    String got = compress(input);
    if (!got.equals(expected)) {
        failed++;
        IO.println("FAIL compress(\"" + input + "\"): expected \"" + expected + "\", got \"" + got + "\"");
    }
}

void main() {
    check("aaabcc", "a3b1c2");
    check("abc", "a1b1c1");
    check("zzzzzzzzzzzz", "z12");
    check("aabbaa", "a2b2a2");
    check("a", "a1");
    check("", "");

    // 400,000 characters with no repeats: the answer is 800,000 characters long, and it must arrive within a second.
    total++;
    String input = "ab".repeat(200_000);
    long start = System.nanoTime();
    String got = compress(input);
    long millis = (System.nanoTime() - start) / 1_000_000;
    if (!got.equals("a1b1".repeat(200_000))) {
        failed++;
        IO.println("FAIL compress of 400,000 characters: wrong result (length " + got.length() + ")");
    } else if (millis > 1_000) {
        failed++;
        IO.println("FAIL compress of 400,000 characters: right, but it took " + millis + " ms");
    }

    IO.println(failed + " of " + total + " checks failed");
    if (failed > 0) {
        System.exit(1);
    }
}

FAIL compress("aaabcc"): expected "a3b1c2", got ""
FAIL compress("abc"): expected "a1b1c1", got ""
FAIL compress("zzzzzzzzzzzz"): expected "z12", got ""
FAIL compress("aabbaa"): expected "a2b2a2", got ""
FAIL compress("a"): expected "a1", got ""
FAIL compress of 400,000 characters: wrong result (length 0)
6 of 7 checks failed

You are done when it prints 0 of 7 checks failed. Hints: walk the string with an index i, move a second index j forward while s.charAt(j) == s.charAt(i), append the character and j - i, then continue from j. Appending an int writes its digits, so out.append(c).append(j - i) needs no conversion. Try the same method with += too: the last check fails, because the result is 800,000 characters long.

Then test yourself on the seven ideas, from what += copies to what a lock protects. Practice asks about your weakest idea first, and each choice says why it fits or misses:

Interview questions

Fresher · What is the difference between String, StringBuilder and StringBuffer?

A String is immutable: every method that seems to change it returns a new string, which makes strings safe to share and to use as keys. StringBuilder and StringBuffer are mutable buffers of chars with the same methods, such as append, insert, delete and reverse, for building or editing text without creating a new object for each step. The difference between those two is synchronisation: StringBuffer synchronises its methods, while StringBuilder (added in Java 5) has no locking and is meant for one thread, which makes it the usual choice. A good answer adds when each is needed: one + expression is already compiled efficiently, += in a loop copies the whole text every round, and StringBuffer is mostly found in old code, because sharing one buffer between threads is rarely a good design anyway.

An interviewer who hears that answer often tests it on a line of code or a design choice. Try these two before you read the explanations:

The module bank holds two longer questions on the same ground, a nightly report that takes 40 minutes to build and audit lines that come out merged:

Key takeaways

• One expression joined with + compiles to a single invokedynamic call (JEP 280) and builds its result once.
• += in a loop copies everything built so far in every round: n(n + 1) / 2 chars, which was 20 GB of allocation for a 200,000-character string in the recorded run.
• A StringBuilder grows to twice its capacity plus 2 when it is full, so n appends copy fewer than 2n chars; presize it with new StringBuilder(capacity) when you know the length.
• setLength, insert, replace, setCharAt, deleteCharAt and reverse edit the builder in place, and StringJoiner, String.join and Collectors.joining put separators only between items.
• new StringBuilder('a') sets a capacity of 97, builders do not override equals, and deleteCharAt can split an emoji in half.
• StringBuffer synchronises each call, which does not make a sequence of calls safe: give each thread its own builder and hand over finished lines.