Channels ▼
RSS

Parallel

Break Up and Interleave Work to Keep Threads Responsive


Option 1:Use Continuations

The first way to tackle the problem is to use continuations. A continuation is just a way to talk about "the rest of the work that's left to do." It includes capturing the state of any local or intermediate variables that we're in the middle of using, so that when we resume the computation we can correctly pick up again where we left off.

Example 1(a) shows one way to implement a continuation style:


// Example 1(a): Using a continuation style
//
class LongOperation : public Message {
 <font color="#FF0000">int start;
   LongHelper helper;</font>
public:
 <font color="#FF0000">LongOperation( int start_ = 0,
      LongHelper helper_ = nullptr )
        : start(start_), helper(helper_) { }</font>
   void run() {
 <font color="#FF0000">if( helper == nullptr
             // if first time through, get helper</font>
        helper = GetHelper();
      int i = 0;
 <font color="#FF0000">// do just another chunk's worth</font>
      for( ; <font color="#FF0000">i < ChunkSize && start+i</font> < items.size();
           ++i ) {
        helper->render( items[ start+i ] );
   }
 <font color="#FF0000">if( start+i < items.size() )
        // if not done, launch a continuation
     queue.push(LongOperation(start+i, helper));
   else
            // if last time through, finish up</font>
      helper->print();
   }
}

The first LongOperationobject executes only a suitably-sized chunk of its loop. To ensure that the remainder of the work gets done, it creates a new LongOperation object (the continuation) that stores the current intermediate state, including the helper local variable and the loop index, and pushes the continuation on the message queue. (For simplicity this code assumes LongOperation has direct access to queue; in practice you would provide an indirection such as a callback to decouple the message type from a specific queue.)

A good way to think about this is that we're "saving our stack frame" off in a separate object on the heap. The overhead we're incurring for each continuation is the cost of copying the local variables, one allocation (and subsequent destruction) for the continuation message, and one extra pair of enqueue/dequeue operations. This approach has the major advantage of fairness. It's fair to the waiting messages, because each continuation gets pushed onto the end of the queue and so all messages currently waiting will be processed before we do another chunk of the longer work. More importantly, it's fair to LongOperation itself, because any other new messages that arrive after the continuation is enqueued, during the time while we're draining the queue, will stay in line behind the continuation.

This fairness can also be a disadvantage, however, if we'd actually like to execute most of the messages in order no matter how long they take, and only enable interleaved "early" execution for certain high-priority messages. Some of that can be accomplished using a priority queue as the message queue, but in general this kind of flexibility will be easier to accomplish under Option 2, where we opt for a different set of tradeoffs.

Beware State Changes When Interleaving

Note that there is a subtle but important semantic issue that we have to be aware of that wasn't possible in the noninterleaved version of the code.

The issue is that whenever the code cedes control to allow other messages to be executed, it must be aware that the thread's state can be changed by that other code that executed on this thread in the meantime. When the code resumes, it cannot in general assume that any data that is private to the thread, including thread-local variables, has remained unchanged across the interruption.

In Example 1(a), consider: What happens if another message changes the size or contents of the items collection? If our operation is trying to process a consistent snapshot of the collection's state, we may need to save even more off to the side by taking a snapshot of the collection and doing all of our work against the snapshot, so that we maintain the semantics of doing our operation against the collection in the state it had when we started:


// Example 1(b): Using a continuation style,
<font color="#FF0000">// and adding resilience to collection changes</font>
//
class LongOperation : public Message {
 <font color="#FF0000">Collection myItems;</font>
   int start;
   LongHelper helper;
public:
   LongOperation(
     int start_ = 0,
     LongHelper helper_ = nullptr,
 <font color="#FF0000">Collection myItems = nullptr</font>
   )
   : start(start_),
     helper(helper_),
     myItems(myItems_)
{ }
void run() {
   if( helper == nullptr ) {// if first time through
      helper = GetHelper(); // get helper
 <font color="#FF0000">myItems = items.copy();// and take a snapshot of items</font>
   }
   int i = 0; <font color="#FF0000">// do just another chunk's worth</font>
   for( ; i < ChunkSize && start+i < myItems.size(); ++i ) {
      helper->render( myItems[ start+i ] );
   }
   if( start+i < <font color="#FF0000">myItems</font>.size() ) // if not done,
                                     // launch a continuation
      queue.push( LongOperation( start+i, helper, <font color="#FF0000">myItems</font> ) );
   else { // if last time through, finish up
      helper->print();
 <font color="#FF0000">Free( myItems ); // and clean up myItems</font>
   }
 }
}

Now the continuation is resilient to the case where other messages may change items, by doing all of its processing using the state the collection had when our operation began.

Note that we have still introduced one other semantic change, in that we're deliberately allowing later messages to run against newer state before this earlier operation on the older state is complete. That's often just fine and dandy, but it's important to be aware that we're buying into those semantics.

All of these considerations apply even more to Option 2. Let's now turn to our second strategy for interleaving work, and see how it offers an alternative set of tradeoffs.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video