В поисках более быстрой реализации IEnumerable / IEnumerator

Question

Я пытаюсь оптимизировать одновременную коллекцию, которая пытается минимизировать конфликт блокировки для чтения. При первом проходе использовался связанный список, который позволял мне блокировать только записи, в то время как многие одновременные чтения могли продолжаться разблокированными. При этом использовались пользовательские IEnumerator до доходность следующего значения ссылки. Как только я начал сравнивать итерацию по коллекции с простой List<T>, я заметил, что моя реализация была примерно вдвое быстрее (для from x in c select x на коллекции из 1 * m * элементов я получил 24ms для List<T> и 49мс для моей коллекции).

Так что я подумал, что я бы использовал ReaderWriteLockSlim и пожертвовал небольшим раздором на чтениях, чтобы я мог использовать List<T> в качестве внутреннего хранилища. Так как мне нужно захватить блокировку чтения при запуске итерации и освободить ее после завершения, я сначала сделал шаблон доходности для моего IEnumerable, foreach над внутренним List<T>. Теперь я получаю только 66мс .

Я посмотрел, что на самом деле делает List, и он использует внутреннее хранилище T[] и пользовательский IEnumerator, который перемещает индекс вперед и возвращает текущее значение индекса. Теперь ручное использование T[] в качестве хранилища означает гораздо больше работ по обслуживанию, , но с , я гоняюсь за микросекундами.

Однако, даже подражая IEnumerator перемещению индекса в массиве, лучшее, что я мог сделать, было около ~ 38 мс . Так что же дает List<T> его секретный соус или, наоборот, что является более быстрой реализацией для итератора?

ОБНОВЛЕНИЕ: Оказалось, что мой главный виновник скорости выполнял отладочную компиляцию, тогда как List<T>, очевидно, является компиляцией выпуска. В релизе моя реализация по-прежнему работает медленнее, чем List<T>, хотя на моно она теперь быстрее.

Еще одно предложение, которое я получил от друга, заключается в том, что BCL быстрее, потому что он находится в GAC и, следовательно, может быть предварительно скомпилирован системой. Придется поставить мой тест в GAC, чтобы проверить эту теорию.

Answer 1

Получение и снятие блокировки на каждой итерации звучит как плохая идея - потому что, если вы выполняете Add или Remove, пока выполняете итерацию по списку, это приведет к аннулированию итератора. List<T> конечно не понравится, например.

Позволит ли ваш сценарий использования вызывающим абонентам ReaderWriterLockSlim на протяжении всего процесса итерации, а не для каждого элемента? Это было бы более эффективным и более надежным. Если нет, то как вы планируете решать проблему параллелизма? Если писатель добавляет элемент раньше, чем место, куда я попал, простая реализация возвращает один и тот же элемент дважды. С удалением произойдет обратное - итератор пропустит элемент.

Наконец, является ли .NET 4.0 вариантом? Я знаю, что там есть несколько оптимизированных параллельных коллекций ...

РЕДАКТИРОВАТЬ: Я не совсем уверен, какова ваша текущая ситуация с точки зрения создания итератора вручную, но одна вещь, которую вы, возможно, захотите исследовать, это использовать структуру для IEnumerator<T> и сделать вашу коллекцию явно объявленной что он возвращает это - это то, что делает List<T>. означает использование изменяемой структуры, которая заставляет котят плакать по всему миру, но если это абсолютно необходимо для производительности, и вы думаете, что можете жить с ужасом, по крайней мере, стоит попробовать.