Is this use of the generic List thread safe

Question

I have a System.Collections.Generic.List<T> to which I only ever add items in a timer callback. The timer is restarted only after the operation completes.

I have a System.Collections.Concurrent.ConcurrentQueue<T> which stores indices of added items in the list above. This store operation is also always performed in the same timer callback described above.

Is a read operation that iterates the queue and accesses the corresponding items in the list thread safe?

Sample code:

private List<Object> items;
private ConcurrentQueue<int> queue;
private Timer timer;
private void callback(object state)
{
    int index = items.Count;
    items.Add(new object());
    if (true)//some condition here
        queue.Enqueue(index);
    timer.Change(TimeSpan.FromMilliseconds(500), TimeSpan.FromMilliseconds(-1));
}

//This can be called from any thread
public IEnumerable<object> AccessItems()
{
    foreach (var index in queue)
    {
        yield return items[index];
    }
}

My understanding: Even if the list is resized when it is being indexed, I am only accessing an item that already exists, so it does not matter whether it is read from the old array or the new array. Hence this should be thread-safe.

Answer 1

It is thread-safish. The foreach statement uses the ConcurrentQueue.GetEnumerator() method. Which promises:

The enumeration represents a moment-in-time snapshot of the contents of the queue. It does not reflect any updates to the collection after GetEnumerator was called. The enumerator is safe to use concurrently with reads from and writes to the queue.

Which is another way of saying that your program isn't going to blow up randomly with an inscrutable exception message like the kind you'll get when you use the Queue class. Beware of the consequences though, implicit in this guarantee is that you may well be looking at a stale version of the queue. Your loop will not be able to see any elements that were added by another thread after your loop started executing. That kind of magic doesn't exist and is impossible to implement in a consistent way. Whether or not that makes your program misbehave is something you will have to think about and can't be guessed from the question. It is pretty rare that you can completely ignore it.

Your usage of the List<> is however utterly unsafe.

Answer 2

Big edit

The ConcurrentQueue is only safe with regard to the Enqueue(T) and T Dequeue() operations. You're doing a foreach on it and that doesn't get synchronized at the required level. The biggest problem in your particular case is the fact the enumerating of the Queue (which is a Collection in it's own right) might throw the wellknown "Collection has been modified" exception. Why is that the biggest problem ? Because you are adding things to the queue after you've added the corresponding objects to the list (there's also a great need for the List to be synchronized but that + the biggest problem get solved with just one "bullet"). While enumerating a collection it is not easy to swallow the fact that another thread is modifying it (even if on a microscopic level the modification is a safe - ConcurrentQueue does just that).

Therefore you absolutely need synchronize the access to the queues (and the central List while you're at it) using another means of synchronization (and by that I mean you can also forget abount ConcurrentQueue and use a simple Queue or even a List since you never Dequeue things).

So just do something like:

public void Writer(object toWrite) {
  this.rwLock.EnterWriteLock();
  try {
    int tailIndex = this.list.Count;
    this.list.Add(toWrite);

    if (..condition1..)
      this.queue1.Enqueue(tailIndex);
    if (..condition2..)
      this.queue2.Enqueue(tailIndex);
    if (..condition3..)
      this.queue3.Enqueue(tailIndex);
    ..etc..
  } finally {
    this.rwLock.ExitWriteLock();
  }
}

and in the AccessItems:

public IEnumerable<object> AccessItems(int queueIndex) {
  Queue<object> whichQueue = null;
  switch (queueIndex) {
    case 1: whichQueue = this.queue1; break;
    case 2: whichQueue = this.queue2; break;
    case 3: whichQueue = this.queue3; break;
    ..etc..
    default: throw new NotSupportedException("Invalid queue disambiguating params");    
  }

  List<object> results = new List<object>();
  this.rwLock.EnterReadLock();
  try {
    foreach (var index in whichQueue)
      results.Add(this.list[index]);
  } finally {
    this.rwLock.ExitReadLock();
  }

  return results;
}

And, based on my entire understanding of the cases in which your app accesses the List and the various Queues, it should be 100% safe.

End of big edit

First of all: What is this thing you call Thread-Safe ? by Eric Lippert

In your particular case, I guess the answer is no.

It is not the case that inconsistencies might arrise in the global context (the actual list).

Instead it is possible that the actual readers (who might very well "collide" with the unique writer) end up with inconsistencies in themselves (their very own Stacks meaning: local variables of all methods, parameters and also their logically isolated portion of the heap)).

The possibility of such "per-Thread" inconsistencies (the Nth thread wants to learn the number of elements in the List and finds out that value is 39404999 although in reality you only added 3 values) is enough to declare that, generally speaking that architecture is not thread-safe ( although you don't actually change the globally accessible List, simply by reading it in a flawed manner ).

I suggest you use the ReaderWriterLockSlim class. I think you will find it fits your needs:

private ReaderWriterLockSlim rwLock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion);

private List<Object> items;
private ConcurrentQueue<int> queue;
private Timer timer;
private void callback(object state)
{
  int index = items.Count;

  this.rwLock.EnterWriteLock();
  try {
    // in this place, right here, there can be only ONE writer
    // and while the writer is between EnterWriteLock and ExitWriteLock
    // there can exist no readers in the following method (between EnterReadLock
    // and ExitReadLock)

    // we add the item to the List
    // AND do the enqueue "atomically" (as loose a term as thread-safe)
    items.Add(new object());

    if (true)//some condition here
      queue.Enqueue(index);
  } finally {
    this.rwLock.ExitWriteLock();
  }

  timer.Change(TimeSpan.FromMilliseconds(500), TimeSpan.FromMilliseconds(-1));
}

//This can be called from any thread
public IEnumerable<object> AccessItems()
{
  List<object> results = new List<object>();

  this.rwLock.EnterReadLock();
  try {
    // in this place there can exist a thousand readers 
    // (doing these actions right here, between EnterReadLock and ExitReadLock)
    // all at the same time, but NO writers
    foreach (var index in queue)
    {
      this.results.Add ( this.items[index] );
    }        
  } finally {
    this.rwLock.ExitReadLock();
  }


  return results; // or foreach yield return you like that more :)
}

Answer 3

Is a read operation that iterates the queue and accesses the corresponding items in the list thread safe?

Is it documented as being thread safe?

If no, then it is foolish to treat it as thread safe, even if it is in this implementation by accident. Thread safety should be by design.

Sharing memory across threads is a bad idea in the first place; if you don't do it then you don't have to ask whether the operation is thread safe.

If you have to do it then use a collection designed for shared memory access.

If you can't do that then use a lock. Locks are cheap if uncontended.

If you have a performance problem because your locks are contended all the time then fix that problem by changing your threading architecture rather than trying to do dangerous and foolish things like low-lock code. No one writes low-lock code correctly except for a handful of experts. (I am not one of them; I don't write low-lock code either.)

Even if the list is resized when it is being indexed, I am only accessing an item that already exists, so it does not matter whether it is read from the old array or the new array.

That's the wrong way to think about it. The right way to think about it is:

If the list is resized then the list's internal data structures are being mutated. It is possible that the internal data structure is mutated into an inconsistent form halfway through the mutation, that will be made consistent by the time the mutation is finished. Therefore my reader can see this inconsistent state from another thread, which makes the behaviour of my entire program unpredictable. It could crash, it could go into an infinite loop, it could corrupt other data structures, I don't know, because I'm running code that assumes a consistent state in a world with inconsistent state.

Answer 4

No because you are reading and writing to/from the same object concurrently. This is not documented to be safe so you can't be sure it is safe. Don't do it.

The fact that it is in fact unsafe as of .NET 4.0 means nothing, btw. Even if it was safe according to Reflector it could change anytime. You can't rely on the current version to predict future versions.

Don't try to get away with tricks like this. Why not just do it in an obviously safe way?

As a side note: Two timer callbacks can execute at the same time, so your code is doubly broken (multiple writers). Don't try to pull off tricks with threads.