Use IndexOf in StringBuilder.Replace(string, string, ...) #81098
Conversation
StringBuilder.Replace(string, string, ...) currently walks character-by-character to find the next location of the oldValue. This change adds the use of MemoryExtensions.IndexOf to search for the oldValue, and only falls back to the character-by-character walk when it nears and needs to account for a chunk boundary. It also switches to track replacement indices using more stack space and the array pool (via ValueListBuilder) rather than less stack space and array allocations.
stephentoub
added
area-System.Runtime
tenet-performance
stephentoub
requested review from
GrabYourPitchforks,
adamsitnik and
tannergooding
ghost
assigned 
|
Tagging subscribers to this area: @dotnet/area-system-runtime Issue DetailsStringBuilder.Replace(string, string, ...) currently walks character-by-character to find the next location of the oldValue. This change adds the use of MemoryExtensions.IndexOf to search for the oldValue, and only falls back to the character-by-character walk when it nears and needs to account for a chunk boundary. It also switches to track replacement indices using more stack space and the array pool (via ValueListBuilder) rather than less stack space and array allocations. Using the benchmark from #80952:
Fixes #80952
|
src/libraries/System.Private.CoreLib/src/System/Text/StringBuilder.cs
Outdated
Show resolved
Hide resolved
|
@adamsitnik, the assert issue is fixed. Can you take another look? Thanks. |
| @@ -1934,8 +1934,7 @@ public StringBuilder Replace(string oldValue, string? newValue, int startIndex, | |||
|
|
|||
| newValue ??= string.Empty; | |||
|
|
|||
| Span<int> replacements = stackalloc int[5]; // A list of replacement positions in a chunk to apply | |||
| int replacementsCount = 0; | |||
| var replacements = new ValueListBuilder<int>(stackalloc int[128]); // A list of replacement positions in a chunk to apply | |||
There was a problem hiding this comment.
great use case for ValueListBuilder 👍 I am surprised that the temporary array allocation survived for so long in this repo ;)
runtime/src/libraries/System.Private.CoreLib/src/System/Text/StringBuilder.cs
Lines 1953 to 1958 in 1b22d37
| { | ||
| indexInChunk++; | ||
| --count; | ||
| if (StartsWith(chunk, indexInChunk, count, oldValue)) |
There was a problem hiding this comment.
this method is the only method using StartsWith, would we gain anything from inlining it? Would you mind running the benchmarks if you still have this branch built on your machine? If not, it's not worth your time (I am just curious and it's really hard to suggest any improvements for this PR)
There was a problem hiding this comment.
if you still have this branch built on your machine
I don't. We can follow-up on your question separately, though.
StringBuilder.Replace(string, string, ...) currently walks character-by-character to find the next location of the oldValue. This change adds the use of MemoryExtensions.IndexOf to search for the oldValue, and only falls back to the character-by-character walk when it nears and needs to account for a chunk boundary. It also switches to track replacement indices using more stack space and the array pool (via ValueListBuilder) rather than less stack space and array allocations.
Using the benchmark from #80952:
Fixes #80952