Procurando uma implementação mais rápida para o iEnumerable/ienumerator

Question

Estou tentando otimizar uma coleção simultânea que tenta minimizar a contenção de bloqueio para leituras. O primeiro passe foi usar uma lista vinculada, o que me permitiu travar apenas as gravações, enquanto muitas leituras simultâneas poderiam continuar desbloqueadas. Isso usou um costume IEnumerator para colheita o próximo valor de link. Depois que comecei a comparar a iteração sobre a coleção com uma planície List<T> Percebi que minha implementação era cerca da metade tão rápida (para from x in c select x Em uma coleção de 1* m* itens, eu tenho 24ms por List<T> e 49ms para minha coleção).

Então eu pensei em usar um ReaderWriteLockSlim e sacrificar um pouco de contenção em leituras para que eu pudesse usar um List<T> como meu armazenamento interno. Como tenho que capturar o bloqueio de leitura no início da iteração e lançá -lo após a conclusão, primeiro fiz um padrão de rendimento para o meu IEnumerable, para cadasobre o interno List<T>. Agora eu estava recebendo apenas 66ms.

Eu espiei o que a lista realmente faz e usa uma loja interna de T[] e um costume IEnumerator Isso move o índice para a frente e retorna o valor atual do índice. Agora, usando manualmente T[] Como armazenamento significa muito mais trabalho de manutenção, mas wth, estou perseguindo microssegundos.

No entanto, mesmo imitando o IEnumerator movendo o índice em uma matriz, o melhor que eu poderia fazer foi sobre ~ 38ms. Então, o que dá List<T> Seu molho secreto ou, alternativamente, o que é uma implementação mais rápida para um iterador?

ATUALIZAR: Acontece que meu culpado de velocidade principal estava executando a compilação de depuração, enquanto List<T> é obviamente uma compilação de lançamento. No lançamento, minha implementação ainda é mais lenta do que List<T>, até o mono agora é mais rápido.

Uma outra sugestão que recebi de um amigo é que o BCL é mais rápido porque está no GAC e, portanto, pode ser pré-compilado pelo sistema. Terá que fazer meu teste no GAC para testar essa teoria.

Answer 1

Adquirir e liberar a trava em cada iteração soa como uma má idéia - porque se você executar um Add ou Remove Enquanto você está iterando a lista, isso invalidará o iterador. List<T> Certamente não gostaria disso, por exemplo.

Seu caso de uso permitiria que os chamadores tirassem um ReaderWriterLockSlim Em todo o seu processo de iteração, em vez de por itens? Isso seria mais eficiente e mais robusto. Caso contrário, como você planeja lidar com a questão da simultaneidade? Se um escritor adicionar um elemento antes do local onde eu tenho, uma simples implementação retornaria o mesmo elemento duas vezes. O oposto aconteceria com uma remoção - o iterador pularia um elemento.

Finalmente, é .NET 4.0 uma opção? Eu sei que existem algumas coleções simultâneas altamente otimizadas lá ...

EDIT: Não tenho muita certeza de qual é a sua situação atual em termos de construção de um iterador manualmente, mas uma coisa que você pode querer investigar é usar uma estrutura para o IEnumerator<T>, e fazer sua coleção declarar explicitamente que retorna que - é isso List<T> faz. Isto faz significa usar uma estrutura mutável, o que faz os gatinhos chorarem em todo o mundo, mas se isso é absolutamente crucial para o desempenho e você acha que pode viver com o horror, vale a pena tentar.