Repository navigation
Iterating over a string builder by index becomes ~exponentially slow for large builders #24395
Description
This is motivated by this issue originally opened against MSBuild, which internally in its reuseable string builder factory compares string builders by index. It happens to start from the end, but that doesn't seem to matter. The opener observed this can be enormously slower that creating a string first.
Using this benchmark program I get the following results:
BenchmarkDotNet=v0.10.11, OS=Windows 10 Redstone 3 [1709, Fall Creators Update] (10.0.16299.98)
Processor=Intel Xeon CPU E5-1620 0 3.60GHz, ProcessorCount=8
Frequency=3507174 Hz, Resolution=285.1299 ns, Timer=TSC
[Host] : .NET Framework 4.7 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.2600.0
DefaultJob : .NET Framework 4.7 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.2600.0
Method | N | Mean | Error | StdDev |
---------------- |----- |-------------:|------------:|------------:|
ToStringFirst | 100 | 2.028 us | 0.0403 us | 0.0465 us |
IndexedBackward | 100 | 21.399 us | 0.4123 us | 0.5063 us |
IndexedForward | 100 | 23.020 us | 0.4461 us | 0.4581 us |
ToStringFirst | 1000 | 43.210 us | 0.5032 us | 0.4202 us |
IndexedBackward | 1000 | 323.959 us | 7.3317 us | 6.8581 us |
IndexedForward | 1000 | 335.538 us | 6.3072 us | 5.8997 us |
ToStringFirst | 5000 | 217.657 us | 4.1058 us | 4.3931 us |
IndexedBackward | 5000 | 6,542.491 us | 131.7964 us | 223.8003 us |
IndexedForward | 5000 | 6,301.246 us | 102.0129 us | 90.4317 us |
64 bit
BenchmarkDotNet=v0.10.11, OS=Windows 10 Redstone 3 [1709, Fall Creators Update] (10.0.16299.98)
Processor=Intel Xeon CPU E5-1620 0 3.60GHz, ProcessorCount=8
Frequency=3507174 Hz, Resolution=285.1299 ns, Timer=TSC
[Host] : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2600.0
DefaultJob : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2600.0
Method | N | Mean | Error | StdDev |
---------------- |----- |-------------:|------------:|------------:|
ToStringFirst | 100 | 1.944 us | 0.0369 us | 0.0410 us |
IndexedBackward | 100 | 22.955 us | 0.2145 us | 0.1902 us |
IndexedForward | 100 | 22.674 us | 0.2493 us | 0.2332 us |
ToStringFirst | 1000 | 40.258 us | 0.4520 us | 0.4007 us |
IndexedBackward | 1000 | 325.231 us | 4.6369 us | 4.3374 us |
IndexedForward | 1000 | 332.819 us | 8.0014 us | 7.4845 us |
ToStringFirst | 5000 | 200.979 us | 1.2610 us | 1.1179 us |
IndexedBackward | 5000 | 7,950.240 us | 157.2641 us | 253.9522 us |
IndexedForward | 5000 | 8,137.382 us | 161.3316 us | 251.1739 us |
Clearly indexing is going to have a lot of overhead such as bounds checking. But I would expect that to be proportional to N, and we see a big jump when N gets large. Related to fragmentation of the SB? Can we do better?
Activity
danmoseley commentedon Dec 8, 2017
MSBuild has this code here and here
This would not show up unless the MSBuild is expanding eg., large lists (such as the content of a large-ish file read in as items) which is not uncommon but quite likely isn't showing up in the ASP.NET scenarios we're looking at right now.
@davkean
AndyAyersMS commentedon Dec 8, 2017
You might see different behavior on Core than on Desktop here.
danmoseley commentedon Dec 8, 2017
ToString (or string comparison) is measurably faster on Core, but indexing seems just as slow.
danmoseley commentedon Dec 8, 2017
Oops, desktop was on 32 bit. Let me try 64 bit.
danmoseley commentedon Dec 8, 2017
Edited to add 64 bit for desktop above. Now Core and Desktop are basically identical.
danmoseley commentedon Dec 8, 2017
The discrepancy is much smaller when the StringBuilder is presized (gist):
Both 1000 and 5000 are approximately 4x, suggesting a more natural linear effect consistent with eg., bounds checks.
danmoseley commentedon Dec 8, 2017
This is presumably because every index has to walk the chain of chunks, checking the offset for each until it finds the one with the indexed location. In the 5000 case above, there are 250K characters so 32 chunks of 8000 characters. On average it has to loop 16 times to find the right chunk - for every index. No doubt this was a conscious compromise when making stringbuilder chunky. @vancem ?
AndyAyersMS commentedon Dec 9, 2017
When we did stuff like this in the past (for chunky sparse bitvectors in a now-defunct compiler) we would cache the result of the last index lookup; subsequent index values tended to be "nearby". Random access would still be slow but this happens less often, but sequential accesses were now good.
This might require some invalidation logic elsewhere if the chunk structure can be messed with.
danmoseley commentedon Dec 9, 2017
Another option is to store the chunk offsets in a shared array that could be binary searched. But I like your idea, it is simple and unlikely to hurt other cases.
danmoseley commentedon Dec 11, 2017
The user always works against the StringBuilder that owns the end chunk and that has is a singly linked list of chunks back to the start (so incidentally the smaller the index the more blocks to traverse to find it).
In the first idea, there would be two fields in the end StringBuilder: the last accessed index and a pointer to the chunk for it. Whenever the chunk chain is changed (by setting
m_ChunkPrevious) those would need to be invalidated with some O(1) math.This scheme could also speed up
FindChunkForIndexandFindChunkForByteby reducing (on average halving) the space they need to walk (using those might not actually set the last accessed, just read it). But for indexing anywhere near the last index, it would change O(chunks) to O(1).@vancem @jkotas does this seem a reasonable approach and unlikely to measurably affect other perf?
Ideally these 2 fields could somehow be put to use in the StringBuilders representing the chunks other than the final one.
jkotas commentedon Dec 11, 2017
Would it be better to just document that StringBuilder indexer is not fast?
StringBuilder is designed for building strings. It is not designed to inspect them - it will never work great for that. And trying to make it work ok for that just hurts the primary purpose what it is meant to be used for.
danmoseley commentedon Dec 11, 2017
Indexing as fast as a string or array would compromise its goals for sure. I just hate to think of people getting O(n^2) indexing when a few field gets and sets could get it to O(n) and potentially help other operations like StartsWith. If not the pit of success then at least the pit of mediocrity.
I looked at Azure profiler data and fortunately the usage of get_Chars, set_Chars, StartsWith, FindChunkForIndex are vastly lower than Append, etc. So I'll close this for now...
Alois-xx commentedon Dec 12, 2017
This should definitely be fixed. I have some build targets which have 8 minutes of "compile" time due to a large string with 900KB length which is compared in MSBuild properties. The resulting string is always the same but trying to intern it takes much longer than to create it and be done with with it. The actual work is < 40s which has definitely some room for improvement.
The MSBuild syntax to batch targets could definitely help to prevent stuffing a large list into a single string but the syntax is rather awkward and only understood by a few. This did lead to less than optimal msbuild targets which were wasting a significant amount of time and computing power at our dev shop.
davkean commentedon Dec 12, 2017
@Alois-xx It would be better to file that issue over on MSBuild so that we can fix its interning behavior. Fixing that issue at the StringBuilder level isn't the right change.
3 remaining items
Alois-xx commentedon Dec 12, 2017
@danmosemsft: Sure. I need something to work with over christmas.
But first I deleted the the single line in our msbuild target file which was only there for a consistency check where no one remembers what it is actually good for.
jkotas commentedon May 4, 2018
@MohammadHamdyGhanem The efficient string builder iterator was proposed and being worked on by @vancem in https://github.com/dotnet/corefx/issues/21248 / dotnet/coreclr#17530.
jkotas commentedon May 5, 2018
None of the proposals considered had the characteristics you are describing. The latest version of the proposal is in fact enumerator. Check the proposed implementation in dotnet/coreclr#17530.
stephentoub commentedon May 5, 2018
The first proposal didn't have those characteristics, either.