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?

I presume you mean "lock-free" and thread-safe, since List<T> is quite lock-free. You should also clarify what you mean by "lock-free". — John Saunders
@damageboy Another note: They (amino) are implementing a LINKED list, not a list. A LinkedList in C# doesn't implement IList/IList<T>. They have a LockFreeVector... But I don't think it's "fully" lock free. — xanatos
How "full" an implementation are you looking for? I highly doubt you'll be able to find, e.g., a type that supports a random Insert without locking (unless you allow spinning, I guess, since that isn't really the same as "locking"). But then, what do I know? — Dan Tao
@xantos: I was referring to the LockFreeVector<T> of amino: amino-cbbs.sourceforge.net/java_apidocs/org/amino/ds/lockfree/… — damageboy
@damageboy: Note that the lock-free structure described in the paper on which LockFreeVector<E> is based does not have a random Insert operation (which is part of the IList<T> interface). — Dan Tao

Valentin Kuzub Valentin Kuzub · Accepted Answer · 2011-02-22T12:27:34

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

Parallel class methods are better than ConcurrentList
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.

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

3 Answers