Concurrent collections, should read methods allow multiple threads at one time?

Question

I have custom collection and I want to add wrapper to allow concurrent access.

public class MyConcurrentCollection<T>
{
 private MyCollection _collection; // passed in constructor
 public void Add(T item)
 {
 //modifies and may temporarily "break" the collection while executing this method
 }
 public bool Contains(T item)
 {
 //only reads
 }
 // other read and write methods
}

At this moment, I have object private member that acts as lock in every method, allowing only one thread at a time to access the collection, so every method looks like this:

public bool Contains(T item)
{
 lock(_lock)
 {
 return _collection.Contains(item);
 }
}

However this seems really inefficient. Since Contains() only reads from the collection, should I allow multiple threads into it?

Of course, I need to lock access to Add() and other methods while there are threads in Contains() and I need to block access to Contains() if there is a thread wishing to modify the collection.

Is there any disadvantage of allowing multiple threads into read only methods, or should I stick with my basic solution?

• npinti: As per this SO thread, you since you are also writing, you should consider synchronizing access whenever you are using the collection.
• AK_: Why arent you using system.collections.concurrent ?
• AK_: you also could use ReaderWriterLockSlim.... but concurrent collections is probably the better aproach.

Answer 1

It is inefficient but it is necessary - what happens if you read from the collection while someone else is adding a new entry but, in the way of threading, hasn't quite finished writing the new entry's data?

There are ways to make it more efficient, particularly using a read-write lock, which locks the entire collection to both readers and writers if someone is writing, but allows multiple readers access (ie a read lock prevents a writer - the writer has to wait until you're done reading, but does not block other readers).

Incidentally, using an object as a lock is not considered best practice. Use a dedicated lock construct. I remember reading somewhere the CLR team wish they'd never allowed such use.

• AK_: this is incorrect... using lock(this) is very bad practice, creating a private object and locking it is fine, and identical to using a Monitor.
• gbjbaanb: @AK_ who said to use this as the lock? I suggested using a CriticalSection or Mutex or similar rather than a private object as the OP is using. I think that's a hangover Java construct.
• AK_: I was referring to your last paragraph. And there is a "but" missing in my comment. I ment to say that lock(this) is bad, but using private object o; ... lock(o) is fine.
• svick: Using lock on a private object (either a dedicated lock object, or existing object, like _collection) is the best practice. There is no CriticalSection type in .Net and Mutex is a wrapper around Win32 mutex, which is much less efficient than lock.
• gbjbaanb: @MikeNakis in C# - try the ReaderWriterLockSlim class that is in .net framework since 2.0 IIRC.

Answer 2

If one thread calls Add, and another thread calls Contains, at exactly the same time, and everything is implemented correctly, then Contains will return either the value that was correct before calling Add, or the value that was correct after calling Add. That's the best that we can expect.

If you can implement both the Add and the Contains method in a way that Contains will return one of these two results, without using a Lock in the contains method, even if it is called right in the middle of Add doing its thing, then you are fine. Typically that is done by Add creating data structures that are not part of the container yet, and then linking everything into the container using a single atomic operation.

Answer 3

You can do it without locks, but the cost is that your add method will be more expensive. If you have a lot more reads than writes then your add method can just create a new and updated MyCollection object:

public void Add(T item)
{
 MyCollection newCollection = new MyCollection();
 newCollection.Append(_collection); // fill with old values
 newCollection.Add(item); // add the new item
 _collection = newCollection; // switch the internal pointer to the new object
}

This works because threads accessing the read method only ever see the old or the new object, so your collection is never in an in-between state for other threads. If you have more than one writer thread you must of course add a lock to the add method (but not to the read methods).

Despite all this, you should use collections from system.collections.concurrent if possible, because they are a lot less error-prone.

• svick: If you want to do something like this, use the Immutable Collections library. It doesn't copy all the data on every change, so it's going to be much more efficient (and you won't have to write all the code yourself).
• Mike Nakis: This is bad. If an item gets added by another thread while this method is running, the item added by the other thread will be lost.
• gnasher729: That's right; this allows Add and Contains to run concurrently (if the assignment to _collection is atomic), but it doesn't allow two Add or Add and Delete to run concurrently.