Exploring the .NET CoreFX Part 13: ImmutableList is an AVL Tree

This is part 13 of my Exploring the .NET CoreFX Series.

Most implementations of IList, including System.Collections.Generic.List, are dynamic arrays. System.Collections.Immutable.ImmutableList is different — it is an AVL tree. This results in significantly different performance characteristics:

  List ImmutableList
Indexing O(1) O(log n)
Append O(1) average, O(n) worst-case O(log n)
Insert at arbitrary index O(n) O(log n)
Remove O(n) O(log n)
Memory layout Contiguous for value types Non-contiguous

The data structure behind ImmutableList was likely chosen so that modifications to the list are non-destructive and require minimal data copying.

Here’s a visual representation of what List and ImmutableList look like behind the scenes:

List ImmutableList
List l = new List();
Array0
ImmutableList l = ImmutableList.Create();
Empty
l.Add(1);
Array1
l = l.Add(1);
1
l.Add(2);
Array2
l = l.Add(2);
2
l.Add(3);
Array3
l = l.Add(3);
3
l.Add(4);
Array4
l = l.Add(4);
4
Advertisements

Exploring the .NET CoreFX Part 12: Aggressive Inlining

This is part 12 of my Exploring the .NET CoreFX Series.

In C++, the inline keyword allows a developer to provide a hint to the compiler that a particular method should be inlined. C# has the identical ability but uses an attribute instead:

internal class SecurePooledObject<T>
{
    ....

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    internal bool IsOwned<TCaller>(ref TCaller caller)
        where TCaller : struct, ISecurePooledObjectUser
    {
        return caller.PoolUserId == _owner;
    }
}

In System.Collections.Immutable, this attribute is used highly selectively — only once, in fact.

Recommendations

  • In rare cases, consider using MethodImpl(MethodImplOptions.AggressiveInlining) to suggest to the .NET runtime that a particular method should be inlined.