Finding a faster implementation of IEnumerable / IEnumerator

Question

I am trying to optimize a concurrent collection that is trying to minimize read lock lock conflict. In the first pass, a linked list was used, which allowed me to lock records only if many simultaneous readings could continue to unlock. This used a custom IEnumerator to get the following link value. As soon as I started comparing collection iteration with a simple List<T> , I noticed that my implementation was about two times faster (for from x in c select x in a collection of 1 * m * elements, I got 24 ms for List<T> and 49ms for my collection).

So, I thought I would use ReaderWriteLockSlim and donate a bit of read disputes, so I could use List<T> as my internal storage. Since I have to grab the read lock on iterative start and release it upon completion, I first made a yield pattern for my IEnumerable by going through the internal List<T> . Now I was only getting 66 ms .

I looked at the list, in fact, and uses the internal T[] store and a custom IEnumerator that moves the index forward and returns the current index value. Now, using T[] , as storage means a lot more maintenance work, but wth, I chase microseconds.

However, even imitating IEnumerator , moving the index through the array, the best I could do was ~ 38 ms . So what gives List<T> its secret sauce, or, alternatively, what is a faster implementation for an iterator?

UPDATE: It turned out that my main speed culprit was doing Debug compilation, and List<T> is obviously Release compilation. In the release, my implementation is still slower than List<T> , although now it is mono more soon.

Another suggestion I received from a friend is that BCL is faster because it is in the GAC and therefore can be precompiled by the system. You have to do a test at the GAC to test this theory.

Answer 1

Acquiring and releasing a lock at each iteration sounds like a bad idea - because if you execute Add or Remove while iterating through the list, it will invalidate the iterator. List<T> , of course, will not like it, for example.

Will your use case allow callers to take out ReaderWriterLockSlim around the entire iteration process, and not for each element? It will be more efficient and reliable. If not, how do you plan to solve the concurrency problem? If the author adds the element earlier than the place where I need it, a simple implementation will return the same element twice. The opposite will be with deletion - the iterator will skip the element.

Finally, is there a .NET 4.0 option? I know there are several optimized parallel collections there ...

EDIT: I'm not quite sure what your current situation is from the point of view of creating an iterator manually, but one thing you can explore is to use the structure for IEnumerator<T> and make your collection explicitly declared that it returns this - that does List<T> . This means using a volatile structure that makes kittens cry around the world, but if it’s absolutely important for performance and you think you can live with horror, it is at least worth a try.