Optimise HtmlEncode and HtmlDecode to produce less garbage#27250
Optimise HtmlEncode and HtmlDecode to produce less garbage#27250ViktorHofer merged 2 commits intodotnet:masterfrom benjamin-hodgson:HtmlEncode-optimisation
Conversation
| HtmlEncode(value, index, sb); | ||
| return StringBuilderCache.GetStringAndRelease(sb); | ||
| var sb = new PooledStringBuilder(value.Length); | ||
| try |
There was a problem hiding this comment.
You do not need try/catch. It is ok to turn the pooled into garbage on exceptions.
|
|
||
| #endregion | ||
|
|
||
| private struct PooledStringBuilder |
There was a problem hiding this comment.
We have a helper class like this here: https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/Text/ValueStringBuilder.cs that has a few more optimizations. Try using that instead.
There was a problem hiding this comment.
It looks like ValueStringBuilder is backed by a Span - what's the best way of writing a Span<char> to a TextWriter? I don't want to just loop over the span and call Write because that'll be slow, and I don't want to copy the span into an array because that'll generate garbage.
There was a problem hiding this comment.
void Write(System.ReadOnlySpan<char> buffer) method.
| return value; | ||
| } | ||
|
|
||
| StringBuilder sb = StringBuilderCache.Acquire(value.Length); |
There was a problem hiding this comment.
Is the project still using StringBuilderCache after this change? If not, it can be removed from the .csproj. If yes, should those places be changed to ValueStringBuilder as well?
There was a problem hiding this comment.
It's used elsewhere (eg). I'd be happy to fix those other usages too, in a separate PR, if you like.
| { | ||
| output.Write(value); | ||
| return; | ||
| } |
There was a problem hiding this comment.
How valuable is this check? In cases where we do have something to encode, we end up paying for the extra checking.
There was a problem hiding this comment.
I just copied this from the existing string overload of HtmlEncode above. My gut tells me that the case when value doesn't have any encoding characters is quite common, probably more common than when it does. Plus index is used to copy the prefix of the string quickly, see line 106
|
FYI there's a much more efficient HtmlEncoder implementation here https://github.com/dotnet/corefx/blob/01fa16ffd618846a913cad719269c8bb441ceb28/src/System.Text.Encodings.Web/src/System/Text/Encodings/Web/HtmlEncoder.cs. |
| } | ||
| } | ||
|
|
||
| public void WriteTo(TextWriter writer) |
There was a problem hiding this comment.
This method is very specialized. It should rather be .AsReadOnlySpan() property. It will handle all future uses that need to get the string as Span.
There was a problem hiding this comment.
Are you sure? That sounds like it could be a bit risky: when the underlying array gets resized the old one gets returned to the pool but the ReadOnlySpan will still have a reference to it.
There was a problem hiding this comment.
This is internal type, not a public API. There are many ways you can use it in a wrong way. For example, you can accidentally pass it by value and create a second copy of it to introduce the same problem as if you use AsReadOnlySpan incorrectly by accident.
|
@davidfowl Thanks, I didn't know about |
|
|
||
| [MethodImpl(MethodImplOptions.AggressiveInlining)] | ||
| private void Clear() | ||
| public void Clear() |
There was a problem hiding this comment.
Nit: It may be better to call it Dispose now that it is public.
There was a problem hiding this comment.
I assume going further and adding IDisposable would be too heavyweight for this -- especially since "leaking" is not a big deal.
There was a problem hiding this comment.
Right. Also, interfaces do not really make sense for ref types - you cannot cast the ref type to the interface.
There was a problem hiding this comment.
A tangent: I haven't tried this, but I imagine a ref struct with an interface might have some limited use in the context of constrained generics. That is, if you had
ref struct Foo : IBar {}
void Baz<T>(T baz) where T : IBaryou should be able to write
Baz(new Foo());There was a problem hiding this comment.
Although: I guess you're probably not allowed to use a ref struct as a type argument, because you don't know whether the method will use the T in a way that you can't use a ref struct (eg casting it to object).
| <ProjectReference Include="..\..\System.Diagnostics.Debug\src\System.Diagnostics.Debug.csproj" /> | ||
| <ProjectReference Include="..\..\System.Security.Principal\src\System.Security.Principal.csproj" /> | ||
| <ProjectReference Include="..\..\System.Runtime\src\System.Runtime.csproj" /> | ||
| <ProjectReference Include="..\..\System.Buffers\src\System.Buffers.csproj" /> |
There was a problem hiding this comment.
Do you actually need to add this reference? Span is in System.Runtime for netcoreapp - you do not need to reference System.Buffers to get it.
There was a problem hiding this comment.
Ah, good catch, thanks! I needed in an earlier commit, because I was using ArrayPool directly, but that's been removed now.
| _chars = initialBuffer; | ||
| _pos = 0; | ||
| } | ||
| public ValueStringBuilder(int initialCapacity) |
There was a problem hiding this comment.
Can you please add some test(s) to ValueStringBuilderTests for your new functionality?
|
|
||
| if (string.IsNullOrEmpty(value)) | ||
| { | ||
| output.Write(value); |
There was a problem hiding this comment.
This will presumably throw if value is null. But, I see previously it would have also thrown doing value.Length.
There was a problem hiding this comment.
Seems we should probably throw ANE if value is null.
There was a problem hiding this comment.
I'm now throwing an ArgumentNullException, but I'm concerned that this is technically a breaking change (see my comment). What do you think?
There was a problem hiding this comment.
We are generally OK with changing NRE->ANE.
There was a problem hiding this comment.
Oh I see you changed back. That's fine too.
| return; | ||
| } | ||
|
|
||
| if (!StringRequiresHtmlDecoding(value)) |
There was a problem hiding this comment.
The code was not previously doing this check. If we have to do it, it might be nice for StringRequiresHtmlDecoding to return the index of the first character to decode, so HtmlDecode can copy up to that point verbatim, the same optimization happening with IndexOfHtmlEncodingChars.
Without that, I am not sure whether this will make it slower or not.
There was a problem hiding this comment.
It was doing this check before, in the HtmlDecode(string value) method (which was being called by this one).
There was a problem hiding this comment.
Ah right. Nevertheless it seems that HtmlDecode could have the same ability to start at an index returned from StringRequiresHtmlDecoding. Future change maybe.
| vsb.Append(s); | ||
| } | ||
|
|
||
| var resultSpan = vsb.AsReadOnlySpan(); |
There was a problem hiding this comment.
We renamed AsReadOnlySpan to AsSpan.
Also, nit: we don't use resultSpan anywhere. Change to:
var resultString = new string(vsb.AsSpan());
| _chars = initialBuffer; | ||
| _pos = 0; | ||
| } | ||
| public ValueStringBuilder(int initialCapacity) |
|
|
||
| using System.Buffers; | ||
| using System.Diagnostics; | ||
| using System.IO; |
There was a problem hiding this comment.
This using should not be needed anymore.
| sb.Dispose(); | ||
| } | ||
|
|
||
| [SuppressMessage("Microsoft.Usage", "CA1806:DoNotIgnoreMethodResults", MessageId = "System.UInt16.TryParse(System.String,System.Globalization.NumberStyles,System.IFormatProvider,System.UInt16@)", Justification = "UInt16.TryParse guarantees that result is zero if the parse fails.")] |
There was a problem hiding this comment.
Since you are optimizing allocations, you can also replace uint.TryParse(value.Substring below with uint.TryParse(value.AsSpan below; and delete this SuppressMessage - it does not seem to be relevant anymore.
|
Rebased. Apologies for the delay in getting this back up to speed. The tests were failing because I changed the code to throw |
| using System.IO; | ||
| using System.Runtime.CompilerServices; | ||
| using System.Text; | ||
| using System.Buffers; |
There was a problem hiding this comment.
I think this import isn't used any more actually. Good catch, thanks!
|
@benjamin-hodgson, the System.Web.Tests.HttpUtilityTest/HtmlEncode_TextWriter(decoded: null, encoded: "") test is failing in CI |
|
@ahsonkhan Yep I know. I think I'm going to undo the |
|
I'm looking into further optimizations in the WebUtility class. Please stand by. |
|
@ViktorHofer Ah thanks very much for looking into that. Those results look really good - is the improvement due to https://github.com/dotnet/coreclr/issues/18005 ? If so should #29921 be closed now? |
danmoseley
left a comment
There was a problem hiding this comment.
Maybe open an issue for htmldecode to be passed the index found by StringRequiresHtmlDecodin, as an optimization
|
The latest commits remove another string allocation and also unnecessary unsafe code where boundary checks are eliminated by the CLR. I benchmarked with my commits and without them and they improve throughput by about 10%. I noticed that the test string wasn't really very expressive and changed it to something which hits all the different paths in the implementation: Before
After
|
ViktorHofer
left a comment
There was a problem hiding this comment.
Big regression (see results)
| output.Append("&#"); | ||
|
|
||
| // Use the buffer directly and reserve a conservative estimate of 10 chars. | ||
| Span<char> s = output.AppendSpan(10); |
There was a problem hiding this comment.
nit: avoid single character variable names.
| { | ||
| parsedSuccessfully = uint.TryParse(value.AsSpan(entityOffset + 1, entityLength - 1), NumberStyles.Integer, CultureInfo.InvariantCulture, out parsedValue); | ||
| } | ||
| bool parsedSuccessfully = value[entityOffset + 1] == 'x' || value[entityOffset + 1] == 'X' |
There was a problem hiding this comment.
This is difficult to parse and read. Can we cache some of these in a local? Like value[entityOffset + 1]?
| var sb = new ValueStringBuilder(value.Length); | ||
|
|
||
| // Prepend non encoding part | ||
| ReadOnlySpan<char> prefixSpan = value.AsSpan(0, index); |
There was a problem hiding this comment.
Nit: I think it would look better without an extra local:
// Prepend non encoding part
sb.Append(value.AsSpan(0, index));
| } | ||
|
|
||
| private static unsafe int IndexOfHtmlEncodingChars(string s, int startPos) | ||
| private static int IndexOfHtmlEncodingChars(string input) |
There was a problem hiding this comment.
Can we use ReadOnlySpan<char> here instead of string? Especially since we already call value.AsSpan multiple times at the call site.
What do the numbers look like for Decoding? ValueStringBuilder that is created for encoding is guaranteed to have insufficient size (modulo bucketing done by ArrayPool) because of encoding always grows. Try changing the line that creates the ValueStringBuilder to |
15ms average improvement! Nice! |
|
With @jkotas suggestion of increasing the buffer size (15ms) and switching to stackalloc for small inputs (10ms) I was able to make it faster than it currently is in master. Before (master)
After (update: latest commit now)
|
| HtmlDecode(value, sb); | ||
| return StringBuilderCache.GetStringAndRelease(sb); | ||
| char[] rawBuffer = null; | ||
| // We expect the encoded pattern to be at least twice as large as the decoded one. |
There was a problem hiding this comment.
I think that this is wrong assumption. I think that there are going to be just a very few escaped characters in the typical case.
There was a problem hiding this comment.
okay, I will trim the check down to 256. do you think the 80 for the encode check is conservative enough or should we maybe even increase it to 100 / 128?
| HtmlDecode(value, sb); | ||
| return StringBuilderCache.GetStringAndRelease(sb); | ||
| char[] rawBuffer = null; | ||
| Span<char> buffer = value.Length < 256 ? |
ViktorHofer
left a comment
There was a problem hiding this comment.
There's not much point in approving my own changes but here I go ![]()
|
Should we remove the ValueStringBuilder ctor overload with its tests now that we are not using it anymore or keep it as it might bring value for future scenarios? |
I think so. |
|
Thanks @benjamin-hodgson for your work, I'm done my changes here now. Both throughput and allocation figures are now better than on master therefore I believe this PR is now in a mergeable state. Thanks @jkotas and others for hints. @stephentoub it would be great if you could glance over the changes before we merge this. thanks! |
| char[] rawBuffer = null; | ||
| Span<char> buffer = value.Length < 80 ? | ||
| stackalloc char[256] : | ||
| (rawBuffer = ArrayPool<char>.Shared.Rent(value.Length + 200)); |
There was a problem hiding this comment.
A comment on how these constants were chosen would be helpful. In particular, I don't understand the relationship between 80 <-> 256 and value.Length <-> value.Length + 200. Do we have any corpus of inputs we can use to determine good estimates here, e.g. that on average 1% of characters need to be encoded, or something similar, and then do the math on value.Length?
There was a problem hiding this comment.
I added comments to explain why we chose these values. The fixed 200 additional characters could/should be transformed into a relative value but for that we first need more information on the distribution of input strings for HtmlEncode & HtmlDecode. See offline thread with Lee.
There was a problem hiding this comment.
I want to merge this in its current state as getting data might take some time. We can refine the buffer sizes afterwards.
| if (rawBuffer != null) | ||
| { | ||
| ArrayPool<char>.Shared.Return(rawBuffer); | ||
| } |
There was a problem hiding this comment.
Why are we doing it this way rather than the previous approach of passing the initial capacity into VSB and having it do the ArrayPool access? With this approach, we're going to hold onto this ArrayPool buffer no matter how many times the VSB grows, whereas if the VSB did it, it would return the original buffer to the pool when it first grew out of it.
| Span<char> buffer = value.Length < 80 ? | ||
| stackalloc char[256] : | ||
| (rawBuffer = ArrayPool<char>.Shared.Rent(value.Length + 200)); | ||
| var sb = new ValueStringBuilder(buffer); |
There was a problem hiding this comment.
Same comments/questions as above.
| // Use the buffer directly and reserve a conservative estimate of 10 chars. | ||
| Span<char> encodingBuffer = output.AppendSpan(10); | ||
| valueToEncode.TryFormat(encodingBuffer, out int charsWritten, provider: CultureInfo.InvariantCulture); | ||
| output.Length -= (10 - charsWritten); |
There was a problem hiding this comment.
I think it'd be helpful to put the 10 that's used multiple times into a const that describes how it was picked, e.g. const int MaxInt32Digits = 10 or something like that. I assume valueToEncode can't be negative at this point? If it could, max digits would need to be 11.
|
|
||
| // Use the buffer directly and reserve a conservative estimate of 10 chars. | ||
| Span<char> encodingBuffer = output.AppendSpan(10); | ||
| valueToEncode.TryFormat(encodingBuffer, out int charsWritten, provider: CultureInfo.InvariantCulture); |
There was a problem hiding this comment.
It shouldn't be necessary to specify the culture here, and doing so will make it slower.
do the same optimisation for HtmlDecode remove now-unneeded reference Add tests for new ValueStringBuilder methods
Reduce allocation and remove unsafe code Use bigger buffer size and use stackallocation for small inputs Optimize decode code path and output writing
|
@benjamin-hodgson I squashed yours commits together so that the PR is ready to be merged, not squashed. |
|
@ViktorHofer OK, no problem. Thanks! |
This fixes https://github.com/dotnet/corefx/issues/13893. I'd noticed in a project of mine that the
TextWriteroverload ofWebUtility.HtmlEncodewas unexpectedly generating garbage.I added a
System.Buffersproject reference to theSystem.Runtime.Extensionscsproj and wrote a simple implementation ofStringBuilderbased onArrayPool, as suggested by @jkotas in #13875.I benchmarked this implementation and while it appears to produce no garbage (except for the
stringthat it returns) it does seem to run around 10-20% slower. I'm keen to get some input from you guys on what might be going on here.Benchmark code (using BenchmarkDotNet):
And the results: