IList<T> implementation

Question

I was wondering about the possibility to create an implementation of IList<T> that is faster than List<T> using C#, or at least faster at adding elements.
I thought to try to write out one using a technique similar to the binary tree that just came up to my mind. Basically, each item is a pointer to a block of memory (let me call it entry) containing three more pointers:

1. A pointer to the item
2. A pointer to the previous entry
3. A pointer to the next entry

Here's my implementation, which is not complete yet, though:

public class FastList<T> : IList<T>
{

    private static readonly int sPtrSize = IntPtr.Size;
    private static readonly int sItemSize = sPtrSize * 3;
    private static readonly int sItemOffset = 0;
    private static readonly int sPreviousOffset = sItemSize - (sPtrSize << 1);
    private static readonly int sNextOffset = sItemSize - sPtrSize;

    private static IntPtr CreateItem() => Marshal.AllocHGlobal(sItemSize);

    private static GCHandle GetItemHandle(IntPtr ptr)
    {
        IntPtr itemPtr = Marshal.ReadIntPtr(ptr, sItemOffset);
        return GCHandle.FromIntPtr(itemPtr);
    }

    private static void DeleteItem(IntPtr item)
    {
        GetItemHandle(item).Free();
        Marshal.FreeHGlobal(item);
    }

    private static T GetItem(IntPtr ptr)
    {
        GCHandle handle = GetItemHandle(ptr);
        return (T)handle.Target;
    }

    private static void SetItem(IntPtr ptr, T item)
    {
        GCHandle handle = GCHandle.Alloc(item, GCHandleType.Pinned);
        IntPtr itemPtr = GCHandle.ToIntPtr(handle);
        Marshal.WriteIntPtr(ptr, sItemOffset, itemPtr);
    }

    private static IntPtr GetPrevious(IntPtr ptr) => Marshal.ReadIntPtr(ptr, sPreviousOffset);

    private static void SetPrevious(IntPtr ptr, IntPtr previous) => Marshal.WriteIntPtr(ptr, sPreviousOffset, previous);

    private static IntPtr GetNext(IntPtr ptr) => Marshal.ReadIntPtr(ptr, sNextOffset);

    private static void SetNext(IntPtr ptr, IntPtr next) => Marshal.WriteIntPtr(ptr, sNextOffset, next);

    private class Enumerator : IEnumerator<T>
    {

        private readonly FastList<T> mList;

        private int mPosition = -1;

        private IntPtr mCurrent = IntPtr.Zero;

        public Enumerator(FastList<T> list) => mList = list;

        public T Current => GetItem(mCurrent);

        object IEnumerator.Current => Current;

        public bool MoveNext()
        {
            if (++mPosition >= mList.Count)
                return false;
            if (mCurrent == IntPtr.Zero)
            {
                mCurrent = mList.mStart;
                return mList.Count != 0;
            }
            mCurrent = GetNext(mCurrent);
            return mCurrent != IntPtr.Zero;
        }

        public void Reset() => mCurrent = mList.mStart;

        public void Dispose()
        {
        }
    }

    private readonly IntPtr mStart = CreateItem();

    private IntPtr mEnd;

    public FastList()
    {
        SetNext(mStart, IntPtr.Zero);
        mEnd = mStart;
    }

    ~FastList() => DeleteItem(mStart);

    public T this[int index]
    {
        get => GetItem(FindItem(index));
        set => SetItem(FindItem(index), value);
    }

    public int Count
    {
        get;
        private set;
    }

    public bool IsReadOnly
    {
        get;
    } = false;

    private IntPtr FindItem(int index)
    {
        int count = Count;
        IntPtr item;
        if (index < count >> 1)
        {
            item = mStart;
            for (; index != -1 && (item = GetNext(item)) != IntPtr.Zero; index--) ;
        }
        else
        {
            item = mEnd;
            index = count - index;
            for (; index != -1 && (item = GetPrevious(item)) != IntPtr.Zero; index--) ;
        }
        return item;
    }

    public void Add(T item)
    {
        SetItem(mEnd, item);
        IntPtr previous = mEnd;
        mEnd = CreateItem();
        SetPrevious(mEnd, previous);
        SetNext(mEnd, IntPtr.Zero);
        SetNext(previous, mEnd);
        Count++;
    }

    public void Clear()
    {
        SetNext(mStart, IntPtr.Zero);
        for (IntPtr item = mStart; (item = GetNext(item)) != IntPtr.Zero;)
            DeleteItem(item);
        Count = 0;
    }

    private void RemoveItem(IntPtr item)
    {
        IntPtr previous = GetPrevious(item);
        IntPtr next = GetNext(item);
        SetNext(previous, next);
        SetPrevious(next, previous);
        DeleteItem(item);
    }

    public bool Contains(T item) => IndexOf(item) != -1;

    public void CopyTo(T[] array, int arrayIndex) => throw new NotImplementedException();

    public int IndexOf(T item) => throw new NotImplementedException();

    public void Insert(int index, T item)
    {
        IntPtr next = FindItem(index);
        IntPtr previous = GetPrevious(next);
        IntPtr itemPtr = CreateItem();
        SetItem(itemPtr, item);
        SetPrevious(itemPtr, previous);
        SetNext(itemPtr, next);
        SetPrevious(next, itemPtr);
        SetNext(previous, itemPtr);
    }

    public bool Remove(T item) => throw new NotImplementedException();

    public void RemoveAt(int index) => RemoveItem(FindItem(index));

    public IEnumerator<T> GetEnumerator() => new Enumerator(this);
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

Unfortunately, however, it turns out that it is roughly 10 times slower than List<T>. I couldn't still understand why.
Could someone, please, tell me why it results so slow and suggest me how can I speed this up?

Answer 1

This is called a doubly linked list. List<T> is basically a wrapper around an array. The only operations where you can hope to be faster are insertions and deletions from the middle of the list.

---

Using Marshal unless you absolutely have to is a bad idea, if not a plain crazy one. This code has memory leaks (how is that destructor meant to release all of the memory allocated for the list? See also the next subsection). And because you're fighting the GC and the JIT, you can't expect high performance.

---

    public void Clear()
    {
        SetNext(mStart, IntPtr.Zero);
        for (IntPtr item = mStart; (item = GetNext(item)) != IntPtr.Zero;)
            DeleteItem(item);
        Count = 0;
    }

Expand that for as a while and see whether you can spot the problems:

    SetNext(mStart, IntPtr.Zero);
    IntPtr item = mStart;
    while ((item = GetNext(item)) != IntPtr.Zero)
        DeleteItem(item);

1. SetNext(mStart, IntPtr.Zero) guarantees that the loop body never executes.
2. DeleteItem(item) before GetNext(item) is a use-after-free bug.

---

I can't figure out whether mStart is a sentinel or an actual element of the list. It seems to do both in different places. Comments!

---

What happens if I modify the list while iterating through it with the enumerator? Is this desirable?

---

I can't think of any good reason to implement IList<T> and not also implement IReadOnlyList<T>.

Answer 2

You've essentially built a doubly-linked list that also performs its own memory management.

Regarding linked lists:

• This makes indexing is an \$O(n)\$ operation, compared to \$O(1)\$ for List<T>. Searching from the end for indexes beyond the center helps, but it does not fundamentally change this performance characteristic.
• Adding is an \$O(1)\$ operation, similar to List<T> (which is \$O(1)\$ on average).
• Inserting and removing-at can also be \$O(1)\$, but only if you provide the right API (for an example, see LinkedList<T>'s AddAfter/Before/First/Last methods). Your current implementation is \$O(n)\$, similar to List<T>.
• Like List<T>, iterating is \$O(n)\$, but having to follow a chain of pointers will make it slower than List<T>, which stores its items in a contiguous block of memory. Pointer-chasing is also less cache-friendly.

---

Regarding custom memory management, GCHandles allow you to access managed objects from unmanaged code, but you don't have any unmanaged code here. This only introduces problems:

• It limits your list to only types that do not contain reference fields (Add will throw an ArgumentException (Object contains non-primitive or non-blittable data.) for all but the most basic types).
• It involves extra allocations, which take additional time and memory.
• It introduces the risk of leaking memory/handles.
• Pinning objects can make the garbage collector less efficient - it'll hinder memory compaction.
• Unexpected program terminations.

Creating a small LinkedListNode<T> class instead would be a much better idea.

---

There are also other problems with your code:

• Indexing is broken: list[0] returns the second item, while the first item is located at list[-1]... and around the center, a higher index might actually give you an earlier item.
• There's no bounds-checking: list[-2] and list[list.Count + 2] result in an AccessViolationException (if you're lucky) rather than an OutOfRangeException.
• RemoveAt seems to be implemented, but it fails with an InvalidOperationException (if it doesn't cause the program to terminate instead).