Нужен список, от которого требуется, чтобы он максимально быстро выполнял операции: создание, добавление элемента, извлечение элемента. Остальные операции не требуются. Подходит и List и Stack и Queue. Но интересует самый быстрый. И чтобы был IEnumerable.

Здравствуйте, Spiceman, Вы писали:

Почему возникла такая проблема?

P.S. На современном процессоре от причуд кеширования можно потерять или приобрести гораздо больше, чем от оптимизации выполнения return _array[index]

Здравствуйте, adontz, Вы писали:

A>Почему возникла такая проблема?

1. Просто интересно. Может кто-то уже тестировал.
2. Код таков, что там большую часть времни делается работа со списками и массивами. Причем мне не нужна большая часть функционала списка. Нужно только сгенерить множество элементов, а потом по ним пройтись.
Сами операции конечно занимают миллисекунды, но их там сотни миллионов. А хочется миллиардов
Кстати, я тут поэкспериментировал с массивами. Работа с byte[][] происходит в два раза быстрее, чем с byte[,].

Здравствуйте, Spiceman, Вы писали:

У List<T> есть причины накладных расходов
1) Версионность. Надо отслеживать изменения списка, чтобы Enumerator кидал исключение.
2) Проверка границ для индекса. Может быть так что индекс укладывается в массив, но не укладывается в List<T>.
Можно это, в принципе, выкинуть.

С другой стороны, выкидывание _version++ явно не даст ощутимой разницы. Выкидывание одного if по большому счёту — тоже. Структуры данных упираются не в процессор, а в кеш.

Здравствуйте, Spiceman, Вы писали:

S>Нужен список, от которого требуется, чтобы он максимально быстро выполнял операции: создание, добавление элемента, извлечение элемента. Остальные операции не требуются. Подходит и List и Stack и Queue. Но интересует самый быстрый. И чтобы был IEnumerable.

Если по сценариям размер списка меняется гораздо реже, чем запрашиваются элементы, то лучший список — это типизированный массив, который пересоздается при удалении или добавлении элементов.
Опять же, операции добавления-удаления могут быть групповыми, что как-бы немного позволяет пересоздавать массив один раз во время группового удаления/вставки. Я использовал эту технику для парсеров, строящихся в рантайм, и получил заметный прирост скорости работы парсера, в сравнении с List<T>. В общем, везде, где есть возможность, надо работать непосредственно с массивом.

Простоты ради можно создать value-type helper:
struct ArrayBasedList<T> {
private T[] array;

public void Add(T value);
public void AddRange(ArraySegment<T> values) { ... }

public bool Remove(T value) {...}
public void RemoveAt(int index) {...}
public int RemoveRange(int index, int count) {...}
public int RemoveRange(ArraySegment<T> values) {...}

...
}