Thread safety of List<T> with One Writer, No Enumerators

Wh开发者_运维问答ile going through some database code looking for a bug unrelated to this question, I noticed that in some places List<T> was being used inappropriately. Specifically:

1. There were many threads concurrently accessing the List as readers, but using indexes into the list instead of enumerators.
2. There was a single writer to the list.
3. There was zero synchronization, readers and writers were accessing the list at the same time, but because of code structure the last element would never be accessed until the method that executed the Add() returned.
4. No elements were ever removed from the list.

By the C# documentation, this should not be thread safe. Yet it has never failed. I am wondering, because of the specific implementation of the List (I am assuming internally it's an array that re-allocs when it runs out of space), it the 1-writer 0-enumerator n-reader add-only scenario accidentally thread safe, or is there some unlikely scenario where this could blow up in the current .NET4 implementation?

edit: Important detail I left out reading some of the replies. The readers treat the List and its contents as read-only.

This can and will blow. It just hasn't yet. Stale indices is usually the first thing that goes. It will blow just when you don't want it to. You are probably lucky at the moment.

As you are using .Net 4.0, I'd suggest changing the list to a suitable collection from System.Collections.Concurrent which is guaranteed to be thread safe. I'd also avoid using array indices and switch to ConcurrentDictionary if you need to look up something:

http://msdn.microsoft.com/en-us/library/dd287108.aspx

Because of it has never failed or your application doesn't crash that doesn't mean that this scenario is thread safe. for instance suppose the writer thread does update a field within the list, lets say that is was a long field, at the same time the reader thread reading that field. the value returned maybe a bitwise combination of the two fields the old one and the new one! that could happen because the reader thread start reading the value from memory but before it finishes reading it the writer thread just updated it.

Edit: That of course if we suppose that the reader threads will just read all the data without updating anything, I am sure that they doesn't change the values of the arrays them self but, but they could change a property or field within the value they read. for instance:

for (int index =0 ; index < list.Count; index++)
{
    MyClass myClass = list[index];//ok we are just reading the value from list
    myClass.SomeInteger++;//boom the same variable will be updated from another threads...
}

This example not talking about thread safe of the list itself rather than the shared variables that the list exposed.

The conclusion is that you have to use a synchronization mechanism such as lock before interaction with the list, even if it has only one writer and no item removed, that will help you prevent tinny bugs and failure scenarios you are dispensable for in the first place.

Thread safety only matters when data is modified more than once at a time. The number of readers does not matter. Even when someone is writing while someone reads, the reader either gets the old data or the new, it still works. The fact that elements can only be accessed after the Add() returns, prevents parts of the element being read seperately. If you would start using the Insert() method readers could get the wrong data.

It follows then, that if the architecture is 32 bits, writing a field bigger than 32 bits, such as long and double, is not a thread safe operation; see the documentation for System.Double:

Assigning an instance of this type is not thread safe on all hardware platforms because the binary representation of that instance might be too large to assign in a single atomic operation.

If the list is fixed in size, however, this situation matters only if the List is storing value types greater than 32 bits. If the list is only holding reference types, then any thread safety issues stem from the reference types themselves, not from their storage and retrieval from the List. For instance, immutable reference types are less likely to cause thread safety issues than mutable reference types.

Moreover, you can't control the implementation details of List: that class was mainly designed for performance, and it's likely to change in the future with that aspect, rather than thread safety, in mind.

In particular, adding elements to a list or otherwise changing its size is not thread safe even if the list's elements are 32 bits long, since there is more involved in inserting, adding, or removing than just placing the element in the list. If such operations are needed after other threads have access to the list, then locking access to the list or using a concurrent list implementation is a better choice.

First off, to some of the posts and comments, since when was documentation reliable?

Second, this answer is more to the general question than the specifics of the OP.

I agree with MrFox in theory because this all boils down to two questions:

1. Is the List class is implemented as a flat array?

If yes, then:

1. Can a write instruction be preempted in the middle of a write>

I believe this is not the case -- the full write will happen before anything can read that DWORD or whatever. In other words, it will never happen that I write two of the four bytes of a DWORD and then you read 1/2 of the new value and 1/2 of the old one.

So, if you're indexing an array by providing an offset to some pointer, you can read safely without thread-locking. If the List is doing more than just simple pointer math, then it is not thread safe.

If the List was not using a flat array, I think you would have seen it crash by now.

My own experience is that it is safe to read a single item from a List via index without thread-locking. This is all just IMHO though, so take it for what it's worth.

Worst case, such as if you need to iterate through the list, the best thing to do is:

1. lock the List
2. create an array the same size
3. use CopyTo() to copy the List to the array
4. unlock the List
5. then iterate through the array instead of the list.

in (whatever you call the .net) C++:

  List<Object^>^ objects = gcnew List<Object^>^();
  // in some reader thread:
  Monitor::Enter(objects);
  array<Object^>^ objs = gcnew array<Object^>(objects->Count);
  objects->CopyTo(objs);
  Monitor::Exit(objects);
  // use objs array

Even with the memory allocation, this will be faster than locking the List and iterating through the entire thing before unlocking it.

Just a heads up though: if you want a fast system, thread-locking is your worst enemy. Use ZeroMQ instead. I can speak from experience, message-based synch is the right way to go.