Lock free & Thread-Safe IList<T> for .NET

Question

Is there a lock-free & thread-safe data structure that implements IList?

Naturally by lock-free I mean an implementation that makes no use of locking primitives in .NET but rather uses interlocked operations / atomic operations to achieve thread safety... There isn't one, apparently under the concurrent data structures...

Has anyone seen one floating around?

I've seen a java one implemented in amino-cbbs, called LockFreeVector but nothing for .NET so far. Any ideas?

Answer 1

Well, I couldn't find such a class anywhere; so I gave it a shot.

The source code for my ConcurrentList<T> class is available on GitHub.

It is lock-free, thread-safe (I think, based on my unit tests), and implements IList<T>.

It does not support Insert, RemoveAt/Remove, or Clear.

I was pleased to discover that my implementation (which I came up with independently) is very similar to that of a data structure published by some well-respected minds within the world of software.

For a fairly brief discussion of the implementation itself, see my recent blog post about it.

At the moment, it is not documented at all, which is kind of bad considering how "tricky" some of the code is :(

And by all means, rip me a new one if you take a look and find bugs or other issues.

Anyway, it might be worth your time to check it out. If you do, let me know what you think.

Answer 2

Think about how random access (implied by IList<T>) could work in a multithreaded environment. You can't actually really do anything without it being immutable since adding and removing, even if they are atomic, don't prevent thread 1 from removing the item at the index that thread 2 was just about to retrieve. That's why the SyncRoot stuff is gone in .NET 2.0+

Answer 3

ConcurrentList implementing IList might be missing in Collections.Concurrent namespace because of whole Parallel.For and Parallel.ForEach class-methods. One can say that they can be used to handle any list as Concurrent, in order to quickly enumerate through the list and perform actions on its items.

Maybe by not providing ConcurrentList they meant or thought that if Parralel.For cannot help one would require to use not a IList but some other kind of collection like a stack or queue or even Bag or even Dictionary

I would agree with this design, because having to deal with indexable collection under multi thread conditions sounds like very error prone and bad design. Whats the purpose of knowing index of an item if collection can be modified at any time and index would be invalidated, in such circumstances when there are multiple readers - writers its pretty clear to me that Queue or Stack will be commonly best fitting collections, or Bag can be good too. Dictionary can be used also because its indexes are not invalidated by adding items to collection, and if you need parallel access to List you got your Parralel.For methods

What I find really weird - http://msdn.microsoft.com/en-us/library/dd381935.aspx here we can read about ConcurrentLinkedList class but I cannot find it in System.dll , only Bag and BlockingCollection are there.

I would also say that there is like 95% chance at least that either of two is true about your problem

1. Parallel class methods are better than ConcurrentList
2. Existing Concurrent collections are going to be better collections than ConcurrentList

I would also say that by not providing ConcurrentList they have saved developers who would mistakenly choose ConcurrentList to solve their problems from making many errors and saved them a lot of time forcing developers to use existing Concurrent collections.