{"id":4903,"date":"2016-09-03T15:55:43","date_gmt":"2016-09-03T15:55:43","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/single-threaded-sum-of-the-elements-of-a-vector\/"},"modified":"2023-06-26T12:44:22","modified_gmt":"2023-06-26T12:44:22","slug":"single-threaded-sum-of-the-elements-of-a-vector","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/single-threaded-sum-of-the-elements-of-a-vector\/","title":{"rendered":"Single Threaded: Summation of a Vector"},"content":{"rendered":"

What is the fastest way to add the elements of a std::vector<\/span>? This a question that I will pursue in the following posts. I use the single-threaded addition as the reference number. In further posts, I discuss atomics, locks, and thread-local data.<\/p>\n

<\/p>\n

 <\/p>\n

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

My plan is to fill a std::vector with one hundred million arbitrary numbers between 1 and 10. I apply the uniform distribution to get the numbers. The task is to calculate the sum of all values. <\/p>\n

I usually use my Linux desktop and Windows laptop to get the numbers. The Linux PC has four, and my Windows PC has two cores. Here are details of my compilers: Thread-safe initialization of a singleton<\/a>. I will measure the performance with and without maximum optimization.<\/p>\n<\/p>\n

<\/span>A simple loop<\/span><\/h2>\n

The obvious strategy is to add the numbers in a range-based for loop.<\/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<\/pre>\n<\/td>\n
\n
\/\/ calculateWithLoop.cpp<\/span>\r\n\r\n#include <chrono><\/span>\r\n#include <iostream><\/span>\r\n#include <random><\/span>\r\n#include <vector><\/span>\r\n\r\nconstexpr long<\/span> long<\/span> size= 100000000;\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  \/\/ random values<\/span>\r\n  std::random_device seed;\r\n  std::mt19937 engine(seed());\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  auto<\/span> start = std::chrono::system_clock::now();\r\n  \r\n  unsigned<\/span> long<\/span> long<\/span> add= {};\r\n  for<\/span> (auto<\/span> n: randValues) add+= n;\r\n \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> << add << 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 calculation takes place in line 26. How fast are my computers? <\/p>\n
<\/span>Without optimization<\/span><\/h3>\n
 \"CalculateWithLoop\"\"CalculateWithLoop<\/p>\n
<\/span>Maximum optimization<\/span><\/h3>\n
 \"CalculateWithLoopOpt\"\"CalculateWithLoopOpt<\/p>\n
You should not use explicit loops. A rule which, in particular, holds for Windows. That’s simple therefore, I have to look in the Standard Template Library (STL). <\/p>\n
<\/span>The STL with std::accumulate<\/span><\/h2>\n
std::accumulate<\/span> is the standard way to calculate the sum.<\/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<\/pre>\n<\/td>\n
\n
\/\/ calculateWithStd.cpp<\/span>\r\n\r\n#include <algorithm><\/span>\r\n#include <chrono><\/span>\r\n#include <iostream><\/span>\r\n#include <numeric><\/span>\r\n#include <random><\/span>\r\n#include <vector><\/span>\r\n\r\nconstexpr long<\/span> long<\/span> size= 100000000;\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  \/\/ random values<\/span>\r\n  std::random_device seed;\r\n  std::mt19937 engine(seed());\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  auto<\/span> start = std::chrono::system_clock::now();\r\n  \r\n  unsigned<\/span> long<\/span> long<\/span> add= std::accumulate(randValues.begin(),randValues.end(),0);\r\n \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> << add << 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 key lines are line 27. The performance of std::acummulate<\/span> corresponds to the performance of the range-based for loop. But not for Windows.<\/p>\n
<\/span>Without optimization<\/span><\/h3>\n
<\/span> \"CalculateWithStd\"\"CalculateWithStd<\/span><\/h3>\n
<\/span>Maximum optimization<\/span><\/h3>\n
 \"CalculateWithStdOpt\"\"CalculateWithStdOpt<\/p>\n
That was all. I have my numbers to compare the single-threaded with the multithreading program. Really? I’m very curious about protecting the summation with a lock or using an atomic. So we get the overhead of protection.<\/p>\n
<\/span>Protection by a lock<\/span><\/h2>\n
If I protect the access to the summation variable with a lock, I get the answers to my two questions.<\/span><\/p>\n
    \n
  1. How expensive is the synchronization of a lock?<\/li>\n
  2. How fast can a lock be if no concurrent access to a variable takes place?<\/li>\n<\/ol>\n
    Of course, I can rephrase point 2. If more the one thread accesses the shared variable, the access time decreases.<\/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<\/pre>\n<\/td>\n
    		\n
    \/\/ calculateWithLock.cpp<\/span>\r\n\r\n#include <chrono><\/span>\r\n#include <iostream><\/span>\r\n#include <mutex><\/span>\r\n#include <numeric><\/span>\r\n#include <random><\/span>\r\n#include <vector><\/span>\r\n\r\nconstexpr long<\/span> long<\/span> size= 100000000;\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  \/\/ random values<\/span>\r\n  std::random_device seed;\r\n  std::mt19937 engine(seed());\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::mutex myMutex;\r\n \r\n  unsigned<\/span> long<\/span> long<\/span> int<\/span> add= 0;\r\n  auto<\/span> start = std::chrono::system_clock::now();\r\n  \r\n  for<\/span> (auto<\/span> i: randValues){\r\n      std::lock_guard<std::mutex> myLockGuard(myMutex);\r\n      add+= i;\r\n  }\r\n \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> << add << 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
    That’s the result I assumed. The access on the protected variable add<\/span> is slower.<\/p>\n
    <\/p>\n
     <\/p>\n
    <\/span>Without optimization<\/span><\/h3>\n
    \"CalculateWithLock\"\"CalculateWithLock<\/p>\n
    <\/span>Maximum optimization<\/span><\/h3>\n
    \"CalculateWithLockOpt\"\"CalculateWithLockOpt<\/p>\n
    The non-optimized version with the lock is 4 – 12 times slower than the maximum optimized. The maximum optimized about 10 – 40 times slower than std::accumulate.<\/span><\/p>\n
    Finally atomics.<\/p>\n
    <\/span>Protection by an atomic<\/span><\/h2>\n
    The same question for locks holds also for atomics.<\/p>\n
      \n
    1. How expensive is the synchronization of a lock?<\/li>\n
    2. How fast can a lock be if no concurrent access to a variable takes place?<\/li>\n<\/ol>\n
      But there is an additional question. What is the performance difference between an atomic and 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<\/pre>\n<\/td>\n
      		\n
      \/\/ calculateWithAtomic.cpp<\/span>\r\n\r\n#include <atomic><\/span>\r\n#include <chrono><\/span>\r\n#include <iostream><\/span>\r\n#include <numeric><\/span>\r\n#include <random><\/span>\r\n#include <vector><\/span>\r\n\r\nconstexpr long<\/span> long<\/span> size= 100000000;\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  \/\/ random values<\/span>\r\n  std::random_device seed;\r\n  std::mt19937 engine(seed());\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>> add={};\r\n  std::cout << std::boolalpha << \"add.is_lock_free(): \"<\/span> << add.is_lock_free() << std::endl;\r\n  std::cout << std::endl;\r\n \r\n  auto<\/span> start = std::chrono::system_clock::now();\r\n  \r\n  for<\/span> (auto<\/span> i: randValues) add+= i;\r\n \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> << add << std::endl;\r\n    \r\n  std::cout << std::endl;\r\n  \r\n  add=0;\r\n  start = std::chrono::system_clock::now();\r\n  \r\n  for<\/span> (auto<\/span> i: randValues) add.fetch_add(i,std::memory_order_relaxed);\r\n  \r\n  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> << add << 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 special. First, I ask in line 26 if the atomic has a lock. That is crucial because otherwise, there is no difference between using locks and atomics. On all mainstream platforms, I knew atomics use no lock. Second I calculate the sum in two ways. I use in line 31 the += operator; in line 42, the method fetch_add<\/span>. Both variants have, in the single-threaded case, a comparable performance, but I can explicitly specify in the case of fetch_add<\/span> the memory model. More about that point in the next post.<\/p>\n
       <\/p>\n
      But now the numbers.<\/p>\n
      <\/span>Without optimization<\/span><\/h3>\n
       \"CalculateWithAtomic\"\"CalculateWithAtomic<\/p>\n
      <\/span>Maximum optimization<\/span><\/h3>\n
      \"CalculateWithAtomicOpt\"\"CalculateWithAtomicOpt<\/p>\n
      In the case of Linux, the atomics are 1.5 times slower, and in the case of windows eight times slower than the std::accumulate<\/span> algorithm. That changes even more in the case of optimization. Now Linux is 15 times; Windows is 50 times faster.<\/p>\n
      I want to stress two points.<\/p>\n
        \n
      1. Atomics are 2 – 3 times faster on Linux and Windows than locks.<\/li>\n
      2. Linux is, in particular, for atomics two times faster than Windows.<\/li>\n<\/ol>\n
        <\/span>All numbers compact<\/span><\/h2>\n
        How lost the orientation because of the number? Here is the overview in seconds.<\/p>\n
        \"SingleThreadedAdditionEng\"<\/p>\n
        <\/span>What’s next?<\/span><\/h2>\n
        Single-threaded becomes multithreaded in the next post<\/a>. In the first step, the summation variable add becomes a shared variable used by four threads. In the second step, add<\/span> will be atomic.<\/p>\n
         <\/p>\n
         <\/p>\n
         <\/p>\n
         <\/p>\n
         <\/p>\n
         <\/p>\n","protected":false},"excerpt":{"rendered":"
        What is the fastest way to add the elements of a std::vector? This a question that I will pursue in the following posts. I use the single-threaded addition as the reference number. In further posts, I discuss atomics, locks, and thread-local data.<\/p>\n","protected":false},"author":21,"featured_media":4886,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[369],"tags":[434,430,470],"class_list":["post-4903","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-multithreading-application","tag-atomics","tag-lock","tag-performance"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/4903","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=4903"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/4903\/revisions"}],"predecessor-version":[{"id":6951,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/4903\/revisions\/6951"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/4886"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=4903"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=4903"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=4903"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}