Parallel summation of the array is slower than the sequential one in C++

user_3622286 0
Viewed 962

I write the code for parallel summation of the array with C++ std::thread. But parallel sum takes 0.6s and sequential sum takes 0.3s.

I don't think that this code does any synchronization on arr or ret.

Why this situation happening?

My CPU is i7-8700 which has 6 physical cores.

#include <stdio.h>
#include <ctime>
#include <thread>

// Constants
#define THREADS 4
#define ARR_SIZE 200000000
int ret[THREADS];

// Function for thread.
void parallel_sum(int *arr, int thread_id) {
    int s = ARR_SIZE / THREADS * thread_id, e = ARR_SIZE / THREADS * (thread_id + 1);
    printf("%d, %d\n", s, e);
    for (int i = s; i < e; i++) ret[thread_id] += arr[i];
}

int main() {

    // Variable definitions
    int *arr = new int[ARR_SIZE]; // 1 billion

    time_t t1, t2; // Variable for time consuming checking
    std::thread *threads = new std::thread[THREADS];

    // Initialization
    for (int i = 0; i < ARR_SIZE; i++) arr[i] = 1;
    for (int i = 0; i < THREADS; i++) ret[i] = 0;
    long long int sum = 0;

    // Parallel sum start
    t1 = clock();
    for (int i = 0; i < THREADS; i++) threads[i] = std::thread(parallel_sum, arr, i);
    for (int i = 0; i < THREADS; i++) threads[i].join();
    t2 = clock();

    for (int i = 0; i < THREADS; i++) sum += ret[i];
    printf("[%lf] Parallel sum %lld \n", (float)(t2 - t1) / (float)CLOCKS_PER_SEC, sum);
    // Parallel sum end


    sum = 0; // Initialization


    // Sequential sum start
    t1 = clock();
    for (int i = 0; i < ARR_SIZE; i++) sum += arr[i];
    t2 = clock();

    printf("[%lf] Sequential sum %lld \n", (float)(t2 - t1) / (float)CLOCKS_PER_SEC, sum);
    // Sequential sum end


    return 0;
}
parallel-processing multithreading c++
2 Answers
for (int i = s; i < e; i++) ret[thread_id] += arr[i];

This causes a lot of cache contention since the elements of ret array likely share the same cache line. It is generally referred to as false sharing.

A simple workaround is to use an auxiliary (thread-)local variable for loop updates and just finally increment the shared counter, such as:

int temp = 0;
for (int i = s; i < e; i++) temp += arr[i];
ret[thread_id] += temp;

Or, better to use a single global ret of type std::atomic<int> for multi-threaded sum. Then, you can simply write:

int temp = 0;
for (int i = s; i < e; i++) temp += arr[i];
ret += temp;

Or, even more-efficiently:

ret.fetch_add(temp, std::memory_order_relaxed);
user_5800830

With compiler optimizations enabled (no point in benchmarking any other way), I get the following results:

[0.093481] Parallel sum 200000000
[0.073333] Sequential sum 200000000

Note that we've logged the total CPU consumption in both cases. It's not surprising that the parallel sum uses a bit more total CPU since it has to start threads and aggregate results. The parallel version uses more CPU time because it has more work to do.

You don't log the wall time, but it's likely that because four cores contributed to doing that work, the wall time was probably less in the parallel case. Adding code to log the elapsed wall time revealed that the parallel version used roughly half the wall time of the serial version. At least, on my machine with reasonable compiler optimization settings.

user_7212690
Related