{"id":4852,"date":"2016-08-13T04:55:35","date_gmt":"2016-08-13T04:55:35","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/ongoing-optiimization-sequential-consistency-with-cppmem\/"},"modified":"2023-06-26T12:46:44","modified_gmt":"2023-06-26T12:46:44","slug":"ongoing-optiimization-sequential-consistency-with-cppmem","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/ongoing-optiimization-sequential-consistency-with-cppmem\/","title":{"rendered":"Ongoing Optimization: Sequential Consistency with CppMem"},"content":{"rendered":"

With atomic data types, you can tailor your program to your needs and optimize it. But now we are in the domain of multithreading experts.<\/p>\n

<\/p>\n

Sequential consistency<\/h2>\n

If you don’t specify the memory model<\/a>, sequential consistency<\/a> 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.<\/p>\n

<\/p>\n

\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18<\/pre>\n<\/td>\n
\n
\/\/ OngoingOptimizationSequentialConsistency.cpp<\/span>\r\n\r\n#include <atomic><\/span>\r\n#include <iostream><\/span>\r\n#include <thread><\/span>\r\n\r\nstd::atomic<int<\/span>> x{0};\r\nstd::atomic<int<\/span>> y{0};\r\n\r\nvoid<\/span> writing(){  \r\n  x.store(2000);  \r\n  y.store(11);\r\n}\r\n\r\nvoid<\/span> reading(){  \r\n  std::cout << y.load() << \" \"<\/span>;  \r\n  std::cout << x.load() << std::endl;\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
This knowledge is sufficient to analyze the program. Because x and y are atomic, the program has no race condition<\/a>. So there is only the question. What values are possible for x and y? But the question is easy<\/em> to answer. Because of the sequential consistency, all threads must follow a global order.<\/p>\n
 <\/p>\n
It holds:<\/p>\n
    \n
  1. x.store(2000); <\/span>happens-before<\/strong> y.store(11);<\/span><\/li>\n
  2. std::cout << y.load() << ” “;<\/span> happens-before<\/strong> std::cout << x.load() << std::endl;<\/span><\/li>\n<\/ol>\n
    Therefor: x.load()<\/span> can not have 0, if y.load()<\/span> is 11, because x.store(2000)<\/span> happens before y.store(11)<\/span>.<\/p>\n
    All other values for x and y are possible. Here are three possible interleavings, producing the three different results for x and y.<\/p>\n
      \n
    1. thread1<\/span> will be completely executed before thread2<\/span>.<\/li>\n
    2. thread2<\/span> will be completely executed before thread1<\/span>.<\/li>\n
    3. thread1<\/span> executes the first instruction  x.store(2000)<\/span>, before thread2<\/span> will be completely executed.<\/li>\n<\/ol>\n
      Here all values for x and y. <\/p>\n
      \"sukzessiveOptimierungSequenzielleKonsistenzEng\"<\/p>\n
      So how does this look like in CppMem<\/a>.<\/p>\n<\/p>\n
      CppMem<\/h2>\n
      <\/p>\n
      \n\n\n\n
      \n
       1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13<\/pre>\n<\/td>\n
      		\n
      int<\/span> main(){\r\n  atomic_int x= 0; \r\n  atomic_int y= 0;\r\n  {{{ { \r\n      x.store(2000);\r\n      y.store(11);\r\n      }\r\n  ||| {\r\n      y.load();\r\n      x.load();\r\n      } \r\n  }}}\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
       <\/p>\n
      At first a little bit of syntax of CppMem. CppMem uses in line 2 and 3 the typedef atomic_int<\/span> for std::atomic<int><\/span>.<\/p>\n
      If I execute the program, I’m overwhelmed by the sheer number of execution candidates.<\/p>\n
      \"SequenzielleKonsistenz\"<\/p>\n
      384 (1<\/strong><\/span>) possible execution candidates, and only 6 of them are consistent. No candidate has a data race<\/a>. How does that work? <\/p>\n
      But I’m only interested in consistent executions. I use interface (2<\/span><\/strong>) to analyze the six annotated graphs. The other (378) are not consistent. That means, for example, they do not respect the modification order<\/a>. So I totally ignore them.<\/p>\n
      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.<\/p>\n
      \"sukzessiveOptimierungSequenzielleKonsistenzEng\"<\/p>\n
      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<\/a>); therefore, I will concentrate my analysis on the results for x and y.<\/p>\n
      Execution for (y= 0, x= 0)<\/h3>\n
      \"first\"<\/p>\n
      Executions for (y= 0, x= 2000)<\/h3>\n
      \"second\"\"third\"<\/p>\n
      \"four\"\"five\"<\/h3>\n
       <\/h3>\n
      Execution for (y= 11, x= 2000)<\/h3>\n
      \"six\"<\/p>\n
      Do you know why I used the red numbers in the graphs? I have because I’m not done with my analysis. <\/p>\n
      Deeper insights<\/h3>\n
      If I look at the six different thread interleavings 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.<\/p>\n
       <\/p>\n
      Sequences of instructions<\/h4>\n
      \"atomicInterleavingEng\"<\/p>\n
      I start with the simpler cases:<\/p>\n