Since we don’t have a new Concurrent Podcast ready, I thought I’d go into a little detail about the change away from IBlockingQueue I mentioned in Episode 1 of the Concurrent Podcast.

A little history

When I first wrote the dispatcher for the PubSubService in Dream, I was hoping to dispatch the work against the .NET Threadpool. Early testing showed that the standard threadpool was near useless for dispatching lots of small work items quickly. Load tests seemed to indicate that there was a lock contention scheduling new work that caused short lived workers to execute in a near sequential manner. I.e. a new worker wouldn’t get dispatched until the the previous one was done.

Another problem with using the standard threadpool for dispatch was that i couldn’t easily limit how many workers would be used in isolation from other users of the threadpool, which would lead to worker starvation.

Blocking on work

Rather than fight with the threadpool, I opted for a classic producer/consumer pattern in which all work was queued while dedicated worker threads would pull from the queue and dispatch the items. Since .NET queues are not threadsafe, I implemented a blocking queue:

    public interface IBlockingQueue<T> : IEnumerable<T> {
        bool TryDequeue(TimeSpan timeout, out T item);
        T Dequeue();
        void Enqueue(T data);
        void Close();
        bool IsClosed { get; }
        int Count { get; }
    }

I also made it IEnumerable, so that the worker thread could simply run the dispatch as a foreach loop. This way any thread can enqueue an item to process, while n dedicated worker threads can process the work like this:

   foreach(var data in queue) {
      // process data
   }

The thread automatically exits when someone closes the queue, dropping each processor out of its foreach loop.

This pattern works great if you have a steady flow of work and can determine the optimum number of worker threads to spawn. Unfortunately, many scenarios revolve around inconsistent producers of work, leading to alternately workers sitting idle and the queue backing up. Since each thread has a significant memory footprint having them sit idle isn’t desirable, and neither is work backing up because  you didn’t spawn enough workers.

PubSub is one of these scenarios where the flow of events is generally feast or famine. In addition, we use a number of chained pubsub services, leading to a number of dedicated threads sitting around. It was clear that further use of this pattern was only going to exasperate the problem.

Enter the ElasticThreadPool

With the existing .NET Threadpool being a known problem and the Work Stealing Threadpool of ParallelFX not arriving until C# 4.0, we had a need for our own threadpool to more efficiently dispatch asynchronous work in Dream. Steve set out to build a lock-free work stealing threadpool and after a couple of iterations arrived at the work dispatch abstraction, IDispatchQueue:

    public interface IDispatchQueue {
        void QueueWorkItem(VoidHandler callback);
        bool TryQueueWorkItem(VoidHandler callback);
    }

one of the implementors of which is ElasticThreadPool(int minReservedThreads, int maxParallelThreads), which takes the number of reserved (as in dedicated) and maximum threads to use for dispatch. An ElasticThreadPool(n,n) would function identically to an IBlockingQueue<VoidHandler> with n dedicated threads spawned to pull items from it. Where  the ElasticThreadPool gets interesting is when maxParallelThreads is larger than minReservedThreads — now the threadpool will get a thread from a global dispatch threadpool to grow or shrink the number of workers according to the amount of work to dispatch.

One of the drawbacks of the built-in threadpool is that it uses a single queue that all workers feed off, creating lock contention for acquiring work. Rather than using raw threads as the workers, the ElasticThreadPool uses a wrapper called DispatchThread, each of which has its own work queue, so that work can be queued on a worker directly and pulled without contention. In addition ElasticThreadPool employs a stealing algorithm, so that an idle worker can steal queued work from another worker. This is done via a lock-free double-ended queue, so that stealing does not re-introduce lock contention in work acquisition. The combination of these techniques means that the ElasticThreadPool is very efficient in dispatching work and dynamically scaling the number of workers required.

Dispatching work is an implementation detail

With IDispatchQueue Dream has abstracted the implementation of how processing of work items happens, so rolling your own consumer with something like IBlockingQueue is no longer required. Should the scenario of fixed dedicated threads with a single blocking queue still appears to be more advantageous, the dispatch interface makes it easy to create an implementation to use instead of the ElasticThreadPool. And while the best fit for most work queuing scenarios is generally the  ElasticThreadPool, Dream already includes several alternative IDispatchQueue implementations, including one that wraps the standard ThreadPool.

One of the goals of the Dream framework is to make parallel programming simpler. For this purpose it provides such helpers as Result<T> for coordination, guidance on asynchronous message dispatch, our coroutine framework, etc. We use the ElasticThreadPool, as the underlying threading model for all our own operations and believe that it is an efficient and simple tool for handling producer/consumer scenarios. Let us know if you find it useful or have suggestions for improvement.