3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Simon Forsberg Jun 2 '18 at 8:57
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$
#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.

\$\endgroup\$
  • \$\begingroup\$ It's okay to write out your answer and then post it. You don't get bonus points for answering as fast as possible. \$\endgroup\$ – yuri Jun 1 '18 at 20:51
  • \$\begingroup\$ Can you please explain me this no code-movement barrier, your benchmark might not be accurate? What does it mean code-movement barrier? \$\endgroup\$ – NutCracker Jun 2 '18 at 7:13
  • \$\begingroup\$ The compiler re-orders instructions. It can and does even mix up what’s done before/after/during a function call! Looking at that, I thought it might start preping the output formatting before it stops the clock. In Microsoft’s compiler, for example, there are intrinsics ReadWriteBarrier etc. that prevent code movement across that boundary. Using a standard sync mechanism with release (before) and acquire (coming out) should also prevent movement of code that reads and writes variables, though that doesn’t prevent all code movement in principle. \$\endgroup\$ – JDługosz Jun 2 '18 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.