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?

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.

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.