Why is the c# generic List implemented as an append-only array?

Question

The C# generic list System.Collections.Generic.List<T> is implemented using a grow-able array as the backing store, in a manner similar of more array list based implementations. It is clear that this provides huge benefits when performing random (indexed) access over e.g. lists that are implemented as linked list.

I am wondering however why the choice was not made to implement it as a circular array. Such an implementation would have the same O(1) performance for indexed random access and appending to the end of the list. But would provide additional benefits, such as allowing O(1) prepend oprations (i.e. inserting new element at the front of the list) and on average halving the amount of time needed for random insertions and deletions.

Summary from some answers so far

As pointed out by @Hachet, in order for a circular array implementation to have indexing performance that is similar to that of the System.Collections.Generic.List<T> it would be required that it always grows to a capacity that is a power of 2 (so that a cheap modulus operation can be performed). This would mean that it is not possible to size it to an exact user supplied initial capacity as is currently possibly on construction of a list instance. So that is a clear trade off question.

And as shown by some quick & dirty performance tests, indexing may be around 2-5 x slower for a circular array implementation.

With indexing being an obvious priority I can imagine this would be too big of penalty to pay versus better performance on prepend operations and slightly better performance on random inserts/deletions.

This is a duplicate with some complementary answer information

This question is indeed related to Why typical Array List implementations aren't double-ended?, which I did not discover before posting my question. It was not answered in a manner that was fully satisfactory I guess:

I haven't done any benchmarks, but it just seemed to me that there would be other bottlenecks (e.g. nonlocal loads/stores) that would beat this by quite a lot. I'll probably accept this if I don't hear something more convincing though, thanks. – Mehrdad May 27 '11 at 4:18

The answers on this question provide additional information on how indexing for a circular list could be made to perform pretty well, including a code example, and some quantitative numbers numbers that make the trade-off decisions being made much clearer. As such they provide information that is complementary to that which is present in the other question. So I agree that the intent of this question was very much the same, and I agree it should therefore be considered a duplicate. It would be a shame however if the new information now accompanying this one would be lost.

Also I am still interested in potential additional reasons for the implementation choice that may not yet be present in the answers on either question.

Answer 1

Indeed a circular array could be implemented with O(1) access time. However I do not believe the intent of List<T> indexer was to be O(1). Big O notation tracks performance as it relates to the size of the collection it operates on. The implementors of List<T>, in addition to wanting O(1), were likely obsessed with other items like instruction count and performance in tight loops. It would need to be as close to array performance in the same scenarios in order to be generally useful. Accessing an element of an array is a very simple operation

• Add index multiplied by size to array start
• Deference

Indexing in a circular array, while still O(1), involves at least one branch operation. It has to check if the array index needs to wrap around or not based on the desired index. This means that tight arrays over loops with known bounds would have branching logic inside of them. This would be a significant downstep in code paths with fast tight loops over a raw array.

EDIT

Ah yes, a branch wouldn't necessarily be needed. However the instruction count would still be higher than that of an array. I believe that would still factor into the concerns of the authors.

Additionally another issue would be whether or not prepend was a priority operation. If prepend wasn't considered a priority then why take any performance hit in a scenario that was (indexing was certainly a priority)? My guess is that indexing, enumerating and adding to the end of the array were the scenarios given the highest priority. Operations like prepend were likely considered rare.

Answer 2

Your question made me curious what the magnitude of runtime difference would be between List<> and a circular version. So I threw together a quick skeleton on one that forces sizes that are powers of two (which avoids modulo operations), i.e. a best case implementation. I've left out growing because I just wanted to compare the indexer property time differences. It wasn't too bad; circularList[x] was about twice as slow as list[x], and both are quite fast. I also haven't really debugged this because I had limited time. This also probably lacks some validation code that List<> is doing, which would make the circular list comparatively a bit slower if it also had it.

In general, I would say this behavior would just be a distraction to the primary purpose of List<>, that would only rarely actually be used. So you are forcing slower performance on very many uses, to benefit a very small number of uses. I think they made a good decision in not baking it into List<>.

using System;

public class CircularList<T> {
    private int start, end, count, mask;
    private T[] items;
    public CircularList() : this(8) { }

    public CircularList(int capacity) {
        int size = IsPowerOf2(capacity) ? capacity : PowerOf2Ceiling(capacity);
        this.items = new T[size];
        this.start = this.end = this.count = 0;
        this.mask = size - 1;
    }

    public void Add(T item) {
        if (this.count == 0) {
            this.items[0] = item;
            this.start = this.end = 0;
        } else {
            this.items[++this.end] = item;
        }
        this.count++;
    }

    public void Prepend(T item) {
        if (this.count == 0) {
            this.items[0] = item;
            this.start = this.end = 0;
        } else {
            this.start--;
            if (this.start < 0) this.start = this.items.Length - 1;
            this.items[this.start] = item;
        }
        this.count++;
    }

    public T this[int index] {
        get {
            if ((index < 0) || (index >= this.count)) throw new ArgumentOutOfRangeException();
            return this.items[(index + this.start) & this.mask]; // (index + start) % length
        }
        set {
            if ((index < 0) || (index >= this.count)) throw new ArgumentOutOfRangeException();
            this.items[(index + this.start) & this.mask] = value; // (index + start) % length
        }
    }

    private bool IsPowerOf2(int value) {
        return (value > 0) && ((value & (value - 1)) == 0);
    }
    private int PowerOf2Ceiling(int value) {
        if (value < 0) return 1;
        switch (value) {
            case 0:
            case 1: return 1;
        }
        value--;
        value |= value >> 1;
        value |= value >> 2;
        value |= value >> 4;
        value |= value >> 8;
        return unchecked((value | (value >> 16)) + 1);
    }
}