What is the optimal StringBuffer initial capacity for inputs with drastically varying lengths?

Question

Good afternoon all, I'm using a java.lang.StringBuilder to store some characters. I have no idea how many characters I'm going to store in advance, except that:

1. 60% of the time, it is only (exactly) 7 characters
2. 39% of the time, it is (roughly) 3500 characters
3. 1% of the time, it is roughly 20k characters

How do we go about calculating the optimal initial buffer length that should be used?

_{Currently I'm using new java.lang.StringBuilder(4000) but that's just because I was too lazy to think previously.}

Answer 1

There are two factors here: time and memory consumption. The time is mostly influenced by the number of times java.lang.AbstractStringBuilder.expandCapacity() is called. Of course the cost of each call is linear to the current size of the buffer, but I am simplifying here and just counting them:

Number of expandCapacity() (time)

Default configuration (16 characters capacity)

• In 60% of the cases the StringBuilder will expand 0 times
• In 39% of the cases the StringBuilder will expand 8 times
• In 1% of the cases the StringBuilder will expand 11 times

The expected number of expandCapacity is 3,23.

Initial capacity of 4096 characters

• In 99% of the cases the StringBuilder will expand 0 times
• In 1% of the cases the StringBuilder will expand 3 times

The expected number of expandCapacity is 0,03.

As you can see the second scenario seems much faster, as it very rarely has to expand the StringBuilder (three time per every 100 inputs). Note however that first expands are less significant (copying small amount of memory); also if you add strings to the builder in huge chunks, it will expand more eagerly in less iterations.

On the other hand the memory consumption grows:

Memory consumption

Default configuration (16 characters capacity)

• In 60% of the cases the StringBuilder will occupy 16 characters
• In 39% of the cases the StringBuilder will occupy 4K characters
• In 1% of the cases the StringBuilder will occupy 32K characters

The expected average memory consumption is: 1935 characters.

Initial capacity of 4096 characters

• In 99% of the cases the StringBuilder will occupy 4K characters
• In 1% of the cases the StringBuilder will occupy 32K characters

The expected average memory consumption is: 4383 characters.

---

TL;DR

This makes me believe that enlarging the initial buffer to 4K will increase the memory consumption by more than two times while speeding up the program by two orders of magnitude.

The bottom line is: try! It is not that hard to write a benchmark that will process million strings of various length with different initial capacity. But I believe a bigger buffer might be a good choice.