skip to content

Explain StringBuilder's internal capacity and growth strategy, and when pre-sizing capacity is worthwhile. How does this affect performance reasoning in hot paths?

level: seniorimportance: should knowfreq 35%

answer

  1. length (content) vs capacity (array size)
  2. Growth ~ oldCap*2+2, geometric -> amortized O(N)
  3. Resizes still allocate+copy = transient garbage
  4. Pre-size via StringBuilder(cap) / buildString(cap){}
  5. Measure first; matters in hot serializers/logging

basics

~20 s

StringBuilder keeps a backing array bigger than the text it holds. When it fills, it makes a bigger array (usually about double) and copies. If you know roughly how long the result is, you can set the capacity up front to skip those copies.

solid answer

~50 s

A `StringBuilder` separates `length` (current char count) from `capacity` (size of the backing `char[]`). When `append` would exceed capacity, the buffer grows — on the JVM typically to `oldCapacity * 2 + 2`, then copies existing characters into the new array. Because growth is geometric, the amortized cost of N appends is O(N) even though individual resizes are O(currentSize). However, the resizes still allocate and copy intermediate arrays, producing transient garbage. In a hot path where you can estimate the output length, constructing with `StringBuilder(capacity)` or `buildString(capacity) { }` pre-allocates the array so no growth/copy happens — fewer allocations, less GC, predictable latency. Don't over-tune blindly: for occasional or small builds the default is fine, and an overly large capacity wastes memory. Measure before pre-sizing; it matters most in tight loops, serializers, and logging fast paths.

code

kotlin · 13 lines
kotlin
// Hot serializer path: avoid resize churn
fun toCsv(rows: List<IntArray>): String {
    val approx = rows.sumOf { it.size } * 5 + rows.size
    return buildString(approx) {
        for (r in rows) {
            for ((i, v) in r.withIndex()) {
                if (i > 0) append(',')
                append(v)
            }
            appendLine()
        }
    }
}

go deeper

for a junior

Understands capacity is a hidden buffer that grows, and that StringBuilder avoids per-step copies.

for a middle

Distinguishes length vs capacity and knows pre-sizing via the constructor/buildString overload avoids some resizes.

for a senior

Explains geometric growth and amortized O(N), why resizes still cause garbage/jitter, and pre-sizes hot paths deliberately.

for a principal

Frames pre-sizing as a measured trade-off (throughput, tail latency, heap waste, cache), insists on profiling, and reasons about ensureCapacity/trimToSize and allocation budgets across a system.

## length vs capacity - **`length`**: number of characters currently stored (what `toString()` materializes). - **`capacity`**: the size of the internal backing array; always `>= length`. It is an allocation detail, not part of the logical content. ```kotlin val sb = StringBuilder(16) // capacity hint = 16 sb.append("hi") // length = 2, capacity still 16 ``` ## Growth strategy (amortization) When an `append` needs more room than `capacity`, the builder allocates a larger array and copies existing characters. On the JVM the new capacity is typically `oldCapacity * 2 + 2` (geometric growth). Geometric growth is what makes N appends **amortized O(N)**: - Total characters copied across all resizes is bounded by ~2N (a geometric series), not N². - Any single resize is O(currentSize), but resizes happen O(log N) times. Contrast with naive `String +=` in a loop, which copies on **every** step — O(N²). StringBuilder's win is precisely avoiding per-element copies. ## Why pre-size? Even amortized-linear growth still: 1. **Allocates** several intermediate arrays (garbage for the GC). 2. **Copies** characters multiple times. 3. Adds **jitter**: a resize on iteration K is a latency spike. If you can estimate the final length, pass it up front: ```kotlin val n = items.size val out = buildString(capacity = n * 12) { // estimate avg 12 chars/item for (it in items) append(it.code).append('\n') } ``` Now zero resizes occur (assuming the estimate holds): one allocation, no copy churn, flat latency. ## When it actually matters - **Hot paths**: serializers (JSON/CSV), template rendering, log formatting executed millions of times. - **Large outputs**: building multi-megabyte strings. - **Latency-sensitive code**: avoiding GC pauses and resize spikes. For a one-off small string, pre-sizing is noise — favor readability. An over-large capacity wastes heap. The discipline: **measure first** (allocation profiler / JMH), then pre-size only proven hot builders. ## ensureCapacity and setLength `ensureCapacity(min)` grows the backing array to at least `min` without changing length — another way to pre-allocate on an existing builder. `setLength(n)` changes the logical length (truncate or pad with `\u0000`), independent of capacity. `trimToSize()` can shrink the backing array to the current length if you want to release slack memory.

  • If the default growth is already amortized O(N), why pre-size at all?
    To cut transient allocations and copies and remove resize-induced latency spikes — throughput and tail-latency wins in hot paths, even though Big-O is unchanged.
  • What's the risk of always pre-sizing with a huge capacity?
    Wasted heap and worse cache behavior; if you guess far too big you allocate memory you never use. Pre-size to a realistic estimate, not a worst case.

Capacity is like booking a banquet hall sized for your best guest estimate: too small and you keep moving everyone to a bigger room (resize+copy); too big wastes rent.

saying these in an interview costs you the question

  • Confusing length with capacity
  • Claiming each append is O(N) (ignoring amortization)
  • Asserting pre-sizing changes the Big-O complexity
  • Always pre-sizing with arbitrary giant capacities
  • Pre-optimizing without ever profiling

context

resolving links…