为什么 pthread 会减慢代码速度？

Question

我是 pthreads 的新手，我编写这段代码用于测试。我不明白为什么如果我运行只有 1 个 pthread 的代码比我运行有多个 pthread 的代码完成得更快。该代码是解决 TSP 的遗传算法的设置部分。我有 3 个保存数据的线性阵列（city_x、city_y、city_id）：

1 代表 x
1 表示 y
1个为每个城市的id

这些数组就像线性化的一样，代表总体的元素。每个元素都有 NUM_CITIES 个 x、y 和 id 数据。所以如果我们有：

人口的 3 个元素
每个元素 10 NUM_CITIES
每个数组的数据总数为3*10=30

代码需要输入种群元素的数量，在city_set数组中设置一些坐标，并使用整个元素的坐标x、y和id创建全局数组人口。

#include <pthread.h>

#include <limits> // std::numeric_limits<double>
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <utility>
//#include <math.h>
#include <algorithm>    // std::lower_bound, std::find
#include <random>
#include <cmath> 
#include <cstring>
#include <iomanip>      // std::setprecision
#include <vector>       // std::vector

#define NUM_CITIES 10  // This is a tour for the LIN105. It has length 14379.
// #define SIZE_POP 100000000
#define SIZE_MATING 3
#define MUTATION_RATE 0.03
#define STALL_LIMIT 10

// variabili condivise
long size_pop = 0;
long tot_elem = 0;
const int num_threads = 24;
int tid[num_threads];
int start[num_threads];
int stop[num_threads];

// città
int city_set_x[NUM_CITIES];
int city_set_y[NUM_CITIES];
int city_set_id[NUM_CITIES];

// elementi della popolazione
int *city_x;
int *city_y;
int *city_id;

void *setup(void *p) {

    int id = *(int *)p;
    // std::cout << "id: " << id << "\n";

    int s = start[id];

    int perm[NUM_CITIES];
    for(int i = 0; i < NUM_CITIES; ++i) {
        perm[i] = i;
        // std::cout << perm[i] << ",";
    }

    for(long i = start[id]; i < stop[id]; i += NUM_CITIES) {
        std::random_shuffle ( perm, perm + NUM_CITIES );

        for(int j = 0; j < NUM_CITIES; ++j) {
            city_id[i + j] =  perm[j];
            city_x[i + j] =  city_set_x[perm[j]];
            city_y[i + j] =  city_set_y[perm[j]];
            // std::cout << "(" << city_x[i + j] << "," << city_y[i + j] << ") ";
        }
        // std::cout << "\n";
    }

}


static inline const double diffmsec(const struct timeval & a, 
                                    const struct timeval & b) {
    long sec  = (a.tv_sec  - b.tv_sec);
    long usec = (a.tv_usec - b.tv_usec);

    if(usec < 0) {
        --sec;
        usec += 1000000;
    }
    return ((double)(sec*1000)+ (double)usec/1000.0);
}

int main(int argc, char *argv[]) {

    size_pop = atol(argv[1]);

    std::cout << size_pop << "\n";

    tot_elem = NUM_CITIES * size_pop;
    std::cout << "tot_elem: " << tot_elem << "\n";

    struct timeval program_start, program_end, setup_start, setup_end;

    std::vector<double> v_set;

    city_x = (int *)malloc(tot_elem * sizeof(int));
    // memset(city_x, -1, tot_elem * sizeof(int));
    city_y = (int *)malloc(tot_elem * sizeof(int));
    // memset(city_y, -1, tot_elem * sizeof(int));
    city_id = (int *)malloc(tot_elem * sizeof(int));
    for(int i = 0; i < tot_elem; ++i) {
        city_x[i] = -1;
        city_y[i] = -1;
        city_id[i] = -1;
    }

    srand(time(NULL));

    int x[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int y[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};


    // stampa
    std::cout << "[CITTA.X]\n";
    for(int i = 0; i < NUM_CITIES; ++i) {

        city_set_x[i] = x[i];
        // city_set[i].x = i + 1;
        std::cout << city_set_x[i] << " ";
    }
    std::cout << "\n";

    std::cout << "[CITTA.Y]\n";
    for(int i = 0; i < NUM_CITIES; ++i) {

        city_set_y[i] = y[i];
        // city_set[i].y = i + 1;
        std::cout << city_set_y[i] << " ";
    }
    std::cout << "\n";

    std::cout << "[CITTA.ID]\n";
    for(int i = 0; i < NUM_CITIES; ++i) {

        city_set_id[i] = i;
        std::cout << city_set_id[i] << " ";
    }
    std::cout << "\n";

    // std::cin.get() != '\n';

    pthread_t threads[num_threads];

    for(int i = 0; i < num_threads; ++i) {
        tid[i] = i;
        start[i] = i * NUM_CITIES * floor(size_pop/num_threads);
        // std::cout << "start: " << start << "\n";
        if(i != num_threads - 1) {
            stop[i] = start[i] + (floor(size_pop/num_threads) * NUM_CITIES);
            // std::cout << "stop: " << stop << "\n";
        }
        else {
            stop[i] = tot_elem;
            // std::cout << "stop: " << stop << "\n";
        }
        // std::cout << "\n";
    }

    for(int c = 0; c < 10; c++) {

        gettimeofday(&setup_start, NULL);

        for(int i = 0; i < num_threads; ++i) {
            if( pthread_create( &threads[i], NULL, &setup, (void *) &tid[i]) )
            {
              printf("Thread creation failed\n");
            }
        }

        for(int i = 0; i < num_threads; ++i) {
            pthread_join( threads[i], NULL);
        }

        gettimeofday(&setup_end, NULL);
        v_set.push_back(diffmsec(setup_end, setup_start) / 1000);
    }

    // // stampa
    // std::cout << "[SETUP]\n";
    // for(int i = 0; i < size_pop; ++i){
    //  long idx = i * NUM_CITIES;
    //  std::cout << "pop[" << i << "]: ";
    //  for(int j = 0; j < NUM_CITIES; ++j){
    //      std::cout << "(" << city_x[idx + j] << "," << city_y[idx + j] << ") ";
    //  }
    //  std::cout << "\n";
    // }

    double sum = 0;
    double mean;


    sum = 0;
    for (int i = 0; i < v_set.size(); ++i) {
        sum += v_set[i];
    }
    mean = sum / v_set.size();
    std::cout << "[SET]: " << mean << " s\n";

    free(city_x);
    free(city_y);
    free(city_id);

}

我运行代码1000000个元素将线程数设置为1，结果为0.332秒。在运行 1000000 个元素 但将线程数设置为 4 之后 结果是 1.361 s。如果我 在 24 处增加数字， 结果是 0.60 s 但是是顺序的两倍！当我超过 24 个线程时，结果保持不变或再次增加。

编辑

使用：grep -c 处理器/proc/cpuinfo

我得到56.

使用：cat /proc/cpuinfo

处理器：0

vendor_id : 正版英特尔

cpu 家庭：6

型号：79

型号名称：Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz 步进：1

微码：0xb00001e

cpu 兆赫：1967.906

缓存大小：35840 KB

实体编号：0

兄弟姐妹：28

核心编号：0

cpu 核心数：14

酸碱度：0

初始酸碱度：0

fpu : 是

fpu_exception : 是

cpu身份证等级：20

wp : 是

标志：fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe 系统调用 nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 fma cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch arat epb pln pts dtherm intel_pt tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm cqm rdseed adx smap xsaveopt cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local

bogomips : 4799.62

clflush 大小：64

cache_alignment : 64

地址大小：46 位物理地址，48 位虚拟地址

对于 56 个处理器中的每一个。

Answer 1

运行具有多个线程的代码，需要系统在每个线程之间进行上下文切换，这意味着您有计算开销而实际上并没有从中获得任何好处。此外，您还需要一个循环来计算线程参数，生成的线程越多，计算量就越大，但这可能是引入的延迟最少的，因为它不需要大量计算。

另请注意，单个物理核心上的线程可能运行，请检查当程序运行时您的资源是如何使用的。如果程序只在单核上运行，那么你实际上并没有使用多核引入的硬件加速。

最后，因为这是 C++，我建议使用本机 std::thread。

最后我认为这种延迟主要是由于线程之间的上下文切换以及线程可能运行在单个内核上的事实。尝试检查运行程序在多个物理内核上的可能性，并检查需要多少时间。

Answer 2

std::random_shuffle使用了一个共享资源，所有的线程都在使用它，所以你的程序竞争很大，线程大多在等待对方。为每个线程使用单独的随机生成器（例如，std::mt19937 和 std::shuffle，查看 cppreference）。

此外，您可能希望增加 NUM_CITIES，因此每个线程都使用单独的缓存行。

为什么 pthread 会减慢代码速度？

Why pthread slow down the code?

c++

performance

pthreads

genetic-algorithm