{"id":4944,"date":"2016-09-11T08:53:37","date_gmt":"2016-09-11T08:53:37","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/my-conclusion-summation-of-a-vector-in-three-variants\/"},"modified":"2023-06-26T12:43:18","modified_gmt":"2023-06-26T12:43:18","slug":"my-conclusion-summation-of-a-vector-in-three-variants","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/my-conclusion-summation-of-a-vector-in-three-variants\/","title":{"rendered":"My Conclusion: Summation of a Vector in three Variants"},"content":{"rendered":"

After I’ve calculated in three different ways the sum of a std::vector<\/span> I want to draw my conclusions.<\/p>\n

<\/p>\n

 <\/p>\n

<\/span>The three strategies<\/span><\/h2>\n

At first, all numbers are in an overview. First, the single-threaded <\/a>variant; second, the multiple threads with a shared summation variable<\/a>; last, the multiple threads with minimal synchronization<\/a>. I have to admit that I was astonished by the last variant.<\/p>\n

<\/span><\/span>Single-threaded (1)<\/a><\/span><\/span><\/h3>\n

\"SingleThreadedAdditionEng\"<\/p>\n

<\/span><\/span>Multiple threads with a shared summation variable (2)<\/a><\/span><\/span><\/h3>\n

\"MultithraedeSharedVariableEng\"<\/p>\n

<\/span><\/span>Multiple threads with minimal synchronization (3)<\/a><\/span><\/span><\/h3>\n

\"MultipleThreadsEng\"<\/p>\n

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

For simplicity reasons, I will only reason about Linux. Thanks to Andreas Sch\u00e4fer (https:\/\/plus.google.com\/u\/0\/+AndreasSch%C3%A4fer_gentryx<\/a>), who gave me more profound insight. <\/p>\n<\/p>\n

<\/span>Single threaded<\/span><\/h3>\n

The range-based for-loop and the STL algorithm std::accumulate are in the same league. This observation holds for the maximal optimized and non-optimized programs. Interestingly, the maximally optimized version is about 30 times faster than the non-optimized version. The compiler uses for the summation in case of the optimized version vectorized instruction (SSE or AVX). Therefore, the loop counter will be increased by 2 (SSE<\/a>) or 4 (AVC).<\/p>\n

<\/span>Multiple threads with a shared summation variable<\/span><\/h3>\n

The synchronization on each access to the shared variable (2)<\/strong><\/span> shows on point: Synchronization is expensive. Although I break the sequential consistency with the relaxed semantics, the program is about 40 times slower than the pendants (1)<\/strong> <\/span>or (3). <\/strong>Not only out of performance reasons, but our goal must also be to minimize the synchronization of the shared variable.<\/span><\/span><\/p>\n

<\/span>Multiple threads with minimal synchronization<\/span><\/h3>\n

The summation with minimal synchronized threads (4 atomic operations or locks) (3)<\/strong><\/span> is hardly faster than the range-based for-loop or std::accumulate (1)<\/strong><\/span><\/span>. However, that holds in the multithreading variant, where four threads can work independently on four cores. That surprised me because I was expecting a nearly fourfold improvement. But what surprised me, even more was that my four cores were not fully utilized.<\/p>\n

 <\/p>\n

\"threadUtilization\"<\/p>\n

 <\/p>\n

The reason is simple. The cores can’t get the data fast enough from memory. Or to say it the other way around. The memory slows down the cores.<\/p>\n

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

My conclusion from the performance measurements is to use for such a simple operation std::accumulate. That’s for two reasons. First, the performance boost<\/em> of variant (3) <\/span><\/strong>doesn’t justify the expense; second, C++ will have in C++17 a parallel version of std::accumulate. <\/span>Therefore, switching from the sequential to the parallel version is very easy.  <\/span> <\/span> <\/span><\/span><\/p>\n

<\/span>What’s next?<\/span><\/h2>\n

The time library does not belong to the multithreading library, but it’s an essential component of the multithreading capabilities of C++. For example, you have to wait for an absolute time for a lock or put your thread for a relative time to sleep. So in the next post, <\/a>I will write about time.<\/p>\n

 <\/p>\n

. <\/p>\n

 <\/p>\n

 <\/p>\n<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

After I’ve calculated in three different ways the sum of a std::vector I want to draw my conclusions.<\/p>\n","protected":false},"author":21,"featured_media":4902,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[369],"tags":[434,470,504,519],"class_list":["post-4944","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-multithreading-application","tag-atomics","tag-performance","tag-relaxed-semantics","tag-sequential-consistency"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/4944","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=4944"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/4944\/revisions"}],"predecessor-version":[{"id":6948,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/4944\/revisions\/6948"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/4902"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=4944"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=4944"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=4944"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}