ImmutableList inconsistency with List

[bartlomiej-dawidow]

ImmutableList is implemented as a tree which is confusing. Judging by its name, the user of this class likely expects performance characteristics similar to a List. Anecdotally we regularly find instances in our project's code where someone unintentionally used an ImmutableList instead of an ImmutableArray.

The proposed solution is to add a FrozenList class, complementing the existing FrozenDictionary and FrozenSet classes, backed by an array and with the same computational complexity as List.

In addition to the above consider renaming ImmutableList to ImmutableTreeList but that would break backward compatibility.

[dotnet-policy-service]

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

[stephentoub]

ImmutableList is implemented as a linked list

It's a tree.

the user of this class likely expects performance characteristics similar to a List

https://devblogs.microsoft.com/dotnet/performance-improvements-in-net-8/#frozen-collections provides background about what the immutable collections are and why they perform the way they do.

The proposed solution is to add a FrozenList class

How would that differ from ImmutableArray<T>?

[bartlomiej-dawidow]

It's a tree.

I corrected the description.

How would that differ from ImmutableArray<T>?

It would not expose any mutation methods for consistency with FrozenDictionary and FrozenSet. It would also provide a way to sunset or rename ImmutableList at a later date if it makes sense.

[colejohnson66]

The purpose of the “frozen” collections is to trade off extra computation time during creation in exchange for much faster reads, similar to SearchValues<T>. A “frozen list” would provide no read advantage over the existing List<T> or ImmutableArray<T>. If you have issues with people accidentally using ImmutableList<T> when they shouldn’t be, the “banned API” analyzer might be helpful.

As for why it’s a tree structure, you have to consider its purpose: it’s an immutable list. That means every modification needs to return a whole new allocation. To reduce how much allocation is required, using segments (which traversing a tree can accomplish) allows only allocating the segments the insertion point requires (which is O(log n)) instead of a whole new array like ImmutableArray<T>. This is explained in the linked blog post.

[bartlomiej-dawidow]

The logic behind the Immutable and Frozen collections is well understood by our team.

This issue is meant to highlight the inconsistency in the naming of the classes:

• An array-backed list implementation is named List, not ArrayList.
• An array-backed immutable list implementation is named ImmutableArray.
• ImmutableList's name misleads its users into thinking that it has similar complexity characteristics to List.

The above leads to human error.

We also never use the mutating methods of the immutable collections. While not reported in my original post, as is it is now we have to use ImmutableArrays for immutable lists and FrozenDictionary or FrozenSet for immutable dictionaries and sets.

Let's say you accidentally added a Dictionary<T> field to your class - you address that by changing it to FrozenDictionary<T>. But if you do the same with a List<T>, you have to change it to ImmutableArray<T>.

So in practical terms we would prefer a set of Frozen* classes, corresponding to their mutable counterparts. We would likely never use the Immutable* variants, unless we find a use case for them. This of course may be specific to our project and may not warrant a .NET-wide change.

[bartlomiej-dawidow]

An alternative would be to add a new set of collections with a different naming convention, let's say UnmodifiableList, UnmodifiableDictionary etc. which would offer the same performance characteristics as the standard mutable collections but would restrict any form of mutation. That is likely what a large number of developers expect, especially if they previously worked in Java and it would likely be the least confusing.

That however would introduce yet another set of classes and so adding the missing Frozen* variants might be more viable.

[eiriktsarpalis]

This issue is meant to highlight the inconsistency in the naming of the classes...

I don't think it's reasonable to assume that the term "List" necessarily implies a buffer backed implementation. This would be similar to assuming that ImmutableDictionary must be a hash table because it's called dictionary (it is not, it also uses a tree). With the exception of ImmutableArray<T> all collections in the S.C.Immutable namespace are optimizing for persistable updates and therefore their implementation and performance characteristics differ from those of their mutable counterparts.

As already mentioned, ImmutableArray<T> already provides a "frozen" implementation that optimizes for access. I don't think we'd want to consider introducing a separately named collection type.

[CyrusNajmabadi]

It would also provide a way to sunset

Why sunset the type? It's invaluable. It's an immutable sequence of elements that can be used to create new immutable sequences much more efficiently than what is possible with types like ImmutableArray.

The different types have different characteristics and different intended use cases. The cases for ImmutableList are quite sound and are needed and appropriate in many domains.

[Clockwork-Muse]

.... Although I think people are missing something really trivial here;

The implication of the OP's needs is that people are passing in whatever collection into something accepting a concrete type.
Instead, those methods should have an IReadOnlyList<T> parameter.

Who cares what the actual backing type is, only hand out the behavior reference.

[jeffhandley]

Assigned to @eiriktsarpalis to finish triaging this