What do you find insane about the C# `List` source code?

I'm not a C# programmer, but the public API looks sound, and the entire thing is like 1K LOC including docstrings (I guess the inherited code would add to that).

I don't think it's even using inheritance - List implements a few interfaces though?

List is an IList/IReadOnlyList; these interfaces do nothing that couldn't be done right inside the file itself.

https://referencesource.microsoft.com/#mscorlib/system/colle...

https://referencesource.microsoft.com/#mscorlib/system/colle...

Instead we have to go diving through the IList, which implements ICollection, which implements IEnumerable, which implements IEnumerable (again). Just because each interface is composed of another interface, doesn't mean you aren't using inheritance. You are effectively creating a custom inheritance tree through willy-nilly composition.

It is gratuitous to make this chain so deep, when the underlying code is just a handful of lines.

https://referencesource.microsoft.com/#mscorlib/system/colle...

https://referencesource.microsoft.com/#mscorlib/system/colle...

https://referencesource.microsoft.com/#mscorlib/system/colle...

----------------------------------------------------------------------------------------------------------------

The doc-strings are unnecessary. It's self-evident what most of the code does if you read it.

        // Returns an enumerator for this list with the given
        // permission for removal of elements. If modifications made to the list 
        // while an enumeration is in progress, the MoveNext and 
        // GetObject methods of the enumerator will throw an exception.
        //
        public Enumerator GetEnumerator() {
            return new Enumerator(this);
        }

        // Returns the index of the last occurrence of a given value in a range of
        // this list. The list is searched backwards, starting at the end 
        // and ending at the first element in the list. The elements of the list 
        // are compared to the given value using the Object.Equals method.
        // 
        // This method uses the Array.LastIndexOf method to perform the
        // search.
        // 
        public int LastIndexOf(T item)
        {
            Contract.Ensures(Contract.Result<int>() >= -1);
            Contract.Ensures(Contract.Result<int>() < Count);
            if (_size == 0) {  // Special case for empty list
                return -1;
            }
            else {
                return LastIndexOf(item, _size - 1, _size);
            }
        }

        // Returns the index of the first occurrence of a given value in a range of
        // this list. The list is searched forwards, starting at index
        // index and upto count number of elements. The
        // elements of the list are compared to the given value using the
        // Object.Equals method.
        // 
        // This method uses the Array.IndexOf method to perform the
        // search.
        // 
        public int IndexOf(T item, int index, int count) {
            if (index > _size)
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
 
            if (count <0 || index > _size - count) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
            Contract.Ensures(Contract.Result<int>() >= -1);
            Contract.Ensures(Contract.Result<int>() < Count);
            Contract.EndContractBlock();
 
            return Array.IndexOf(_items, item, index, count);
        }

If you remove these 300 lines of pointless comments, you still have 900 lines of code that is terribly space-inefficient. Everything is "pretty," but slow to read, because of the immense amount of whitespace, nesting, and lines longer than 76 chars. You cannot read long swathes of code in one screenful. You have to scroll vertically and horizontally, because for some reason a standard library needs to throw exceptions (exceptions aren't free; they negatively and noticeably impact performance).

Seriously, you could just use an "out" errno/status. "But then we would have to always check to see if the operation succeeded!": exceptions make people lazy. Just because an exception wasn't thrown, doesn't mean you're doing things correctly.

----------------------------------------------------------------------------------------------------------------

Why does a List implement a search algorithm? Why binary search of all things -- because it's convenient? You know if I need a binary search, I can write one myself. Don't pollute my namespace.

        // Searches a section of the list for a given element using a binary search
        // algorithm. Elements of the list are compared to the search value using
        // the given IComparer interface. If comparer is null, elements of
        // the list are compared to the search value using the IComparable
        // interface, which in that case must be implemented by all elements of the
        // list and the given search value. This method assumes that the given
        // section of the list is already sorted; if this is not the case, the
        // result will be incorrect.
        //
        // The method returns the index of the given value in the list. If the
        // list does not contain the given value, the method returns a negative
        // integer. The bitwise complement operator (~) can be applied to a
        // negative result to produce the index of the first element (if any) that
        // is larger than the given search value. This is also the index at which
        // the search value should be inserted into the list in order for the list
        // to remain sorted.
        // 
        // The method uses the Array.BinarySearch method to perform the
        // search.
        // 
        public int BinarySearch(int index, int count, T item, IComparer<T> comparer) {
            if (index < 0)
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            if (count < 0)
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            if (_size - index < count)
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
            Contract.Ensures(Contract.Result<int>() <= index + count);
            Contract.EndContractBlock();
 
            return Array.BinarySearch<T>(_items, index, count, item, comparer);
        }

What if my list -- as is almost always the case -- is unsorted? The result will be incorrect? Looking through the chain of indirection, I cannot see any code checking to see that the list is sorted. Maybe it's there, but it's so much overhead trying to make sense of the List.BinarySearch -> Array.BinarySearch -> ArraySortHelper<T>.Default.BinarySearch -> arraysorthelper.BinarySearch -> arraysorthelper.InternalBinarySearch chain. So I'm going to silently get a wrong result, and the only way to know is to read the docstrings? Thanks.

----------------------------------------------------------------------------------------------------------------

As far as I can tell, it's unoptimized. It's just plain, OO C# meant to be readable. I don't see any tricks or tweaks to get the IL to be more concise/performant. Maybe the compiler is aggressively optimized for the core lib (but I'm not holding my breath -- because I can't see it).

I stopped using C# & F# almost a decade ago, but there are some relevant pieces of information that answer your questions:

1. Optimization is primarily handled by the .Net JIT, not the C# compiler. That allows F#, C#, VB.Net and other runtime languages to share similar performance characteristics without duplicating effort.

2. Docstrings are used by the IDE to help the user. That avoids the need to read the source code itself for regular usage.

3. When comparing the .Net List<> implementation against any C++ std::vector implementation, the former looks quite tame in comparison...

Numbering your citations from zero, ehe? I like the cut of your jib.