[API Proposal]: Provide optimized read-only collections

[geeknoid]

EDITED on 10/30/2022 by @stephentoub

Here's what I recommend we do:

namespace System.Collections.Immutable
{
 public static partial class FrozenCollectionExtensions
 {
 public static FrozenDictionary<TKey, TValue> ToFrozenDictionary<TKey, TValue>(
 this IEnumerable<KeyValuePair<TKey, TValue>> source, IEqualityComparer<TKey>? comparer = null)
 where TKey : notnull;

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

 public abstract class FrozenDictionary<TKey, TValue> :
 IDictionary<TKey, TValue>, IReadOnlyDictionary<TKey, TValue>, IDictionary
 where TKey : notnull
 {
 internal FrozenDictionary(); // not designed for external extensibility

 public static FrozenDictionary<TKey, TValue> Empty { get; }

 public IEqualityComparer<TKey> Comparer { get; }
 public abstract int Count { get; }

 public abstract ImmutableArray<TKey> Keys { get; }
 public abstract ImmutableArray<TValue> Values { get; }

 public bool ContainsKey(TKey key);
 public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value);
 public ref readonly TValue this[TKey key] { get; }
 public abstract ref readonly TValue GetValueRefOrNullRef(TKey key);

 public void CopyTo(KeyValuePair<TKey, TValue>[] destination, int destinationIndex);
 public void CopyTo(Span<KeyValuePair<TKey, TValue>> destination);

 public abstract Enumerator GetEnumerator();
 public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
 {
 public readonly KeyValuePair<TKey, TValue> Current { get; }
 public bool MoveNext();
 }
 }

 public abstract class FrozenSet<T> : ISet<T>, ICollection,
#if NET5_0_OR_GREATER
 IReadOnlySet<T>
#else
 IReadOnlyCollection<T>
#endif
 {
 internal FrozenSet(); // not designed for external extensibility

 public static FrozenSet<T> Empty { get; }

 public IEqualityComparer<T> Comparer { get; }
 public abstract int Count { get; }

 public abstract ImmutableArray<T> Items { get; }

 public bool Contains(T item);

 public void CopyTo(Span<T> destination);
 public void CopyTo(T[] destination, int destinationIndex);

 public abstract bool IsProperSubsetOf(IEnumerable<T> other);
 public abstract bool IsProperSupersetOf(IEnumerable<T> other);
 public abstract bool IsSubsetOf(IEnumerable<T> other);
 public abstract bool IsSupersetOf(IEnumerable<T> other);
 public abstract bool Overlaps(IEnumerable<T> other);
 public abstract bool SetEquals(IEnumerable<T> other);

 public abstract Enumerator GetEnumerator();
 public struct Enumerator : IEnumerator<T>
 {
 public readonly T Current { get; }
 public bool MoveNext();
 }
 }
}

A few notes for discussion:

• Assembly. I've prototyped this to live in System.Collections.Immutable.dll. These types are immutable, differing from the existing immutable collections primarily in that the existing ones are primarily "persistent" and are designed with mutable-like members that return a new instance with the mutation rather than changing the original. Including these in S.C.Immutable.dll has the added bonus that we ship that assembly downlevel, and we'd like for these collections to be widely available.
• Namespace. I've similarly included the types in the System.Collections.Immutable namespace, but we could choose something else, like System.Collections.Frozen. Note that the public surface area of these types depends on ImmutableArray<T>.
• Ref-returning Members. One of the design goals here is to enable all means of reading to be efficient; that includes when the values stored in a dictionary are large structs. Thus, as with ReadOnlySpan<T>, the indexer here returns a ref readonly T rather than just a T. There aren't safety concerns here as the underlying storage is immutable. For advanced usage, this also exposes a GetValueRefOrNullRef that mirrors the same method for Dictionary<,> we expose from CollectionsMarshal (but there, we put it on CollectionsMarshal because a growing dictionary can make the ref erroneous, and that's not a problem here).
• Abstract base types. As with types like Dictionary<,> and HashSet<>, these types are not meant to be extended arbitrarily. However, because they optimize for the exact set of inputs frozen into the collection, it's important to be able to customize the implementation based on the inputs. Thus, the collections are abstract, with a ToFrozenDictionary/Set factory that produces the right internally-derived implementation. Developers consuming the types only concern themselves with the FrozenDictionary<,>/FrozenSet<,> types and the associated extension methods, and the abstractness is just an implementation detail that's required to be public.
• Extension methods. I've put the two ToFrozenDictionary/Set extension methods on a new FrozenCollectionExtensions type. We could instead introduce two new non-generic FrozenDictionary/Set types, with one extension method each (which is closer to how the existing immutable collections work), or we could put these on to some existing type in the same namespace.
• Immutable interfaces. I did not make these types implement IImmutableDictionary/Set. While it'd be possible, with the "mutating" methods constructing ImmutableDictionary/Set, it doesn't seem valuable, and also seems potentially misleading.
• Non-generic interfaces. Dictionary<,> implements IDictionary and SortedSet<> implements ICollection, so I chose to also implement those on FrozenDictionary<,> and FrozenSet<>, respectively.

---

Background and motivation

There are many scenarios where collections are initialized during startup, or during major state changes in the application, and are not mutated afterwards. Taking advantage of this pattern can lead to substantial improvements in overall access performance of the collections.

Additionally, the overwhelming majority of dictionaries and sets use strings and int as key types. Providing collections that are optimized for these types can also contribute to substantial performance gains relative to the canonical Dictionary<K,V> and HashSet types.

API Proposal

Please see https://github.com/geeknoid/FrozenCollections for an API and implementation which delivers substantial performance gains relative to the built-in .NET collections for long-live read-only collections. The implementation spends extra time during the construction phase of these collections in order to increase lookup performance. The README file shows current performance gains using .NET 6.

The Freezer class provides a number of extension methods which make it a snap to turn an existing dictionary or set into a frozen dictionary or set.

In addition to the freezing functionality, the frozen dictionary API also provides the GetByRef method which makes it possible to get a byref to a value in a frozen dictionary, making dictionaries holding large value types efficient.

API Usage

var d = new Dictionary<string, int>(...);
var frozen = d.Freeze();

Alternative Designs

No response

Risks

No response

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

Issue Details

---

Background and motivation

There are many scenarios where collections are initialized during startup, or during major state changes in the application, and are not mutated afterwards. Taking advantage of this pattern can lead to substantial improvements in overall access performance of the collections.

Additionally, the overwhelming majority of dictionaries and sets use strings and int as key types. Providing collections that are optimized for these types can also contribute to substantial performance gains relative to the canonical Dictionary<K,V> and HashSet types.

API Proposal

Please see https://github.com/geeknoid/FrozenCollections for an API and implementation which delivers substantial performance gains relative to the built-in .NET collections for long-live read-only collections. The implementation spends extra time during the construction phase of these collections in order to increase lookup performance. The README file shows current performance gains using .NET 6.

The Freezer class provides a number of extension methods which make it a snap to turn an existing dictionary or set into a frozen dictionary or set.

In addition to the freezing functionality, the frozen dictionary API also provides the GetByRef method which makes it possible to get a byref to a value in a frozen dictionary, making dictionaries holding large value types efficient.

API Usage

var d = new Dictionary<string, int>(...);
var frozen = d.Freeze();

Alternative Designs

No response

Risks

No response

Author:	geeknoid
Assignees:	-
Labels:	api-suggestion, area-System.Collections
Milestone:	-

[huoyaoyuan]

How does it compare to builder of immutable collections?

[eiriktsarpalis]

How does it compare to builder of immutable collections?

Immutable collections are a bit different, since they have been designed with persistent updates in mind. As such lookup in, say, ImmutableDictionary is O(log N), regardless how it was constructed. It would be interesting to see benchmarks comparing System.Collections.Generic with Immutable and optimized read-only collections.

cc @krwq

[GSPP]

I find it very common to have read-only dictionaries. This is more than 95% of my usage (I'm sure it varies by codebase). It could be worth creating specialized collections for that. Build once and use many times.

This could provide additional performance due to a number of factors:

• Free list management can be removed.
• The version field can be removed.
• Optimized building from an IEnumerable, list or array. Potentially save on version updates, pre-size better and maybe algorithms are faster for adding if there are no free lists to consider. Maybe a faster bulk creation mechanism can be devised.
• The collections could be a struct.

Another related change would be to use a simpler mapping function from hash code to bucket. A while ago it was the slow modulo. This was replaced with a faster solution. It could be replaced with power-of-two table sizes and a binary and operation. While this was not deemed appropriate in the "mainstream" collections, it could now be.

Frankly, I'm surprised that the framework internally uses the publicly-exposed general-purpose collections so much. I'd kind of expect that specialized, possibly unsafe collections could pay off in aggregate. But maybe it is smart to dogfood on the public collections.

I've personally written me a "fast" dictionary. I copied the framework code and then optimized it, achieving major gains which payed off in my application under specialized circumstances. This was many years ago, so the framework now contains many of these optimizations and then some. But the basic idea remains useful.

[theodorzoulias]

Frankly, I'm surprised that the framework internally uses the publicly-exposed general-purpose collections so much. I'd kind of expect that specialized, possibly unsafe collections could pay off in aggregate. But maybe it is smart to dogfood on the public collections.

@GSPP AFAIK there is another negative consequence from the standard Dictionary<K,V> being used extensively by the framework internally. It impedes the approval of API proposals for this class, for reasons related with memory bloat. For example for this reason we can't have the extremely handy and efficient Dictionary.GetOrAdd method. Btw the suggested workaround is potentially corruptive, and so it's dangerous to use. Adding a public freezable dictionary class wouldn't solve this problem. The solution would be to avoid dogfooding popular public components, and use internal components instead!

[geeknoid]

@GSPP Please check out the implementation I linked to, which takes advantage of what you suggest.

A benefit I wasn't expecting when starting fiddling with this code is the optimizations that become possible when you know the kind of key you're dealing with, as opposed to relying on fully generic comparers. In particular, when dealing with string keys, my code goes through some effort to reduce the overhead of computing the hash code. Specifically, since I know all the keys up front, I look through the keys to find the shortest possible slice of text across the strings which produces distinct substrings. I do this using "left-aligned" and "right-aligned" comparisons, which helps with strings that have similar prefixes or similar suffixes. Running my tests, I found that in a great many cases, I can cut down the number of characters to hash down to 2 characters per string, rather than the normal mode of hashing the entirety of the strings. This delivers a substantial perf boost at runtime.

[theodorzoulias]

@geeknoid your idea of optimizing the hashcode calculation for strings would be more useful IMHO if it was offered as a custom IEqualityComparer<string> implementation. This would allow it to be used anywhere hashing is required, like in HashSet<T>s, in LINQ GroupBy operations etc. By baking it into the implementation of a specific collection, the opportunities for exploiting this functionality are limited.

[Clockwork-Muse]

custom IEqualityComparer<string> implementation.

Currently equality (and other) comparers are static and maintain no state. You can't implement this sort of optimization that way - at minimum you need to store the minimum length to hash/compare, if not a custom hash collection. Or potentially oddball things like not even using hashing for small collections. Which means:

HashSet<T>

would (potentially) have to invalidate it on every add.... but there's no method to call to do that.

LINQ GroupBy

This is essentially a running collection modification

the opportunities for exploiting this functionality are limited.

It's relatively expensive to calculate the optimization, and it's really only useful when you know the collection isn't going to be modified for the duration of its use....

[geeknoid]

@theodorzoulias As @Clockwork-Muse points out, what enabled me to perform these kinds of comparer-level optimization stems from the fact the collections are frozen and as such we're willing to burn cycles up front doing all this extra processing, in order to make later reads faster. The pattern doesn't really work for mutable collections (at least given how the mutable collections are currently implemented and the extension points they expose). You could certainly create some wrappers for the mutable collections which track all adds/removes and update some state kept in a stateful comparer and that might give you some benefit, but that'd be completely unrelated implementation to what I have here.

[theodorzoulias]

@geeknoid I was thinking about something like this:

class FastHashStringComparer : IEqualityComparer<string>
{
 public FastHashStringComparer(IEnumerable<string> trainingValues) { }
}

The implementation of this comparer would study the provided trainingValues, and it would decide what slice of the string values provides enough entropy for generating hashcodes of sufficient quality.

I could then use this comparer to create (for example) a lookup for my list of items, like this:

List<Item> items = GetItems();
FastHashStringComparer comparer = new(items.Select(x => x.Category));
ILookup<string, Item> lookup = items.ToLookup(x => x.Category, comparer);

Querying this lookup should be faster compared to querying a lookup backed by the default string comparer.

Or I could use it with a LinkedDictionary<K,V> that I found in a third-party NuGet package, to cover some special need. Lots of options.