{"id":23291,"date":"2023-08-07T05:00:00","date_gmt":"2023-08-07T03:00:00","guid":{"rendered":"https:\/\/sii.pl\/blog\/?p=23291"},"modified":"2023-08-03T15:00:16","modified_gmt":"2023-08-03T13:00:16","slug":"effective-multi-threaded-code-debugging","status":"publish","type":"post","link":"https:\/\/sii.pl\/blog\/en\/effective-multi-threaded-code-debugging\/","title":{"rendered":"Effective multi-threaded code debugging"},"content":{"rendered":"\n

Concurrency issues are one of the hardest to investigate and fix. It is caused mainly by the nondeterministic nature of threads and processes. Every time you run a concurrent code it may execute in a slightly different order which certainly affects the correctness and performance of a program. As a result, the most popular techniques used in investigating sequential code like log analysis or examinating code with debugger<\/em> are insufficient.<\/p>\n\n\n\n

You could obviously say that there are multiple high-level solutions like Node.js based frameworks, Java applications server frameworks or simply databases which implement whole concurrency stuff internally and you don\u2019t need to care about that at all. That sounds fair for enterprise applications or web services but not necessarily for embedded systems where you often reach out for low-level stuff to deliver expected efficiency.<\/p>\n\n\n\n

This article aims at presenting methods and tools which might be quite helpful in dealing with nondeterminism and typical problems of multi-threaded applications.<\/p>\n\n\n\n

Prerequisite<\/strong><\/h2>\n\n\n\n

In the article I mainly use tools available on Linux platform with kernel release 5.19.0. All the examples have been written in C++ programming language and compiled with GCC 12.0 on Intel(R)Core(TM)i7-7700CPU@3.60GHz<\/em> processor. However, the presented techniques are universal so you can find analogous tools for different platforms and programming languages.<\/p>\n\n\n\n

Analyzing deadlocks with “post-mortem” debugging<\/strong><\/h2>\n\n\n\n

Let\u2019s start with the first typical anomaly that occurs in multi-threaded environment called deadlock<\/em>. Deadlock<\/em> is a situation where two or more threads try to acquire the same resources and wait for others in a way that puts them in a deadly embrace. As a result, none of threads can proceed and do useful work.<\/p>\n\n\n\n

To illustrate the issue better it\u2019s good to evoke dining philosophers’ problem<\/em>. In a nutshell you have a finite number of philosophers that sit at the same table and each one has a plate. There is only one fork between each plate and each philosopher can do two actions: eat or think. <\/p>\n\n\n\n

Certainly, a philosopher needs two forks to eat (left and right). Now you can imagine the situation where each philosopher wants to eat at the same time and grabs one of available forks. As a result, all the forks are occupied and none of philosophers can eat because they block each other. That\u2019s exactly what you understand by deadlock<\/em>.<\/p>\n\n\n\n

Surprisingly, this class of problems is quite simple to investigate and fix. All you need is actually a debugger<\/em> \ud83d\ude42 You already know the theory so you can jump into the Example 1.<\/p>\n\n\n

\n#include &lt;iostream>\n#include &lt;chrono>\n#include &lt;thread>\n#include &lt;mutex>\n\n\nusing namespace std::chrono_literals;\n\nstatic std::mutex m1, m2;\n\nvoid Alice()\n{\n    std::lock_guard&lt;std::mutex> lock1{m1};\n    std::this_thread::sleep_for(1s);\n    std::lock_guard&lt;std::mutex> lock2{m2};\n}\n\nvoid Bob()\n{\n    std::lock_guard&lt;std::mutex> lock2{m2};\n    std::this_thread::sleep_for(1s);\n    std::lock_guard&lt;std::mutex> lock1{m1};\n}\n\n\nint main()\n{\n    std::thread aliceThread(Alice);\n    std::thread bobThread(Bob);\n    \n    aliceThread.join();\n    bobThread.join();\n    return 0;\n}\n<\/pre><\/div>\n\n\n
You can compile the Example 1 and run it as follows:<\/p>\n\n\n\n
$ g++ -ggdb -o deadlock -lpthread deadlock.cpp\n$ .\/deadlock\n<\/pre>\n\n\n\n
The code is compiled with a flag adding particular debugging symbols to the binary for gdb<\/em> debugger only \u2014 that\u2019s the tool that will be used in the analysis. After running the above program multiple times, you can observe it freezes \u2014 you have classical deadlock<\/em>. The very first step in dealing with such case is reading a PID of a hanged process and sending SIGABRT signal to it \u2014 this forces Linux kernel to generate core dump file which is crucial for further analysis (make sure that core file size is not set to 0 for your Linux OS. You can check it ulimit -c command). The following commands do the job:<\/p>\n\n\n\n
$ ps x | grep \"deadlock\"\n   5767 pts\/0    Sl+    0:00 .\/deadlock\n   5785 pts\/1    S+     0:00 grep --color=auto deadlock\n$ kill -SIGABRT 5767\n<\/pre>\n\n\n\n
On most Linux distribution core dump files are stored in the current working directory but some of them define a specific global path for all processes \u2014 you need to check how it works for your platform (It\u2019s possible to edit a default core file path in \/proc\/sys\/kernel\/core_pattern<\/em> file). Having a core dump file you can run gdb<\/em> on it.<\/p>\n\n\n\n
$ gdb .\/deadlock core_dump<\/pre>\n\n\n\n
Now you can display information about threads:<\/p>\n\n\n\n
(gdb) info threads\n Id   Target Id                        Frame \n  * 1  Thread 0x7f2ec07043c0 (LWP 6179) __futex_abstimed_wait_common64\n  2    Thread 0x7f2ebffff640 (LWP 6180) futex_wait\n  3    Thread 0x7f2ebf7fe640 (LWP 6181) futex_wait\n<\/pre>\n\n\n\n
As you see it seems that two threads are waiting for a lock. Let\u2019s dig into call stack of specific threads. You can simply do it by running the following:<\/p>\n\n\n\n
(gdb) thread 2\n(gdb) bt\n#0  futex_wait  \n#1  __GI___lll_lock_wait\n#2  0x00007f2ec0098082 in lll_mutex_lock_optimized \n#3  ___pthread_mutex_lock \n#4  0x0000559f706ea5d5 in __gthread_mutex_lock\n#5  0x0000559f706ea74c in std::mutex::lock\n#6  0x0000559f706ea7c6 in std::lock_guard<std::mutex>::lock_guard \n#7  0x0000559f706ea371 in Alice () at deadlock.cpp:15\n#8  0x0000559f706eb24d in std::__invoke_impl<void, void (*)()> \n#9  0x0000559f706eb1f9 in std::__invoke<void (*)()> \n...\n<\/pre>\n\n\n\n
If you go carefully via stack trace you notice that the problem occurs in line 15 \u2014 that\u2019s the place where Alice<\/em> is blocked:<\/p>\n\n\n\n
std::lock_guard<std::mutex> lock2{m2};<\/pre>\n\n\n\n
Now if you repeat the same steps for Bob<\/em>, you realize that this thread is also blocked in line 22:<\/p>\n\n\n\n
std::lock_guard<std::mutex> lock1{m1};<\/pre>\n\n\n\n
It\u2019s relatively simple to explain the issue \u2014 a thread Bob<\/em> tries to obtain a resource m1<\/em> which has been grabbed by Alice<\/em> and vice versa. So how can you fix the problem? In this particular case you need to make sure that the resources are locked in the same order by Alice<\/em> and Bob<\/em>. You can look at the Example 2.<\/p>\n\n\n
\nvoid Alice()\n{\n    std::lock_guard&lt;std::mutex> lock1{m1};\n    std::this_thread::sleep_for(1s);\n    std::lock_guard&lt;std::mutex> lock2{m2};\n}\n\nvoid Bob()\n{\n\n    std::lock_guard&lt;std::mutex> lock1{m1};\n    std::this_thread::sleep_for(1s);\n    std::lock_guard&lt;std::mutex> lock2{m2};\n}\n<\/pre><\/div>\n\n\n
So simple isn\u2019t it? Let\u2019s move on.<\/p>\n\n\n\n
Tracking race conditions with capture and replicate technique<\/strong><\/h2>\n\n\n\n
Now things are getting much more interesting as this time you are going to face race condition<\/em> :). In the previous example it was quite easy to track the problem as the program suspended and you could simply take a snapshot of process\u2019s memory. In case of race condition<\/em> it is, to put it mildly, a little bit more challenging.<\/p>\n\n\n\n
In general, this anomaly is a situation where two or more operations are performed simultaneously and a specific order of those operations is required to make the program work properly. In a nutshell the race condition results in undefined behaviour of a program. Ok, that\u2019s enough in term of theory. Let\u2019s have a look at the Example 3:<\/p>\n\n\n
\n#include &lt;iostream>\n#include &lt;thread>\n#include &lt;vector>\n\n\nstatic auto counter = 0u;\nconstexpr auto MAX_ITER_NUMBER = 20000000u;\n\n\nvoid task()\n{\n\tauto tmp = counter;\n\t++tmp;\n\tcounter = tmp;\n}\n\nvoid worker()\n{\n    for(auto idx=0; idx&lt;MAX_ITER_NUMBER; ++idx)\n    {\n\t    task();\n    }\n}\n\n\nint main()\n{\n\tconst auto threadNumber = std::thread::hardware_concurrency();\n\tstd::vector&lt;std::thread> threads;\n\tthreads.reserve(threadNumber);\n\tfor(auto idx=0;idx&lt;threadNumber; ++idx)\n\t{\n\t\tthreads.emplace_back(worker);\n\t}\n\tfor(auto&amp; th : threads)\n\t{\n\t\tth.join();\n\t}\n\tstd::cout &lt;&lt; "Expected calls: " &lt;&lt; threadNumber*MAX_ITER_NUMBER &lt;&lt; " Real calls: " &lt;&lt; counter &lt;&lt; std::endl;\n    \treturn 0;\n}\n<\/pre><\/div>\n\n\n
This time the program creates multiple workers depending on the number of, so called, hardware threads supporting by your processor. Each thread just increments a counter<\/em> and in the end of the program the number of increments is written to stdout<\/em>. In theory, you expect that value of counter<\/em> is predictable and equal to a number of thread multiple by a number of iterations. Let\u2019s compile the code and run it.<\/p>\n\n\n\n
$ g++ -o race -ggdb -lpthread race.cpp\n$ .\/race\n$ Expected calls: 160000000 Real calls: 25869183\n<\/pre>\n\n\n\n
As you see the displayed values are different and what is more if you run the program multiple times you realize that the final counter<\/em> value is completely random \u2014 that\u2019s a pure race condition<\/em>. It\u2019s worth emphasizing that in the example you get a wrong result almost each time you fire the code \u2014 that\u2019s the best possible case. Usually, you witness the failure quite rare and thus race conditions<\/em> are irritating and hard to detect (especially in complex systems). Anyway, let\u2019s discuss one of techniques which is quite flexible and effective in dealing with this kind of bugs.<\/p>\n\n\n\n
The method is called capture and replicate<\/em> (some people say time travel debugging :)) which actually can be described with the following steps:<\/p>\n\n\n\n
    \n
  1. Run the program repeatedly with recording until you reproduce an issue.<\/li>\n\n\n\n
  2. Analyse the recording.<\/li>\n\n\n\n
  3. Replay the recording running the program under a debugger until a bug occurred.<\/li>\n\n\n\n
  4. Analyse a program\u2019s state at that point.<\/li>\n<\/ol>\n\n\n\n
    Unfortunately, this time a standard debugger is not sufficient \u2014 you need support from some external tool. In fact, the most mysterious thing in terms of this approach is the recording functionality. There are multiple (commercial and non-commercial) tools that offer this feature and in this specific case you will use which is a free and lightweight recording tool (Pin$PLay<\/em> tool created by Intel and UDB<\/em> are also interesting options).<\/p>\n\n\n\n
    It is also worth mentioning that gdb<\/em>\u00a0itself also has the recording feature. Unfortunately, it does not support some crucial system calls for simulating concurrency behaviour \u2014 it is expected to be added in the future. Ok, now you know the theory so it\u2019s high time to put it into practise. Let\u2019s check what tool can do:<\/p>\n\n\n\n
    $ rr record -h .\/race\r\n(rr): Saving execution to trace directory \/root\/.local\/share\/rr\/race-20.\r\nExpected calls: 60000000 Real calls: 25757037\r<\/pre>\n\n\n\n
    As you see, we\u2019ve succeeded in recording the failure \u2014 that\u2019s half the battle. The cool thing about the recording is the fact that now you can repeat the sequence of events that leads to race condition<\/em>\u00a0deterministically (time travel). The second super feature of rr<\/em>\u00a0is a possibility of running gdbserver<\/em>\u00a0with our recording and simply attaching to it with GNU<\/em>\u00a0debugger.<\/p>\n\n\n\n
    $ rr replay race-20\r\nFor help, type \"help\".\r\nType \"apropos\\ word\" to search for commands related to \"word\"...\r\nReading symbols from \/home\/michal\/race...\r\nReally redefine built-in command \"restart\"? (y or n)\r\nRemote debugging using 127.0.0.1:7599\r\nReading symbols from \/lib64\/ld-linux-x86-64.so.2...\r\n(rr)\r<\/pre>\n\n\n\n
    Looks good, isn\u2019t it? You have a gdb<\/em>\u00a0session fired which allows an advanced analysis of the misbehaviour. In the beginning you can set a conditional breakpoint in order to stop a program at some point and then check what kind of operations are performed by specific threads.<\/p>\n\n\n\n
    (rr) break 14 if counter>15757037\r\nBreakpoint 1 at 0x5626f30a73be: file race.cpp, line 14.\r\n(rr) c\r\nContinuing.\r\n[New Thread 21868.21872]\r\n[New Thread 21868.21871]\r\n[New Thread 21868.21870]\r\n[New Thread 21868.21869]\r\n[Switching to Thread 21868.21871]\r\nThread 3 hit Breakpoint 1, task () at race.cpp:14\r\n(rr) info thread\r\n  Id   Target Id                 Frame \r\n  1    Thread 21868.21868 (race) __futex_abstimed_wait_common64\r\n  2    Thread 21868.21872 (race) task () at race.cpp:14\r\n* 3    Thread 21868.21871 (race) task () at race.cpp:14\r\n  4    Thread 21868.21870 (race) task () at race.cpp:14\r\n  5    Thread 21868.21869 (race) task () at race.cpp:15\r\n(rr) thread 2\r\n[Switching to thread 2 (Thread 21868.21872)]\r\n#0  task () at race.cpp:14\r\n14      counter = tmp;\r\n(rr) print(tmp)\r\n$8 = 15355793\r\n(rr) thread 3\r\n[Switching to thread 3 (Thread 21868.21871)]\r\n#0  task () at race.cpp:14\r\n14      counter = tmp;\r\n(rr) print(tmp)\r\n$9 = 15757044\r\n(rr) thread 4\r\n[Switching to thread 4 (Thread 21868.21870)]\r\n#0  task () at race.cpp:14\r\n14      counter = tmp;\r\n(rr) print(tmp)\r\n$10 = 13297385\r<\/pre>\n\n\n\n
    As you see 3 threads out of 5 try to write completely different values to counter<\/em>\u00a0at the same time! Now everything becomes clear \u2014 the source of the problem is lack of atomicity in case of read and write operations on counter<\/em>\u00a0variable. You can simply fix it by adding some synchronization mechanism.<\/p>\n\n\n\n
    It\u2019s worth to remember that adding synchronization always affect the performance of a program so be careful. In this case the best option is an atomic variable with relaxed memory ordering (actually memory barriers and memory ordering are other interesting topic in terms of concurrency, but I will not touch them in this paper). You can check the full solution in Example 4:<\/p>\n\n\n
    \n#include &lt;iostream>\n#include &lt;thread>\n#include &lt;vector>\n#include &lt;atomic>\n\n\nstatic std::atomic_int counter = 0u;\nconstexpr auto MAX_ITER_NUMBER = 20000000u;\n\n\nvoid task()\n{\n\tcounter.fetch_add(1, std::memory_order_relaxed);\n}\n<\/pre><\/div>\n\n\n
    Finally let\u2019s make sure that everything works fine.<\/p>\n\n\n\n
    $ g++ -o fix_race -ggdb -lpthread fix_race.cpp\r\n$ .\/fix_race\r\n$ Expected calls: 160000000 Real calls: 160000000\r<\/pre>\n\n\n\n
    In the end it is significant to mention about limitations of rr\u00a0<\/em>which touch different recording tools as well:<\/p>\n\n\n\n
      \n
    1. rr<\/em>\u00a0works only with intel processors and requires a brand-new linux kernel.<\/li>\n\n\n\n
    2. Despite being quite effective in reproducing concurrency environment, it is still single core simulation which might behave different than expected.<\/li>\n\n\n\n
    3. A great majority of system calls is supported (recorded) but not all of them.<\/li>\n\n\n\n
    4. Debugging the recording is a slow process \u2014 moving from one breakpoint to another take some time, especially when multiple threads must be simulated.<\/li>\n<\/ol>\n\n\n\n
      Anyway, time travel tools really make your life easier in terms of finding bugs (not necessarily always in mutli-threaded applications) so I encourage you to play with them a little bit.<\/p>\n\n\n\n
      Investigating performance issues with performance counters<\/strong><\/h2>\n\n\n\n
      So far you have been investigating issues affecting correctness of programs. This time let\u2019s try to dig into another class of concurrency problems connected with performance. Let\u2019s start with some portion of theory at first\u2026<\/p>\n\n\n\n
      In modern multi-core processor architectures, each core possesses his own internal memory (cache). The reason for that is obviously \u2026performance. If some data stored in a specific memory region is accessed frequently it is just worth caching it to make the access faster. The data are transferred between main memory and cache using fix size blocks called cachelines<\/em>.<\/p>\n\n\n\n
      And here comes the question: what if multiple threads share data from the same cache line? At first glance it looks like a potential race condition. However, you do not have to care of that \u2014 the processor cores use cache coherency protocol which synchronizes data between threads. Unfortunately, this synchronization primitive has a negative impact on performance. This effect is well-known as false sharing<\/em>. Let\u2019s have a look at the following piece of code in Example 5:<\/p>\n\n\n
      \n#include &lt;random>\n#include &lt;algorithm>\n#include &lt;array>\n\n#include &lt;omp.h>\n\nconstexpr auto THREAD_NUMBER = 8;\nconstexpr auto N = 10000000;\n\nstd::array&lt;unsigned, THREAD_NUMBER> sums;\nstd::array&lt;unsigned, N> values;\n\n\nvoid calculateSums()\n{\n\tauto threadId = 0;\n#ifdef _OPENMP\n\tomp_set_num_threads(THREAD_NUMBER);\n\t#pragma omp parallel private(threadId)\n\t{\n\t\tthreadId = omp_get_thread_num();\n#else\n\tfor(threadId=0; threadId&lt;THREAD_NUMBER; ++threadId)\n\t{\n#endif\n\t\tfor(auto idx=0; idx&lt;N; ++idx)\n\t\t{\n\t\t\tsums[threadId] += values[idx] >> threadId;\n\t\t}\n\t}\n}\n\n\nint main() \n{\n\tstd::random_device rDevice;\n\tstd::mt19937 engine {rDevice()};\n\tstd::uniform_int_distribution&lt;unsigned> dist {1, N};\n\tstd::generate(values.begin(), values.end(), [&amp;dist, &amp;engine]() {\n\t\treturn dist(engine);\n\t});\n\tcalculateSums();\t\n\treturn 0;\n}\n<\/pre><\/div>\n\n\n
      The program calculates 8 sums divided by a power of 2 in two modes: sequentially and in parallel using OpenMP<\/em>\u00a0library. In theory you should expect the second approach to be much faster \u2014 eventually each sum is calculated independently using 8 threads. Let\u2019s find out how fast it works with OpenMP<\/em>\u00a0support.<\/p>\n\n\n\n
      $ g++ -o false_sharing_par -fopenmp false_sharing.cpp\r\n$ time .\/false_sharing\r\n$ real  0m1,097s\r\n$ user  0m6,061s\r\n$ sys   0m0,004s\r<\/pre>\n\n\n\n
      As you see it takes about 1.097s to perform 8 sums. Now let\u2019s compile the code without OpenMP<\/em>\u00a0support and repeat the experiment.<\/p>\n\n\n\n
      $ g++ -o false_sharing_seq false_sharing.cpp\r\n$ time .\/false_sharing_seq\r\n$ real  0m0,928s\r\n$ user  0m0,907s\r\n$ sys   0m0,020s\r<\/pre>\n\n\n\n
      This time it took about 0.928s so the time of performing the same task sequentially decreased\u2026 Are you surprised? What you\u2019re currently witnessing is certainly false_sharing<\/em>. All 8 threads modify the same buffer while calculating the sums. As a result, CPU cores fire synchronization protocol and you observe performance degradation.<\/p>\n\n\n\n
      Now let\u2019s try to dig into a problem and track a bottleneck. In order to debug this, you will tap into CPU\u2019s performance counters. The counters track event connected with \u2026CPU\u2019s performance for instance the number of executed instructions or CPU cycles etc. There are obviously multiple tools to analyze performance counters but as long as you use Linux, perf<\/em>\u00a0tool is sufficient for your needs.<\/p>\n\n\n\n
      In order to investigate the issue, you will mainly focus on LLC – loads<\/em>\u00a0counter which stands for last-level cache misses. In fact, when falsesharing<\/em>\u00a0occurs the number of cache misses (lack of specific data in CPU core\u2019s cache memory) dramatically increases because the coherency protocol kicks into action. Let\u2019s compare the counter for sequential and parallel versions of the code.<\/p>\n\n\n\n
      $ perf stat -e LLC-loads .\/false_sharing_seq \r\n  Performance counter stats for '.\/false_sharing_seq':\r\n            339 028      LLC-loads\r\n$ perf stat -e LLC-loads .\/false_sharing_par\r\n  Performance counter stats for '.\/false_sharing_seq':\r\n            2 343 694      LLC-loads\r<\/pre>\n\n\n\n
      As you see the difference is meaningful \u2014 the number of misses is approximately 7 times higher for parallel code. Now you need to locate a source of the problem (to be more specific a place where false_sharing<\/em>\u00a0affects the code). In order to do that you can use perf<\/em>\u00a0tool again. The following command will record the event which is interesting from your perspective.<\/p>\n\n\n\n
      $ perf record -e LLC-loads .\/false_sharing_seq <\/pre>\n\n\n\n
      Finally, you can analyze the results of recording with the following command.<\/p>\n\n\n\n
      $ perf record -e LLC-loads .\/false_sharing_seq\r\nPercent | Source code & Disassembly of false_sharing_par for LLC-loads \r\n-------------------------------------------\r\n         :\r\n         :\r\n         :\r\n         : 3    Disassembly of section .text:\r\n         :\r\n         : 5    000000000000263f <calculateSums()\r\n         : 6    calculateSums() [clone ._omp_fn.0]:\r\n         : 19   void calculateSums()\r\n         : 19   void calculateSums()\r\n         : 20   {\r\n         : 19   void calculateSums()\r\n         : 20   {\r\n         : 21   auto threadId = 0;\r\n         : 22   #ifdef _OPENMP\r\n         : 23   omp_set_num_threads(THREAD_NUMBER);\r\n         : 24   #pragma omp parallel private(threadId)\r\n    0.00 :   263f:   endbr64\r\n    0.00 :   2643:   push   %rbp\r\n    0.00 :   2644:   mov    %rsp,%rbp\r\n    0.00 :   2647:   push   %rbx\r\n    0.00 :   2648:   sub    $0x28,%rsp\r\n    0.00 :   264c:   mov    %rdi,-0x28(%rbp)\r\n         : 21   {\r\n         : 22   threadId = omp_get_thread_num();\r\n    0.00 :   2650:   call   2310 <omp_get_thread_num@plt>\r\n    0.00 :   2655:   mov    %eax,-0x14(%rbp)\r\n         : 26   #else\r\n         : 27   for(threadId=0; threadId<THREAD_NUMBER; ++threadId)\r\n         : 28   {\r\n         : 29   #endif\r\n         : 30   for(auto idx=0; idx<N; ++idx)\r\n    0.00 :   2658:   movl   $0x0,-0x18(%rbp)\r\n    0.00 :   265f:   nop\r\n    0.00 :   2660:   cmpl   $0x98967f,-0x18(%rbp)\r\n    0.02 :   2667:   jg     26ae <calculateSums()\r\n         : 28   {\r\n         : 29   sums[threadId] += values[idx] >> threadId;\r\n    0.02 :   2669:   mov    -0x18(%rbp),%eax\r\n    0.00 :   266c:   cltq\r\n    0.00 :   266e:   mov    %rax,%rsi\r\n    0.00 :   2671:   lea    0x39e8(%rip),%rax\r\n    0.02 :   2678:   mov    %rax,%rdi\r\n    0.00 :   267b:   call   2996 <std::array<>::operator[](unsigned long)>\r\n    0.00 :   2680:   mov    (%rax),%edx\r\n    0.29 :   2682:   mov    -0x14(%rbp),%eax\r\n    0.00 :   2685:   mov    %edx,%ebx\r\n    0.59 :   2687:   mov    %eax,%ecx\r\n    0.00 :   2689:   shr    %cl,%ebx\r\n    2.92 :   268b:   mov    -0x14(%rbp),%eax\r\n    0.00 :   268e:   cltq\r\n    0.00 :   2690:   mov    %rax,%rsi\r\n   32.50 :   2693:   lea    0x39a6(%rip),%rax\r\n   49.12 :   269a:   mov    %rax,%rdi\r\n    0.01 :   269d:   call   296c <std::array<unsigned int, 8ul>::operator[](unsigned long)>\r\n    0.00 :   26a2:   mov    (%rax),%edx\r\n   13.48 :   26a4:   add    %ebx,%edx\r\n    0.97 :   26a6:   mov    %edx,(%rax)\r\n         : 26   for(auto idx=0; idx<N; ++idx)\r\n    0.04 :   26a8:   addl   $0x1,-0x18(%rbp)\r\n    0.03 :   26ac:   jmp    2660 <calculateSums()\r\n         : 19   #pragma omp parallel private(threadId)\r\n    0.00 :   26ae:   nop\r\n    0.00 :   26af:   mov    -0x8(%rbp),%rbx\r\n    0.00 :   26b3:   leave\r<\/pre>\n\n\n\n
      The command produces low-level AT&T assembler code with information about cache misses generated by each instruction. Thanks to debugging symbols the output is more human-readable and you can simply notice that almost all the misses occur after executing in line 28.<\/p>\n\n\n\n
      sums[threadId] += values[idx] >> threadId;<\/pre>\n\n\n\n
      So, the problem lies in writing data to the shared sums<\/em>\u00a0buffer in the loop. Fixing the issue requires to limit the number of writes to the sums<\/em>. You can simply do that by adding a stack-base variable which stores a temporary sum which will be finally assigned to the buffer after summing all elements from values. Check the code in Example 6:<\/p>\n\n\n
      \nvoid calculateSums()\n{\n\tauto threadId = 0;\n#ifdef _OPENMP\n\tomp_set_num_threads(THREAD_NUMBER);\n\t#pragma omp parallel private(threadId)\n\t{\n\t\tthreadId = omp_get_thread_num();\n#else\n\tfor(threadId=0; threadId&lt;THREAD_NUMBER; ++threadId)\n\t{\n#endif\n\t\tauto tmp = 0;\n\t\tfor(auto idx=0; idx&lt;N; ++idx)\n\t\t{\n\t\t\ttmp += values[idx] >> threadId; \n\t\t}\n\t\tsums[threadId] = tmp;\n\t}\n}\n<\/pre><\/div>\n\n\n
      Let\u2019s find out how this cosmetic change affects the performance of the program.<\/p>\n\n\n\n
      $ g++ -o false_sharing_par -fopenmp false_sharing.cpp\r\n$ time .\/false_sharing\r\n$ real  0m0,387s\r\n$ user  0m0,908s\r\n$ sys   0m0,000s\r<\/pre>\n\n\n\n
      Looks much better! This time it takes 0.387s which is quite satisfying.<\/p>\n\n\n\n
      As you see performance counter statistics allowed to track the issue connected with memory. It is worth mentioning that perf\u00a0<\/em>is quite a powerful tool and can be used to investigate different problems connected with performance.<\/p>\n\n\n\n
      Summary<\/strong><\/h2>\n\n\n\n
      Finally, you got to the end \ud83d\ude42 As you see analysing the concurrent code is not a piece of cake. Even for simple examples presenting in this article it\u2019s not so easy to find a source of a problem (for instance in case of false_sharing<\/em>).<\/p>\n\n\n\n
      I hope that the techniques described in the article will help you improve your debugging skills and track some concurrency issues in your application faster. Using low-level threads or processes stuff requires good understanding of OS and processors\u2019 internals, so think twice about the design before implementing it. If you spend a lot of time dealing with new multi-threaded code you should definitely consider some high-level solutions.<\/p>\n\n\n\n
      References<\/strong><\/h2>\n\n\n\n