Frozen collection follow-ups

[stephentoub]

https://github.com/dotnet/runtime/pull/77799 adds new FrozenDictionary and FrozenSet types. These are in decent shape but not yet ready to ship. Several follow-ups are required:

• [x] #87964 The initial use cases for these types was for long-lived processes, where overall it's a better use of resources to spend more time at construction time to optimize the data structures and algorithms used for later data access. However, the current construction time is one or more orders of magnitude more than for the standard dictionary/set types. We need to a) invest in driving down those construction costs, and b) consider making the default performance of ToFrozenDictionary/Set as close that of Dictionary/Set as possible via an additional optional parameter to these methods, e.g.

  
  public static FrozenSet<T> ToFrozenSet<T>(this IEnumerable<T> source, IEqualityComparer<T>? comparer = null,

• double constructionOptimization = default // pick a better name );

  
  When `0.0`, this would effectively default to creating a FrozenSet/Dictionary that just wrapped a HashSet/Dictionary, providing the same FrozenSet/Dictionary semantics but primarily just as a wrapper for a HashSet/Dictionary, such that the only additional costs were cloning of the data (assuming the Items/Keys/Values properties remain as they are today, they could be lazily-created on first need).  On a scale from 0.0 to 1.0, the larger the double value, the more optimization would be performed at construction time, enabling the caller to choose how much time is spent at construction vs how fast subsequent data access can be made, with 1.0 meaning construction would take the longest in exchange for fastest data access.  Having the default be fast construction would make this the least surprising for casual use and would avoid falling into pits of failure in the average case; consumers willing to spend more time at construction because they know their processes will be long-lived can then opt-in to longer startup times.

• [x] #86719 https://github.com/dotnet/runtime/labels/blocking-release The current design has Items/Keys/Values properties that return ImmutableArray<>. This is to enable access to the data as a ReadOnlySpan<>, indexibility, via refs, and with very fast enumeration. This does, however, place a requirement on implementations that they either store the keys/values/items separately and in contiguous memory or that implementations maintain a second copy of the data that does so. If we'd be willing to give up on the ReadOnlySpan<> and indexing capabilities, these types should instead be changed to some FrozenEnumerable<>-like type that would allow different implementations to vary how the data was stored.
• [x] Small collections There's currently an optimized implementation for empty collections, but not for other small sizes, e.g. <= 8 elements. We should investigate adding simple implementations that don't do any hashing or other complicated storage for small sizes. This includes looking at various code bases / sources of information to determine the most common sizes to be optimized for, e.g. is it worth having a dedicated implementation for collections of just 1 or 2 elements.
• [ ] Other data structures and algorithms Would a perfect hashing implementation yield any benefits? Would tries be useful in some situations for strings? Should we consider doing reflection emit code gen in some circumstances?
• [x] Trimming friendliness The factory nature here means that every implementation needs to be kept by a trimmer regardless of whether it's actually used (though a trimmer should, even if not today, be able to get rid of implementations unique to Ts where it can see those Ts are never used). We thus need to be thoughtful about how many custom implementations there are, and potentially have one or more feature switches to exclude one or more that add only incremental value, potentially opting them out by default.
• [ ] Source generation If/when Roslyn source generators support some kind of mechanism that would allow a source generator to look at constant data in the C# file and augment ToFrozenSet/Dictionary call sites in some manner, it would be beneficial if the optimizations could be performed at compile-time, feeding something into an optional parameter to ToFrozenSet/Dictionary to enable them to be fast, with all the work supplied at build time. This would likely also require more work on the API to make the existing types extensible, which is something we've actively avoided today.

[andrewjsaid]

Would tries be useful in some situations for strings? Should we consider doing reflection emit code gen in some circumstances?

After I saw that routing in ASP.NET Core uses reflection emitted Trie, I also spent some time attempting to implement an alternative to stringly-keyed ASCII FrozenDictionary in a similar way. After lots of attempts, I no longer think it's possible for Tree structures to be faster than Hash based data structures in general purpose use-cases. However the IL-Emit Trie did indeed come out faster than the FrozenDictionary in my small experiments.

https://github.com/andrewjsaid/trie

[rampaa]

It's something we'll consider for .NET 9.

Is it being considered for .NET 9?

[stephentoub]

It's something we'll consider for .NET 9.

Is it being considered for .NET 9?

Unlikely at this point.

[sanghel-orbyta]

Any chance of considering adding something like:

• FrozenSortedSet<T>
• FrozenSortedDictionary<T>
• IEnumerable<T>.ToFrozenSortedSet<T>
• IEnumerable<T>.ToFrozenSortedDictionary<T> ?

Perhaps via analogous methods such as those for .ToImmutableSortedDictionary/Set()

[stephentoub]

Any chance of considering adding something like:

• FrozenSortedSet<T>
• FrozenSortedDictionary<T>
• IEnumerable<T>.ToFrozenSortedSet<T>
• IEnumerable<T>.ToFrozenSortedDictionary<T> ?

Perhaps via analogous methods such as those for .ToImmutableSortedDictionary/Set()

What functionality are you hoping for here? Specifically just that the exposed Items and Key/Value arrays are sorted and that enumerating happens in that order as well?

[sanghel-orbyta]

@stephentoub exactly.

I have a ConcurrentDictionary that I accumulate into and then need to read from ordered by key, as quickly as possibile (using this for some UDP traffic re-ordering, the dictionary is a ConcurrentDictionary<long, (int packetOffset, int packetLength)>, that keeps track of offsets in a Memory<byte> buffer... linear, I know, but I'm not expert enough to know how to do this with a ring buffer with pooled memory alocations avoiding GC... any ideas on this?).

Right now I'm using .ToImmutableSortedDictionary(), but from what I've understood, a FrozenDictionary would be quicker to enumerate.

[stephentoub]

What functionality are you hoping for here? Specifically just that the exposed Items and Key/Value arrays are sorted and that enumerating happens in that order as well?

@stephentoub exactly.

Thanks. In that case, I don't think this warrants or necessitates new types. We could just have the creation of a FrozenDictionary/Set sort the arrays at construction, either using a type's built-in notion of ordering (via IComparable) which could be done without any API additions, or via an extra overload that accepts a Comparer to use for that purpose.

[sanghel-orbyta]

In that case, I don't think this warrants or necessitates new types. We could just have the creation of a FrozenDictionary/Set sort the arrays at construction

That would definitely work, thanks for the feedback @stephentoub .