Frozen collections in .NET 8

[giscus[bot]]

Frozen collections in .NET 8

.NET 7 was freshly released but Microsoft does not sleep. .NET 8 is already in the making and I want to showcase to you one new area where the dotnet team is working on Frozen collections.
So let's have a look at what frozen collections are and how they are working.

https://steven-giesel.com/blogPost/34e0fd95-0b3f-40f2-ba2a-36d1d4eb5601

[Issung]

Why have they created only FrozenSet and not FrozenList for example? Comparing the performance of List and FrozenSet seems unfair, you should compare HashSet and FrozenSet no? Please let me know what detail I am missing.

[linkdotnet]

There is no FrozenList at the moment. I will expand on that part in the article.

I had a look at the .net8-alpha.1 build and also checked the GitHub tracker. It doesn't seem that there will be a FrozenList (or FrozenCollection) soon.

[fabianoliver]

I agree that the benchmark unfortunately doesn't look too meaningful. Lists aren't exactly designed for lookups/contains operations and do so in O(N), sets are generally designed to be faster (often O(1)).

A fair comparison would probably be a classic HashSet, as well as maybe an ImmutableSet compared against a frozen set.

It'd also be quite interesting to explore how the frozen state is achieved, as that almost certainly has some performance overhead at some point too. Eg does it just create a defensive copy of the underlying data (which might mean construcition is O(N)'ish, vs. O(1) of just wrapping a set into some IReadOnlySet)? Can it do anything smarter than that?

[linkdotnet]

I added the HashSet to the mix to indicate that the FrozenSet outperforms the HashSet.

I will add the GitHub-Tracker link, where also the PR is linked. The proposal show-cases some of the performance benefits. I also had a look at the Pull Request. Some data structures like int have specific hot-path optimizations.

[wilbit]

Meaningless benchmarks.
It would make sense to compare FrozenSet and ImmutableHashSet, for instance.

[linkdotnet]

Oh, I don't think they are meaningless. Anyway, benchmarks are only one dimension of the whole topic. Benchmarks don't mean anything out of context. If you are not operating in a tight loop, do 200 nanoseconds matter? Probably not. The benchmarks were one way of supporting the argumentation, that those new types are specialized and do bring performance gains.

Anyway, I added also ImmutableHashSet to the mix. So you can directly compare FrozenSet against ImmutableHashSet as well as the "normal" HashSet.

[wilbit]

I would suggest to update CODE section in Benchmark chapter, because now it is not clear what stays behind numbers of LookupHashSet and LookupImmutableHashSet.

[linkdotnet]

@wilbit Yeah that sounds reasonable. Let me merge that together.

[lucasven]

In order to make the post more accurate, the transformation to each of the subtypes (frozen, immutable and hash) should also have benchmarks, since the guy that developed it said it would take longer to setup the immutable set

[linkdotnet]

I will think of that. The purpose of a frozen set (or dictionary) is that you create it at the beginning of your application and use it through out its lifetime. For sure creating a set is more expensive than a list.

[linkdotnet]

Hey @lucasven I added a passage about the performance of creating those set's in comparison to our List<int>. Thanks for the input.

[lucasven]

thanks a lot, it really makes a huge difference, so it should be used with care, right?

[linkdotnet]

Exactly. As this new collection is intended for special use cases I would check if this applies to your needs.
If you know you have a static set of data you regularly will look up, it is worth checking.

For example, if you have a rather static list like in FileExtensionContentTypeProvider. If there so no need to be extensible and can be a FrozenDictionary.

PS: This particular instance of course is extensible and it would change the API if they would switch over to the frozen Dictionary. But I do hope you get my point, where the new collection could be applicable.

[MSBassSinger]

Is this implemented only in C# or is it part of MSIL? Most of the C# languages tricks/shortcuts, when viewed in MSIL, are not really an improvement.

[linkdotnet]

As far as I see it, it is "just" C# code. Here is the PR, which adds the frozen collections:
https://github.com/dotnet/runtime/pull/77799/files

[opwernby]

private const int OneHundred = 100;

Why....?

[Issung]

Perfectly valid thing to do so he can easily bump his tests to other numbers, like 1000, which I think he should do to get a better sample size and it will still be lightning fast regardless. Variable just needs a better name like Iterations or CollectionSize, etc.

[linkdotnet]

I bumped it to 1000 as well as renamed it.

[tetryds]

Would help a lot if you did not use the var keyword so that the types are explicit and easy to discern.

[linkdotnet]

Done

[tetryds]

Your two hashset definitions seem to be exactly the same. Also, discarding result variables can lead to dead code optimizations that can greatly skew the results. A more ideal approach would be for example using that result to increment a field.

[linkdotnet]

Thanks. Corrected it.

[felixcollins]

C# is getting bloated. I'm going back to C to get some actual work done. :-)

[JayNitzel]

The ReadOnlyList in your implementation is, like you put it, only a view to a reference.
To have it as a true read only list, you need to have it point to a new instance of the list:

ReadOnlyCollection<int> readonlyList = new List<int>(normalList).AsReadOnly();
or
ReadOnlyCollection<int> readonlyList = normalList.ToList().AsReadOnly();

I can't speak for the performance though.

[linkdotnet]

Of course, my examples are simplified. In a normal situation, you would return this from a method. Anyway calling ToList().AsReadOnly() will allocate a completely new list. I am not sure what is the benefit here. Can you elaborate on this one?

Your approach goes more in the direction of an ImmutableList. Mine and your example are both readonly lists. Kind of like a view in SQL. If the underlying object changes, you can see those changes. Read-only just means you are not allowed to add or remove or whatnot.

[JayNitzel]

Hi, yes, the benefit of creating a new list is that you are no longer referencing an existing list, thus no longer being affected by changes to that list.
I think that in this way the readonlyList would work just like a frozen list: read only and unbound from the normalList.

[geeknoid]

The reason why there isn't a FrozenList is that ImmutableArray already serves the same role.

Whereas the other ImmutableXXX types are designed to provide reasonably efficient way to create modified clones of themselves, ImmutableArray is not and works in fact like the FrozenXXX collections. Unfortunately, renaming ImmutableArray to FrozenList would be a breaking change, so we'll have to live with the name as-is.

[linkdotnet]

Ahh, thanks for clarifying @geeknoid. Maybe one more question regarding the motivation:

If I understood correctly, backward compatibility is the main driver for creating a new type rather than extending/changing.
For example, in the FrozenDictionary, returning ref readonly T would be a breaking change.

What major or breaking change was the driver for creating a FrozenSet instead of extending ImmutableXXX?

[geeknoid]

@linkdotnet ImmutableSet and ImmutableDictionary are designed to be immutable and to make it easy to create slightly modified copies of a given instance at a reasonable cost. So imagine you create an immutable set with a million entries in it. You cannot mutate this set since it is immutable. Now, you need a new set with 1 extra entry. You could recreate the set from the ground up, which would be very expensive. Instead, you can start from your original immutable set and apply a delta to create a new distinct set instance which under the covers shares most of the state from the original set. You use less memory this way, and it takes much less time to create the new instance.

The problem is that in order to allow this mode of operation, ImmutableDictionary and ImmutableSet are complex implementations which introduce substantial compromises in overall read performance as a trade-off for this ability to make cheap delta clones.

FrozenSet and FrozenDictionary do not provide the delta clone ability, they are optimized strictly for fast read performance. You pay more for creation, you pay more for making a clone with modifications, as a trade-off for getting faster steady state read performance.

[linkdotnet]

Crystal clear explanation, thanks @geeknoid

[Kymveis]

Thanks! It explains when should I use which

[koplenov]

Nailing functionality to language? :D
Too bad c# won't outgrow Nemerle, but what is described above is the base of Cojure and many other functional languages

[MSBassSinger]

Nailing functionality to language? :D

Too bad c# won't outgrow Nemerle, but what is described above is the base of Cojure and many other functional languages

Thanks for starting my day with a good laugh. That statement is profoundly ignorant.

Nemerle, a C# wannabe, was abandoned by JetBrains and is now just some Russian hack as low quality as everything else Russian.

Clojure is a derivative of Lisp running on a JVM, dependent on outdated Java.

Both Nemerle and Clojure together barely have market share, and both lag behind C#/.NET in functionality, performance, and time-to-market.

[erdihu]

Does anybody know if these new Frozen collections will be thread safe to read?

[linkdotnet]

The frozen collections, like other immutable collections, are constructed once and then, throughout their lifetime, get only read. So I don't see where reading should lead to any issues.

[erdihu]

I have had a chance to experience with these new collection types and found that a read optimized FrozenSet performs much better than a ImmutableHashSet. I have not tested for creation times of the collections since those numbers were not important for my use case. However, I think it would be much better if we could initiate a FrozenSet from a Span. Consider the following use case which is repeated multiple times in a minute:

1. Read data from a database. The length of the result set is known ahead.
2. Since we cannot create a FrozenSet dynamically, let's create an intermediary array to hold the information. We can choose to rent an array from an array pool to minimize allocations.
3. Fill the array, which may be longer in length than the actual data.
4. Since we cannot convert the array to a FrozenSet as is, we can get a Span with the correct length.
5. Span cannot be converted to FrozenSet...

After checking the implementation of the FrozenSet, I saw that it is using HashSet under the hood. So I just went by using an HashSet instead of a rented array.