No ConcurrentList T in Net 4 0

Question

I was thrilled to see the new System Collections Concurrent namespace in  Net 4 0  quite nice   I ve seen ConcurrentDictionary  ConcurrentQueue  ConcurrentStack  ConcurrentBag and BlockingCollection   One thing that seems to be mysteriously missing is a ConcurrentList lt T gt    Do I have to write that myself  or get it off the web         Am I missing something obvious here

User · Accepted Answer

I gave it a try a while back  also  on GitHub   My implementation had some problems  which I won t get into here  Let me tell you  more importantly  what I learned   Firstly  there s no way you re going to get a full implementation of IList lt T gt  that is lockless and thread-safe  In particular  random insertions and removals are not going to work  unless you also forget about O 1  random access  i e   unless you  cheat  and just use some sort of linked list and let the indexing suck    What I thought might be worthwhile was a thread-safe  limited subset of IList lt T gt   in particular  one that would allow an Add and provide random read-only access by index  but no Insert  RemoveAt  etc   and also no random write access    This was the goal of my ConcurrentList lt T gt  implementation  But when I tested its performance in multithreaded scenarios  I found that simply synchronizing adds to a List lt T gt  was faster  Basically  adding to a List lt T gt  is lightning fast already  the complexity of the computational steps involved is miniscule  increment an index and assign to an element in an array  that s really it   You would need a ton of concurrent writes to see any sort of lock contention on this  and even then  the average performance of each write would still beat out the more expensive albeit lockless implementation in ConcurrentList lt T gt    In the relatively rare event that the list s internal array needs to resize itself  you do pay a small cost  So ultimately I concluded that this was the one niche scenario where an add-only ConcurrentList lt T gt  collection type would make sense  when you want guaranteed low overhead of adding an element on every single call  so  as opposed to an amortized performance goal    It s simply not nearly as useful a class as you would think

User · Answer

System Collections Generic List lt t gt  is already thread safe for multiple readers  Trying to make it thread safe for multiple writers wouldn t make sense   For reasons Henk and Stephen already mentioned

User · Answer

lockless Copy and Write approach works great if you re not dealing with too many items  Here s a class I wrote   public class CopyAndWriteList lt T gt        public static List lt T gt  Clear List lt T gt  list                var a   new List lt T gt  list           a Clear            return a             public static List lt T gt  Add List lt T gt  list  T item                var a   new List lt T gt  list           a Add item           return a             public static List lt T gt  RemoveAt List lt T gt  list  int index                var a   new List lt T gt  list           a RemoveAt index           return a             public static List lt T gt  Remove List lt T gt  list  T item                var a   new List lt T gt  list           a Remove item           return a             example usage  orders BUY   CopyAndWriteList Clear orders BUY

User · Answer

I implemented one similar to Brian s  Mine is different    I manage the array directly  I don t enter the locks within the try block  I use yield return for producing an enumerator  I support lock recursion  This allows reads from list during iteration  I use upgradable read locks where possible  DoSync and GetSync methods allowing sequential interactions that require exclusive access to the list    The code   public class ConcurrentList lt T gt    IList lt T gt   IDisposable       private ReaderWriterLockSlim  lock   new ReaderWriterLockSlim LockRecursionPolicy SupportsRecursion       private int  count   0       public int Count               get                         lock EnterReadLock                try                                          return  count                            finally                                lock ExitReadLock                                       public int InternalArrayLength                get                         lock EnterReadLock                try                                          return  arr Length                            finally                                lock ExitReadLock                                       private T    arr       public ConcurrentList int initialCapacity                 arr   new T initialCapacity              public ConcurrentList   this 4               public ConcurrentList IEnumerable lt T gt  items                 arr   items ToArray             count    arr Length             public void Add T item                 lock EnterWriteLock            try                              var newCount    count   1                        EnsureCapacity newCount                           arr  count    item               count   newCount                                      finally                        lock ExitWriteLock                                public void AddRange IEnumerable lt T gt  items                if  items    null              throw new ArgumentNullException  items              lock EnterWriteLock             try                                  var arr   items as T      items ToArray                          var newCount    count   arr Length              EnsureCapacity newCount                          Array Copy arr  0   arr   count  arr Length                       count   newCount                    finally                        lock ExitWriteLock                                   private void EnsureCapacity int capacity                   if   arr Length  gt   capacity              return           int doubled          checked                       try                                          doubled    arr Length   2                            catch  OverflowException                                doubled   int MaxValue                                   var newLength   Math Max doubled  capacity                       Array Resize ref  arr  newLength              public bool Remove T item                 lock EnterUpgradeableReadLock             try                                  var i   IndexOfInternal item                if  i    -1                  return false                lock EnterWriteLock                try                                  RemoveAtInternal i                   return true                            finally                                               lock ExitWriteLock                                    finally                                   lock ExitUpgradeableReadLock                         public IEnumerator lt T gt  GetEnumerator                  lock EnterReadLock             try                           for  int i   0  i  lt   count  i                       deadlocking potential mitigated by lock recursion enforcement                 yield return  arr i                      finally                                   lock ExitReadLock                         IEnumerator IEnumerable GetEnumerator                 return this GetEnumerator               public int IndexOf T item                 lock EnterReadLock            try                          return IndexOfInternal item                     finally                        lock ExitReadLock                         private int IndexOfInternal T item                return Array FindIndex  arr  0   count  x   gt  x Equals item               public void Insert int index  T item                 lock EnterUpgradeableReadLock             try                                              if  index  gt   count                  throw new ArgumentOutOfRangeException  index                   lock EnterWriteLock                try                                      var newCount    count   1                  EnsureCapacity newCount                       shift everything right by one  starting at index                 Array Copy  arr  index   arr  index   1   count - index                       insert                  arr index    item                        count   newCount                            finally                                           lock ExitWriteLock                                    finally                        lock ExitUpgradeableReadLock                                       public void RemoveAt int index                    lock EnterUpgradeableReadLock            try                          if  index  gt    count                  throw new ArgumentOutOfRangeException  index                  lock EnterWriteLock                try                                          RemoveAtInternal index                             finally                                lock ExitWriteLock                                    finally                        lock ExitUpgradeableReadLock                                     private void RemoveAtInternal int index                           Array Copy  arr  index   1   arr  index   count - index-1            count--              release last element         Array Clear  arr   count  1              public void Clear                  lock EnterWriteLock            try                               Array Clear  arr  0   count                count   0                    finally                                   lock ExitWriteLock                            public bool Contains T item                 lock EnterReadLock            try                          return IndexOfInternal item     -1                    finally                                   lock ExitReadLock                         public void CopyTo T   array  int arrayIndex                        lock EnterReadLock            try                                  if  count  gt  array Length - arrayIndex                  throw new ArgumentException  Destination array was not long enough                  Array Copy  arr  0  array  arrayIndex   count                     finally                        lock ExitReadLock                                    public bool IsReadOnly                  get   return false               public T this int index                get                        lock EnterReadLock                try                                          if  index  gt    count                      throw new ArgumentOutOfRangeException  index                     return  arr index                              finally                                lock ExitReadLock                                                              set                        lock EnterUpgradeableReadLock                try                                if  index  gt    count                      throw new ArgumentOutOfRangeException  index                      lock EnterWriteLock                    try                                                               arr index    value                                    finally                                        lock ExitWriteLock                                                              finally                                lock ExitUpgradeableReadLock                                        public void DoSync Action lt ConcurrentList lt T gt  gt  action                GetSync l   gt                        action l               return 0                         public TResult GetSync lt TResult gt  Func lt ConcurrentList lt T gt  TResult gt  func                 lock EnterWriteLock            try                                  return func this                     finally                        lock ExitWriteLock                         public void Dispose                     lock Dispose

User · Answer

ConcurrentList  as a resizeable array  not a linked list  is not easy to write with nonblocking operations  Its API doesn t translate well to a  concurrent  version

User · Answer

In cases where reads greatly outnumber writes  or  however frequent  writes are non-concurrent  a copy-on-write approach may be appropriate   The implementation shown below is   lockless blazingly fast for concurrent reads  even while concurrent modifications are ongoing - no matter how long they take because  snapshots  are immutable  lockless atomicity is possible  i e  var snap    list  snap snap Count - 1   will never  well  except for an empty list of course  throw  and you also get thread-safe enumeration with snapshot semantics for free   how I LOVE immutability  implemented generically  applicable to any data structure and any type of modification dead simple  i e  easy to test  debug  verify by reading the code usable in  Net 3 5   For copy-on-write to work  you have to keep your data structures effectively immutable  i e  no one is allowed to change them after you made them available to other threads  When you want to modify  you   clone the structure make modifications on the clone atomically swap in the reference to the modified clone   Code  static class CopyOnWriteSwapper       public static void Swap lt T gt  ref T obj  Func lt T  T gt  cloner  Action lt T gt  op          where T   class               while  true                        var objBefore   Volatile Read ref obj               var newObj   cloner objBefore               op newObj               if  Interlocked CompareExchange ref obj  newObj  objBefore     objBefore                  return                      Usage  CopyOnWriteSwapper Swap ref  myList      orig   gt  new List lt string gt  orig       clone   gt  clone Add  asdf       If you need more performance  it will help to ungenerify the method  e g  create one method for every type of modification  Add  Remove       you want  and hard code the function pointers cloner and op   N B   1 It is your responsibility to make sure the no one modifies the  supposedly  immutable data structure  There s nothing we can do in a generic implementation to prevent that  but when specializing to List lt T gt   you could guard against modification using List AsReadOnly    N B   2 Be careful about the values in the list  The copy on write approach above guards their list membership only  but if you d put not strings  but some other mutable objects in there  you have to take care of thread safety  e g  locking   But that is orthogonal to this solution and e g  locking of the mutable values can be easily used without issues  You just need to be aware of it   N B   3 If your data structure is huge and you modify it frequently  the copy-all-on-write approach might be prohibitive both in terms of memory consumption and the CPU cost of copying involved  In that case  you might want to use MS s Immutable Collections instead

User · Answer

The reason why there is no ConcurrentList is because it fundamentally cannot be written   The reason why is that several important operations in IList rely on indices  and that just plain won t work   For example   int catIndex   list IndexOf  cat    list Insert catIndex   dog      The effect that the author is going after is to insert  dog  before  cat   but in a multithreaded environment  anything can happen to the list between those two lines of code   For example  another thread might do list RemoveAt 0   shifting the entire list to the left  but crucially  catIndex will not change   The impact here is that the Insert operation will actually put the  dog  after the cat  not before it   The several implementations that you see offered as  answers  to this question are well-meaning  but as the above shows  they don t offer reliable results   If you really want list-like semantics in a multithreaded environment  you can t get there by putting locks inside the list implementation methods   You have to ensure that any index you use lives entirely inside the context of the lock   The upshot is that you can use a List in a multithreaded environment with the right locking   but the list itself cannot be made to exist in that world   If you think you need a concurrent list  there are really just two possibilities    What you really need is a ConcurrentBag You need to create your own collection  perhaps implemented with a List and your own concurrency control    If you have a ConcurrentBag and are in a position where you need to pass it as an IList  then you have a problem  because the method you re calling has specified that they might try to do something like I did above with the cat  amp  dog   In most worlds  what that means is that the method you re calling is simply not built to work in a multi-threaded environment   That means you either refactor it so that it is or  if you can t  you re going to have to handle it very carefully   You you ll almost certainly be required to create your own collection with its own locks  and call the offending method within a lock

User · Answer

In sequentially executing code the data structures used are different from  well written  concurrently executing code  The reason is that sequential code implies implicit order  Concurrent code however does not imply any order  better yet it implies the lack of any defined order   Due to this  data structures with implied order  like List  are not very useful for solving concurrent problems  A list implies order  but it does not clearly define what that order is  Because of this the execution order of the code manipulating the list will determine  to some degree  the implicit order of the list  which is in direct conflict with an efficient concurrent solution   Remember concurrency is a data problem  not a code problem  You cannot Implement the code first  or rewriting existing sequential code  and get a well designed concurrent solution  You need to design the data structures first while keeping in mind that implicit ordering doesn   t exist in a concurrent system

User · Answer

With all due respect to the great answers provided already  there are times that I simply want a thread-safe IList  Nothing advanced or fancy  Performance is important in many cases but at times that just isn t a concern  Yes  there are always going to be challenges without methods like  TryGetValue  etc  but most cases I just want something that I can enumerate without needing to worry about putting locks around everything  And yes  somebody can probably find some  bug  in my implementation that might lead to a deadlock or something  I suppose  but lets be honest  When it comes to multi-threading  if you don t write your code correctly  it is going deadlock anyway  With that in mind I decided to make a simple ConcurrentList implementation that provides these basic needs   And for what its worth  I did a basic test of adding 10 000 000 items to regular List and ConcurrentList and the results were   List finished in  7793 milliseconds  Concurrent finished in  8064 milliseconds   public class ConcurrentList lt T gt    IList lt T gt   IDisposable        region Fields     private readonly List lt T gt   list      private readonly ReaderWriterLockSlim  lock       endregion       region Constructors     public ConcurrentList                 this  lock   new ReaderWriterLockSlim LockRecursionPolicy NoRecursion           this  list   new List lt T gt                public ConcurrentList int capacity                this  lock   new ReaderWriterLockSlim LockRecursionPolicy NoRecursion           this  list   new List lt T gt  capacity              public ConcurrentList IEnumerable lt T gt  items                this  lock   new ReaderWriterLockSlim LockRecursionPolicy NoRecursion           this  list   new List lt T gt  items              endregion       region Methods     public void Add T item                try                       this  lock EnterWriteLock                this  list Add item                     finally                       this  lock ExitWriteLock                         public void Insert int index  T item                try                       this  lock EnterWriteLock                this  list Insert index  item                     finally                       this  lock ExitWriteLock                         public bool Remove T item                try                       this  lock EnterWriteLock                return this  list Remove item                     finally                       this  lock ExitWriteLock                         public void RemoveAt int index                try                       this  lock EnterWriteLock                this  list RemoveAt index                     finally                       this  lock ExitWriteLock                         public int IndexOf T item                try                       this  lock EnterReadLock                return this  list IndexOf item                     finally                       this  lock ExitReadLock                         public void Clear                 try                       this  lock EnterWriteLock                this  list Clear                      finally                       this  lock ExitWriteLock                         public bool Contains T item                try                       this  lock EnterReadLock                return this  list Contains item                     finally                       this  lock ExitReadLock                         public void CopyTo T   array  int arrayIndex                try                       this  lock EnterReadLock                this  list CopyTo array  arrayIndex                     finally                       this  lock ExitReadLock                         public IEnumerator lt T gt  GetEnumerator                 return new ConcurrentEnumerator lt T gt  this  list  this  lock              IEnumerator IEnumerable GetEnumerator                 return new ConcurrentEnumerator lt T gt  this  list  this  lock               ConcurrentList                 this Dispose false              public void Dispose                 this Dispose true              private void Dispose bool disposing                if  disposing              GC SuppressFinalize this            this  lock Dispose               endregion       region Properties     public T this int index                get                       try                               this  lock EnterReadLock                    return this  list index                             finally                               this  lock ExitReadLock                                    set                       try                               this  lock EnterWriteLock                    this  list index    value                            finally                               this  lock ExitWriteLock                                       public int Count               get                       try                               this  lock EnterReadLock                    return this  list Count                            finally                               this  lock ExitReadLock                                       public bool IsReadOnly               get   return false               endregion        public class ConcurrentEnumerator lt T gt    IEnumerator lt T gt         region Fields     private readonly IEnumerator lt T gt   inner      private readonly ReaderWriterLockSlim  lock       endregion       region Constructor     public ConcurrentEnumerator IEnumerable lt T gt  inner  ReaderWriterLockSlim  lock                this  lock    lock          this  lock EnterReadLock            this  inner   inner GetEnumerator               endregion       region Methods     public bool MoveNext                 return  inner MoveNext               public void Reset                  inner Reset               public void Dispose                 this  lock ExitReadLock               endregion       region Properties     public T Current               get   return  inner Current               object IEnumerator Current               get   return  inner Current               endregion

User · Answer

I m surprised no-one has mentioned using LinkedList as a base for writing a specialised class  Often we don t need the full API s of the various collection classes  and if you write mostly functional side effect free code  using immutable classes as far as possible  then you ll actually NOT want to mutate the collection favouring various snapshot implementations  LinkedList solves some difficult problems of creating snapshot copies clones of large collections  I also use it to create  quot threadsafe quot  enumerators to enumerate over the collection  I can cheat  because I know that I m not changing the collection in any way other than appending  I can keep track of the list size  and only lock on changes to list size  Then my enumerator code simply enumerates from 0 to n for any thread that wants a  quot snapshot quot  of the append only collection  that will be guaranteed to represent a  quot snapshot quot  of the collection at any moment in time  regardless of what other threads are appending to the head of the collection  I m pretty certain that most requirements are often extremely simple  and you need 2 or 3 methods only  Writing a truly generic library is awfully difficult  but solving your own codes needs can sometimes be easy with a trick or two  Long live LinkedList and good functional programming  Cheers      love ya all  Al p s  sample hack AppendOnly class here   https   github com goblinfactory AppendOnly

User · Answer

What would you use a ConcurrentList for    The concept of a Random Access container in a threaded world isn t as useful as it may appear  The statement     if  i  lt  MyConcurrentList Count          x   MyConcurrentList i      as a whole would still not be thread-safe    Instead of creating a ConcurrentList  try to build solutions with what s there  The most common classes are  the ConcurrentBag and especially the BlockingCollection

User · Answer

Some people hilighted some goods points  and some of my thoughts     It could looklikes insane to unable random accesser  indexer  but to me it appears fine  You only have to think that there is many methods on multi-threaded collections that could fail like Indexer and Delete  You could also define failure  fallback  action for write accessor like  fail  or simply  add at the end    It is not because it is a multithreaded collection that it will always be used in a multithreaded context  Or it could also be used by only one writer and one reader  Another way to be able to use indexer in a safe manner could be to wrap actions into a lock of the collection using its root  if made public   For many people  making a rootLock visible goes agaist  Good practice   I m not 100  sure about this point because if it is hidden you remove a lot of flexibility to the user  We always have to remember that programming multithread is not for anybody  We can t prevent every kind of wrong usage  Microsoft will have to do some work and define some new standard to introduce proper usage of Multithreaded collection  First the IEnumerator should not have a moveNext but should have a GetNext that return true or false and get an out paramter of type T  this way the iteration would not be blocking anymore   Also  Microsoft already use  using  internally in the foreach but sometimes use the IEnumerator directly without wrapping it with  using   a bug in collection view and probably at more places  - Wrapping usage of IEnumerator is a recommended pratice by Microsoft  This bug remove good potential for safe iterator    Iterator that lock collection in constructor and unlock on its Dispose method - for a blocking foreach method     That is not an answer  This is only comments that do not really fit to a specific place       My conclusion  Microsoft has to make some deep changes to the  foreach  to make MultiThreaded collection easier to use  Also it has to follow there own rules of IEnumerator usage  Until that  we can write a MultiThreadList easily that would use a blocking iterator but that will not follow  IList   Instead  you will have to define own  IListPersonnal  interface that could fail on  insert    remove  and random accessor  indexer  without exception  But who will want to use it if it is not standard

[c#] No ConcurrentList<T> in .Net 4.0?

Examples related to c#

Examples related to .net

Examples related to parallel-processing

Examples related to task-parallel-library