Single Threaded: Summation of a Vector

3 September 2016

Contents[Show]

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.

My strategy

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.

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. I will measure the performance with and without maximum optimization.

Modernes C++ Mentoring

Be part of my mentoring programs:

- - - - "Fundamentals for C++ Professionals" (open)
- - - - "Design Patterns and Architectural Patterns with C++" (open)
        
        "C++20: Get the Details" (July 2023)

Do you want to stay informed about my mentoring programs: Subscribe via E-Mail.

A simple loop

The obvious strategy is to add the numbers in a range-based for loop.

// calculateWithLoop.cpp

#include <chrono>
#include <iostream>
#include <random>
#include <vector>

constexpr long long size= 100000000;

int main(){

  std::cout << std::endl;

  std::vector<int> randValues;
  randValues.reserve(size);

  // random values
  std::random_device seed;
  std::mt19937 engine(seed());
  std::uniform_int_distribution<> uniformDist(1,10);
  for ( long long i=0 ; i< size ; ++i) randValues.push_back(uniformDist(engine));
 
  auto start = std::chrono::system_clock::now();
  
  unsigned long long add= {};
  for (auto n: randValues) add+= n;
 
  std::chrono::duration<double> dur= std::chrono::system_clock::now() - start;
  std::cout << "Time for addition " << dur.count() << " seconds" << std::endl;
  std::cout << "Result: " << add << std::endl;

  std::cout << std::endl;

}

The calculation takes place in line 26. How fast are my computers?

Without optimization

CalculateWithLoop CalculateWithLoop win

Maximum optimization

CalculateWithLoopOpt CalculateWithLoopOpt win

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).

The STL with std::accumulate

std::accumulate is the standard way to calculate the sum.

// calculateWithStd.cpp

#include <algorithm>
#include <chrono>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

constexpr long long size= 100000000;

int main(){

  std::cout << std::endl;

  std::vector<int> randValues;
  randValues.reserve(size);

  // random values
  std::random_device seed;
  std::mt19937 engine(seed());
  std::uniform_int_distribution<> uniformDist(1,10);
  for ( long long i=0 ; i< size ; ++i) randValues.push_back(uniformDist(engine));
 
  auto start = std::chrono::system_clock::now();
  
  unsigned long long add= std::accumulate(randValues.begin(),randValues.end(),0);
 
  std::chrono::duration<double> dur= std::chrono::system_clock::now() - start;
  std::cout << "Time for addition " << dur.count() << " seconds" << std::endl;
  std::cout << "Result: " << add << std::endl;

  std::cout << std::endl;

}

The key lines are line 27. The performance of std::acummulate corresponds to the performance of the range-based for loop. But not for Windows.

Without optimization

Maximum optimization

CalculateWithStdOpt CalculateWithStdOpt win

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.

Protection by a lock

If I protect the access to the summation variable with a lock, I get the answers to my two questions.

How expensive is the synchronization of a lock?
How fast can a lock be if no concurrent access to a variable takes place?

Of course, I can rephrase point 2. If more the one thread accesses the shared variable, the access time decreases.

// calculateWithLock.cpp

#include <chrono>
#include <iostream>
#include <mutex>
#include <numeric>
#include <random>
#include <vector>

constexpr long long size= 100000000;

int main(){

  std::cout << std::endl;

  std::vector<int> randValues;
  randValues.reserve(size);

  // random values
  std::random_device seed;
  std::mt19937 engine(seed());
  std::uniform_int_distribution<> uniformDist(1,10);
  for ( long long i=0 ; i< size ; ++i) randValues.push_back(uniformDist(engine));

  std::mutex myMutex;
 
  unsigned long long int add= 0;
  auto start = std::chrono::system_clock::now();
  
  for (auto i: randValues){
      std::lock_guard<std::mutex> myLockGuard(myMutex);
      add+= i;
  }
 
  std::chrono::duration<double> dur= std::chrono::system_clock::now() - start;
  std::cout << "Time for addition " << dur.count() << " seconds" << std::endl;
  std::cout << "Result: " << add << std::endl;
    
  std::cout << std::endl;

}

That's the result I assumed. The access on the protected variable add is slower.

Without optimization

CalculateWithLock CalculateWithLock win

Maximum optimization

CalculateWithLockOpt CalculateWithLockOpt win

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.

Finally atomics.

Protection by an atomic

The same question for locks holds also for atomics.

How expensive is the synchronization of a lock?
How fast can a lock be if no concurrent access to a variable takes place?

But there is an additional question. What is the performance difference between an atomic and a lock?

// calculateWithAtomic.cpp

#include <atomic>
#include <chrono>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

constexpr long long size= 100000000;

int main(){

  std::cout << std::endl;

  std::vector<int> randValues;
  randValues.reserve(size);

  // random values
  std::random_device seed;
  std::mt19937 engine(seed());
  std::uniform_int_distribution<> uniformDist(1,10);
  for ( long long i=0 ; i< size ; ++i) randValues.push_back(uniformDist(engine));
  
  std::atomic<unsigned long long> add={};
  std::cout << std::boolalpha << "add.is_lock_free(): " << add.is_lock_free() << std::endl;
  std::cout << std::endl;
 
  auto start = std::chrono::system_clock::now();
  
  for (auto i: randValues) add+= i;
 
  std::chrono::duration<double> dur= std::chrono::system_clock::now() - start;
  std::cout << "Time for addition " << dur.count() << " seconds" << std::endl;
  std::cout << "Result: " << add << std::endl;
    
  std::cout << std::endl;
  
  add=0;
  start = std::chrono::system_clock::now();
  
  for (auto i: randValues) add.fetch_add(i,std::memory_order_relaxed);
  
  dur= std::chrono::system_clock::now() - start;
  std::cout << "Time for addition " << dur.count() << " seconds" << std::endl;
  std::cout << "Result: " << add << std::endl;
    
  std::cout << std::endl;

}

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. Both variants have, in the single-threaded case, a comparable performance, but I can explicitly specify in the case of fetch_add the memory model. More about that point in the next post.

But now the numbers.

Without optimization

CalculateWithAtomic CalculateWithAtomic win

Maximum optimization

CalculateWithAtomicOpt CalculateWithAtomicOpt win

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 algorithm. That changes even more in the case of optimization. Now Linux is 15 times; Windows is 50 times faster.

I want to stress two points.

Atomics are 2 - 3 times faster on Linux and Windows than locks.
Linux is, in particular, for atomics two times faster than Windows.

All numbers compact

How lost the orientation because of the number? Here is the overview in seconds.

SingleThreadedAdditionEng

What's next?

Single-threaded becomes multithreaded in the next post. In the first step, the summation variable add becomes a shared variable used by four threads. In the second step, add will be atomic.

Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Animus24, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, and Rob North.

Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, and Slavko Radman.

My special thanks to Embarcadero

My special thanks to PVS-Studio

My special thanks to Tipi.build

My special thanks to Take Up Code

Seminars

I'm happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

Bookable (Online)

German

Clean Code: Best Practices für modernes C++: 20.06.2023 - 22.06.2023 (Präsenzschulung, Termingarantie)
Design Pattern und Architekturpattern mit C++: 22.08.2023 - 24.08.2023 (Präsenzschulung)
Embedded Programmierung mit modernem C++ 12.12.2023 - 14.12.2023 (Präsenzschulung)

Standard Seminars (English/German)

Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

C++ - The Core Language
C++ - The Standard Library
C++ - Compact
C++11 and C++14
Concurrency with Modern C++
Design Pattern and Architectural Pattern with C++
Embedded Programming with Modern C++
Generic Programming (Templates) with C++

New

Clean Code with Modern C++
C++20

Contact Me

Phone: +49 7472 917441
Mobil:: +49 176 5506 5086
Mail: This email address is being protected from spambots. You need JavaScript enabled to view it.
German Seminar Page: www.ModernesCpp.de
Mentoring Page: www.ModernesCpp.org

Modernes C++,

RainerGrimmDunkelBlauSmall

Tags: Atomics, lock, Performance

Comments

0 #1 Alexey Nikitin 2016-09-09 19:43

Using the sum of type int in calculateWithStd.cpp leads to incorrect measurement results. In my opinion it's better to use std::accumulate(randValues.begin(), randValues.end(), 0ULL)

Quote

0 #2 Rainer Grimm 2016-09-10 14:51

Quoting Alexey Nikitin:

Using the sum of type int in calculateWithStd.cpp leads to incorrect measurement results. In my opinion it's better to use std::accumulate(randValues.begin(), randValues.end(), 0ULL)

On my platform int is big enough, but in general you are right.

std::numeric_limits<int>::max() : 2147483647
std::numeric_limits<unsigned long long>::max(): 18446744073709551615

So my int can hold about 2 billions and my sum is about 1/2 a billion.

Quote

0 #3 Jaroslaw 2016-09-19 19:08

Quoting Alexey Nikitin:

The atomics are in the case of Linux 1.5 times faster, in the case of windows 8 times faster than the std::accumulate algorithm. That changes even more in the case of optimization. Now Linux is 15 times, Windows is 50 times faster.

Did you mean "atomics are 1.5 time slower"?

Quote

0 #4 Rainer Grimm 2016-09-20 06:49

Quoting Jaroslaw:

Quoting Alexey Nikitin:
The atomics are in the case of Linux 1.5 times faster, in the case of windows 8 times faster than the std::accumulate algorithm. That changes even more in the case of optimization. Now Linux is 15 times, Windows is 50 times faster.

Did you mean "atomics are 1.5 time slower"?

Thanks. Of course you are right. I fix it.

Quote

0 #5 SEO 2016-09-27 10:27

I like the valuable info you provide in your articles.

I will bookmark your blog and check again here frequently.
I am quite certain I will learn plenty of new stuff right here!

Good luck for the next!

Quote

0 #6 Mel 2016-11-11 20:21

Had a lot of hassle researching posts about business casual outfits with leggings,
glad I came across this...incredibly helpful
Single threaded: Summation of a vector - The newest addition to my RSS feed

Quote

0 #7 Carmine 2018-07-20 21:30

Thank you for sharing your info. I truly appreciate your
efforts and I will be waiting for your further write
ups thank you once again.