C++ 11 std thread sumation with atomic very slow

Question

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

#include <iostream> 
#include <thread> 
#include <conio.h> 
#include <atomic> 

std::atomic<long long> sum(0); 
//long long sum; 

using namespace std; 

const int RANGE = 100000000; 

void test_without_threds() 
{ 
    sum = 0; 
    for(unsigned int j = 0; j < 2; j++) 
    for(unsigned int k = 0; k < RANGE; k++) 
     sum ++ ; 
} 

void call_from_thread(int tid) 
{ 
    for(unsigned int k = 0; k < RANGE; k++) 
     sum ++ ; 
} 

void test_with_2_threds() 
{ 
    std::thread t[2]; 
    sum = 0; 
    //Launch a group of threads 
    for (int i = 0; i < 2; ++i) { 
     t[i] = std::thread(call_from_thread, i); 
    } 

    //Join the threads with the main thread 
    for (int i = 0; i < 2; ++i) { 
     t[i].join(); 
    } 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    chrono::time_point<chrono::system_clock> start, end; 

    cout << "-----------------------------------------\n"; 
    cout << "test without threds()\n"; 

    start = chrono::system_clock::now(); 
    test_without_threds(); 
    end = chrono::system_clock::now(); 

    chrono::duration<double> elapsed_seconds = end-start; 

    cout << "finished calculation for " 
       << chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
       << "ms.\n"; 

    cout << "sum:\t" << sum << "\n";\ 

    cout << "-----------------------------------------\n"; 
    cout << "test with 2_threds\n"; 

    start = chrono::system_clock::now(); 
    test_with_2_threds(); 
    end = chrono::system_clock::now(); 

    cout << "finished calculation for " 
       << chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
       << "ms.\n"; 

    cout << "sum:\t" << sum << "\n";\ 

    _getch(); 
    return 0; 
} 

Теперь, когда я использую для счетчика только долго долго переменной (которая комментируется) Я получаю значение, которое отличается от правильного - 100000000 вместо 200000000. Я не уверен, почему это так, и я полагаю, что эти два потока меняют счетчик одновременно, но я не уверен, как это происходит на самом деле, потому что ++ - просто очень простая инструкция. Кажется, что потоки кэшируют переменную суммы в начале. Производительность составляет 110 мс с двумя потоками против 200 мс для одного потока.

Таким образом, правильный способ согласно документации - использовать std :: atomic. Однако сейчас производительность намного хуже для обоих случаев как около 3300 мс без потоков и 15820 мс с потоками. Каков правильный способ использования std :: atomic в этом случае?

Answer 1

Я не уверен, почему это так, и я полагаю, что эти два потока меняют счетчик одновременно, но я не уверен, как это происходит на самом деле, потому что ++ - это просто простая инструкция.

Каждый поток тянет значение sum в регистр, регистр приращения, и, наконец, писать его обратно в память в конце цикла.

Таким образом, правильный путь в соответствии с документацией заключается в использовании std :: atomic. Однако сейчас производительность намного хуже для обоих случаев как около 3300 мс без потоков и 15820 мс с потоками. Каков правильный способ использования std :: atomic в этом случае?

Вы платите за синхронизацию std::atomic. Это не будет почти так же быстро, как Вы используете не синхронизируются целое, хотя вы можете получить небольшое усовершенствование производительности за счет совершенствования порядка памяти оных:

sum.fetch_add(1, std::memory_order_relaxed); 

В данном конкретном случае, вы собираете для x86 и работает с 64-битным целым числом. Это означает, что компилятор должен сгенерировать код для обновления значения в двух 32-битных операциях; если вы измените целевую платформу на x64, компилятор сгенерирует код для выполнения приращения в одной 64-разрядной операции.

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

Answer 2

У вашего кода есть несколько проблем. Прежде всего, все задействованные «входы» - это константы времени компиляции, поэтому хороший компилятор может предварительно вычислить значение для однопоточного кода, поэтому (независимо от значения, которое вы даете для range), оно отображается как работает в 0 Миз.

Во-вторых, вы разделяете одну переменную (sum) между всеми потоками, заставляя все их обращения синхронизироваться в этой точке. Без синхронизации это дает неопределенное поведение. Как вы уже нашли, синхронизация доступа к этой переменной довольно дорого, поэтому вы обычно хотите избежать ее, если вообще разумно.

Один из способов сделать это - использовать отдельный промежуточный итог для каждого потока, чтобы они могли выполнять свои добавления параллельно, без синхронизации, добавляя отдельные результаты в конец.

Другим моментом является обеспечение ложного обмена. Ложное совместное использование возникает, когда два (или более) потока записывают данные, которые действительно являются отдельными, но были выделены в одной и той же строке кэша. В этом случае доступ к памяти может быть сериализован, хотя (как уже отмечалось) у вас нет данных, фактически разделяемых между потоками.

Исходя из этих факторов, я немного переписал код, чтобы создать отдельную переменную sum для каждого потока. Эти переменные имеют тип class, который дает (справедливо) прямой доступ к данным, но не позволяет оптимизатору видеть, что он может выполнять весь расчет во время компиляции, поэтому мы сравниваем один поток с 4 (что напоминает мне : Я увеличил количество потоков от 2 до 4, так как я использую четырехъядерную машину). Я переместил это число в константную переменную, так что это должно быть легко протестировать с различным количеством потоков.

#include <iostream> 
#include <thread> 
#include <conio.h> 
#include <atomic> 
#include <numeric> 

const int num_threads = 4; 

struct val { 
    long long sum; 
    int pad[2]; 

    val &operator=(long long i) { sum = i; return *this; } 
    operator long long &() { return sum; } 
    operator long long() const { return sum; } 
}; 

val sum[num_threads]; 

using namespace std; 

const int RANGE = 100000000; 

void test_without_threds() 
{ 
    sum[0] = 0LL; 
    for(unsigned int j = 0; j < num_threads; j++) 
    for(unsigned int k = 0; k < RANGE; k++) 
     sum[0] ++ ; 
} 

void call_from_thread(int tid) 
{ 
    for(unsigned int k = 0; k < RANGE; k++) 
     sum[tid] ++ ; 
} 

void test_with_threads() 
{ 
    std::thread t[num_threads]; 
    std::fill_n(sum, num_threads, 0); 
    //Launch a group of threads 
    for (int i = 0; i < num_threads; ++i) { 
     t[i] = std::thread(call_from_thread, i); 
    } 

    //Join the threads with the main thread 
    for (int i = 0; i < num_threads; ++i) { 
     t[i].join(); 
    } 
    long long total = std::accumulate(std::begin(sum), std::end(sum), 0LL); 
} 

int main() 
{ 
    chrono::time_point<chrono::system_clock> start, end; 

    cout << "-----------------------------------------\n"; 
    cout << "test without threds()\n"; 

    start = chrono::system_clock::now(); 
    test_without_threds(); 
    end = chrono::system_clock::now(); 

    chrono::duration<double> elapsed_seconds = end-start; 

    cout << "finished calculation for " 
       << chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
       << "ms.\n"; 

    cout << "sum:\t" << sum << "\n";\ 

    cout << "-----------------------------------------\n"; 
    cout << "test with threads\n"; 

    start = chrono::system_clock::now(); 
    test_with_threads(); 
    end = chrono::system_clock::now(); 

    cout << "finished calculation for " 
       << chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
       << "ms.\n"; 

    cout << "sum:\t" << sum << "\n";\ 

    _getch(); 
    return 0; 
} 

Когда я запускаю это, мои результаты ближе к тому, что я предполагаю, что вы надеялись:

----------------------------------------- 
test without threds() 
finished calculation for 78ms. 
sum: 000000013FCBC370 
----------------------------------------- 
test with threads 
finished calculation for 15ms. 
sum: 000000013FCBC370 

... суммы одинаковы, но N нитей увеличивает скорость на коэффициент приблизительно N (до количества доступных сердечников).

Answer 3

Попробуйте использовать префиксный прирост, который обеспечит повышение производительности. Тест на моей машине, std :: memory_order_relaxed не дает никаких преимуществ.