Menu
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?
522
Lock-freedom An algorithm is lock-free if, when the program threads are run for a sufficiently long time, at least one of the threads makes progress (for some sensible definition of progress). All wait-free algorithms are lock-free.
lock-free usually doesn't mean "any lock", it means something like transactional memory, or optimistic design, where you don't use lock for every operation, but once in a while (for rolling back or doing transaction) - some kind of lock will be needed.
Lock-free techniques allow multiple threads to work together in a non-blocking way, often achieving incredible performance. As the name suggests, locks are not used. If the idea of a multithreaded program without mutexes makes you uncomfortable, you are quite sane. Yet lock-free systems are pervasive.
A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps. A method is wait-free if it guarantees that every call finishes its execution in a finite number of steps.
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.
51
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
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.
28
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
