Coordination Data Structures Overview

Coordination Data Structures Overview

  • Comments 11

The June 2008 CTP of Parallel Extensions provides the first look at its 3rd major piece, a set of coordination data structures we lovably refer to as CDS. It contains lightweight and scalable thread-safe data structures and synchronization primitives.  There are of course already many synchronization primitives present in the System.Threading namespace of the .Net Framework, such as ManualResetEvent, Monitor, Mutex, and Semaphore: these types are still very useful for developing multithreading applications, and in fact Parallel Extensions relies on many of them, but sometimes higher-level or lighter-weight primitives are required to facilitate communications between threads.  CDS augments the existing types in System.Threading to provide just such primitives. Here is a brief introduction for each CDS type included in the June 2008 CTP.

ConcurrentStack<T> / CocncurrentQueue<T>
Generic, thread-safe LIFO stack and FIFO queue data structures. They impalement IConcurrentCollection<T>, a new interface providing thread-safe Add and Remove methods for adding a data element to a collection and removing a data element from a collection, according to the semantics of the implementing type.
Cistina already posted the ConcurrentStack<T> post http://blogs.msdn.com/pfxteam/archive/2008/06/18/8614596.aspx

SpinWait
Since context switches and kernel transitions are relatively expensive operations, sometimes it’s beneficial and actually costs less to busy wait rather than to wait on a kernel synchronization primitive. SpinWait provides simple, correct, and efficient busy waiting.

SpinLock
Provides a locking mechanism based on spinning rather than based on waiting on kernel events. This can be useful in advanced scenarios where the critical region being protected is tiny and where it would be more costly to use heavier synchronization primitives like Monitor.

CountdownEvent
System.Threading already contains a ManualResetEvent that allows threads to wait on the event until it’s set by another thread. In common “fork/join” operations, where multiple pieces of asynchronous work are generated and where additional work can’t proceed until all of those forks have joined, a typical pattern is to initial a ManualResetEvent that a thread blocks waiting on, and also initial a count that is decremented every time one of the forked operations completes: when the count reaches 0, the event is set. CountdownEvent encapsulates this pattern.  It is initialized with a count (this count can also be increased with its Increment method), and when work items complete they can call to its Decrement method.  When the internal count reaches 0, the CountdownEvent is set, and any threads waiting on the event unblock.

ManualResetEventSlim
Like a ManualResetEvent, ManualResetEventSlim is an event that allows threads to wait on it until other threads have set it.  However, ManualResetEventSlim is optimized for short waiting times, as it utilizes spinning and lazy-initialization of any necessary synchronization primitives . It supports basic event functionalities, such as Set, Reset, and Wait.

SemaphoreSlim
SemaphoreSlim is a lightweight semaphore implementation, also optimized for short waiting times. It also provides a few features not present in the System.Threading.Semaphore class, such as its current count, which can be useful for debugging purposes.

BlockingCollection<T>
A blocking queue is a popular data structure in concurrent programming, as it provides a useful primitive for producer/consumer scenarios (with producers writing data into the queue and with consumers reading data from the queue, blocking until data is available to consume). The BlockingCollection<T> type provides this same functionality. However, rather than being tied to a particular storage implementation (e.g. the queue in a blocking queue), it provides a blocking and bounding mechanism for any IConcurrentCollection<T> implementation, including but not limited to implementations included with CDS (e.g. ConcurrentQueue<T> and ConcurrentStack<T>). BlockingCollection<T> supports not only blocking on removals, but also optional bounding on additions if it has maximum capacity set.

LazyInit<T>
Lazy initialization is a common need in many applications, deferring the cost of creating an object until the object is actually needed.  There are several common patterns for lazy-initialization, and all of them can be difficult to get right and efficient, especially in concurrent situations.  Our LazyInit<T> type provides support for several of these common patterns.

WriteOnce<T>
The readonly keyword in C# (ReadOnly in Visual Basic) supports single initialization for a type and only from the constructor; any other attempt to initialize a readonly variable outside the constructor produces compilation error. However, sometimes developers need to create a variable that can be initialized only once, but the initialization doesn’t have to be inside the constructor. WriteOnce<T> provides that behavior, such that the variable can be initialized only once, and any other attempted set operations will fail.

Leave a Comment
  • Please add 3 and 6 and type the answer here:
  • Post
  • The call CountdownEvent.Wait() can block the scheduler, is this correct?

    For example on a task manager with 2 processors and 2 threads per processor if there are 4 CountdownEvent waiting and then no more tasks can start.

    var event1 = new CountdownEvent(1);

    Parallel.For(0, 8, i => { Debug.WriteLine(i); event1.Wait(); });

    //2 3 0 1

    The behaviour is the same using BlockingCollection.Remove().

    There is no such behaviour using Future.Wait().

    var event1 = Future<bool>.Create();

    Parallel.For(0, 8, i => { Debug.WriteLine(i); event1.Wait(); });

    //1 0 3 2 4 5 7 6

  • This looks more and more interesting.

    I have been following this blog for a little while, and I have had a question in mind since then, which I have not seen addressed, and which I do not really know where to post:

    Is there any plan for PFX to use the GPU (graphics processor) incredible parallel processing abilities to accelerate Parallel.NET routines?

  • Steffen, with the current CTP, yes, you can end up blocking all of the scheduler's threads, but the situation will improve with future releases; the current implementation is missing some features that causes the behavior you're seeing.

  • Alexandre, we're certainly investigating general purpose GPU support, but we don't have anything to discuss regarding it at this time.

  • Hi Stephen. Thanks for the blog.

    I like Edward Lee's paper, is that MS's direction?

    The Problem with Threads, by Edward A. Lee

    EECS Department, University of California, Berkeley

    http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf

    Threads are a seemingly straightforward adaptation of the dominant sequential model of computation to concurrent systems... in software in order to take advantage of the predicted increases in parallelism ... I argue that this is not a good idea. They discard the most essential and appealing properties of sequential computation: understandability, predictability, and determinism. Threads, as a model of computation, are wildly nondeterministic, and the job of the programmer becomes one of pruning that nondeterminism. Rather than pruning nondeterminism, we should build from essentially deterministic, composable components. The consequences of this principle are profound. I argue for the development of concurrent coordination languages based on sound, composable formalisms.

  • I concur with the concerns expressed about graphics concurrent parallel performance benefiting from multi-core-CPU-GPGPU HW systems improvements.

    I'd like to know more about the uniqueness, specialness of the UI thread in a multi-core world.

    Thanks

  • It would be nice if heap-based collection or any other type of priority-queue will be introduced in standard library.

  • "They impalement IConcurrentCollection<T>, a new interface providing thread-safe Add and Remove ..."

    Impalement seems a bit strong for such a useful interface.

    - Rick

  • PingBack from http://blog.netmedia.info/index.php/2008/07/29/c-30-and-parallel-fxlinq-in-mono/

  • I really like the idea behind the LazyInit<T> class you added to the June CTP. I would like to give my feedback on the scenario's where I would like to use it that I think are not fully supported

    T is not allowed to be a value type, this prevents me from using it for calculations returning integers or decimals that are quite common in financial scenario's.

    Moreover the ValueSelector is not allowed to return null. In some of cases however null can be a valid value for a field an doesn't have to mean 'has not been initialized yet.

    I would opt to throw in the extra _isInitialized boolean to allow for both value types and refrence types that may be null, that would make this a real usefull feature..

    Besides that I was thinking about the way I would use this LazyInit object in a class like the following:

       class person

       {

           string FirstName { get; set; }

           string LastName { get; set; }

           string WholeName { get { return FirstName + LastName);} }

       }

    I would like to cache the value of WholeName (being an expensive calculation), and do something like:

       class person

       {

           string FirstName { get; set; }

           string LastName { get; set; }

           LazyInit<string> _wholeName = new LazyInit<string>(() => FirstName + LastName);

    string Wholename { get { return _wholeName.Value; } }

       }

    Unfortunately it is not allowed by the compiler to reference other fields inside the lambda that is used in de field initializer and I would have to create the LazyInit object in the constructor (introducing more code). An alternative approach could be:

       class person

       {

           string FirstName { get; set; }

           string LastName { get; set; }

           LazyInit<string> _wholeName = new LazyInit<string>();

           string Wholename { get { return _wholeName.Retreive(() => FirstName + LastName);}

       }

    The retrieve would look something like

       T Retrieve(Func<T> valueSelector)

       {

    // add some smart double checking and locking here

           if (!_initialized)

           {

               _value = valueSelector();

           }

           return _value;

       }

    The retrieve retrieves the initialized value if present, or create it if not. This allows me to write the delegate in the same context as where I want to use the result, which is generally where I want it.

    Maybe I'm stretching the intended semantics for LazyInit and maybe these models should be implemented in separate types instead of mixed, but this model it would reduce the amount of code in a lot of common situations.

  • PingBack from http://greenteafatburner.info/story.php?id=4662

Page 1 of 1 (11 items)