Card 06/ 09
String Concatenation in a Loop: What += Costs
A thousand values take a moment; ten thousand take far more than ten times as long.
Because a string cannot change, row += value builds a whole new string holding everything row had plus the new piece. Inside a loop that copies everything built so far on every pass, so the total work grows with the square of the number of pieces.
A method that builds a line of comma-separated values out of a thousand values takes a noticeable moment. The same method over ten thousand values takes far more than ten times as long:
String row = "";
for (String value : values) {
row += value + ",";
}row += value cannot add to row, because nothing can add to a string. What it does instead, on every pass, is build a whole new string containing everything row already held plus the new piece, and then point row at that.
| Pass | Characters copied | Strings left for the garbage collector to free |
|---|---|---|
| 1 | The first piece | 1 |
| 2 | Everything so far, again | 2 |
| n | Everything so far, again | n |
The work per pass grows with what has already been built, so the total grows with the square of the number of pieces. Ten times the input is a hundred times the copying, which is why ten thousand values take far more than ten times as long as a thousand.
A single + between two values is fine and always has been: the cost only appears when the result of one concatenation is the input to the next. That is what a loop does, and it is the one place to reach for a StringBuilder instead, which appends into one growing buffer.
← → move through sections and cards