Scaling Up with Task Parallel Library (TPL) and CLR 4.0 Thread Pool

Seeing that the CPU hit the power wall and probably wont go any faster and in the light of the shift to many core machines, software developers are starting to realize that in order to achieve a continuous increase in performances (re-enable the free lunch) there’s no escape from writing programs that scale up to multiple processors, for the most part by introducing more and more parallelism.

In order to make parallel programming easier, Microsoft is introducing a new library called TPL (Task Parallel Library) which aims to lower the cost of fine-grained parallelism by executing the asynchronous work (tasks) in a way that fit the number of available cores, and providing developers with more control over the way in which the tasks get scheduled and executed.

TPL exposes rich set of APIs that enable operations such as waiting for tasks, canceling tasks, optimizing the fairness when scheduling tasks, marking tasks known to be long-running to help the scheduler execute efficiently, creating tasks as attached or detached to the parent task, scheduling continuations that run if a task threw an exception or got cancelled, running tasks synchronously, and more.

Recently, The TPL team published a code base that includes very useful functionality that’s too application-specific to be included in the core of TPL’s Framework. It provides a wealth of code that can be used as a starting point or as a learning tool to understand how various kinds of functionality might be implemented. It’s exposed through the ParallelExtensionsExtras project.

In order to support TPL and to provide a better solution for the increasing number of concurrent tasks, Microsoft made some significant improvements to the CLR ThreadPool for .NET Framework 4.o.

Side by side, Microsoft is making an effort to make effective parallel programming easier by supporting ‘transactional memory’ though the STM.NET platform, which provides experimental language and runtime features that allow programmers to declaratively define regions of code that run in isolation

In this post we’ll discuss the motivation for TPL, examine the improvements made to the CLR ThreadPool and review the operation manner and fundamental features of TPL.

The Free Lunch is Over

Already in the year 2003, CPU performance growth had hit a wall. Up until then, most of us wrote sequential code and relayed on the CPU frequency to consistently raise (in 12 years it climbed from 400Hz to 3.8GHz) while futilely counting on Moore law (that the number of transistors on a chip will double about every two years) to keep on translating into faster processors.

Unfortunately, due to the power wall hit, adding transistors stopped translating into faster processors, primarily because of power consumption and the heat generated.

As you can see in the figure bellow, the number of transistors on Intel’s chips never stopped climbing, even after the year 2010. However, clock speed stopped on 2003 somewhere near 3GHz.

(Source: The Free Lunch Is Over by Herb Sutter)

Other CPU vendors are showing similar results..

As a result, instead of putting more and more transistors on a single processor, the major processor manufacturers start putting more and more processors on a single chip.

Intel's Tera-scale Computing Research Program, aimed at breaking barriers to scaling future chips to 10s-100s of cores, has managed to successfully produce a prototype 80-core processor that consumes less than 100W of power, but lacks a lot of necessary functionality.

Recently, Intel has announced that "limited quantities" of an experimental, fully working processors, featuring 48 physical processing cores will be shipping to researchers by the middle of the year. The new processor draws between 25 watts and 125 watts of power, and posses the ability to shutdown cores at will in order to reduce clock speed and power consumption.

Quite possibly, in less than 10 years we will be seeing main stream computers with up to 256 cores!

Legacy versions of windows (XP, Vista, Server 2003) support 32/64 processors on a single machine due to the limitation of the process/thread affinity mask APIs. However, Windows Server 2008 R2 and Windows 7 support up to 256 CPUs. 

CLR Thread Pool

The .NET ThreadPool provides a convenient way to run asynchronous work. It optimizes the creation and destruction of threads through the use of heuristic ‘thread injection and retirement algorithm’ that determines the optimal number of threads by looking at the machine architecture, rate of incoming work and current CPU utilization (using daemon thread that runs in the background and periodically monitor the CPU). All in order to reduce the overhead associated with creating and destroying a thread (according to Joe Duffy, it cost approximately 200,000 cycles to create a thread, and 100,000 to destroy one), keep high CPU utilization and minimize the amount of context switches (context switch costs 2,000–8,000 cycles).

How Does the CLR Thread Pool Work?

In the post ‘.NET CLR Thread Pool Internals’ you can find in detail review of the ‘thread injection and retirement algorithm’ which optimizes the creation and destruction of threads in order to execute asynchronous callbacks in a scalable fashion.

CLR Thread Pool 2.0

The CLR 2.0 ThreadPool contains a single queue to which multiple application objects concurrently queue (push) work items and from which multiple worker threads concurrently pull work items. In order to keep things thread safe, an exclusive lock is acquired during the push and during the pull.

 

Already in .NET Framework 3.5

In order to reduce the number of transitions between AppDomains, since .NET Framework 3.5 the thread pool also maintains separate queue for each AppDomain while using round-robin scheduling algorithms to allow each queue to execute work for some time before moving on to the next.

CLR Thread Pool 4.0

The legacy thread pools was designed for applications that targeted 1-2-4 processors machines. Since applications of that nature usually allow only few worker threads to run coarse grained work concurrently, the ‘single queue’ ‘single lock’ schema worked just fine.

However, new age applications will target machines with hundreds of cores. Consequently, in order to scale up, they’ll have to be designed to run lots of fine grained work concurrently, thus, the number of work items and worker threads will increase dramatically which will result in a problematic contention on the pool.

Performance

The new ThreadPool significantly reduces the synchronization overhead associated with pushing/pulling work items to/from the pool. While in previous versions the ThreadPool queue was implemented as a linked list protected by a big lock - the new version of the queue is based on the new array-style, lock-free, GC-friendly ConcurrentQueue<T> class.

Since the new queue is implemented more like an Array instead of a Linked-List, there’s no need to restructure every time an item is pulled/pushed (which is naturally done within a lock), instead, all that have to be done is to increment/decrement a pointer in an atomic operation via InternalLock. In addition, it’s a lot easier for the GC to travels through an Array than through a Linked-List.

Not official benchmarks published recently show dramatic increase in performance when running on .NET framework 4.0 thread pool. The benchmark runs 10 million empty work items concurrently in order to calculate the thread pool overhead. It provides the following results.

Machine	.NET 3.5	.NET 4	Improvement
A dual-core box	5.03 seconds	2.45 seconds	2.05x
A quad-core box	19.39 seconds	3.42 seconds	5.67x

Worker Thread Queues and Work Stealing Support

The CLR 4.0 thread pool also supports a local queue per task and implements a work stealing algorithm that load balance the work amongst the queues. This feature only applies when working with the Task Parallel Library that will be reviewed shortly.

Operation Manner

The ‘thread injection and retirement algorithm’ for CLR 4.0 has changed since previous versions of the CLR, please refer to ‘.NET CLR Thread Pool Internals’ for in detail review.

Backward Compatibility

For most applications the upgrade to the new 4.0 thread pool should be transparent and a performance gain should be spotted without changing line of code. However, the modifications made to the ‘thread injection and retirement algorithm’ require some spatial attention since it might lead to some unaccustomed starvation.

Task Parallel Library

In contrast to working directly with the ThreadPool - Task Parallel Library (TPL) provides rich API for paralleling work. The new API finally enables control over work items (tasks) that were scheduled including non-evil cancelation, it allows the developers to 1) provide more information about the work that is to be scheduled for parallel execution, and 2) configure the scheduling fashion by setting the concurrency level and setting priorities. 

The Task Parallel Library includes many features that enable the application to scale better. This post reviews the support for worker thread local pool (to reduce contentions on the global queue) with work stealing capabilities, and the support for concurrency levels tuning (setting the number of tasks that are allowed to run in parallel)

Worker Thread Local Pool

How?

Task task1 = Task.Factory.StartNew(delegate { taskWork(); });

Using the ThreadPool all work requests travel through the same queue and all the worker threads get work items from the same queue. With TPL, in order to reduce the contention on the global queue and to provide better cache behavior - when a parent task schedule tasks, the child tasks don’t get queue in the global queue, rather they’re being queued in a local queue dedicated to the parent task.

When the parent task finishes its own work, the child tasks are picked up and executed by the same thread that executed the parent task. In order to provide a better caching behavior, the child tasks are being fetched from the local pool in a LIFO fashion (the last child that was queued is being fetched first).

When a worker thread is done with all of its work (including executing the child tasks), if there’s no work available in the global queue, it checks other threads local queues to see if there’s any work to steal. If there is, it fetches the work from the other thread local queue in a FIFO fashion.

The local queue is based on an array that changes size dynamically, and has two ends. One end (“private”) allows lock-free pushes and pops, the other end (“public”) requires synchronization. When the queue gets small so private and public operations could conflict, synchronization is necessary.

Child tasks are being fetched from the private end, there for fetching child tasks doesn’t require a lock. Stills are being done from the public end, thus requires the protection of a lock.

The local queuing feature can be disabled by including the PreferFairness flag in the TaskCreationOptions of the parent task (this flag is not included by default); with the PreferFairness flag set – the scheduler will still enqueue the child task to the global queue rather than to the local queue.

Concurrency Control and Priorities

The concurrency control feature enables developers to manually tune the amount of threads (concurrency level) that the TPL task scheduler will ideally generate for a given set of tasks

Please refer to ‘Concurrency Levels Tuning with Task Parallel Library (TPL)’ for code code samples and in detail review.

Benchmark

ThreadPool vs TPL benchmark (for Visual Studio 2008) can be downloaded from here.

Please be very cautious about using this benchmarks to make decisions or to evaluate whether the ThreadPool or TPL is right for you.  The implementation and architecture of both have changed significantly since previous releases, and it's quite likely that any performance measurements done thus far are no longer valid.  Moreover, in .NET 4.0, the Task Parallel Library uses the new .NET 4.0 ThreadPool as its default scheduler

ThreadPool vs TPL benchmark (for Visual Studio 2010 beta) can be downloaded from here.

Links

Parallel Programming with .NET : Slides from Parallelism Tour

CLR Inside Out - Using concurrency for scalability (Joe Dufy)

CLR Inside Out - Thread Management In The CLR

Sasha's articles about parallelism

Video - Daniel Moth presents working with ThreadPool v.s. TPL, TaskMananger and Task cancelation

http://blogs.msdn.com/ericeil/archive/2009/04/23/clr-4-0-threadpool-improvements-part-1.aspx

http://www.builderau.com.au/program/windows/soa/The-basics-of-threading-in-the-NET-Framework/0,339024644,320282954,00.htm

http://blogs.msdn.com/salvapatuel/archive/2007/11/11/task-parallel-library-explored.aspx

http://www.danielmoth.com/Blog/2008/11/new-and-improved-clr-4-thread-pool.html

Thread Synchronization in .NET (Monitor, ReaderWriterLock, ContextBoundObject, and Immutable Objects)

The are many locking techniques out there that can be applied to synchronize access to a shared resource, making the right decision regarding to which technique to use can make the different between application that scales and application that performs poorly, doesn’t scale or even suffers from lock convoys phenomena's.

Since lock based programming is so error prone, Microsoft introduced the STM.NET platform that provides experimental language and runtime features that allow the programmer to declaratively define regions of code that run in isolation, which eliminate the need to use locks altogether. However, until STM.NET will become operational and proven efficient we are stuck with primitive locks - so we might as well learn how to use them.

This post reviews the Monitor class that enables exclusive locking, the 3 versions of the ReaderWriterLock that enable both exclusive and shared locking, the use of context bound synchronized objects that allow only one thread to access an object at a given time, and the immutability approach where object is designed as read-only thus no lock is required on read. We’ll examine the pros and cons of every technique and attempt to spot the cases in which each should be applied.

Technique	Concurrent Read	Concurrent Read-Write	Concurrent Write
Monitor
Synchronization Domain
ReaderWriterLock
Immutability

In Sasha Goldshtein blog you can read about lock free techniques such as spin lock, Cyclic Lock-Free Buffer (spinners) and thread local cache that can be applied to protect a shared resource while dismantling the performance hit associated with a kernel lock.

The Object Model

The locking techniques will be demonstrated on a simple object model that consist of shared resource object, single writer object and many reader objects. The SharedResource object encapsulates list of items and allow adding/getting items to/from the list. The Writer object adds items to the shared resource and the Reader objects reads from the list. The Writer and the Readers run from the context of different threads so they may access the shared resource concurrently.

Using a Monitor (lock)

the obvious way to protect the shared resource is to disallow concurrent access to it by using the well known Monitor class (in C# using the lock keyword) which is the managed equivalent of Win32’s critical section. By using the simple one-at-a-time lock only one thread can access the SharedResouce at a time, so there are no simultaneous reading/writing from the list.

public class SharedResource { object m_locker = new object(); List<SharedResourceItem> m_items = new List<SharedResourceItem>(); public SharedResourceItem GetItem(int index) { lock (m_locker) { return m_items[index]; } } public void SetItem(SharedResourceItem sharedResourceItem) { lock (m_locker) { m_items.Add(sharedResourceItem); } } }//end SharedResource

Lock Encapsulation

Pay attention that the code snippet above uses a private, not exposed object to lock the critical region. Be careful not to break lock encapsulation by locking with public member, exposed fields, the object itself via ‘lock(this)’ or type object via ‘lock(typeof(T))’. Violating this rule will make your code vulnerable to undetectable dead-locks caused by others that violated the same rule and used your public locks.

Moreover, locking with type objects can even cause deadlock between AppDomains that can be very hard to spot. AppDomains are assumed to be completely isolated, but that is not the case when it comes to ‘marshal-by-bleed’ objects such as type objects of assemblies that were optimized to be loaded across domains (for instance by using the LoaderOptimizationAttribute).

Recursive Acquires

The Monitor lock can be recursively acquired from the same thread, so the following code will not lead to a dead lock. 

public class RecursiveLocked { object m_locker = new object(); public void Foo() { lock (m_locker) { // recursion counter = 0 lock (m_locker) { //No dead lock here, recursion counter = 1 } } } }

Performance

With Monitor, you only start paying the price when lock contention is encountered, since only then kernel object is actually allocated (or reused) to kick the thread off to a waiting state which result in a context switch (that according to Joe Duffy, costs 2,000–8,000 cycles).

In order to avoid the performance hit associated with entering to a waiting state - both Win32 critical sections and CLR Monitor class spins a little while checking that the lock is still required before entering to a waiting state. While the amount of time that win32’s critical section spins is optimized according to the ‘success’ history of previous spins, the CLR Monitor spinning time on the other hand is steady. 

Pros

The good thing about the Monitor is that it is very simple to use, understand and maintain. In addition, it is more reliable in the sense that it doesn’t leak due to a thread abort occurring in the middle of a lock (thanks to “hack” in the JIT), unlike the 3 versions of the ReaderWriterLock that will be reviewed shortly.

Cons

Since the Monitor lock is so easy to use – people tend to use it in cases where shared locks (reader/writer) are by far more appropriate, which leads to unavoidable lock convoys. Think about a case where the same action run concurrently and access a shared resource during 10% of the time, while during 1% it writes to it and 9% it reads from it. Since the resource can be safely read concurrently by multiple threads - acquiring an exclusive lock such as the Monitor during the read can unnecessarily block other threads during up to 9% of the time.

ContextBoundObject  (Synchronization Context)

Instead of putting lock on every method, we can let the .NET runtime keep the object thread-safe for us. By decorating the class with SynchronizationAttribute and deriving from ContextBoundObject we can instruct the runtime to restrict access to a single thread at one particular time (read more).

The runtime creates synchronization domain for the context bound object and use invocation interception mechanism (utilizing Reflection) in order to lock the object before any method execute and release the lock when method exits. Sadly, this will slow any invocation on the object by one order of magnitude.

[Synchronization] public class SharedResourceSynchronized : ContextBoundObject { List<SharedResourceItem> m_items = new List<SharedResourceItem>(); public SharedResourceItem GetItem(int index) { return m_items[index]; } public void SetItem(SharedResourceItem sharedResourceItem) { m_items.Add(sharedResourceItem); } }//end SharedResource

Synchronization Context v.s. COM Apartments

COM apartments contain threads and objects. When an object is created within an
apartment, it stays there all its life, forever house-bound along with the resident thread(s). This is similar to an object being contained within a .NET synchronization context, except that a
synchronization context does not own or contain threads. Any thread can call upon an object in any synchronization context – subject to waiting for the exclusive lock. But objects contained within an apartment can only be called upon by a thread within the apartment.

Using a Reader-Writer Lock

ReaderWriterLock (RWL) works best where most accesses are reads, while writes are infrequent and of short duration. With RWL multiple threads can acquire the reader lock (a.k.a shared lock) simultaneously but only one thread can acquire the writer lock (a.k.a exclusive lock), while both reader and writer locks cannot be acquired at the same time. Such being the case, holding reader locks or writer locks for long periods will starve other threads. For best performance, consider restructuring your application to minimize the duration of writes.

public class SharedResourceRWLock { private ReaderWriterLock rwl = new ReaderWriterLock(); List<SharedResourceItem> m_items = new List<SharedResourceItem>(); public SharedResourceItem GetItem(int index) { rwl.AcquireReaderLock(TimeSpan.FromSeconds(5)); try { return m_items[index]; } finally { // Ensure that the lock is released. rwl.ReleaseReaderLock(); } } public void SetItem(SharedResourceItem sharedResourceItem) { rwl.AcquireWriterLock(TimeSpan.FromSeconds(5)); try { m_items.Add(sharedResourceItem); } finally { // Ensure that the lock is released. rwl.ReleaseWriterLock(); } } }//end SharedResource

Pros

The fact that RWL allows concurrent reads (shared lock) makes it appealing to most parallel applications since most of them read more then they write, so replacing the Monitor lock that allows only exclusive locking with RWL that enables combination of shared locking (for readers) and exclusive locking (for writers) can make the different between application that scales and application that suffers from lock convoys phenomena's.

cons

The problem with the former versions of the RWL (.NET Framework 1-3) is that in case of a ‘hot lock’ (where there’s actual lock contention between the threads thus the locking kernel object is actually allocated or pulled out) it performs much worst than the Monitor lock (about 6 times slower).

Alternatives

The new versions of the .NET Framework (starting from 3.5)  introduce the ReaderWriterLockSlim class (purely managed) that does the same but performs better (however, still about 2 times slower than the Monitor lock).

However improved, the implementation of ReaderWriterLockSlim, even when acquiring a read lock, requires an update to a shared location in the lock data structure (using interlocked). When many threads are attempting to acquire the read lock frequently, there can be contention on the cache line holding this shared location. When the critical section is not big enough to “space out” the cost of the lock acquisitions, the resulting cache contention prevents scaling.

The Win32 slim reader/writer lock (SRWL) that is new to Vista and Server 2008 - performs even better than the Monitor lock since it’s not based on the standard kernel object, it is very thin and it executes almost entirely in user mode (so there’s no kernel transitions required to access and manipulate it which spare thousands of cycles, in contrast to almost every other available locks that lazily allocate or reuse kernel object). The price that we pay for SRWL thinness is that unlike ReaderWriterLock and ReaderWriterLockSlim the SRWL cannot be recursively acquired (which may not be so bed after all because it encourages better locking design), cannot be upgraded/downgraded and doesn’t hold information about its owning thread so it can be acquired by one thread and released by the other without yielding a SynchronizationLockException.

Using Immutable objects

An immutable object is an object whose state cannot be modified after it is created. Thus, multiple threads can act on data represented by immutable objects without concern of the data being changed by other threads. To make this work, instead of changing the objects itself - we create new object that reflects the new state.

In this case, we will make the m_items list immutable, so on read (GetItem) we can use it freely without a lock (just read the reference into a local variable which is an atomic operation), and on write we create a new list with the new item - and replace the m_items with the new updated list.  Naturally, the cloning and the setting of m_items is done within a lock to prevent data lost (so there's no concurrent writing).

public class SharedResourceImmutable { private object m_writeLock = new object(); List<SharedResourceItem> m_items = new List<SharedResourceItem>(); public SharedResourceItem GetItem(int index) { List<SharedResourceItem> items = m_items; return items[index]; } public void SetItem(SharedResourceItem sharedResourceItem) { lock (m_writeLock) { List<SharedResourceItem> buffer = new List<SharedResourceItem>(); buffer.AddRange(m_items); buffer.Add(sharedResourceItem); m_items = buffer; } } }

Pros

The great thing about immutability is that the readers are never locked. Think about a case where single resource is being frequently read while the manipulation of the resource takes significant amount of time; using locking mechanism that doesn't allow concurrent write/read will produce many contentions that can drastically harm performance. So in this case - the price that we pay for immutably (cloning on every write) is worthwhile to say the least.

cons

The problem with immutable object is that they have to be cloned every time they change and that they are not so comfortable to write, understand and maintain.

Links

http://igoro.com/archive/overview-of-concurrency-in-net-framework-35/