Aug 27 2009

.NET 4.0 Work Stealing Queue, Parallel and PLINQ

In my previous post, we have seen basis of Task Parallel Library, where I have mentioned new task scheduler in .NET 4.0 thread pool. In this post I brief about it along with “Task” class. Before this, let us see how to make LINQ as parallel using PLINQ.

PLINQ

PLINQ has implementation of all LINQ to Objects extension methods in System.Linq.ParallelEnumerable for IEnumerable. To make an IEnumerable parallel, you simply call AsParallel() extension method. AsParallel() internally calls System.Linq.Parallel.ParallelEnumerableWrapper which is of type System.Linq.ParallelQuery. Let us take the same customer-order example as shown in my previous post with PLINQ enabled.

var customersForOrderId7 =
    from c in customers.AsParallel()
    from o in c.Orders
    where o.OrderId == 7
    select c;
 

customersForOrderId7.ForAll(c =>
    Console.WriteLine(c.ToString()));

The above code selects customers who have ordered OrderId 7. AsParallel() at line 3 makes Customer[] as parallel enabled. In this example, you can see that instead of typical for…each, I’ve used ForAll(). This differs from for..each, means that for..each preservs the final order of the results.

Thread Pool and Work Stealing Queue

Until .NET3.5, we can queue our work items as thread in to ThreadPool using QueueUserWorkItem(). In .NET 4.0, improvements had been made in the thread pool. It is now based on System.Threading.Tasks.Task.

Task

Task is a work item which can be executed independently along with other tasks, technically it represents an asynchronous operation i.e. System.Action. It is defined in System.Threading.Tasks.Task which enables you to do the following actions on a task instance:

start – to start the instance
wait – to wait to for a task to complete
cancel – cancel the task asynchronously

It seems that task is a lite version of thread.

Thread Pool

Following diagram shows the conceptual view of .NET 4.0 thread pool.

.NET 4.0 Thread Pool

Previously, thread pool had only one queue on which all the work items were queued and enqueued in FIFO order (ofcourse, thats why queue). The worker threads are allocated for every work item access the work item from this queue. In .NET 4.0, it has been improved by introducing local queue for every worker thread, in addition to qlobal queue. Tasks those are created by program thread queued on global queue. The task scheduler enqueues the tasks from global queue in FIFO order and distributes to respective worker thread’s local queue. The worker thread enqueues the tasks from its local queue in LIFO order. Interesting!

The introduction of local queue makes these threads can be executed on different processors without contention issue which normally occur in single queue thread pool. The reason for worker thread picking up the tasks in LIFO order is the assumption that “last-in” is hot to act which results no qurantee in task ordering, but better performance.

Work Stealing Queue

Let us assume that worker thread 1 completed all of its tasks in the queue. It scans the global queue for any task and if nothing there, it scans other worker thread’s local queue. In this case, let us assume there are two tasks in WT2 queue. WT1 enqueues first-in task from WT2 queue which avoids contention issue. Getting tasks from other local queue is called as work stealing. This again results better performance.