Consider using SortedList instead of Dictionary in HttpHeaders

[geoffkizer]

The Dictionary we allocate in HttpHeaders for the headers table seems to use a significant amount of memory. Since the headers table itself is typically not that large, it seems reasonable to use SortedList instead and trade off reduced memory usage for a small amount of added CPU cost on update and retrieval -- I doubt this added CPU cost is significant, whereas the memory savings may be significant.

[ghost]

Tagging subscribers to this area: @dotnet/ncl
See info in area-owners.md if you want to be subscribed.

Issue Details

---

The Dictionary we allocate in HttpHeaders for the headers table seems to use a significant amount of memory. Since the headers table itself is typically not that large, it seems reasonable to use SortedList instead and trade off reduced memory usage for a small amount of added CPU cost on update and retrieval -- I doubt this added CPU cost is significant, whereas the memory savings may be significant.

Author:	geoffkizer
Assignees:	-
Labels:	area-System.Net.Http
Milestone:	Future

[MihaZupan]

This may require a custom SortedList implementation (or improvements to the existing collection).
Using the existing implementation as-is would likely be worse (for example it boxes the enumerator)

[geoffkizer]

Well that's unfortunate. Aside from boxing the enumerator, are there other known issues?

[MihaZupan]

An insertion has O(n) runtime, so I think that disqualifies this type of collection from a DOS security perspective as well.

[geoffkizer]

An insertion has O(n) runtime, so I think that disqualifies this type of collection from a DOS security perspective as well.

I'm not sure it matters. We limit the size of the response headers that we will accept, so there's a bound on the total number of headers we will add. While O(n^2) isn't great, it's not necessarily a DOS as long as n is smallish.

[geoffkizer]

Another alternative here might be to simply have an unsorted list of key value pairs. This has cheap insertion but makes both lookup and removal expensive. That might not be a bad tradeoff though. And if we did it this way, we could actually preserve the original header ordering, which seems like a nice benefit.

For stuff like YARP we would want to just enumerate the raw headers and not worry about grouping by header name, which means that "raw enumeration" for these sorts of scenarios would be cheap as well. Unfortunately we defined the NonValidated collection to group by header name as well...

[MihaZupan]

While O(n^2) isn't great, it's not necessarily a DOS as long as n is smallish.

Right, but as of right now n could still reach a few thousand by default which isn't ideal.

[Clockwork-Muse]

An insertion has O(n) runtime, so I think that disqualifies this type of collection from a DOS security perspective as well.

.... do we insert headers singly, or as a range?

[danmoseley]

Using the existing implementation as-is would likely be worse (for example it boxes the enumerator)

Are you referring to the non generic SortedList? SortedList<K,V> should not do this.

[MihaZupan]

The generic as well. The enumerator is a struct, but the type is not publicly exposed so the GetEnumerator returns an IEnumerator.

runtime/src/libraries/System.Collections/src/System/Collections/Generic/SortedList.cs

Line 555 in af726fc

public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()

[karelz]

Triage:

• Would be nice to save some memory if we don't hurt CPU too much
• It may help with order of headers - we had few issues in the space

Further design discussion:

• Idea: Could we have a list/array as backing field and create something like Dictionary for string lookups? (they are rare)
• In extreme case we might want to add another API, which would return multiple headers (not happening today), unsorted
• Or perhaps just add another IEnumerable<string, string>

[geoffkizer]

Similarly, ConcurrentDictionary<K, V> boxes its enumerator: https://docs.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2.getenumerator?view=net-6.0

I noticed this in the same trace. It's a small impact in this case because we only enumerate the concurrent dictionary when scavenging connections.

I'm not sure why these collections were implemented so that their enumerators must be boxed. Is this simply an oversight? Can we fix it? It's a breaking change, but a very small one...

[gfoidl]

For a dictionary approach maybe dotnet/aspnetcore#31360 is also of interest (the AdaptiveCapacityDictionary).

[stephentoub]

It's a breaking change, but a very small one...

It's a binary breaking change. I don't think it's that small. Anyone enumerating one of these today would fail at run time.

Similarly, ConcurrentDictionary<K, V> boxes its enumerator:

#25448

[geoffkizer]

It's a binary breaking change. I don't think it's that small. Anyone enumerating one of these today would fail at run time.

Makes sense, thanks for clarifying.