Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

Immo Landwerth and Andrew Arnott: Inside Immutable Collections

Download

Right click “Save as…”

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...).

Tags:

Follow the Discussion

  • MarcusMarcus

    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.

    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?

    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.

    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?

    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?

    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.

    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.

  • felix9felix9 the cat that walked by itself

    Nice Smiley

    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

  • CharlesCharles Welcome Change

    @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...

  • felix9felix9 the cat that walked by itself

    Hmm... waiting for Wesner Moise's update post about this:

    http://wesnerm.blogs.com/net_undocumented/2013/03/immutable-collections-critique.html

  • Bent Rasmussenexoteric stuck in a loop, for a while

    Wesner Moise - previously a top blogger, now resurrected from deep sleep. I'll follow...

  • CharlesCharles Welcome Change

     

    , exoteric wrote

    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)

     

  • Onur GumusOnur Gumus

    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 ?

  • Jan de VaanJan de Vaan

    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

Comments Closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums,
or Contact Us and let us know.