Время выполнения с двумя потоками против одного потока не улучшается

Question

Я новичок в многопоточном программировании на C ++. Я написал простой кусок кода, который я вставлю ниже. При запуске в двух потоках код заканчивается чуть быстрее, чем при однопоточном. Я сталкивался с другими подобными вопросами, однако они отличаются, так как у меня нет общих ресурсов, к которым оба потока должны будут обращаться :

Код ниже:

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>

using namespace std;

typedef unsigned long long ull;

ull oddSum = 0;
ull evenSum = 0;

void addOdd(){
    for(int i = 1; i <= 1999999999; i++){
        if(i % 2 == 1)
            oddSum += i;
    }
}

void addEven(){
    for(int i = 1; i <= 1999999999; i++){
        if(i % 2 == 0)
            evenSum += i;
    }
}

int main(){
    auto startTime = std::chrono::high_resolution_clock::now();

    //Two threads
    std::thread t1(addEven);    //launch the two threads to run
    std::thread t2(addOdd); 

    t1.join();
    t2.join();    //wait for both to finish

    //One thread
    //addEven();
    //addOdd();

    auto stopTime = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::microseconds>(stopTime - startTime);

    cout << "Odd Sum: " << oddSum << endl;
    cout << "Even Sum: " << evenSum << endl;

    cout << elapsed.count()/(double)1000000 << endl;

    return 0;
}

Когда я работаю с однопоточным , среднее значение для 10 прогонов составляет около 7,3 секунд .

Когда я работаю с двумя потоками , среднее значение для 10 циклов составляет около 6,8 секунд .

Поскольку подавляющее большинство времени занимают циклы в функциях, я считаю, что параллельное выполнение двух потоков, каждый с одна функция, которая вдвое сокращает время, необходимое для выполнения.

Примечание 1 : я знаю, что время не может быть должным образом уменьшено вдвое, более образованное предположение может быть Время выполнения до 5 секунд в двух потоках. Я понимаю, что создание объектов потока имеет свои издержки.

Примечание 2 : Может быть, я что-то упустил, но потоки не имеют доступа к общему расположению между ними.

Любая идея приветствуется. Я знаком с теорией параллельного программирования, и сейчас я только начинаю приобретать практический опыт. У меня Intel i7 с 4 ядрами.

Answer 1

При частом обращении к переменным из разных потоков вы должны убедиться, что они находятся на разных строках кэша (ширина которых составляет 64 байта в x86).

Это можно сделать, совместив переменные:

ull oddSum __attribute__((aligned(64))) = 0;
ull evenSum  __attribute__((aligned(64))) = 0;

Неспособность сделать это эффективно сериализует записи, так как строка кэша будет изменяться только одним процессором за один раз.

Выравнивание переменных сокращает время выполнения на 30% для меня во множественном числе. случай потока.

Как упомянул @walnut в своем комментарии, это можно сделать переносимым способом, если ваш компилятор поддерживает C ++ 17:

#include <new>
alignas(std::hardware_destructive_interference_size) ull oddSum = 0;
alignas(std::hardware_destructive_interference_size) ull evenSum  = 0;

Answer 2

Поскольку у вас есть две глобальные переменные, объявленные рядом друг с другом, вы, вероятно, сталкиваетесь с ложным разделением .

Answer 3

Вы не провели оптимизацию для двух потоков. Ниже приведено однопоточное решение. Поток перебрал числа 1999999999.

for(int i = 1; i <= 1999999999; i++){
    if(i % 2 == 1)
        oddSum += i;
    else
        evenSum += i;
}

Ниже приведены два цикла для двух потоков, каждый из которых перебирает одинаковые числа. Таким образом, каждый поток выполняет почти одинаковый объем работы.

for(int i = 1; i <= 1999999999; i++){
    if(i % 2 == 1)
        oddSum += i;
}

for(int i = 1; i <= 1999999999; i++){
    if(i % 2 == 0)
        evenSum += i;
}

Оптимизированное решение для двух потоков, разделяя 1999999999 итераций между двумя потоками:

for(int i = 1; i <= 1999999999; i += 2){
    oddSum += i;
}


for(int i = 2; i <= 1999999999; i += 2){
    evenSum += i;
}

Теперь каждый поток выполняется в два раза меньше работы.