8
\$\begingroup\$

I'm working on a WPF 4.5 desktop application that has several nested collections with the following key aspects:

  • writes mainly from UI thread, but also from worker threads
  • writes are relatively seldom, mainly directly after a user interaction
  • reads from any thread, but esp. one performance critical worker thread with very many reads (iterating in millisecond intervals)
  • with the exception of the thread mentioned above, read/write performance should not be critical
  • items need to be ordered, i.e. an item's position must always stay the same
  • "remove item" must be supported
  • "insert at" must be supported, although I'm aware that indices must be handled with care, if several threads are involved
  • collection will be used as a WPF binding source and must be observable (implement INotifyCollectionChanged and INotifyPropertyChanged so WPF can update the UI, if items are added/removed)
  • collection must support live-shaping (allowing WPF to instantly update a control's sorting/filtering, if relevant items' properties change; requires the underlying collection to implement IList or similar, so a ListCollectionView can be used)
  • a lookup via key is not required (or can be achieved using extension methods, e.g. FirstOrDefault)
  • approx. max. number of collections < 10k
  • approx. max. number of items / collection < 1k

The out-of-the-box system classes have the following issues (for my use-case) which prevent me from using them as-is:

  • System.Collections.Concurrent classes do not implement IList - and cannot be used for live-shaping
  • System.Collections.ObjectModel.ObservableCollection<T> is not thread-safe

So to fulfill all above requirements I created a wrapper class that implements the required interfaces (e.g. IList, INotifyCollectionChanged...). Internally I chose to use List<T>. (I could have chosen ObservableCollection, but I wanted full control when invoking/dispatching CollectionChanged.)

For all write operations the wrapper class uses lock(_lock) and delegates the call to the inner list. Also - from within the lock - it updates an Array snapshot of the current list, stored in a private field, _snapshot. Then - still from within the lock - it uses System.Windows.Threading.Dispatcher.InvokeAsync() to raise the CollectionChanged event on the correct UI thread.

All read operations use the cached _snapshot, esp. GetEnumerator. The intention behind the snapshot is to avoid locking in the GetEnumerator implementation, for performance reasons of the thread with many reads.

Is the approach ok, what am I missing, what else must I be aware of?

Here's my current code (with some omissions), which appears to work:

EDIT: I included the previously omitted ICollection and IList implementations.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.ComponentModel;
using System.Linq;
using System.Threading;
using System.Windows;

namespace StackOverflow.Questions
{
    public class ObservableConcurrentList<T> : IList, IList<T>, INotifyCollectionChanged, INotifyPropertyChanged
    {
        private readonly System.Windows.Threading.Dispatcher _context;
        private readonly IList<T> _list = new List<T>();
        private readonly object _lock = new object();
        private T[] _snapshot; 

        public ObservableConcurrentList()
        {
            _context = Application.Current?.Dispatcher;

            updateSnapshot();

            SuppressNotifications = suppressNotifications;
        }

        public event NotifyCollectionChangedEventHandler CollectionChanged;

        public event PropertyChangedEventHandler PropertyChanged;

        private void updateSnapshot()
        {
            lock (_lock) //precautionary; should be re-entry
            {
                Interlocked.Exchange(ref _snapshot, _list.ToArray());
            }
        }

        private void notify(NotifyCollectionChangedEventArgs args)
        {
            if (_context == null)
            {
                invokeCollectionChanged(args);
            }
            else
            {
                _context.InvokeAsync(() => invokeCollectionChanged(args));
            }
        }

        private void invokeCollectionChanged(NotifyCollectionChangedEventArgs args)
        {
            CollectionChanged?.Invoke(this, args);
            PropertyChanged?.Invoke(this, new PropertyChangedEventArgs(nameof(Count)));
        }

        #region IEnumerable
        public IEnumerator<T> GetEnumerator()
        {
            var localSnapshot = _snapshot; //create local variable to protect enumerator, if class member (_snapshot) should be changed/replaced while iterating
            return ((IEnumerable<T>)localSnapshot).GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
        #endregion

        #region ICollection<T>
        public void Add(T item)
        {
            lock (_lock)
            {
                _list.Add(item);
                updateSnapshot();

                notify(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Add, item, _list.Count - 1));
            }
        }

        public bool Contains(T item)
        {
            return _snapshot.Contains(item);
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            _snapshot.CopyTo(array, arrayIndex);
        }

        public bool Remove(T item)
        {
            lock (_lock)
            {
                var index = _list.IndexOf(item);
                if (index > -1)
                {
                    if (_list.Remove(item))
                    {
                        updateSnapshot();

                        notify(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Remove, item, index));
                        return true;
                    }
                }

                return false;
            }
        }

        public void Clear()
        {
            lock (_lock)
            {
                _list.Clear();
                updateSnapshot();

                notify(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Reset));
            }
        }

        public bool IsReadOnly => false;

        #endregion

        #region IList<T>

        public int IndexOf(T item)
        {
            return Array.IndexOf(_snapshot, item);
        }

        public void Insert(int index, T item)
        {
            lock (_lock)
            {
                _list.Insert(index, item);
                updateSnapshot();

                notify(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Add, item, index));
            }
        }

        public void RemoveAt(int index)
        {
            lock (_lock)
            {
                var item = _list[index];
                _list.RemoveAt(index);
                updateSnapshot();

                notify(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Remove, item, index));
            }
        }


        public T this[int index]
        {
            get => _snapshot[index];
            set
            {
                lock (_lock)
                {
                    var item = _list[index];
                    _list[index] = value;
                    updateSnapshot();

                    notify(new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Replace, value, item, index));
                }
            }
        }
        #endregion

        #region ICollection (explicit)
        void ICollection.CopyTo(Array array, int index)
        {
            CopyTo((T[])array, index);
        }

        public int Count => _snapshot.Length;

        object ICollection.SyncRoot => this; //https://stackoverflow.com/questions/728896/whats-the-use-of-the-syncroot-pattern/728934#728934

        bool ICollection.IsSynchronized => false; //https://stackoverflow.com/questions/728896/whats-the-use-of-the-syncroot-pattern/728934#728934

        #endregion

        #region IList (explicit)

        object IList.this[int index]
        {
            get => ((IList<T>)this)[index];
            set => ((IList<T>)this)[index] = (T)value;
        }

        int IList.Add(object value)
        {
            lock (_lock)
            {
                Add((T)value);

                return _list.Count - 1;
            }
        }

        bool IList.Contains(object value)
        {
            return Contains((T)value);
        }

        int IList.IndexOf(object value)
        {
            return IndexOf((T)value);
        }

        void IList.Insert(int index, object value)
        {
            Insert(index, (T)value);
        }

        bool IList.IsFixedSize => false;

        void IList.Remove(object value)
        {
            Remove((T)value);
        }
        #endregion
    }
}

EDIT: Coming back to this after some time in which I've had some real-life experience with the above concept, I'd like to add:

  • The above implementation will not work reliably. If I find the time, I will try to update the post using an extract from my actual working class.
  • Raising CollectionChanged from within the lock is indeed more than a smell as noted in the comments.
  • If dispatched using Invoke from within the lock, deadlocks can and will occur.
  • Dispatching from within the lock using InvokeAsync defies the intention/purpose, because the event will be handled later, actually outside the lock, because the call will be added to the message loop.
  • Ergo: Use DispatchAsync from outside the lock - as "fire & forget" is often best practice regarding UI events.
  • Consequences:
    • For the CollectionChanged event the Reset variant must always be used, because the colleciton may have changed since the event was raised, because it is handled at an undetermined time later. That would lead to inconsistencies and/or exceptions.
    • As defined for the Reset flag, the UI will always update the entire list, instead of adding/removing specific items. Performance-wise this is sup-optimal, of course.
\$\endgroup\$
  • 3
    \$\begingroup\$ I'm not happy about you ommiting the IList implementation. Since this is one of the main reasons you've decided to create your own type it definitely shouldn't have been removed. \$\endgroup\$ – t3chb0t Dec 30 '18 at 10:43
  • \$\begingroup\$ the IList methods only wrap IList<T> methods. \$\endgroup\$ – mike Dec 30 '18 at 10:47
  • 1
    \$\begingroup\$ Please add it anyway. \$\endgroup\$ – Mast Dec 30 '18 at 11:19
  • 1
    \$\begingroup\$ @t3chb0t, @Mast: I just added the implementations of ICollection and IList \$\endgroup\$ – mike Dec 30 '18 at 13:25
4
\$\begingroup\$

Raising events inside of a lock is a code smell. Locks should be short lived as possible. Plus since, maybe today, you know what the events will do that doesn't mean in the future they won't change. Having a long processing event could make this a bottle neck or if an event also subscribed and wanted to update the collection has the potential for a deadlock.

You have this statement in the constructor

SuppressNotifications = suppressNotifications;

This field and parameter don't exist. I assume it's a copy / paste error.

Instead of locking and creating a snapshot each time you could use the ReaderWriterLockSlim class to lock reading and writing. The GetEnumerator would probably still want a snapshot but could be done by making the snapshot lazy. Then the code would look something similar to this

private void UpdateSnapshot()
{
    if (_snapShot == null || _snapShot.IsValueCreated)
    {
        Interlocked.Exchange(ref _snapShot, new Lazy<T[]>(() =>
        {
            T[] result;
            var lockTaken = false;
            try
            {
                _lock.EnterReadLock();
                lockTaken = true;
                result = _list.ToArray();
            }
            finally
            {
                if (lockTaken)
                {
                    _lock.ExitReadLock();
                }
            }
            return result;
        }));
    }
}

Basically this would defer the coping of all the items to the snapshot until an enumerator has accessed it and if no updates where done then the Lazy object is acting like a caching object. Again this code is assuming switching to the ReaderWriterLockSlim Class. But this way when collection has a process that is adding items to the collection the class doesn't make a new copy of the list every add.

** As a side note the coding for the ReaderWriterLockSlim class is a bit much but it's not hard to create an IDisposable class that wraps it so the locks turn into using statements that hide the try/finally/lock taken code.

For saving the dispatcher I would suggest reading this blog. It gets a list of event handler target to see if it's a dispatcher object

var delegates = eventHandler.GetInvocationList();
// Walk thru invocation list
foreach (NotifyCollectionChangedEventHandler handler in delegates)
{
    var dispatcherObject = handler.Target as DispatcherObject;
    // If the subscriber is a DispatcherObject and different thread
    if (dispatcherObject != null && dispatcherObject.CheckAccess() == false)
    {
        // Invoke handler in the target dispatcher's thread
        dispatcherObject.Dispatcher.Invoke(DispatcherPriority.DataBind, handler, this, e);
    }
    else // Execute handler as is
    {
        handler(this, e);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Regarding the event from within the lock, I get the code smell, but figured it would be safer this way when the UI (WPF) handles the event, making sure it is not changed again in the meantime which could make the NotifyCollectionChangedEventArgswrong. \$\endgroup\$ – mike Jan 3 at 21:52
  • \$\begingroup\$ Regarding the dispatcher: the code presented here will soon be modified to use a custom dispatcher (interface) that may wrap System.Windows.Threading.Dispatcher, but may also use a queue etc. Thanks a lot for the link, though, it may come in handy sometime else. \$\endgroup\$ – mike Jan 3 at 21:56
  • \$\begingroup\$ Regarding the lazy snapshot for GetEnumerator: that is specifically the code where I want as little overhead as possible and the extra memory cost will not be a problem. Nonetheless: a lazy snapshot implementation could be an interesting (if optional) feature. \$\endgroup\$ – mike Jan 3 at 22:01
2
\$\begingroup\$

Usability (WPF Only)

I've read in comments on a different answer that you were going to wrap private readonly System.Windows.Threading.Dispatcher _context; in some kind of custom dispatcher. Don't do this! Your class depends on a WPF dispatcher, hence it's use cases are limited to WPF. You should use a TaskScheduler instead. If you create your list in the main UI thread of WPF, you could give it an instance like this:

var uiCallbackScheduler = TaskScheduler.FromCurrentSynchronizationContext();

You are using some nasty tricks to make the collection work for unit tests I suppose. The problem is you have a hard dependency on Application.Current. Whether you keep the dispatcher or use a task scheduler, you should always try to avoid dependencies like this. You won't even be able to test the production pattern (using a dispatcher) in unit tests.

 // so you won't always have a dispatcher, why allow this?
_context = Application.Current?.Dispatcher; 

private void notify(NotifyCollectionChangedEventArgs args)
{
    if (_context == null)
    {
        invokeCollectionChanged(args);
    }
    else
    {
        _context.InvokeAsync(() => invokeCollectionChanged(args));
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.