Runtime: Investigate queueing string references for StringBuilder

[jamesqo]

Currently, in StringBuilder.Append(string) we copy all of the characters of the input string to our internal buffers. Then, we copy all of these characters again to the output string if ToString is called. So basically, we're copying each input string twice.

We can reduce this to 1 copy. Instead of eagerly copying the string when Append is called, we can queue it up into a list of string references we have. Then, during ToString, we will copy the part from our char buffers before that string, copy the string, then copy the part from our buffers before the next string, etc.

Here is a visualization:

new StringBuilder()
    .Append('a')
    .Append("reallylongstring" + new string(Enumerable.Repeat('g', 100).ToArray()))
    .Append(',');

// Before

InternalBuffers: ['a', 'r', 'e', 'a', ... 'g', 'g', '.']

// After

InternalBuffers: ['a', '.']
StringQueue: ["reallylongstringggggg...gg"] // Only 8 bytes to store!

It is a little overly simplistic because StringBuilder actually uses a linked list of char buffers for internal storage, but I hope the point still gets across.

Downsides

• It will complicate the indexer logic more
• We will have to add an extra field or 2 to StringBuilder
• The string reference itself may be more expensive to store than the string's characters
  
  
  
  • However, we can easily work around this by checking the length of the string, and calculating whether that takes up 8 bytes (the size of a 64-bit reference) or more. If yes, then we queue it; if no, then we copy its individual characters.
  
  

Other Notes

I made a proof-of-concept PR last month to corefxlab, so you can see more how this is implemented if you're interested: https://github.com/dotnet/corefxlab/pull/976

[jamesqo]

/cc @jkotas, @KrzysztofCwalina, @AlexGhiondea, @vancem; interested to hear what you four think about this if you have time. Unlike the corefxlab PR, it will not just benefit strings, but all types except char (things like ints, objects, etc. are all ToString'd and go through Append(string) anyway).

[AlexGhiondea]

This sounds like a very interesting idea to optimize Append! Thanks for bringing it up!

How does this work with other operations on StringBuilder? You mentioned the indexer, but what about Replace? If you do a replace you need to traverse and potentially adjust the pointers in the StringQueue (did I get that right - dont have the code in front)? I assume the same for Insert.

What kind of improvement did you see for Append with this change?

[jamesqo]

@AlexGhiondea

You mentioned the indexer, but what about Replace? If you do a replace you need to traverse and potentially adjust the pointers in the StringQueue (did I get that right - dont have the code in front)? I assume the same for Insert.

Good point, I had not thought about Insert and Replace.

• We can handle inserts by adding an extra int along with every string reference. This will represent the index into another array that contains the offset + count in the string that's relevant.

InternalBuffers: ['a', '.']
StringQueue: [{
    str: "reallylongstringggggg...gg",
    index: 1, // Copy after 1st char
    partitionIndex: 0 // Partitions[0] contain relevant offset + count, or -1 if we're appending the whole string
}]
Partitions: [{
    offset: X,
    count: Y
}]

Although we are adding an extra int field along with every string reference, this should not degrade perf since those 4 bytes are padded anyway.

• Replace we can handle similarly by adjusting the offset + count pointers, I believe. If the replaced string differs in length from the original, then we could insert it into the StringQueue or put it in a new array somewhere.

[vancem]

First, as a general point, I think it is very interesting to try to optimize StringBuilder. In particular I think a more important optimization to have a 'StringBuilder.Write(Stream, Encoding) that allows you to write a StringBuilder to a stream without ever generating the intermediate string. Then I would use that to enlighten TextWriter to use it for its Write() methods (both normal and formatted).

However the optimization of being lazy (simply remembering the string rather than copying it), is also interesting. However it is VERY likely to be WORSE when the strings are small (It is easier to simply copy the bytes than it is to deal with the references. Thus I would recommend if you do this having a length check (only remember the reference if the string is larger than say 32bytes or so (we can tune this)).

It would be interesting to simply get some statistics on what size strings typically get passed to StringBuilder.Append(). I am assuming typically they are small (under the 32 byte case), and thus the optimization being suggested may only have benefit in relatively rare cases. This argues that we should not increase the complexity of StringBuilder much to achieve this.

Note that to keep complexity low, we should not bother with this optimization for rare operations like Replace or Insert. The should probably just do the copy and use the existing code (the goal being keeping the code as simple as possible).

It is a worthy experiment, but we do have to tread carefully. I would start by trying to get at least SOME data on how big strings you pass to StringBuilder.Append() typically are (at least on some scenarios).

One final comment is that I think is a very good idea to add some other operations to StringBuilder that make it more like a 'Mutable String'. In particular it should have a SubString() (which returns a StringBuilder) and Compare methods. Thus in very high performance cases, you could make APIs take StringBuilder instead of string and thus again, avoid the copy. This needs to be thought through carefully, but is another worthy line of attack.

[jamesqo]

@AlexGhiondea @vancem I'm trying to implement this myself now that dotnet/runtime#17890 was merged. Out of curiosity, do you know why StringBuilder uses a linked list of char[] rather than a char[][] to store the buffers?

[vancem]

I would advice caution and a methodical approach here. Stringbuilder has a wide variety of important use scenarios, and it would be very easy to unintentionally damage an important scenario.

As mentioned above, keeping references to strings will trade off the performance in the short string case (which is frankly what I would expect to be the common case), so we must have good information that suggests that that change is an overall win.

To answer your question, StringBuilder is a linked list because it is tuned for the small string case (where you only have one chunk). Even in the large multi-chunk case, by FAR the operation that is executed on StringBuilder is 'Append' and THAT only needs access to the last chunk. Random access is really not needed and a two level structure would slow that down.

I would strongly recommend that you concentrate first on optimizations that do not require a change in the data structure. In particular

1. The ability to write the StringBuilder to a stream without first creating a String.
2. The SubString and Compare methods mentioned above.

But before starting any of this, I think we should be reviewing the performance benchmarks for StringBuidler and confirming that we like the coverage it provides. Beefing this up would be a welcome first step.

The other useful thing would be to get some information from 'real scenarios' that indicate 'hot spots' where optimization would be helpful (and ideally we would have a benchmark that tests this). This can drive the discussions about tradeoffs as we make changes.

@jkotas

[danmosemsft]

@jamesqo happened to come across this. Are you still interested in finding optimizations in StringBuilder? I like the incremental, data-based approach @vancem suggests.

[jamesqo]

@danmosemsft The StringBuilder code is quite complex so it would take a while for me to implement this. Maybe this can be marked up-for-grabs?

[danmosemsft]

@jamesqo - for sure, just wanted to check first.

[stephentoub]

This is a theory about a potential perf improvement to potentially investigate. There are many such things that could be looked at... we don't need issues tracking them. If someone finds a performance improvement somewhere and wants to submit a PR for it, that's welcome. I also notice that the associated PR in corefxlabs was closed (https://github.com/dotnet/corefxlab/pull/976). Thanks.