Allocations in FormReader

[rynowak]

There's a lot of overhead right now in FormReader

Data is from 3000 requests to https://github.com/aspnet/Performance/tree/dev/testapp/BigModelBinding (x64). The client is doing a form post of about 100 form fields - we kinda consider this the upper bound for the amount of data (and shape of data) that you'd want to put through MVC model binding.

Based on this profile, my napkin math shows about 77mb of allocations from our underlying representation (string + System.Collections.Generic.Dictionary<String, StringValues> + etc) and about 122mb coming from various overheads.

I'm excluding from the 122mb stuff that's in theory covered by @benaadams current work (byte/char buffers, etc).

---

Breaking this down further

Task<string> - 47mb

Cost of being async

Task<Nullable<KeyValuePair<string, string>>> - 28mb

Cost of being async

Dictionary<string, List<String>>, List<string>, string[] - 25mb 12mb 9mb

Scratch data used in KeyValueAccumulator to build the final Dictionary<string, StringValues>

Note that 5mb of string[] allocations are coming from a hashset in MVC, so I excluded it from this total

Some thoughts

We should consider a design for FormReader where we pass the accumulator around or store values in fields/properties instead of returning them via Task<T>. Using async plus Task<T> at such a chatty level is what causes all of this overhead. Using Task on the other hand can avoid this issue.

If we're in a state where we know the entire body is buffered in memory, we might want to just optimize that path to do a synchronous read. That's probably a simpler fix, and it will result in running much more efficient code without any async overhead.

We should also consider changing KeyValueAccumulator to just operate on Dictionary<string, StringValues directly. Having multiple values for the same fields is the less-common case. If we wanted to be smart about it, we could basically build List<T>'s resizing behavior into a StringValues.Add method (returns a StringValues since they are immutable), and then all cases would be pretty optimal.

Right now we're making the worst case the common case by allocating a List<string> and string[] for the common case of a single value per key.

[benaadams]

ValueTask would also be an option here, its also the exact scenario it was designed for.

[benaadams]

#554 + #556 should hopefully resolve all of the above

[rynowak]

Would it be better overall to just make formreader a "push" parser? Using value task might kill the allocs, but it's still a lot of code to run. We could also avoid a second pass on the "output" stream.

Pseudocode:

Stream input = ...;
Stream output = ...; // our buffered stream
byte[] bBuffer = ...;
char[] cBuffer;
Decoder decoder;
FormReader formReader = ...;

while (await input.Read(bBuffer, 0, bBuffer.Length > 0)
{
    var chars = decoder.GetChars(...);
    formReader.Write(cBuffer, 0, chars);

   await output.WriteAsync(bBuffer, 0, bBuffer.Length > 0);
}

output.Seek(Begin, 0);
formReader.Complete();

[rynowak]

I'll do some profiling this AM. I want to see where reading form data fits in to the big picture in a sampling profile

[rynowak]

Some sampling data (same benchmark):

MVC at a high level

The 100% in this case is time spend inside MVC+Routing (only negligible work done in other parts of the pipeline).

The 13.39% AddValueProviderAsync is the time spend reading the form data and building the form value provider. I'll provide a further drill-down here.
The 2.65% AddValueProviderAsync is the jQuery form value provider which parses and duplicates the form data keys for some reasons
The 80.05% InvokeExceptionFilterAsync is model binding + the action code

Some extras:
2.47% InvokeResultFilterAsync is JSON.Net outputting the same data as JSON.
About 1% of time spend on routing and other misc overhead to get to this point.

Breaking down form reading

There's a very small amount of overhead here between MVC and the form reader, I was surprised how small it was. So, reading and parsing the input is 13.29% of the request time. Let's drill in more.

More drill in

The bottom-up breakdown provided by dottrace is pretty instructive:

We're looking at a pretty significant amount of time spend in async/task overhead 11.63% spent in AsyncMethodBuilder and 17.95% in <ReadWordAsync>...s exclusive time. The call tree above clearly shows that all the methods called here were not inlined https://github.com/aspnet/HttpAbstractions/blob/dev/src/Microsoft.AspNetCore.WebUtilities/FormReader.cs#L112 and are not included in the 17.95%. The fact that StringBuilder.Append(char) wasn't inlined seems like a red flag.

Additionally, another big cost is hashing. In the common case, we hash each key twice (once for a TryGetValue and again for an Insert. If we can find a way to avoid rehashing, that would be a significant gain (hashing was 18.75%).

[benaadams]

Is this pre or post change? ValueTask should also kill a lot of the AsyncMethodBuilder work

[benaadams]

Re: 18.75% of the total time being spent on hashing and multi-hashing. The cost is in KeyValueAccumulator for the Dictionary?

@stephentoub proposed a TryAdd here https://github.com/dotnet/corefx/issues/1942 though it would probably need an AddOrUpdate with Func<TKey, TVal, TVal, TVal> on the exists branch that has access to current & new value to avoid a closure, as that's where it does interesting things.

Other approach would be to not use Dictionary and use a different data structure - however that's more complicated as its also the return type (to allow struct enumerable rather than IEnumerable)

Also the Dictionary has had security mitigations applied for this scenario - so a different datastructure would be a complicated choice :(

[rynowak]

@benaadams - well we're using dictionary as a multi-map, so really the best choice for us would be a dedicated multi-map type, or something like python's dict which lets you specify the default value for a key.

A GetOrAdd would certainly help in the common case. You'd want it to be something like:

List list;
dict.GetOrAdd(key, () => new List(), out list);
list.Add(value);

or

var list = dict.GetOrAdd(key, () => new List());
list.Add(value);

It has to be built in to Dictionary<> or else you'll hash twice.

Really for our usage, a sorted list<kvp<string, *>> is probably more efficient overall than hashing. It depends how many values we really want to accept into a form. For MVC that number is around 100, if you're doing more than that, you've got an extreme scenario and your design is crazy.

Example here: https://github.com/aspnet/Mvc/blob/dev/src/Microsoft.AspNetCore.Mvc.ViewFeatures/ViewFeatures/AttributeDictionary.cs

Form-data isn't a good general serialization format, and it's not a replacement for JSON (or others).

[rynowak]

Is this pre or post change? ValueTask should also kill a lot of the AsyncMethodBuilder work

This is without any of your changes I think.

[benaadams]

if you're doing more than that, you've got an extreme scenario and your design is crazy.

Is user input though so want to avoid a data structure that might behave like this did http://www.troyhunt.com/2012/08/fixing-hash-dos-good-and-proper-and.html

[benaadams]

Actually TryAdd would probably cut a lot of these...

[stephentoub]

@benaadams, @rynowak, if the concern is that we need to frequently double-hash, have you considered storing a:

struct StringWithHash
{
    public int HashCode;
    public string Value;
    ...
}

as the key rather than a raw string? You can either compute the hash upfront and store it in the struct, and override GetHashCode to return it, or you can compute the hash lazily in GetHashCode if it wasn't already computed.

[rynowak]

@stephentoub - that introduces yet another tradeoff, on the common-case path we're directly building the dictionary that's going to exposed to the user as IDictionary<string, StringValues>.

A custom dictionary implementation would get us out of this mess, but I'd rather try literally everything else first.

Do you have any thoughts on the AsyncMethodBuilder overhead? Will using ValueTask<> change anything there or is our best bet to rewrite this as a push parser?

[stephentoub]

Do you have any thoughts on the AsyncMethodBuilder overhead?

Where in Async*MethodBuilder? And is this trace on full framework or CoreCLR?

Will using ValueTask<> change anything

Depends where the costs are.

[rynowak]

Snapshot from some similar data - 10% of execution time reading the form is in AsyncMethodBuilder:

This is x64 CoreCLR

Call Tree

https://github.com/aspnet/HttpAbstractions/blob/dev/src/Microsoft.AspNetCore.WebUtilities/FormReader.cs#L188

There's a parsing loop around async reads of a stream

[rynowak]

BTW @benaadams - this benchmark is here https://github.com/aspnet/Performance/tree/dev/testapp/BigModelBinding

npm install -g loadtest to get the driver
dnx web
modify loadtest.ps1 to your liking

[stephentoub]

In that case, yes, I'd expect @benaadams' PR at #556 to help.

[benaadams]

@stephentoub some thoughts, not conclusions...

Not sure storing the hash code is possible; doesn't Dictionary have randomised string hashing for strings that was specifically introduced for aspnet and user-input, would hashing on an int cause issues?

However, string does look like it uses InternalMarvin32HashString to generate the hashcode so it might be ok; but there is a lot of behaviour determined by #if in this area so am not entirely sure what the code paths are.

I did briefly look previously as to whether string could cache its hash before realising the special relationship between string and m_firstChar would mean it would need changes in the C++ (also didn't know whether it was a viable overhead either adding it to every string - or how it would behave with previously interned strings, or whether dictionary would actually use it).

Not changing the public signature (e.g. returning Dictionary<string, StringValue>) but using Dictionary<StringWithHash, StringValue> internally would mean a double hash in the dictionary conversion and an extra dictionary create for the return.

This could be hidden via implementing the interface IDictionary<string, StringValues> but it would need an additional Dictionary<StringWithHash, StringValue> return for those areas that want access to the struct enumerator (which is why its exposed as a Dictionary on the return currently) - then that type would be on the public api :-/

[benaadams]

@rynowak it wasn't happy with the wacky date format ;)

So set it to 1st Jan, but have the tests working now

[benaadams]

@rynowak I'm getting degraded perf with #556; but there is a lot of changes in it so investigating.

[benaadams]

Hitting disk; due to different Length behaviour with fixed sized MemoryStream, correcting.

[benaadams]

Current

With #556 (Buffers + ValueTask)

With both #554 + #556 (+ Accumulator)

So they all give a boost

[benaadams]

BufferAsync breakdown

[benaadams]

Revisiting the original allocation issue from 30,000 requests (x10 on original)

ValueTask dramatically reduces the Task allocations to around 1% of the current (7MB vs 750MB)

[benaadams]

Re: Dictionary hashing on non string types https://github.com/dotnet/coreclr/issues/2279

[Tratcher]

Summary:

• Switching from Tasks to ValueTasks would help allocations, but requires writing your own state machine at 10x the code & complexity. Maybe Roslyn can do this for us? Proposal: arbitrary task-like types returned from async methods dotnet/roslyn#7169
• There are still string hashing issues in the KeyValueAcumulator