数组的并行求和比C++中的序列求和要慢

Question

我用C++ std :: thread编写了数组并行求和的代码.但平行和需要0.6s,顺序总和需要0.3s.

我不认为这个代码在arr或上进行任何同步ret.

为什么会出现这种情况？

我的CPU是i7-8700,有6个物理内核.

#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;
}

Answer 1

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

这会导致大量的缓存争用,因为ret阵列的元素可能共享相同的缓存行.它通常被称为虚假共享.

一个简单的解决方法是使用辅助(线程)局部变量进行循环更新,最后增加共享计数器,例如:

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

或者,最好使用单个全局ret类型std::atomic<int>进行多线程求和.然后,你可以简单地写:

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

或者,更有效率:

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