Sequential and parallel addition of 2 vectors

Question

I have done sequential and parallel addition of 2 vectors that I have filled with some dummy values. I am also measuring the time of execution for both, sequential and parallel execution.

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <functional>
#include <chrono>
#include <cassert>
#include <thread>

#define NUM_OF_THREADS 8
#define VECTOR_SIZE    512

using time_point = std::chrono::high_resolution_clock::time_point;

template<typename T>
std::vector<T> operator+(std::vector<T> const& first, std::vector<T> const& second)
{
    assert(first.size() == second.size());

    std::vector<T> result;
    result.reserve(first.size());

    std::transform(first.begin(), first.end(), second.begin(), std::back_inserter(result), std::plus<T>());
    return result;
}

template<typename T>
void parallel_addition(std::vector<T>& result,
                       std::vector<T> const& first,
                       std::vector<T> const& second,
                       size_t lower_bound,
                       size_t upper_bound)
{
    for (size_t i = lower_bound; i < upper_bound; i++)
    {
        result[i] = first[i] + second[i];
    }
}

int main(int argc, char *argv[])
{
    std::vector<int> first_vec, second_vec;

    /* Filling up the vectors with dummy values */
    for (int i = 1; i <= VECTOR_SIZE; i++)
    {
        first_vec.push_back(i);
        second_vec.push_back(i);
    }

    /* Sequential addition of vectors */
    time_point t1_seq = std::chrono::high_resolution_clock::now();
    std::vector<int> sequential_result = first_vec + second_vec;
    time_point t2_seq = std::chrono::high_resolution_clock::now();
    auto duration_seq = std::chrono::duration_cast<std::chrono::microseconds>(t2_seq - t1_seq).count();
    std::cout << "Sequential addition of vectors - execution time: " << duration_seq << "us" << std::endl;

    /* Parallel addition of vectors */
    std::vector<std::thread> threads;
    std::vector<int> parallel_result(VECTOR_SIZE);

    time_point t1_par = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < NUM_OF_THREADS; i++)
    {
        threads.push_back(std::thread(parallel_addition<int>,
                                      std::ref(parallel_result),
                                      first_vec,
                                      second_vec,
                                      i * (VECTOR_SIZE / NUM_OF_THREADS),
                                      (i + 1) * (VECTOR_SIZE / NUM_OF_THREADS)));
    }

    for (auto &thread : threads)
    {
        thread.join();
    }

    time_point t2_par = std::chrono::high_resolution_clock::now();
    auto duration_par = std::chrono::duration_cast<std::chrono::microseconds>(t2_par - t1_par).count();
    std::cout << "Parallel (" << NUM_OF_THREADS << " threads) addition of vectors - execution time: " << duration_par << "us" << std::endl;

    return 0;
}

Despite style review, can you also tell me if there is another, better, approach to addition of two vectors in multiple threads? My intention was to write in C++17.

Answer 1

Most of the points are already mentioned by others, thus I will only tell you my opinion about the missing ones.

I don't really like your parallel_addition function. You obviously know how to use std algorithms, why don't you simply use them for your purpose? It all boils down to something like that:

auto range = std::size(first_vec) / NUM_OF_THREADS;
for (int i = 0; i < NUM_OF_THREADS; i++)
{
    auto start = i * range;
    auto firstBegin = std::begin(first_vec) + start;
    auto secondBegin = std::begin(second_vec) + start;
    auto resultBegin = std::begin(parallel_result) + start;

    auto firstEnd = firstBegin + range;
    threads.emplace_back(
        [firstBegin, firstEnd, secondBegin, resultBegin]()
        {
            std::transform(firstBegin, firstEnd, secondBegin, resultBegin, std::plus<int>());
        }
    );
}

Be aware of the fact, that you have to take care for the cases, where your vector size isn't a multiplication of thread count. There will be some elements left untouched, but I let this job as a task for you ;)

vector::emplace_back

I prefer emplace_back over push_back, because it enables the possibility to create the objects inside the vector in place instead of copying.

use the parallel std algorithms

In the end you could simply use the std::transform overloading for ExecutionPolicies rather than writing the stuff yourself on the base of threads. Have a look here.

Answer 2

#define NUM_OF_THREADS 8
#define VECTOR_SIZE    512

Don't use #define for constants or "functions" (⧺ES.31)

---

using time_point = std::chrono::high_resolution_clock::time_point;

Good! bring down just the stuff you need, and give it a friendly name. I think

using std::chrono::high_resolution_clock::time_point;

would be the same thing, and is the usual way of importing symbols from a library’s namespace.

---

assert(first.size() == second.size());

That will not do anything in a release build, you know.

If you really want checking, make a precondition that always works. The GSL support library has Expects that can be programmed at compile time to assert, throw, or die.

---

In general operator+ looks good! You are using a value return, and you ensure NVRO takes place. You reserve the vector size. You use STL algorithms.

---

for (int i = 1; i <= VECTOR_SIZE; i++)
{
    first_vec.push_back(i);
    second_vec.push_back(i);
}

There is a standard algorithm for that.

---

time_point t1_seq = std::chrono::high_resolution_clock::now();
⋮

Use auto (almost everywhere).

since there is no code-movement barrier, your benchmark might not be accurate.

---

for (auto &thread : threads)

Good! You use the range-for where you can.