Channels ▼
RSS

Design

Avoid Exposing Concurrency: Hide It Inside Synchronous Methods


Example: Optimistic Iteration

Now consider the following loop that uses an enumerator/iterator style to visit each item in a collection:


// Example 2, common calling code
void f( WidgetCollection wc ) {
  using( i = wc.GetEnumerator() ) {
   while( <b>i.MoveNext()</b> ) {       // fetch next element
      // … some work …                        // and process it
      DoSomethingWith( i.Current );
      // … more work …
    }
  }
}

Imagine the enumerator is implemented something like this:


// Example 2(a), synchronous enumerator (sketch)
class WidgetEnumerator {
  // …
  // Construct
 <b>WidgetEnumerator</b>() {
    // set up any necessary resources
  }
  // Destroy (C++ destructor, Java/C# disposer)
  void <b>Dispose</b>() {
    // release any resources we got
  }
  bool <b>MoveNext</b>() {
   if( AtEnd() ) {
      return false;
    }
    <b>// note: this may be an expensive operation
   NavigateToNextItem();</b>
   return true;
  }
  <b>Widget Current</b>() {
    <font color="red">lock( myWidgetQueue ) {
        return myWidgetQueue.First;
     }</font>
  }

Each time the caller asks for the next element, we go look for it, then return and let the caller process it. So in this sequential version of the code, the fetching and processing work is interleaved, as in Figure 1.

What if NavigateToNextItem (and therefore MoveNext) is an expensive operation? What if it has to perform an expensive computation, or take another round trip to a disk or database or web service? Then it's quite likely that we can do significantly better even for this simple common iteration pattern by applying concurrency.

Everyone who has implemented or used an enumeration API like this knows that, if the caller is asking for one item, he's likely to soon come back, hat in hand, and ask for the next one too, and then the next one after that. If getting the next element takes nontrivial time for any of a variety of reasons, and we have resources to spare, we may want to be more proactive about generating the results so that we can deliver them faster once the caller actually requests them. And, if we guess wrong, we want a way to throw away the results we didn't need after all. Even if the cost to find and prepare the next item is less than the time for the caller to complete a loop iteration and ask for the next item, as in Figure 1, we can gain a useful speedup by running the enumerator's fetching concurrently with the caller's processing.

So consider performing the iteration concurrently (and speculatively, because if the caller doesn't end up traversing the whole range we may end up throwing some work away):


// Example 2(b), concurrent enumerator (sketch)
class WidgetEnumerator {
  // …
  // Construct
 <b>WidgetEnumerator</b>() {
    // set up any necessary resources
   <font color="red"> // and launch a traversal worker thread
   done = false;
   pleaseStop = false;
   myWidgetQueue.Append( /* dummy */ );
   <b>myWorker = new thread</b>( () => {
      while( !pleaseStop && !AtEnd() ) {
        // note: this may be an expensive operation
        NavigateToNextItem();
        <b>lock( myWidgetQueue )</b> {
          myWidgetQueue.Append( /* current item */ );
        }
        newItem.Notify();            // notify consumer
      }
      <b>lock( myWidgetQueue</b> ) {
        myWidgetQueue.Append( /* sentinel */ );
      }
      newItem.Notify();            // notify one last time
    } );</font>
  }
  // Destroy (C++ destructor, Java/C# disposer)
  void <b>Dispose</b>() {
   <font color="red"> // stop and join the background worker
   <b>pleaseStop = true;
   myWorker.join();</b></font>
    // release any resources we got
  }
  bool <b>MoveNext</b>() {
  <font color="red"> if( !done ) {
      lock( myWidgetQueue ) {
       myWidgetQueue.PopFirst();
      }
      newItem.Wait();
    }
   <b>lock( myWidgetQueue ) {</font></b>
      if( <font color="red">myWidgetQueue.First == /* sentinel */</font> ) {
        <font color="red">done = true</font>;
        return false;
      }
      return true;
    }
  }
   Widget Current() {
   lock( myWidgetQueue ) {
      <font color="red">return myWidgetQueue.First;</font>
    }
  }

Now we can perform the fetching and processing concurrently, as in Figure 2. We can further improve this code by doing things like bounding the size of the queue, so that in general fewer resources are in use at once and in particular less work is wasted if the caller should happen to throw away the enumerator before reaching the end, but this is enough to sketch the basic strategy.

Figure 2: Background fetching

You may have noticed that what we've really done is create a two-stage pipeline, and we'll look at the general strategy of pipelining in more depth in a future article. For now, the key point to notice here is that the caller's code has no idea that it's participating as a pipeline stage, but remains happily oblivious to the concurrency because we've once again managed to hide it under the covers behind a synchronous-looking API.

Summary

The less code has to be upgraded to know about concurrency and nondeterminism, the better. Prefer to keep knowledge of concurrent work compartmentalized: Where possible, hide it behind a "synchronous" API to limit its effect and let callers remain insulated from the concurrency. This is an excellent strategy to reach for first when migrating an existing code base to take advantage of concurrent execution or scale on parallel hardware.

Acknowledgment

Thanks to Terry Crowley for his insightful comments on drafts of this article.


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