Многопоточность без блокировок медленнее, чем однопоточная программа?
Я рассмотрел распараллеливание программы так, чтобы на первом этапе она сортировала элементы по сегментам по модулю числа параллельных рабочих, чтобы избежать столкновений на втором этапе. Каждый поток параллельной программы использует std::atomic::fetch_add зарезервировать место в выходном массиве, а затем он использует std::atomic::compare_exchange_weak обновить текущий указатель головки ковша. Так что это без блокировки. Однако у меня возникли сомнения по поводу производительности нескольких потоков, борющихся за один атом (тот, который мы делаем fetch_add, так как количество головок ковша равно количеству потоков, таким образом, в среднем не так много споров), поэтому я решил измерить это. Вот код:
#include <atomic>
#include <chrono>
#include <cstdio>
#include <string>
#include <thread>
#include <vector>
std::atomic<int64_t> gCounter(0);
const int64_t gnAtomicIterations = 10 * 1000 * 1000;
void CountingThread() {
for (int64_t i = 0; i < gnAtomicIterations; i++) {
gCounter.fetch_add(1, std::memory_order_acq_rel);
}
}
void BenchmarkAtomic() {
const uint32_t maxThreads = std::thread::hardware_concurrency();
std::vector<std::thread> thrs;
thrs.reserve(maxThreads + 1);
for (uint32_t nThreads = 1; nThreads <= maxThreads; nThreads++) {
auto start = std::chrono::high_resolution_clock::now();
for (uint32_t i = 0; i < nThreads; i++) {
thrs.emplace_back(CountingThread);
}
for (uint32_t i = 0; i < nThreads; i++) {
thrs[i].join();
}
auto elapsed = std::chrono::high_resolution_clock::now() - start;
double nSec = 1e-6 * std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();
printf("%d threads: %.3lf Ops/sec, counter=%lld\n", (int)nThreads, (nThreads * gnAtomicIterations) / nSec,
(long long)gCounter.load(std::memory_order_acquire));
thrs.clear();
gCounter.store(0, std::memory_order_release);
}
}
int __cdecl main() {
BenchmarkAtomic();
return 0;
}
И вот вывод:
1 threads: 150836387.770 Ops/sec, counter=10000000
2 threads: 91198022.827 Ops/sec, counter=20000000
3 threads: 78989357.501 Ops/sec, counter=30000000
4 threads: 66808858.187 Ops/sec, counter=40000000
5 threads: 68732962.817 Ops/sec, counter=50000000
6 threads: 64296828.452 Ops/sec, counter=60000000
7 threads: 66575046.721 Ops/sec, counter=70000000
8 threads: 64487317.763 Ops/sec, counter=80000000
9 threads: 63598622.030 Ops/sec, counter=90000000
10 threads: 62666457.778 Ops/sec, counter=100000000
11 threads: 62341701.668 Ops/sec, counter=110000000
12 threads: 62043591.828 Ops/sec, counter=120000000
13 threads: 61933752.800 Ops/sec, counter=130000000
14 threads: 62063367.585 Ops/sec, counter=140000000
15 threads: 61994384.135 Ops/sec, counter=150000000
16 threads: 61760299.784 Ops/sec, counter=160000000
Процессор 8-ядерный, 16-потоковый (Ryzen 1800X @3,9 ГГц). Таким образом, общее количество операций во всех потоках в секунду резко уменьшается, пока не будет использовано 4 потока. Затем он медленно уменьшается и немного колеблется.
Так характерно ли это явление для других процессоров и компиляторов? Есть ли обходной путь (кроме обращения к одному потоку)?
3 ответа
Многопоточная программа без блокировки не медленнее, чем однопоточная. Что делает его медленным, так это конфликт данных. Пример Предоставленный на самом деле весьма спорная искусственная программа. В реальной программе вы будете выполнять большую работу между каждым доступом к общим данным, и, следовательно, у вас будет меньше недействительных кэшей и так далее. Этот доклад CppCon Джеффа Прешинга может объяснить некоторые ваши вопросы лучше, чем я.
Добавить: Попробуйте изменить CountingThread и время от времени добавлять спящий режим, чтобы представить, что вы заняты чем-то еще, кроме увеличения атомарной переменной gCounter. Затем продолжите и поиграйте со значением в операторе if, чтобы увидеть, как оно повлияет на результаты вашей программы.
void CountingThread() {
for (int64_t i = 0; i < gnAtomicIterations; i++) {
// take a nap every 10000th iteration to simulate work on something
// unrelated to access to shared resource
if (i%10000 == 0) {
std::chrono::milliseconds timespan(1);
std::this_thread::sleep_for(timespan);
}
gCounter.fetch_add(1, std::memory_order_acq_rel);
}
}
В общем каждый раз звонишь gCounter.fetch_add это означает маркировку этих данных как недопустимых в кеше другого ядра. Это вынуждает их обращаться к данным в кеше от ядра. Этот эффект является основным фактором снижения производительности вашей программы.
local L1 CACHE hit, ~4 cycles ( 2.1 - 1.2 ns ) local L2 CACHE hit, ~10 cycles ( 5.3 - 3.0 ns ) local L3 CACHE hit, line unshared ~40 cycles ( 21.4 - 12.0 ns ) local L3 CACHE hit, shared line in another core ~65 cycles ( 34.8 - 19.5 ns ) local L3 CACHE hit, modified in another core ~75 cycles ( 40.2 - 22.5 ns ) remote L3 CACHE (Ref: Fig.1 [Pg. 5]) ~100-300 cycles ( 160.7 - 30.0 ns ) local DRAM ~60 ns remote DRAM ~100 nsВыше таблицы взяты из Приблизительная стоимость доступа к различным кэшам и основной памяти?
Без блокировки не означает, что вы можете обмениваться данными между потоками без затрат. Без блокировки означает, что вы не ждете, пока другие потоки не разблокируют мьютекс для чтения общих данных. Фактически даже программы без блокировки используют механизмы блокировки, чтобы предотвратить повреждение данных.
Просто следуйте простому правилу. Попробуйте получить доступ к общим данным как можно меньше, чтобы получить больше от многоядерного программирования.
Это зависит от конкретной рабочей нагрузки.
См закон Амдаля
100 % (whole workload in percentage)
speedup = -----------------------------------------------------------
(sequential work load in %) + (parallel workload in %) / (count of workers)
Параллельная рабочая нагрузка в вашей программе 0 %так что ускорение 1, Ака нет ускорения. (Вы выполняете синхронизацию для увеличения одной и той же ячейки памяти, и поэтому только один поток может увеличивать эту ячейку в любой момент времени.)
Грубое объяснение, почему это даже хуже speedup=1:
Строка кэша, содержащая gCounter остается в кэше процессора только с одним потоком.
С несколькими потоками, которые запланированы на разные процессоры или ядра, строка кэша, содержащая gCounter будет подпрыгивать вокруг различных тайников для ядер процессорной руды.
Таким образом, разница в некоторой степени сопоставима с приращением регистра только с одним потоком по сравнению с доступом к памяти для каждой операции приращения. (Иногда это быстрее, чем доступ к памяти, поскольку в современных архитектурах ЦП имеется кэш-память для передачи.)
Как и большинство очень широких, которые являются более быстрыми вопросами, единственный полностью общий ответ - это зависит.
Хорошая ментальная модель заключается в том, что при распараллеливании существующей задачи время выполнения параллельной версии превышает N темы будут состоять из трех вкладов:
Неподвижная последовательная часть, общая для последовательных и параллельных алгоритмов. То есть,. работа, которая не была распараллелена, например, работа по настройке или демонтажу, или работа, которая не выполнялась параллельно, потому что задача была неточно разделена1.
Параллельная часть, которая была эффективно распараллелена среди
Nработников.Компонент служебной информации, представляющий дополнительную работу, выполняемую в параллельном алгоритме, которого нет в последовательной версии. Практически всегда присутствуют небольшие накладные расходы на разделение работы, делегирование рабочим потокам и объединение результатов, но в некоторых случаях накладные расходы могут затопить реальную работу.
Итак, в целом у вас есть эти три вклада, и давайте назначим T1p, T2p а также T3p соответственно. Теперь T1p Компонент существует и занимает одно и то же время как в последовательном, так и в параллельном алгоритмах, поэтому мы можем его игнорировать, так как он отменяет для определения, что медленнее.
Конечно, если вы используете более грубую синхронизацию, например, увеличиваете локальную переменную в каждом потоке и только периодически (возможно, только один раз в самом конце) обновляете общую переменную, ситуация будет обратной.
1 Это также относится к случаю, когда рабочая нагрузка была хорошо разделена, но некоторые потоки выполняли больше работы за единицу времени, что характерно для современных процессоров и современных ОС.