Ongoing Optimization: Sequential Consistency with CppMem

Contents[Show]

With atomic data types, you can tailor your program to your needs and therefore optimize it. But now we are in the domain of the multithreading experts.

Sequential consistency

If you don't specify the memory model, the sequential consistency will be used. The sequential consistency guarantees two properties. Each thread executes its instructions in source code order and all threads follow a global order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// OngoingOptimizationSequentialConsistency.cpp

#include <atomic>
#include <iostream>
#include <thread>

std::atomic<int> x{0};
std::atomic<int> y{0};

void writing(){  
  x.store(2000);  
  y.store(11);
}

void reading(){  
  std::cout << y.load() << " ";  
  std::cout << x.load() << std::endl;
}

 

This knowledge is sufficient to analyse the program. Because x and y are atomic, the program has no race condition. So there is only the question. What values are possible for x and y? But the question is easy to answer. Because of the sequential consistency, all threads have to follow a global order.

 

It holds:

  1. x.store(2000); happens-before y.store(11);
  2. std::cout << y.load() << " "; happens-before std::cout << x.load() << std::endl;

Therefor: x.load() can not have 0, if y.load() is 11, because x.store(2000) happens before y.store(11).

All other values for x and y are possible. Here are three possible interleavings, producing the three different results for x and y.

  1. thread1 will completely executed beforel thread2.
  2. thread2 will completely executed before thread1.
  3. thread1 executes the first instruction x.store(2000), before thread2 will be completely executed.

Here all values for x and y. 

sukzessiveOptimierungSequenzielleKonsistenzEng

So how does this look like in CppMem.

CppMem

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int main(){
  atomic_int x= 0; 
  atomic_int y= 0;
  {{{ { 
      x.store(2000);
      y.store(11);
      }
  ||| {
      y.load();
      x.load();
      } 
  }}}
}

 

At first a little bit of syntax of CppMem. CppMem uses in line 2 and 3 the typedef atomic_int for std::atomic<int>.

If I execute the program, I'm overwhelmed by the sheer number of execution candidates.

SequenzielleKonsistenz

384 (1) possible execution candidates, only 6 of them are consistent. No candidate has a data race. How does that work? 

But I'm only interested in the consistent executions. I use interface (2) to analyse the six annotated graphs. The other (378) are not consistent. That means, for example, they do not respect the modification order. So I totally ignore them.

We know already, that all values for x and y are possible, except for y= 11 and x= 0. That's because of the default memory model.

sukzessiveOptimierungSequenzielleKonsistenzEng

Now the questions are. Which interleavings of the threads produce which values for x and y? I already introduce the symbols in the annotated graph (CppMem - An overview), therefore I will concentrate my analysis on the results for x and y.

Execution for (y= 0, x= 0)

first

Executions for (y= 0, x= 2000)

secondthird

fourfive

 

Execution for (y= 11, x= 2000)

six

Do you have an idea, why I used the red numbers in the graphs? I have because I'm not done with my analysis. 

Deeper insights

If I look at the 6 different interleavings of thread in the following graphic, I have the question? Which sequence of instructions corresponds to which graph? Here is the solution. I have assigned to each sequence of instructions the corresponding graph.

 

Sequences of instructions

atomicInterleavingEng

I start with the simpler cases:

  • (1): It's quite simple to assign the graph (1) to the sequence (1). In the sequence (1) have x and y the values 0, because y.load() and x.load() are executed before the operations x.store(2000) and y.store(11).
  • (6): The argumentation for the execution (6) is accordingly. y has the value 11 and y the value 2000 if all load operations happen after all store operations. 
  • (2),(3),(4),(5): Now to the more interesting cases, in which y has den value 0 and x has the value 2000. The yellow arrows (sc) are the key to my reasoning because they stand for the sequence of instructions. For example, let's look at execution (2).
    • (2): The sequence of the yellow arrows (sc) in the graph (2) is: Write x= 2000 => Read y= 0 => Write y= 11 => Read x= 2000. This sequence corresponds to the sequence of instructions of the second interleaving of threads (2)

     

What's next?

In the next post, I will break the sequential consistency. So what will happen, if a base my optimization on the acquire-release semantic?

 

 

 

 

 

Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, Marko, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Animus24, Jozo Leko, John Breland, espkk, Louis St-Amour, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Neil Wang, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Tobi Heideman, Daniel Hufschläger, Red Trip, Alexander Schwarz, Tornike Porchxidze, Alessandro Pezzato, Evangelos Denaxas, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Dimitrov Tsvetomir, Leo Goodstadt, Eduardo Velasquez, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, and Michael Young.

 

Thanks in particular to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, and Rusty Fleming.

 

 

My special thanks to Embarcadero CBUIDER STUDIO FINAL ICONS 1024 Small

 

Seminars

I'm happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

Bookable (Online)

German

Standard Seminars (English/German)

Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

New

Contact Me

Modernes C++,

RainerGrimmSmall

Comments   

0 #1 Zoila 2016-10-04 15:02
Hi! I'm at work browsing your blog from my new iphone 3gs!
Just wanted to say I love reading your blog and look forward to all your posts!

Carry on the fantastic work!
Quote
0 #2 Iphone 7 Launch 2016-11-16 21:28
This is really interesting, You are a very skilled blogger.

I've joined your feed and look forward to seeking more of your great post.
Also, I've shared your site in my social networks!
Quote
0 #3 Iphone 7 Launch 2016-11-22 03:10
What's up everybody, here every one is sharing such know-how, thus it's fastidious to
read this blog, and I used to go to see this weblog daily.
Quote
0 #4 CHRISTIAN 2017-02-01 08:08
whoah this blog is excellent i really like studying your posts.

Stay up the great work! You understand, a lot of people are looking round for this information, you could
aid them greatly.
Quote

My Newest E-Books

Course: Modern C++ Concurrency in Practice

Course: C++ Standard Library including C++14 & C++17

Course: Embedded Programming with Modern C++

Course: Generic Programming (Templates)

Course: C++ Fundamentals for Professionals

Interactive Course: The All-in-One Guide to C++20

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 6329

Yesterday 7646

Week 39624

Month 106290

All 7374130

Currently are 175 guests and no members online

Kubik-Rubik Joomla! Extensions

Latest comments