Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Introduction Option 1:Use Continuations Option 2:Use Reentrant Message Pumping What About Yield?

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

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.

Previous Page | 1 Introduction | 2 Option 1:Use Continuations | 3 Option 2:Use Reentrant Message Pumping | 4 What About Yield? Next Page

RELATED ARTICLES Securing the Java Core Petascale Tools and Genomic Evolution Legal Compliance: Open Source and Quality Assurance SEI, Army Team Up on Software Testing Highly Scalable Parallel Sorting		TOP 5 ARTICLES No Top Articles.