In .NET, there is such a structure as a thread-safe ConcurrentDictionary. But for some reason there is no thread-safe list? Maybe someone knows why? Thank you in advance

  • one
    in a nutshell, because List <T> with locks is faster - Grundy
  • one
    I think because the index of the element, unlike the key, is not secure. If you add an item with a key to the Dictionary, and then delete the item with another key, you can get access using the old key. But removing an item from the list invalidates all indexes. - VladD
  • one
    @andreycha, if only in the evening :-) via the first link, by the way, a quote from the book C # 5.0 Unleashed 1st Edition by Bart De Smet (Author) - Grundy
  • one
    @ixSci Grundy imho not quite correctly translated. It says that it is not easy to make an effective implementation of ConcurrentList , and that such an implementation will not be much faster than a regular sheet with locks (unlike the stack and the queue), so we decided not to bother. - andreycha
  • one
    @ixSci: Perhaps this is due to the lesser load on the allocator. The standard allocator in C ++ is slow, so a 10-fold increase can only be due to this. It is interesting to compare in speed List<int> with lock'om and the very implementation, which is 10 times faster :-D - VladD

4 answers 4

Why is there no ConcurrentList <T>?
The answer is that all Concurrent* collections in the System.Collections.Concurrent namespace have extremely efficient and scalable implementations. That is, inside they use such lightweight synchronization primitives as SpinLock and SpinWait . In fact, the ConcurrentQueue <T> and ConcurrentStack <T> implementations do not use any locks at all.
This led to the fact that writing the same effective list was not an easy task.
As a result, there is no ConcurrentList <T> type , because its implementation will not be significantly better than a List <T> with classic lock (which will be rather heavy)

C # 5.0 Unleashed
Bart de smet

    In the IList<T> interface, there are methods for working with elements by their index. However, in a multi-threaded environment, elements can be removed or shifted from their place at any time, and thus access by index loses meaning. Therefore, there is no thread-safe ConcurrentList<T> , but there is a thread-safe BlockingCollection<T> .

      I do not know the exact reason, I can only guess. In my opinion, there is no such structure due to the fact that the List in C # contains elements in one piece (contiguous memory), and it is rather difficult to implement such a structure in terms of lock-free, apparently. All the examples of lock-free or wait-free structures that I saw were based on nodes that referred to each other. Apparently, it is quite difficult to do with a structure that does not have nodes, so they decided that “not worth the money”.

      Here I found the description of the lock-free vector for C ++, which is suitable for the List from C #, as a whole.

        This is done for the sake of performance. If there is exactly the need for a thread-safe list, use CopyOnWriteArrayList

        A thread-safe variant of {@link java.util.ArrayList}

        • 2
          This is all about .NET and c # :-) - Grundy