System.Text.StringBuilder.Insert uses a lot of memory in certain scenarios

[AlexGhiondea]

Ported from: https://developercommunity.visualstudio.com/content/problem/63747/systemtextstringbuilderinsert.html

Method System.Text.StringBuilder.Insert in a couple with System.Text.StringBuilder.Clear in some cases leads to very dramatic performance degradation and very high memory consumption. For the following test the StringBuilder class is absolutely unsuilable. But this case is only a simple try to reuse object in order to reduce the loading of GC. But the test shows that the result is absolutely opposite to expected.

Test case:

        [TestMethod]
        public void TestStringBuilderInsert()
        {
            const int iterationGranularity = 10000;
            var buffer = new StringBuilder();
            var s = new string(' ', 10);
            Console.WriteLine($"{buffer.Length}->{buffer.Capacity}");
            var sw = Stopwatch.StartNew();
            for (int k = 0; k < 10; k++)
            {
                for (int i = 1; i <= iterationGranularity; i++)
                {
                    buffer.Clear();
                    buffer.Append(s);
                    buffer.Append(s);
                    buffer.Append(s);
                    buffer.Insert(0, s);
                    buffer.Insert(0, s);
                }
                Console.WriteLine($"{sw.ElapsedMilliseconds,5}: {buffer.Length}->{buffer.Capacity}");
            }
            sw.Stop();
        }

Test result:

0->16
   71: 50->100042
  251: 50->200042
  548: 50->300042
 1456: 50->400042
 2807: 50->500042
 4311: 50->600042
 6091: 50->700042
 8007: 50->800042
 9999: 50->900042
12203: 50->1000042

So, the question: If I never put into builder more than 50 characters at the iteration why the Capacity is over 1e6?
Moreover if you use memory profiler, you will understand that the memory usage is much worse that it seems at first glance.
Screenshot of profiler I will attach. Do you think that allocation 100 Gb of memory is enought? I operated only with 10 Mb...

Name Inclusive Allocations Exclusive Allocations Inclusive Bytes Exclusive Bytes Inclusive Allocations %
System.Char[] 200 018 200 018 100 015 401 486 100 015 401 486 66,63

[danmoseley]

1. After the first Clear and Append there is one chunk with 10 chars and default 16 capacity
   |0123456789......|
2. The second Append can't fit in the 16 so it chains a new chunk of 16 , now length 20 capacity 32. Last 12 chars are not used yet.
   |0123456789012345|6789............|
3. The third Append can fit so now length 30 capacity 32 in 2 chunks. Last 2 chars are not used yet.
   |0123456789012345|67890123456789..|
4. Insert has no room in the first chunk so it prepends a new chunk of 16. Interestingly it writes on the front of the chunk, leaving 6 dead space. It sets the m_ChunkOffset of the next chunk to 10. Because Capacity is the m_ChunkOffset of the last block plus the length of itself, this means Capacity is now 42 - the remaining 6 of the 3x16 allocated are potentially dead.
   |0123456789......|0123456789012345|67890123456789..|
5. The second Insert does the same, leaving 4x16 allocated with Capacity of 52 and 2x6 dead spaces.
   |0123456789......|0123456789......|0123456789012345|67890123456789..|
6. Now Clear happens. By policy it does not reduce capacity, but if any chunks become redundant it coalesces them into one new large chunk. Since all chunks are redundant with length of 0, we end up with 1 chunk of 52 chars. At least we lost the 12 dead space.
   |....................................................|
7. Next 3 appends simply write to this chunk. Now length 30, Capacity 52, buffer is 1x52.
   |012345678901234567890123456789......................|
8. Insert happens. It has a policy that if there is space in the chunk already, and it doesn’t have to copy more than twice the default 16 capacity, it will move the contents along. This happens, now there is length 40 capacity 52.
   |0123456789012345678901234567890123456789............|
9. Insert again. Again there is space but it would have to move 40 characters, which is more than 2x16, so instead it prepends a block of 16. As before capacity increases by the length, so we have capacity 62 with chunks of 16 and 52. 6 characters are dead at the front and 12 unused at the end.
   |01234567890......|0123456789012345678901234567890123456789............|
10. Clear defrags again, back to one block of 62 entirely used.
    |..............................................................|

And so forth, every Clear() releases all the blocks and allocates a new block that is 10 larger than last time.

[danmoseley]

@stephentoub @jkotas I assume all the above is by design?

Clearly StringBuilder is optimized for Append. Insert does not try hard to reuse space (it won't move more than 32 characters) so it's fairly easy to end up prepending a new block.

Those prepended blocks are made only as big as needed but no less than the default of 16. So Inserts of less than 16 leave slack space that will remain unused unless there are more inserts into that chunk no more than 16 from the end of it so that its contents get shuffled along. If there's an insert at the end of that block it will create a new block rather than writing to the dead area. eg given
|0123456789012345| (where | is block end) inserting 0123456789 leaves us with |0123456789......|0123456789012345| - 6 dead - and then inserting abc at offset 10 gives us |0123456789......|abc.............|0123456789012345| rather than |0123456789abc..|0123456789012345| as you might expect. That seems like a bug.

[danmoseley]

Also interesting is the behavior of Clear(). By policy it does not reduce capacity, which is fine, but it chooses to make one ginormous block for everything beyond the new length. Possibly that is because it does not want to walk through all the blocks resetting them, but it means Clear() immediately puts long builders into the LOH.

[danmoseley]

@vancem

[vancem]

@danmosemsft - behavior of 'insert' is roughly by design. I say roughly because the design point assumes that insert is rare compared to 'Append' and thus simplicity of implementation has value. If we can improve its behavior with trivial increases in complexity, than that is certainly worth doing. If it is complex, It is not clear to me at least it is the right tradeoff. I would want some data showing that this prepending scenario is at least somewhat important.

I think the more interesting issue is the fact that 'Clear' allocates, and the size of that allocation grows in an unbounded way for a scenario that only needs finite memory. This is what the user is actually complaining about and certainly is reasonable to fix.

The rational for Clear() coalescing buffers is that you keep reusing the StringBuilder (likely if you used Clear once, you probably will do it many times), then you eventually make the buffer big enough that you don't need to allocate at all. This is actually pretty nice behavior for a StringBuilder used as a cache, so think it is worth it.

It occurs to me that you can fix this problem by instead of using the sum of all data blocks, you use the true length of user data. I would probably do something like use min(capacity, length * 1.2), which keeps the behavior exactly like it is except in these weird cases where you inserted and left slack space.

This change is pretty trivial. It is my recommendation.

[danmoseley]

I agree with this. The Clear change makes sense. Insert changes would only be worthwhile if complexity was limited.

If there is no other feedback I will get the Clear changed made.

[danmoseley]

@maryamariyan let's see whether @stephentoub or @jkotas have a concern about the Clear() change, if not you can do this.

[jkotas]

As Vance said. No concerns.

[stephentoub]

Sounds fine.

[danmoseley]

@maryamariyan you might also consider adding an #if DEBUG-only method on StringBuilder that can be invoked in the debugger to produce pictures like
|0123456789......|0123456789......|0123456789012345|67890123456789..| (showing the actual characters, and . for nulls, and the chunk boundaries). When chunks are really large, you could elide bits.
That would have saved me a lot of time figuring out what was going on and I expect it to be useful in future.