Channels ▼
RSS

Design

Maximize Locality, Minimize Contention


Sharing and False Sharing (Ping-Pong)

Consider the following code where two threads update two distinct global integers x and y, and assume we've disabled optimizations to prevent the optimizer from eliminating the loops entirely in this toy example:


// Thread 1
for( i = 0; i < MAX; ++i ) {
  ++x;
}

// Thread 2
for( i = 0; i < MAX; ++i ) {
  ++y;
}


Question: What relative performance would you expect if running Thread 1 in isolation versus running both threads:

  • On a machine with one core?
  • On a machine with two or more cores?

On a machine with one core, the program would probably take twice as long to run, as we'd probably get the same throughput (additions/sec), maybe with a little overhead for context switches as the operating system schedules the two threads interleaved on the single core.

On a machine with two or more cores, we'd probably expect to get a 2x throughput improvement as the two threads each run at full speed on their own cores. And that is what in fact will happen...but only if x and y are on different cache lines.

If x and y are on the same cache line, however, only one core can be updating the cache line at a time, because only one core can have exclusive access at a time—it's as if the cache line is a token being passed between the threads/cores to say who is currently allowed to run. So the situation is exactly as if we had explicitly written:


// Thread 1
for( i = 0; i < MAX; ++i ) {
  lightweightMutexForXandY.lock();
  ++x;
  lightweightMutexForXandY.unlock();
}

// Thread 2
for( i = 0; i < MAX; ++i ) {
  lightweightMutexForXandY.lock();
  ++y;
  lightweightMutexForXandY.unlock();
}


Which of course is exactly what we said we would never willingly do: Only one thread can make progress at a time. This effect is called "false sharing" because, even though the cores are trying to update different parts of the cache line, that doesn't matter; the unit of sharing is the whole line, and so the performance effect is the same as if the two threads were trying to share the same variable. It's also called ping-ponging because that's an apt description of how the cache line ownership keeps hopping back and forth madly between the two cores.

Even in this simple example, what could we do to ensure x and y are on different cache lines? First, we can rearrange the data: For example, if x and y are data values inside the same object, perhaps we can rearrange the object's members so that x and y are sufficiently further apart. Second, we can add padding: If we have no other data that's easy to put adjacent to x, we can ensure x is alone on its cache line by allocating extra space, such as by allocating a larger object with x as a member (preceded/followed by appropriate padding to fill the cache line) instead of allocating x by itself as a naked integer. This is a great example of how to deliberately waste space to improve performance.

False sharing arises in lots of hard-to-see places. For example:

  • Two independent variables or objects are too close together, as in the above examples.
  • Two node-based containers (lists or trees, for example) interleave in memory, so that the same cache line contains nodes from two containers.

Cache-Conscious Design

Locality is a first-order issue that trumps much of our existing understanding of performance optimization. Most traditional optimization techniques come after "locality" on parallel hardware (although a few are still equally or more important than locality, such as big-Oh algorithmic complexity for example).

Arrange your data carefully by following these three guidelines, starting with the most important:

First: Keep data that are not used together apart in memory. If variables A and B are not protected by the same mutex and are liable to be used by two different threads, keep them on separate cache lines. (Add padding, if necessary; it's a great way to "waste" memory to make your code run faster.) This avoids the invisible convoying of false sharing (ping-pong) where in the worst case only one contending thread can make progress at all, and so typically trumps other important cache considerations.

Second: Keep data that is frequently used together close together in memory. If a thread that uses variable A frequently also needs variable B, try to put A and B in the same cache line if possible. For example, A and B might be two fields in the same object that are frequently used together. This is a traditional technique to improve memory performance in both sequential and concurrent code, which now comes second to keeping separate data apart.

Third: Keep "hot" (frequently accessed) and "cold" (infrequently accessed) data apart. This is true even if the data is conceptually in the same logical object. This helps both to fit "hot" data into the fewest possible cache lines and memory pages and to avoid needlessly loading the "colder" parts. Together these effects reduce (a) the cache footprint and cache misses, and (b) the memory footprint and virtual memory paging.

Next Steps

Achieving parallel scalability involves two things:

  1. Express it: Find the work that can be parallelized effectively.
  2. Then don't lose it: Avoid visible and invisible scalability busters like the ones noted in this article.

We've seen some ways to avoid losing scalability unwittingly by invisibly adding contention. Next time, we'll consider one other important way we need to avoid invisibly adding contention and losing scalability: Choosing concurrency-friendly data structures, and avoiding concurrency-hostile ones. Stay tuned.

Notes

[1] H. Sutter. "Break Amdahl's Law!" (www.ddj.com/cpp/205900309)

[2] H. Sutter. "Super Linearity and the Bigger Machine" (www.ddj.com/architect/206903306).


Herb is a software development consultant, a software architect at Microsoft, and chair of the ISO C++ Standards committee. He can be contacted at www.gotw.ca.



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