{"id":4921,"date":"2016-09-05T05:17:33","date_gmt":"2016-09-05T05:17:33","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/multithreaded-summation-of-a-vector\/"},"modified":"2023-06-26T12:43:56","modified_gmt":"2023-06-26T12:43:56","slug":"multithreaded-summation-of-a-vector","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/multithreaded-summation-of-a-vector\/","title":{"rendered":"Multithreaded: Summation of a Vector"},"content":{"rendered":"

My goal is to sum up all elements of a vector. I used in the last post<\/a> a single thread. In this post, I use multiple threads and, therefore, the full power of my PC. The addition will be done on a shared variable. What, at first glance, seems like a good idea is a very naive strategy. The synchronization overhead of the summation variable is higher than the performance benefit of my four or two cores.<\/p>\n

<\/p>\n

 <\/p>\n

<\/span>The strategy<\/span><\/h2>\n

Following my last post, I sum up 100 000 000 million random numbers between 1 and 10. To be sure that my calculation is right I reduce the randomness. So I use no seed, and I get each time the same random numbers on my two architectures each. Therefore it’s easy to verify my total result. Both calculations will run on my 4-CPU Linux and my 2-CPU Windows PC, as ever, with maximum and without optimization. On Windows, I was very puzzled. <\/p>\n

What are the exciting questions?<\/p>\n

    \n
  1. How differs locks and atomics work?<\/li>\n
  2. What’s the difference between the single threaded <\/a>and the multithreading execution of std::accumulate<\/span>?<\/li>\n<\/ol>\n

    <\/span>Protection of the shared variable with the std::lock_guard<\/span><\/h2>\n

    The simplest way to protect a shared variable is to wrap a mutex in a lock.<\/p>\n

     <\/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\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40\r\n41\r\n42\r\n43\r\n44\r\n45\r\n46\r\n47\r\n48\r\n49\r\n50\r\n51\r\n52\r\n53\r\n54\r\n55\r\n56\r\n57<\/pre>\n<\/td>\n
    		\n
    \/\/ synchronizationWithLock.cpp<\/span>\r\n\r\n#include <chrono><\/span>\r\n#include <iostream><\/span>\r\n#include <mutex><\/span>\r\n#include <random><\/span>\r\n#include <thread><\/span>\r\n#include <utility><\/span>\r\n#include <vector><\/span>\r\n\r\nconstexpr long<\/span> long<\/span> size= 100000000;   \r\n\r\nconstexpr long<\/span> long<\/span> firBound=  25000000;\r\nconstexpr long<\/span> long<\/span> secBound=  50000000;\r\nconstexpr long<\/span> long<\/span> thiBound=  75000000;\r\nconstexpr long<\/span> long<\/span> fouBound= 100000000;\r\n\r\nstd::mutex myMutex;\r\n\r\nvoid<\/span> sumUp(unsigned<\/span> long<\/span> long<\/span>& sum, const<\/span> std::vector<int<\/span>>& val, unsigned<\/span> long<\/span> long<\/span> beg, unsigned<\/span> long<\/span> long<\/span> end){\r\n    for<\/span> (auto<\/span> it= beg; it < end; ++it){\r\n        std::lock_guard<std::mutex> myLock(myMutex);\r\n        sum+= val[it];\r\n    }\r\n}\r\n\r\nint<\/span> main(){\r\n\r\n  std::cout << std::endl;\r\n\r\n  std::vector<int<\/span>> randValues;\r\n  randValues.reserve(size);\r\n\r\n  std::mt19937 engine;\r\n  std::uniform_int_distribution<> uniformDist(1,10);\r\n  for<\/span> ( long<\/span> long<\/span> i=0 ; i< size ; ++i) randValues.push_back(uniformDist(engine));\r\n \r\n  unsigned<\/span> long<\/span> long<\/span> sum= 0;\r\n  auto<\/span> start = std::chrono::system_clock::now();\r\n  \r\n  std::thread<\/span> t1(sumUp,std::ref(sum),std::ref(randValues),0,firBound);\r\n  std::thread<\/span> t2(sumUp,std::ref(sum),std::ref(randValues),firBound,secBound);\r\n  std::thread<\/span> t3(sumUp,std::ref(sum),std::ref(randValues),secBound,thiBound);\r\n  std::thread<\/span> t4(sumUp,std::ref(sum),std::ref(randValues),thiBound,fouBound);   \r\n  \r\n \r\n  t1.join();\r\n  t2.join();\r\n  t3.join();\r\n  t4.join();\r\n  std::chrono::duration<double<\/span>> dur= std::chrono::system_clock::now() - start;\r\n  std::cout << \"Time for addition \"<\/span> << dur.count() << \" seconds\"<\/span> << std::endl;\r\n  std::cout << \"Result: \"<\/span> << sum << std::endl;\r\n\r\n  std::cout << std::endl;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
     <\/p>\n
    The program is easy to explain. The function sumUp<\/span> (lines 20 – 25) is each thread’s work package. This work package consists of the summation variable sum<\/span> and the std::vector val<\/span>, both getting by reference. beg and end limit the range on which the summation takes place. As mentioned, I use a std::lock_guard <\/span>(line 22) to protect the shared variable. Each thread line 41 – 44 does a quarter of the work. <\/p>\n
    Here are the numbers of the program.<\/p>\n
    <\/span>Without optimization<\/span><\/h3>\n
    \"synchronizeWithLock\"\"synchronizeWithLock<\/p>\n
    <\/span>Maximum optimization<\/span><\/h3>\n
    \"synchronizeWithLockOpt\"\"synchronizeWithLockOpt<\/p>\n
    The bottleneck of the program is the shared variable, which is expensively protected by a std::lock_guard. <\/span>Therefore the obvious solution is to replace the heavyweight lock with a lightweight atomic. <\/span><\/p>\n
    <\/span>Addition with an atomic<\/span><\/h2>\n
    The variable sum<\/span> is atomic. So I can skip the std::lock_guard<\/span> in the function sumUp<\/span> (lines 18 – 22). That was all.<\/p>\n
     <\/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\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40\r\n41\r\n42\r\n43\r\n44\r\n45\r\n46\r\n47\r\n48\r\n49\r\n50\r\n51\r\n52\r\n53\r\n54<\/pre>\n<\/td>\n
    		\n
    \/\/ synchronizationWithAtomic.cpp<\/span>\r\n\r\n#include <atomic><\/span>\r\n#include <chrono><\/span>\r\n#include <iostream><\/span>\r\n#include <random><\/span>\r\n#include <thread><\/span>\r\n#include <utility><\/span>\r\n#include <vector><\/span>\r\n\r\nconstexpr long<\/span> long<\/span> size= 100000000;   \r\n\r\nconstexpr long<\/span> long<\/span> firBound=  25000000;\r\nconstexpr long<\/span> long<\/span> secBound=  50000000;\r\nconstexpr long<\/span> long<\/span> thiBound=  75000000;\r\nconstexpr long<\/span> long<\/span> fouBound= 100000000;\r\n\r\nvoid<\/span> sumUp(std::atomic<unsigned<\/span> long<\/span> long<\/span>>& sum, const<\/span> std::vector<int<\/span>>& val, unsigned<\/span> long<\/span> long<\/span> beg, unsigned<\/span> long<\/span> long<\/span> end){\r\n    for<\/span> (auto<\/span> it= beg; it < end; ++it){\r\n        sum+= val[it];\r\n    }\r\n}\r\n\r\nint<\/span> main(){\r\n\r\n  std::cout << std::endl;\r\n\r\n  std::vector<int<\/span>> randValues;\r\n  randValues.reserve(size);\r\n\r\n  std::mt19937 engine;\r\n  std::uniform_int_distribution<> uniformDist(1,10);\r\n  for<\/span> ( long<\/span> long<\/span> i=0 ; i< size ; ++i) randValues.push_back(uniformDist(engine));\r\n \r\n  std::atomic<unsigned<\/span> long<\/span> long<\/span>> sum(0);\r\n  auto<\/span> start = std::chrono::system_clock::now();\r\n  \r\n  std::thread<\/span> t1(sumUp,std::ref(sum),std::ref(randValues),0,firBound);\r\n  std::thread<\/span> t2(sumUp,std::ref(sum),std::ref(randValues),firBound,secBound);\r\n  std::thread<\/span> t3(sumUp,std::ref(sum),std::ref(randValues),secBound,thiBound);\r\n  std::thread<\/span> t4(sumUp,std::ref(sum),std::ref(randValues),thiBound,fouBound);   \r\n  \r\n \r\n  t1.join();\r\n  t2.join();\r\n  t3.join();\r\n  t4.join();\r\n  std::chrono::duration<double<\/span>> dur= std::chrono::system_clock::now() - start;\r\n  std::cout << \"Time for addition \"<\/span> << dur.count() << \" seconds\"<\/span> << std::endl;\r\n  std::cout << \"Result: \"<\/span> << sum << std::endl;\r\n\r\n  std::cout << std::endl;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
     <\/p>\n
    <\/span>Without optimization<\/span><\/h3>\n
    \"synchronizeWithAtomic\"\"synchronizeWithAtomic<\/p>\n
    <\/span>Maximum optimization<\/span><\/h3>\n
    \"synchronizeWithAtomicOpt\"\"synchronizeWithAtomicOpt<\/p>\n
    <\/span>A strange phenomenon<\/span><\/h2>\n
    If you study the numbers carefully, you will notice a strange phenomenon on Windows. The maximum optimized program is slower than the non-optimized one. That observation will also hold for the next two variations. This puzzled me. I executed the program in addition to a virtualized Windows 8 PC with only one core. Here the optimized version was faster. Something strange is going on with my Windows 10 PC and atomics.<\/p>\n
    Besides +=, there is a further way to calculate the sum of an atomic with fetch_add. Let’s try it out. The numbers should be similar.<\/p>\n
     <\/p>\n
    <\/span>Addition with fetch_add<\/span><\/h2>\n
    The change in the source code is minimal. I have only to touch line 20.<\/p>\n
     <\/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\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40\r\n41\r\n42\r\n43\r\n44\r\n45\r\n46\r\n47\r\n48\r\n49\r\n50\r\n51\r\n52\r\n53\r\n54<\/pre>\n<\/td>\n
    		\n
    \/\/ synchronizationWithFetchAdd.cpp<\/span>\r\n\r\n#include <atomic><\/span>\r\n#include <chrono><\/span>\r\n#include <iostream><\/span>\r\n#include <random><\/span>\r\n#include <thread><\/span>\r\n#include <utility><\/span>\r\n#include <vector><\/span>\r\n\r\nconstexpr long<\/span> long<\/span> size= 100000000;   \r\n\r\nconstexpr long<\/span> long<\/span> firBound=  25000000;\r\nconstexpr long<\/span> long<\/span> secBound=  50000000;\r\nconstexpr long<\/span> long<\/span> thiBound=  75000000;\r\nconstexpr long<\/span> long<\/span> fouBound= 100000000;\r\n\r\nvoid<\/span> sumUp(std::atomic<unsigned<\/span> long<\/span> long<\/span>>& sum, const<\/span> std::vector<int<\/span>>& val, unsigned<\/span> long<\/span> long<\/span> beg, unsigned<\/span> long<\/span> long<\/span> end){\r\n    for<\/span> (auto<\/span> it= beg; it < end; ++it){\r\n\t\tsum.fetch_add(val[it]);\r\n    }\r\n}\r\n\r\nint<\/span> main(){\r\n\r\n  std::cout << std::endl;\r\n\r\n  std::vector<int<\/span>> randValues;\r\n  randValues.reserve(size);\r\n\r\n  std::mt19937 engine;\r\n  std::uniform_int_distribution<> uniformDist(1,10);\r\n  for<\/span> ( long<\/span> long<\/span> i=0 ; i< size ; ++i) randValues.push_back(uniformDist(engine));\r\n \r\n  std::atomic<unsigned<\/span> long<\/span> long<\/span>> sum(0);\r\n  auto<\/span> start = std::chrono::system_clock::now();\r\n  \r\n  std::thread<\/span> t1(sumUp,std::ref(sum),std::ref(randValues),0,firBound);\r\n  std::thread<\/span> t2(sumUp,std::ref(sum),std::ref(randValues),firBound,secBound);\r\n  std::thread<\/span> t3(sumUp,std::ref(sum),std::ref(randValues),secBound,thiBound);\r\n  std::thread<\/span> t4(sumUp,std::ref(sum),std::ref(randValues),thiBound,fouBound);   \r\n  \r\n \r\n  t1.join();\r\n  t2.join();\r\n  t3.join();\r\n  t4.join();\r\n  std::chrono::duration<double<\/span>> dur= std::chrono::system_clock::now() - start;\r\n  std::cout << \"Time for addition \"<\/span> << dur.count() << \" seconds\"<\/span> << std::endl;\r\n  std::cout << \"Result: \"<\/span> << sum << std::endl;\r\n\r\n  std::cout << std::endl;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
    <\/span> <\/span><\/h3>\n
    <\/span>Without optimization<\/span><\/h3>\n
    \"synchronizeWithFetchAdd\"\"synchronizeWithFetchAdd<\/strong><\/p>\n
    <\/span>Maximum optimization<\/span><\/h3>\n
    \"synchronizeWithFetchAddOpt\"\"synchronizeWithFetchAddOpt<\/p>\n
    Strictly speaking, is the fetch_add<\/span> variation no improvement to the += variation but the contrary? The += variation is more intuitive. But wait, there is a small difference.<\/p>\n
    <\/span>In addition, with fetch_add and relaxed semantic<\/span><\/h2>\n
    The default behavior for atomics is sequential consistency<\/a>. This statement is true for adding and assigning an atomic and, of course, for the fetch_add variant. But we can do better. Let’s adjust the memory model with the fetch variations<\/a>. That’s the final step in my optimization. You see it in line 20.<\/p>\n
     <\/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\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40\r\n41\r\n42\r\n43\r\n44\r\n45\r\n46\r\n47\r\n48\r\n49\r\n50\r\n51\r\n52\r\n53\r\n54<\/pre>\n<\/td>\n
    		\n
    \/\/ synchronizationWithFetchAddRelaxed.cpp<\/span>\r\n\r\n#include <atomic><\/span>\r\n#include <chrono><\/span>\r\n#include <iostream><\/span>\r\n#include <random><\/span>\r\n#include <thread><\/span>\r\n#include <utility><\/span>\r\n#include <vector><\/span>\r\n\r\nconstexpr long<\/span> long<\/span> size= 100000000;   \r\n\r\nconstexpr long<\/span> long<\/span> firBound=  25000000;\r\nconstexpr long<\/span> long<\/span> secBound=  50000000;\r\nconstexpr long<\/span> long<\/span> thiBound=  75000000;\r\nconstexpr long<\/span> long<\/span> fouBound= 100000000;\r\n\r\nvoid<\/span> sumUp(std::atomic<unsigned<\/span> long<\/span> long<\/span>>& sum, const<\/span> std::vector<int<\/span>>& val, unsigned<\/span> long<\/span> long<\/span> beg, unsigned<\/span> long<\/span> long<\/span> end){\r\n    for<\/span> (auto<\/span> it= beg; it < end; ++it){\r\n\t\tsum.fetch_add(val[it],std::memory_order_relaxed);\r\n    }\r\n}\r\n\r\nint<\/span> main(){\r\n\r\n  std::cout << std::endl;\r\n\r\n  std::vector<int<\/span>> randValues;\r\n  randValues.reserve(size);\r\n\r\n  std::mt19937 engine;\r\n  std::uniform_int_distribution<> uniformDist(1,10);\r\n  for<\/span> ( long<\/span> long<\/span> i=0 ; i< size ; ++i) randValues.push_back(uniformDist(engine));\r\n \r\n  std::atomic<unsigned<\/span> long<\/span> long<\/span>> sum(0);\r\n  auto<\/span> start = std::chrono::system_clock::now();\r\n  \r\n  std::thread<\/span> t1(sumUp,std::ref(sum),std::ref(randValues),0,firBound);\r\n  std::thread<\/span> t2(sumUp,std::ref(sum),std::ref(randValues),firBound,secBound);\r\n  std::thread<\/span> t3(sumUp,std::ref(sum),std::ref(randValues),secBound,thiBound);\r\n  std::thread<\/span> t4(sumUp,std::ref(sum),std::ref(randValues),thiBound,fouBound);   \r\n  \r\n \r\n  t1.join();\r\n  t2.join();\r\n  t3.join();\r\n  t4.join();\r\n  std::chrono::duration<double<\/span>> dur= std::chrono::system_clock::now() - start;\r\n  std::cout << \"Time for addition \"<\/span> << dur.count() << \" seconds\"<\/span> << std::endl;\r\n  std::cout << \"Result: \"<\/span> << sum << std::endl;\r\n\r\n  std::cout << std::endl;\r\n\r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
     <\/p>\n
    The question is. Why is it ok to use the relaxed-semantics<\/a> in line 20? Relaxed-semantics will not guarantee that one thread sees the operation in another in the same order. But this is not necessary. Necessary is only that each addition is atomically performed. <\/p>\n
    Does the optimization pay off?<\/p>\n
    <\/span>Without optimization<\/span><\/h3>\n
    \"synchronizeWithFetchAddRelaxed\"\"synchronizeWithFetchAddRelaxed<\/p>\n
    <\/span>Maximum optimization<\/span><\/h3>\n
    \"synchronizeWithFetchAddRelaxedOpt\"\"synchronizeWithFetchAddRelaxedOpt<\/p>\n
    As expected, for Linux and GCC is, the fetch_add<\/span> variant with relaxed-semantic the fastest one. I’m still puzzled with Windows.<\/p>\n
    In the end, all numbers are together in a table.<\/p>\n
    <\/span>The overview<\/span><\/h2>\n
    Although I have successively optimized the access to the shared variable and improved the performance accordingly, the results are not very promising. The addition in the single threaded <\/a>case with std::accumulate<\/span> is far faster. To say it precisely 40 times.<\/strong><\/p>\n
    \"MultithraedeSharedVariableEng\"<\/p>\n
    <\/span>What’s next?<\/span><\/h2>\n
    I will combine in the next post <\/a>the best of the two worlds. I combine the non-synchronized summation in one thread with the power of many threads. Let’s see if I beat the performance of the single thread variant of std::accumulate<\/span>.<\/p>\n
     <\/p>\n
     <\/p>\n<\/p>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    My goal is to sum up all elements of a vector. I used in the last post a single thread. In this post, I use multiple threads and, therefore, the full power of my PC. The addition will be done on a shared variable. What, at first glance, seems like a good idea is a […]<\/p>\n","protected":false},"author":21,"featured_media":4904,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[369],"tags":[470],"class_list":["post-4921","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-multithreading-application","tag-performance"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/4921","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=4921"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/4921\/revisions"}],"predecessor-version":[{"id":6950,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/4921\/revisions\/6950"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/4904"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=4921"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=4921"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=4921"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}