Some while ago I was explaining what "Lowering" is. And the interesting part is that List
behaves differently like an array while also a List
is backed by an array. But why?
Lowered Array
Here a small recap about the Array:
var range = new[] { 1, 2 };
foreach(var item in range)
Console.Write(item);
Gets lowered to:
int[] array = new int[2];
array[0] = 1;
array[1] = 2;
int[] array2 = array;
int num = 0;
while (num < array2.Length)
{
int value = array2[num];
Console.Write(value);
num++;
}
Lowered List
While a list:
var list = new List<int> { 1, 2 };
foreach(var item in list)
Console.Write(item);
Get's lowered to:
List<int> list = new List<int>();
list.Add(1);
list.Add(2);
List<int>.Enumerator enumerator = list.GetEnumerator();
try
{
while (enumerator.MoveNext())
{
Console.Write(enumerator.Current);
}
}
finally
{
((IDisposable)enumerator).Dispose();
}
Why no array?
We know that a List
is backed by an array that gets dynamically sized (if not here is a refresher: "How does List work under the hood"). So wouldn't it be beneficial from a performance point of view to use that array? Given that we can do: list[1]
and so on? Furthermore, can't we just generalize that to every IReadOnlyList<T>
as they always have an indexer?
Let's start with the list and why it isn't used and the reason is very simple: foreach
has a safeguard that prevents you from modifiying the collection. Also here I wrote an article: "How does a List know that you changed it while enumerating it?". Basically, the list has a version field that gets incremented everything you mutate the list. If the foreach sees that the version was changed during the enumeration you get an exception.
We would loss the semantics if we take the while
approach like the Array. For Arrays that approach is safe as you can't remove items or clear the whole collection.
If we have a look at IReadOnlyList<T>
not only might we run into the same problem (as many collection types do that so we would loss the version check) but we also add two more:
- The compiler has to know more specifics here. It has to know how to special case
IReadOnlyList<T>
which increases complexity. - More importantly:
IReadOnlyList<T>
does not guarantee that you access a specific index viaO(1)
time or space complexity. You can implement the indexer as you want without giving guarantees. But developers assume, rightfully so, that accessing an index is something fast. For example: You can access a character of aStringBuilder
with an index, but that isn't aO(1)
operation necessarily.StringBuilder
is basically a linked list where each node can hold up to 8000 characters.