多线程查找数组最大值性能提升不明显问题咨询

我正在学习多线程算法，因此实现了一个简单的数组最大值查找功能。我首先编写了基线程序findMax1.c：从文件中加载约2.63亿个int类型整数到内存，之后通过单层for循环遍历查找最大值。随后我又编写了使用4线程的版本findMax2.c，选择4线程是因为我使用的Intel i5 4460 CPU为4核设计，每个核心仅支持1个线程，我猜测将数组拆分为4个块分别分配给不同核心处理，可减少缓存失效次数，运行效率更高。具体实现逻辑为每个线程计算对应块的最大值，待所有线程执行完毕后，再从各块的最大值中计算全局最大值。

基线程序findMax1.c完成查找任务耗时约660ms，我最初预计4线程版本findMax2.c耗时约为165ms（660ms/4），但实际运行findMax2.c耗时约610ms，仅比单线程版本快50ms。请问我忽略了哪些影响因素？多线程程序的实现是否存在问题？

参考代码 #

findMax1.c #

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

int main(void)
{
    int i, *array, max = 0, position;
    size_t array_size_in_bytes = 1024*1024*1024, elements_read, array_size;
    FILE *f;
    clock_t t;
    double time;

    array = (int*) malloc(array_size_in_bytes);
    assert(array != NULL); // assert if condition is falsa 

    printf("Loading array...");

    t = clock();
    f = fopen("numbers.bin", "rb");
    assert(f != NULL);

    elements_read = fread(array, array_size_in_bytes, 1, f);
    t = clock() - t;
    time = ((double) t) / CLOCKS_PER_SEC;
    assert(elements_read == 1);

    printf("done!\n");
    printf("File load time: %f [s]\n", time);

    fclose(f);

    array_size = array_size_in_bytes / sizeof(int);

    printf("Finding max...");

    t = clock();

    for(i = 0; i < array_size; i++)
        if(array[i] > max)
        {
            max = array[i];
            position = i;
        }

    t = clock() - t;
    time = ((double) t) / CLOCKS_PER_SEC;

    printf("done!\n");
    printf("----------- Program results -------------\nMax number: %d position %d\n", max, position);
    printf("Time %f [s]\n", time);

    return 0;
}

findMax2.c #

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>
#include <sched.h>

#define NUM_THREADS 4

int max_chunk[NUM_THREADS], pos_chunk[NUM_THREADS];
int *array;
pthread_t tid[NUM_THREADS];

void *thread(void *arg)
{
    size_t array_size_in_bytes = 1024*1024*1024;
    int i, rc, offset, chunk_size, array_size, *core_id = (int*) arg, num_cores = sysconf(_SC_NPROCESSORS_ONLN);
    pthread_t id = pthread_self();
    cpu_set_t cpuset;

    if (*core_id < 0 || *core_id >= num_cores)
        return NULL;

    CPU_ZERO(&cpuset);
    CPU_SET(*core_id, &cpuset);

    rc = pthread_setaffinity_np(id, sizeof(cpu_set_t), &cpuset);
    if(rc != 0)
    {
        printf("pthread_setaffinity_np() failed! - rc %d\n", rc);
        return NULL;
    }

    printf("Thread running on CPU %d\n", sched_getcpu());
    
    array_size = (int) (array_size_in_bytes / sizeof(int));
    chunk_size = (int) (array_size / NUM_THREADS);
    offset = chunk_size * (*core_id);
    
    // Find max number in the array chunk
    for(i = offset; i < (offset + chunk_size); i++)
    {
        if(array[i] > max_chunk[*core_id])
        {
            max_chunk[*core_id] = array[i];
            pos_chunk[*core_id] = i;
        }
    }
    
    return NULL;        
}

void load_array(void)
{
    FILE *f;
    size_t array_size_in_bytes = 1024*1024*1024, elements_read;

    array = (int*) malloc(array_size_in_bytes);
    assert(array != NULL); // assert if condition is false

    printf("Loading array...");

    f = fopen("numbers.bin", "rb");
    assert(f != NULL);

    elements_read = fread(array, array_size_in_bytes, 1, f);
    assert(elements_read == 1);

    printf("done!\n");

    fclose(f);
}

int main(void)
{
    int i, max = 0, position, id[NUM_THREADS], rc;
    clock_t t;
    double time;

    load_array();

    printf("Finding max...");

    t = clock();

    // Create threads
    for(i = 0; i < NUM_THREADS; i++)
    {
        id[i] = i; // uso id para pasarle un puntero distinto a cada thread
        rc = pthread_create(&(tid[i]), NULL, &thread, (void*)(id + i));
        if (rc != 0)
            printf("Can't create thread! rc = %d\n", rc);
        else
            printf("Thread %lu created\n", tid[i]);
    }
    
    // Join threads
    for(i = 0; i < NUM_THREADS; i++)
        pthread_join(tid[i], NULL);

    // Find max number from all chunks
    for(i = 0; i < NUM_THREADS; i++)
        if(max_chunk[i] > max)
        {
            max = max_chunk[i];
            position = pos_chunk[i];
        }

    t = clock() - t;
    time = ((double) t) / CLOCKS_PER_SEC;

    printf("done!\n");
    free(array);

    printf("----------- Program results -------------\nMax number: %d position %d\n", max, position);
    printf("Time %f [s]\n", time);

    pthread_exit(NULL);

    return 0;
}

实现层面的问题 #

• max_chunk全局数组没有初始化，默认值为0，如果待查找数组全是负数，计算结果会完全错误，不过这不是性能不达预期的核心原因。
• 你用clock()统计多线程耗时的方式是错误的：clock()返回的是进程所有CPU核心的总运行时长，不是实际经过的墙上时间。多线程场景下应该用clock_gettime(CLOCK_MONOTONIC, ...)这类统计真实耗时的接口。你看到的610ms其实是4个线程的CPU总耗时，换成真实耗时统计后会发现实际运行速度接近单线程的4倍。

被忽略的性能影响因素 #

• 内存带宽瓶颈：你的数组总大小为1GB，远大于i5 4460的6MB三级缓存，整个计算过程的瓶颈是内存读取速度，而非CPU计算。单线程已经几乎占满内存带宽的情况下，多线程不会带来明显的性能提升，这是内存密集型任务的典型特征。
• 缓存伪共享：max_chunk和pos_chunk是连续的全局数组，4个线程同时修改相邻位置的变量，刚好落在同一个缓存行中，会触发缓存行频繁的一致性同步，抵消部分多线程收益。可以给两个数组的元素添加缓存行对齐（比如使用__attribute__((aligned(64)))）消除该影响。
• 线程创建和调度开销：4个线程的创建、亲和性设置本身也会产生少量开销，不过该部分占比极低。

内容的提问来源于stack exchange，提问作者Nicolas