Creating Thread Safe List using Reader Writer Lock

Question

Completely editing the earlier version, Can the following implementation be the Thread Safe List implementation. I just need to know whether it would truly thread safe or not, I know performance wise there would still be issues. Currently version is using ReaderWriterLockSlim, I have another implementation using the Lock, doing the same job

using System.Collections.Generic; using System.Threading;

/// <summary>
/// Thread safe version of the List using ReaderWriterLockSlim 
/// </summary>
/// <typeparam name="T"></typeparam>
public class ThreadSafeListWithRWLock<T> : IList<T>
{
    // Internal private list which would be accessed in a thread safe manner
    private List<T> internalList;

    // ReaderWriterLockSlim object to take care of thread safe acess between multiple readers and writers
    private readonly ReaderWriterLockSlim rwLockList;

    /// <summary>
    /// Public constructor with variable initialization code
    /// </summary>
    public ThreadSafeListWithRWLock()
    {
        internalList = new List<T>();

        rwLockList = new ReaderWriterLockSlim();
    }

    /// <summary>
    /// Get the Enumerator to the Thread safe list
    /// </summary>
    /// <returns></returns>
    public IEnumerator<T> GetEnumerator()
    {
        return Clone().GetEnumerator();
    }

    /// <summary>
    /// System.Collections.IEnumerable.GetEnumerator implementation to get the IEnumerator type
    /// </summary>
    /// <returns></returns>
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return Clone().GetEnumerator();
    }

    /// <summary>
    /// Clone method to create an in memory copy of the Thread safe list
    /// </summary>
    /// <returns></returns>
    public List<T> Clone()
    {
        List<T> clonedList = new List<T>();

        rwLockList.EnterReadLock();

        internalList.ForEach(element => { clonedList.Add(element); });            

        rwLockList.ExitReadLock();

        return (clonedList);
    }

    /// <summary>
    /// Add an item to Thread safe list
    /// </summary>
    /// <param name="item"></param>
    public void Add(T item)
    {
        rwLockList.EnterWriteLock();

        internalList.Add(item);

        rwLockList.ExitWriteLock();
    }

    /// <summary>
    /// Remove an item from Thread safe list
    /// </summary>
    /// <param name="item"></param>
    /// <returns></returns>
    public bool Remove(T item)
    {
        bool isRemoved;

        rwLockList.EnterWriteLock();

        isRemoved = internalList.Remove(item);

        rwLockList.ExitWriteLock();

        return (isRemoved);
    }

    /// <summary>
    /// Clear all elements of Thread safe list
    /// </summary>
    public void Clear()
    {
        rwLockList.EnterWriteLock();

        internalList.Clear();

        rwLockList.ExitWriteLock();
    }

    /// <summary>
    /// Contains an item in the Thread safe list
    /// </summary>
    /// <param name="item"></param>
    /// <returns></returns>
    public bool Contains(T item)
    {
        bool containsItem;

        rwLockList.EnterReadLock();

        containsItem = internalList.Contains(item);

        rwLockList.ExitReadLock();

        return (containsItem);
    }

    /// <summary>
    /// Copy elements of the Thread safe list to a compatible array from specified index in the aray
    /// </summary>
    /// <param name="array"></param>
    /// <param name="arrayIndex"></param>
    public void CopyTo(T[] array, int arrayIndex)
    {
        rwLockList.EnterReadLock();

        internalList.CopyTo(array,arrayIndex);

        rwLockList.ExitReadLock();
    }

    /// <summary>
    /// Count elements in a Thread safe list
    /// </summary>
    public int Count
    {
        get
        {
            int count;

            rwLockList.EnterReadLock();

            count = internalList.Count;

            rwLockList.ExitReadLock();

            return (count);
        }
    }

    /// <summary>
    /// Check whether Thread safe list is read only
    /// </summary>
    public bool IsReadOnly
    {
        get { return false; }
    }

    /// <summary>
    /// Index of an item in the Thread safe list
    /// </summary>
    /// <param name="item"></param>
    /// <returns></returns>
    public int IndexOf(T item)
    {
        int itemIndex;

        rwLockList.EnterReadLock();

        itemIndex = internalList.IndexOf(item);

        rwLockList.ExitReadLock();

        return (itemIndex);
    }

    /// <summary>
    /// Insert an item at a specified index in a Thread safe list
    /// </summary>
    /// <param name="index"></param>
    /// <param name="item"></param>
    public void Insert(int index, T item)
    {
      rwLockList.EnterWriteLock();

      if (index <= internalList.Count - 1 && index >= 0)
        internalList.Insert(index,item);

      rwLockList.ExitWriteLock();
    }

    /// <summary>
    /// Remove an item at a specified index in Thread safe list
    /// </summary>
    /// <param name="index"></param>
    public void RemoveAt(int index)
    {
       rwLockList.EnterWriteLock();

       if (index <= internalList.Count - 1 && index >= 0)
        internalList.RemoveAt(index);

       rwLockList.ExitWriteLock();
    }

    /// <summary>
    /// Indexer for the Thread safe list
    /// </summary>
    /// <param name="index"></param>
    /// <returns></returns>
    public T this[int index] 
    {
        get
        {
            T returnItem = default(T);

           rwLockList.EnterReadLock();

           if (index <= internalList.Count - 1 && index >= 0)
               returnItem = internalList[index];              

           rwLockList.ExitReadLock();

            return (returnItem);
        }
        set
        {
            rwLockList.EnterWriteLock();

            if (index <= internalList.Count - 1 && index >= 0)
                internalList[index] = value;

            rwLockList.ExitWriteLock();
        }
    }
}

Why not use [`ConcurrentBag`](http://msdn.microsoft.com/en-us/library/dd381779(v=vs.110).aspx) or any other list type in the Concurrent namespace? — Patrick Hofman, Sep 05 '14 at 08:12
You're much better off just using `lock` whenever the list is accessed. Also, as written above enumeration is not thread safe. — Zer0, Sep 05 '14 at 08:12
Why are you creating a concurrent list instead of using the built in constructs, like ConcurrentBag. — i3arnon, Sep 05 '14 at 08:12
That `GetEnumerator` is entirely broken; in most scenarios, a reader-writer lock is actually overkill and overhead compared to a simple lock — Marc Gravell, Sep 05 '14 at 08:13
@PatrickHofman `ConcurrentBag` is not ordered. Also it uses `ThreadLocal` storage so it's not always ideal. — Zer0, Sep 05 '14 at 08:14
Why do you catch exceptions only to then simply throw them again? — Daniel Kelley, Sep 05 '14 at 08:15
@Zer0 Just locking whenever the list is accessed is not sufficient. `if (list.Count > 0) return list[0];` would still be buggy due to a race condition. — Matthew Watson, Sep 05 '14 at 08:15
Is there any particular reason why you can't use the standard `lock(object){}` mechanism? — Evil Dog Pie, Sep 05 '14 at 08:16
@MatthewWatson Of course locking is sufficient. `lock(list) { if(list.Count > 0) return list[0]; }` — Zer0, Sep 05 '14 at 08:18
@Zer0 Yes, but that is adding locking outside the class; I was talking about adding locking with the list. I agree that external locking would work, but it is impossible to guarantee if any method returns a native list because you have no direct control over how it is used. Better to use a different data structure or return a copy of the list, IMO. — Matthew Watson, Sep 05 '14 at 08:20
@Daniel Kelley Exception handler is a wrapper layer, that's why exception is re-thrown, anyway this point has nothing to do with the main question — Mrinal Kamboj, Sep 05 '14 at 08:56
@MrinalKamboj It doesn't indeed which is why it was a comment. However, the "wrapper layer" explanation makes zero sense. it is a poor practice. — Daniel Kelley, Sep 05 '14 at 08:59
@Daniel Kelley why is it a poor practice to catch and throw an exception. It certainly aids debugging. Is there any issue to do it this way, does it impacts performance — Mrinal Kamboj, Sep 05 '14 at 09:04
@MrinalKamboj The comments section of a question is not the place for me to explain why it is poor practice. However, for a start you have just lost your stack trace by calling `throw ex` - you should instead call `throw`. However, catching an exception simply to throw it again is pointless. — Daniel Kelley, Sep 05 '14 at 09:08
@Daniel Kelley got the point thanks, it was a mistake on my end, since we have number of custom exception classes, which are build in the data layer on receiving the error code an then thrown to be logged at the wrapper, that's why I added this kind of implementation — Mrinal Kamboj, Sep 05 '14 at 09:33

score 4 · Accepted Answer · answered Sep 05 '14 at 08:47

4

Implementing a custom List<T> that encapsulates thread-safety is rarely worth the effort. You're likely best off just using lock whenever you access the List<T>.

But being in a performance intensive industry myself there have been cases where this becomes a bottleneck. The main drawback to lock is the possibility of context switching which is, relatively speaking, extremely expensive both in wall clock time and CPU cycles.

The best way around this is using immutability. Have all readers access an immutable list and writers "update" it using Interlocked operations to replace it with a new instance. This is a lock-free design that makes reads free of synchronization and writes lock-free (eliminates context switching).

I will stress that in almost all cases this is overkill and I wouldn't even consider going down this path unless you're positive you need to and you understand the drawbacks. A couple of the obvious ones are readers getting point-in-time snapshots and wasting memory creating copies.

ImmutableList from Microsoft.Bcl.Immutable is also worth a look. It's entirely thread-safe.

answered Sep 05 '14 at 08:47

Zer0

7,191
1
20
34

As an alternative to using an immutable list, you can simply return copies of the list when it is asked for, which is a good solution if the list isn't too large. (Note that the Microsoft immutable list makes a copy of itself whenever you call an apparently mutating operation, similar to how string operations work - so that is also heavy on memory use if the list is large.) – Matthew Watson Sep 05 '14 at 08:49
There's an implementation at the following link - http://stackoverflow.com/questions/5874317/thread-safe-listt-property Here the GetEnumerator is implemented in a thread safe way, along with that if we make the modification (Add / Remove) thread safe, using a lock will that serve the purpose – Mrinal Kamboj Sep 05 '14 at 09:16
The SynchronizedCollection can that be a replacement, though it's not part of Concurrent namespace, since it was introduced earlier than .Net 4.0 – Mrinal Kamboj Sep 05 '14 at 09:29
@MrinalKamboj If you look at the implementation of the GetEnumerator() in the link you mention, you'll see that it makes a copy of the entire list each time it is called. If you're going to do that, I think you might as well just return a copy of the list in the first place. – Matthew Watson Sep 05 '14 at 09:34
@Matthew Watson While creating a copy, which will be a shallow copy, to the reference type List, only job that it will do is maintain the state of the enumerator, still I would need to make the copying process thread safe, since if another thread modified the List at same time, then it could be a case of exception. Though that situation in my case would be rare, but still possible – Mrinal Kamboj Sep 05 '14 at 10:24
@Matthew Watson, I think I understood your view, so I lock while creating a clone or copy too, to ensure that state doesn't get modified while getting the shallow copy. This will ensure that there's no corruption even if a thread modifies the List, which will be again in same lock object, thus making the operation thread safe – Mrinal Kamboj Sep 05 '14 at 10:40
I think this is best possible explanation which clarifies the point, along with various comments that simple locking and cloning would best serve the purpose. – Mrinal Kamboj Sep 05 '14 at 10:42

score 3 · Answer 2 · edited May 23 '17 at 12:16

3

That is not threadsafe.

The method GetEnumerator() will not retain any lock after the enumerator has been returned, so any thread would be free to use the returned enumerator without any locking to prevent them from doing so.

In general, trying to create a threadsafe list type is very difficult.

See this StackOverflow thread for some discussion: No ConcurrentList<T> in .Net 4.0?

edited May 23 '17 at 12:16

Community

1
1

answered Sep 05 '14 at 08:13

Matthew Watson

104,400
10
158
276

score 1 · Answer 3 · edited May 23 '17 at 12:08

If you are trying to use some kind of reader/writer lock, rather than a simple locking scheme for both reading and writing, your concurrent reads probably greatly outnumber your writes. In that case, a copy-on-write approach, as suggested by Zer0, can be appropriate.

In an answer to a related question I posted a generic utility function that helps turning any modification on any data structure into a thread-safe and highly concurrent operation.

Code

static class CopyOnWriteSwapper
{
    public static void Swap<T>(ref T obj, Func<T, T> cloner, Action<T> op)
        where T : class
    {
        while (true)
        {
            var objBefore = Volatile.Read(ref obj);
            var newObj = cloner(objBefore);
            op(newObj);
            if (Interlocked.CompareExchange(ref obj, newObj, objBefore) == objBefore)
                return;
        }
    }
}

Usage

CopyOnWriteSwapper.Swap(ref _myList,
    orig => new List<string>(orig),
    clone => clone.Add("asdf"));

More details about what you can do with it, and a couple caveats can be found in the original answer.

Creating Thread Safe List using Reader Writer Lock

3 Answers3

Linked