Immo Landwerth and Andrew Arnott: Inside Immutable Collections
- Posted: Mar 19, 2013 at 11:08 AM
- 41,454 Views
- 12 Comments
Immutable Collections are a new set of immutable types for .NET. We covered the high level aspects of this new technology a few months back when Erik Meijer interrogated (in his friendly way) the PM of the project, Immo Landwerth, and the lead developer, Andrew Arnott. Since this time, they have received a lot of feedback (thank you!) and have also been busy refining and optimizing their code. Here, Andrew and Immo go deep into how this stuff works and why it's designed the way it is. We talk about how to use these new types and how not to. We learn what the team has been working on and may work on for future releases. As is the case with any Going Deep episode, this is long form conversation and, well, deep. Tune in!
More on Immutable Collections (download the preview versions via NuGet):
The NuGet package preview includes these types:
- ImmutableStack<T>
- ImmutableQueue<T>
- ImmutableList<T>
- ImmutableHashSet<T>
- ImmutableSortedSet<T>
- ImmutableDictionary<K, V>
- ImmutableSortedDictionary<K, V>
Interfaces for each of these types are also defined to facilitate exchange of immutable collection types that may be implemented differently to optimize for very specific performance or memory requirements.
See Andrew's blog for more detailed information (on immutable types for .NET and more. Lots of great info...).
Comment on the Post
Already have a Channel 9 account? Please sign in
More episodes in this show
-
Programming the Cloud with Actors: Inside ActorFx
-
Immo Landwerth and Andrew Arnott: Inside…
-
Nikolai Tillmann and Peli de Halleux: Inside Code…
Follow the Discussion
Oops, something didn't work.
What does this mean?
Following an item on Channel 9 allows you to watch for new content and comments that you are interested in. You need to be signed in to Channel 9 to use this feature.What does this mean?
Following an item on Channel 9 allows you to watch for new content and comments that you are interested in and view them all on your notifications page.sign up for email notifications?
Why not allow user to select implementation using a factory function? The allocator most often knows how the collection will be used. For example that indexer or add must be O(1). The current AVL solution doesn't sound too good for paging and slicing. How would I create a slice of an ImmutableList? Did you look at Dlang ranges?
And .ToList() is commonly used on IEnumerables to materialize them from linq or other enums to make sure they are O(1) indexed. Not only to get a safe copy to foreach over. Will you add a ToImmutableList()? And will that be a noop if the IEnumerable is already an ImmList?
An immutable list where add/indexer is O(1) with an array backing store would be nice. The allocation time would be amortized. The extra space created in array realloc could be used for non concurrent adds or adds in creator thread.
I loved to hear that you are finallt working on language support for immutable types.
Hi Marcus,
That's a lot of interesting questions! Let me take them one by one.
I haven't looked at Dlang ranges -- Andrew might have more context there. In general, we are not convinced that offering a knob for every option is the right thing. In the end, our goal is delivering a list of collection types that work for a wide variety while still being easy to use and agree upon. The Roslyn use case we brought up is quite special -- Roslyn has super tight perf constraints that most developers will not have. Once you are in this boat, chances are you want to have more control than what we can realistically offer in the BCL.
For those case we still offer the immutable interfaces as the exchange currency.
Our library offers an extension method for IEnumerable<T> that provides ToImmutableList().
If you call ToImmutableList() on an immutable list, you will get back the same instance, assuming it uses the default comparer. If it doesn't we change the comparer. In any case, that's an O(1) operation.
Is that what you are looking for?
We still entertain the idea of ImmutableArray<T>. The type would be a struct wrapper around an array. Constructing would copy the array once to avoid anybody can violate the immutability guarantee. Indexer would be O(1). However, we wouldn't support persistent operations. In other words, adding or changing items would not be supported.
Nice
If the MSR work you talked about is this
http://research.microsoft.com/apps/pubs/default.aspx?id=170528
then its very interesting to think about it, IIRC (could be wrong) the 'immutable' reference applies to the whole object graph can be reached from it, meaning a 'immutable' collection can't have mutable objects as elements !? so the pattern here is actually quite different.
That said, as far as I understand it, the algorithm itself should be perfectly suitable for immutable references, you just create an 'isolated' node, mutate it as you like, including let it point to the previous immuable tree nodes etc, then return it as an immutable reference, its exactly the 'builder' pattern and 'freeze'/consume pattern, and I think this kind of ability is exactly why the approach in that paper is better than previous works.
Thanks for the great video, guys! It's nice to know the underlying data structures.
Just one question (for the interviewer): how is async being overused?
-Steve
@Stephen_Cleary: Perhaps "overused" was a poor choice of wording... The fact is, however, that folks have been using async in ways it's not intended or in ways where it can lead them into traps. Best to watch this: http://channel9.msdn.com/Series/Three-Essential-Tips-for-Async
C
Yes, I believe that's the paper we referred to during the interview.
I like language innovation a lot but things that affect the type subsystem in such a fundamental way are very hard to incorporate into an existing language like C#. It seems impossible to this on "on the side" as immutability is quite sticky; meaning you those sort of constraints need to be propagated around in the entire system to be beneficial.
Also, applying this to the hundreds of thousands of APIs in the .NET FX might be prohibitively expensive...
Hmm... waiting for Wesner Moise's update post about this:
http://wesnerm.blogs.com/net_undocumented/2013/03/immutable-collections-critique.html
Wesner Moise - previously a top blogger, now resurrected from deep sleep. I'll follow...
It worked!
C
Sounds interesting... As this is very functional approach, I hope there will be also good interfaces to use these with F# (where the default list is already one-way linked list).
Speaking of that, good posts of tree-traversal: Catamorphisms in F# (Part 1, 2, 3, 4, 5, 6, 7)
This was one of the missing pieces in BCL but I have two questions:
The nuget package has been announced many months ago but it is in PreRelease status in Nuget repos. Any soon plans to update them as Stable in Nuget ?
HashSet ISet always treated second class citizens in BCL. But I find them as usuable as List<T>. Now .net 4.5 introduced an IReadOnlyList but not an IReadOnlySet. Don't you think Sets are still not treated as first class ?
This would be a great addition!
I wonder, how does the iteration speed compare to a List<T>, when accessed through an IList<T> or IEnumerable<T> interface?
I also see the use case for the readonly array. I have been playing around with implementations for a read-only array myself. (ReadOnlyCollection<T> is still too slow in .net 4.0).
If you add such a class, it could be useful if it also has CreateStream() function, that produces a fast readonly stream on the array. That is great for streaming out arrays of primitive types.
Remove this comment
Remove this thread
close