У вас нет никакой защиты от потока, который снова берет блокировку сразу после ее освобождения, только чтобы найти _vec.empty() было не ложным, или сохранить другое значение TS C, перезаписав его этого никогда не видел читатель. Я подозреваю, что ваше изменение позволяет читателю тратить больше времени на блокировку писателя (и наоборот), что приводит к снижению реальной пропускной способности.
TL: DR: Настоящая проблема заключалась в отсутствии справедливости в вашем блокировка (слишком просто для потока, который только что разблокировал, чтобы выиграть гонку, чтобы снова заблокировать его), и то, как вы используете эту блокировку. (Вы должны принять это, прежде чем сможете определить, есть ли что-нибудь полезное, заставляя другой поток повторить попытку и вызывая дополнительные передачи строки кэша между ядрами.)
Повторное получение блокировки потоком если другой поток не получает очередь, это всегда бесполезно и тратит впустую работу, в отличие от многих реальных случаев, когда для заполнения или опустошения очереди требуется больше повторений. Это плохой алгоритм производителя-потребителя (слишком маленькая очередь (размер 1) и / или считыватель отбрасывает все элементы вектора после чтения vec[0]) и наихудшая из возможных схем блокировки для него.
_lock.store(false, seq_cst); компилируется в xchg вместо обычного mov хранилища. Он должен ждать, пока буфер хранилища истощится, и он просто медленный 1 (например, на Skylake, микрокодируется как 8 мопов, пропускная способность составляет один за 23 цикла для многих повторяющихся последовательных операций, в случай отсутствия конкуренции, когда в кеше L1d уже горячо. Вы ничего не указали о том, какое оборудование у вас есть).
_lock.store(false, std::memory_order_release); просто компилируется в обычное хранилище mov без дополнительных инструкций барьера . Таким образом, перезагрузка _counter может происходить параллельно с ним (хотя предсказание ветвления + спекулятивное выполнение не представляет проблемы). И что еще более важно, следующая попытка CAS взять блокировку может быть предпринята раньше.
Существует аппаратный арбитраж для доступа к строке кэша, когда несколько ядер работают с ней, по-видимому, с некоторой эвристикой справедливости, но я не Не знаю, известны ли подробности.
Сноска 1: xchg не так медленен, как mov + mfence на некоторых последних процессорах, особенно на процессорах, производных от Skylake. Это лучший способ реализовать чистое хранилище seq_cst на x86. Но он медленнее, чем обычный mov.
Вы можете полностью решить эту проблему, установив чередующийся писатель / считыватель с силой блокировки
Writer ждет false, а затем сохраняет true, когда это сделано. Читатель поступает наоборот. Таким образом, писатель никогда не сможет повторно войти в критическую секцию, если другой поток не успел по очереди. (Когда вы «ждете значения», делайте это только для чтения с загрузкой, а не с CAS. CAS на x86 требует исключительного владения строкой кэша, предотвращая чтение других потоков. Имея только один считыватель и один модуль записи, вы не нужны никакие atomi c RMW, чтобы это работало.)
Если у вас было несколько читателей и несколько писателей, у вас могла бы быть переменная syn c с 4 состояниями, где писатель пытается ее CAS от 0 до 1, после чего сохраняет 2. Читатели пытаются использовать CAS от 2 до 3, а затем сохраняют 0.
Случай SPS C (один производитель и один потребитель) прост:
enum lockstates { LK_WRITER=0, LK_READER=1, LK_EXIT=2 };
std::atomic<lockstates> shared_lock;
uint64_t shared_queue; // single entry
uint64_t global_total{ 0 }, global_counter{ 0 };
static const uint64_t LIMIT = 1000000;
void writer()
{
while(1) {
enum lockstates lk;
while ((lk = shared_lock.load(std::memory_order_acquire)) != LK_WRITER) {
if (lk == LK_EXIT)
return;
else
SPIN; // _mm_pause() or empty
}
//_vec.push_back(__rdtsc());
shared_queue = __rdtsc();
shared_lock.store(LK_READER, ORDER); // seq_cst or release
}
}
void reader()
{
uint64_t total=0, counter=0;
while(1) {
enum lockstates lk;
while ((lk = shared_lock.load(std::memory_order_acquire)) != LK_READER) {
SPIN; // _mm_pause() or empty
}
const uint64_t latency = __rdtsc() - shared_queue; // _vec[0];
//_vec.clear();
total += latency;
++counter;
if (counter < LIMIT) {
shared_lock.store(LK_WRITER, ORDER);
}else{
break; // must avoid storing a LK_WRITER right before LK_EXIT, otherwise writer races and can overwrite with LK_READER
}
}
global_total = total;
global_counter = counter;
shared_lock.store(LK_EXIT, ORDER);
}
Полная версия на Godbolt . На моем рабочем столе Skylake i7-6700k (2-ядерный турбо = 4200 МГц, TS C = 4008 МГц), скомпилированный с помощью clang ++ 9.0.1 -O3. Как и ожидалось, данные довольно зашумлены; Я сделал несколько запусков и вручную выбрал нижнюю и верхнюю точки, игнорируя некоторые реальные выбросы, которые, вероятно, были вызваны эффектами разогрева.
На отдельных физических ядрах:
-
-DSPIN='_mm_pause()' -DORDER=std::memory_order_release: от ~ 180 до ~ 210 циклов / операцию, в основном ноль machine_clears.memory_ordering (например, 19 всего за 1000000 операций, благодаря pause в циклическом ожидании l oop.) -DSPIN='_mm_pause()' -DORDER=std::memory_order_seq_cst: от ~ 195 до ~ 215 эталонных циклов / операцию, тот же прибор, близкий к нулю, очищается. -DSPIN='' -DORDER=std::memory_order_release: от ~ 195 до ~ 225 эталонных циклов / операцию, от 9 до 10 Мвыб / сек c машина очищает без pause. -DSPIN='' -DORDER=std::memory_order_seq_cst: более изменчивый и медленный, от ~ 250 до ~ 315 циклов / операцию, от 8 до 10 Мбит / с c машина очищается без pause
Эти тайминги примерно в 3 раза быстрее, чем ваш seq_cst "быстрый" оригинал в моей системе . Использование std::vector<> вместо скаляра может составлять ~ 4 цикла этого; Думаю, при замене был небольшой эффект. Хотя, может, просто случайный шум. 200 / 4,008 ГГц - это примерно 50 нс межъядерная задержка, что звучит примерно правильно для четырехъядерного «клиентского» чипа.
Из лучшей версии (mo_release, вращение на pause во избежание очистки компьютера):
$ clang++ -Wall -g -DSPIN='_mm_pause()' -DORDER=std::memory_order_release -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r4 ./a.out
195 ref cycles per op. total ticks: 195973463 / 1000000 ops
189 ref cycles per op. total ticks: 189439761 / 1000000 ops
193 ref cycles per op. total ticks: 193271479 / 1000000 ops
198 ref cycles per op. total ticks: 198413469 / 1000000 ops
Performance counter stats for './a.out' (4 runs):
199.83 msec task-clock:u # 1.985 CPUs utilized ( +- 1.23% )
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
128 page-faults # 0.643 K/sec ( +- 0.39% )
825,876,682 cycles:u # 4.133 GHz ( +- 1.26% )
10,680,088 branches:u # 53.445 M/sec ( +- 0.66% )
44,754,875 instructions:u # 0.05 insn per cycle ( +- 0.54% )
106,208,704 uops_issued.any:u # 531.491 M/sec ( +- 1.07% )
78,593,440 uops_executed.thread:u # 393.298 M/sec ( +- 0.60% )
19 machine_clears.memory_ordering # 0.094 K/sec ( +- 3.36% )
0.10067 +- 0.00123 seconds time elapsed ( +- 1.22% )
И из худшей версии (mo_seq_cst, no pause): spin-wait l oop вращается быстрее, поэтому количество выданных / выполненных ветвей и мопов намного выше, но фактическая полезная пропускная способность несколько ниже хуже.
$ clang++ -Wall -g -DSPIN='' -DORDER=std::memory_order_seq_cst -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r4 ./a.out
280 ref cycles per op. total ticks: 280529403 / 1000000 ops
215 ref cycles per op. total ticks: 215763699 / 1000000 ops
282 ref cycles per op. total ticks: 282170615 / 1000000 ops
174 ref cycles per op. total ticks: 174261685 / 1000000 ops
Performance counter stats for './a.out' (4 runs):
207.82 msec task-clock:u # 1.985 CPUs utilized ( +- 4.42% )
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
130 page-faults # 0.623 K/sec ( +- 0.67% )
857,989,286 cycles:u # 4.129 GHz ( +- 4.57% )
236,364,970 branches:u # 1137.362 M/sec ( +- 2.50% )
630,960,629 instructions:u # 0.74 insn per cycle ( +- 2.75% )
812,986,840 uops_issued.any:u # 3912.003 M/sec ( +- 5.98% )
637,070,771 uops_executed.thread:u # 3065.514 M/sec ( +- 4.51% )
1,565,106 machine_clears.memory_ordering # 7.531 M/sec ( +- 20.07% )
0.10468 +- 0.00459 seconds time elapsed ( +- 4.38% )
Прикрепление читателя и записывающего устройства к логическим ядрам одного физического ядра ускоряет его лот : в моей системе, ядра 3 и 7 являются братьями и сестрами, поэтому Linux taskset -c 3,7 ./a.out не позволяет ядру планировать их где-либо еще: от 33 до 39 циклов ссылок на операцию или от 80 до 82 без pause.
( Что будет использоваться для обмен данными между потоками выполняется на одном ядре с HT? ,)
$ clang++ -Wall -g -DSPIN='_mm_pause()' -DORDER=std::memory_order_release -O3 inter-thread.cpp -pthread &&
taskset -c 3,7 perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r4 ./a.out
39 ref cycles per op. total ticks: 39085983 / 1000000 ops
37 ref cycles per op. total ticks: 37279590 / 1000000 ops
36 ref cycles per op. total ticks: 36663809 / 1000000 ops
33 ref cycles per op. total ticks: 33546524 / 1000000 ops
Performance counter stats for './a.out' (4 runs):
89.10 msec task-clock:u # 1.942 CPUs utilized ( +- 1.77% )
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
128 page-faults # 0.001 M/sec ( +- 0.45% )
365,711,339 cycles:u # 4.104 GHz ( +- 1.66% )
7,658,957 branches:u # 85.958 M/sec ( +- 0.67% )
34,693,352 instructions:u # 0.09 insn per cycle ( +- 0.53% )
84,261,390 uops_issued.any:u # 945.680 M/sec ( +- 0.45% )
71,114,444 uops_executed.thread:u # 798.130 M/sec ( +- 0.16% )
16 machine_clears.memory_ordering # 0.182 K/sec ( +- 1.54% )
0.04589 +- 0.00138 seconds time elapsed ( +- 3.01% )
На логических ядрах, совместно использующих одно физическое ядро. В лучшем случае задержка примерно в 5 раз меньше, чем между ядрами, опять же для pause + mo_release. Но фактический эталонный тест завершается только в 40% случаев, а не в 20%.
-DSPIN='_mm_pause()' -DORDER=std::memory_order_release: ~ от 33 до ~ 39 эталонных циклов / операцию , почти- ноль machine_clears.memory_ordering-DSPIN='_mm_pause()' -DORDER=std::memory_order_seq_cst: от ~ 111 до ~ 113 опорных циклов / операцию, всего 19 сбросов машины. На удивление худшее! -DSPIN='' -DORDER=std::memory_order_release: от ~ 81 до ~ 84 эталонных циклов / операцию, ~ 12,5 млн очищений машины / сек c. -DSPIN='' -DORDER=std::memory_order_seq_cst: от ~ 94 до ~ 96 c / op, 5 M / se c машина очищает без pause.
Все эти тесты выполняются с clang++, который использует xchg для хранения seq_cst. g++ использует mov + mfence, что медленнее в случаях pause, быстрее без pause и с меньшим количеством машинных сбросов. (Для случая гиперпоточности.) Обычно очень похоже на случай отдельных ядер с pause, но быстрее в случае отдельных ядер seq_cst без случая pause. (Опять же, специально на Skylake, для этого одного теста.)
Дополнительные исследования исходной версии:
Также стоит проверить счетчики производительности для machine_clears.memory_ordering ( Почему грипп sh конвейер для нарушения порядка памяти, вызванного другими логическими процессорами? ).
Я проверил свой Skylake i7-6700k, и существенной разницы не было со скоростью machine_clears.memory_ordering в секунду (около 5M / se c как для быстрого seq_cst, так и для медленного выпуска) при 4,2 ГГц. Результат «циклов на операцию» на удивление согласован для версии seq_cst (от 400 до 422). Опорная частота моего процессора TS C составляет 4008 МГц, фактическая частота ядра 4200 МГц при максимальном турбо. Я предполагаю, что максимальная турбо-частота вашего процессора выше по сравнению с его эталонной частотой, чем у меня, если у вас есть цикл 340-380. И / или другая микроархитектура.
Но я обнаружил дико разные результаты для версии mo_release: с GCC9.3.0 -O3 на Arch GNU / Linux: 5790 для одного пробег, 2269 для другого. С clang9.0.1 -O3 73346 и 7333 для двух прогонов, да действительно с коэффициентом 10). Это сюрприз. Ни одна из версий не выполняет системные вызовы для освобождения / выделения памяти при опустошении / выталкивании вектора, и я не вижу, чтобы машина упорядочивала много памяти из версии clang. С вашим исходным LIMIT два прогона с clang показали 1394 и 22101 цикл на операцию.
С clang ++ даже времена seq_cst меняются несколько больше, чем с G CC, и выше, например, от 630 до 700. (g ++ использует mov + mfence для чистых хранилищ seq_cst, clang ++ использует xchg, как MSV C).
Другие счетчики производительности с mo_release показывают схожую скорость выполнения инструкций, ветвей и операций в секунду, поэтому я думаю, что это показатель того, что код просто тратит больше времени на то, чтобы крутить колеса с неправильным потоком в критической секции и другая застряла при повторной попытке.
Два запуска perf, первый - mo_release, второй - mo_seq_cst.
$ clang++ -DORDER=std::memory_order_release -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r1 ./a.out
27989 cycles per op
Performance counter stats for './a.out':
16,350.66 msec task-clock:u # 2.000 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
231 page-faults # 0.014 K/sec
67,412,606,699 cycles:u # 4.123 GHz
697,024,141 branches:u # 42.630 M/sec
3,090,238,185 instructions:u # 0.05 insn per cycle
35,317,247,745 uops_issued.any:u # 2159.989 M/sec
17,580,390,316 uops_executed.thread:u # 1075.210 M/sec
125,365,500 machine_clears.memory_ordering # 7.667 M/sec
8.176141807 seconds time elapsed
16.342571000 seconds user
0.000000000 seconds sys
$ clang++ -DORDER=std::memory_order_seq_cst -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r1 ./a.out
779 cycles per op
Performance counter stats for './a.out':
875.59 msec task-clock:u # 1.996 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
137 page-faults # 0.156 K/sec
3,619,660,607 cycles:u # 4.134 GHz
28,100,896 branches:u # 32.094 M/sec
114,893,965 instructions:u # 0.03 insn per cycle
1,956,774,777 uops_issued.any:u # 2234.806 M/sec
1,030,510,882 uops_executed.thread:u # 1176.932 M/sec
8,869,793 machine_clears.memory_ordering # 10.130 M/sec
0.438589812 seconds time elapsed
0.875432000 seconds user
0.000000000 seconds sys
Я изменил ваш код с порядком памяти как макрос CPP, поэтому вы можете скомпилировать с помощью -DORDER=std::memory_order_release, чтобы получить медленную версию.
acquire vs. seq_cst здесь не имеет значения; он компилируется в тот же asm на x86 для нагрузок и atomi c RMW. Только чистые хранилища нуждаются в специальном asm для seq_cst.
Также вы исключили stdint.h и intrin.h (MSV C) / x86intrin.h (все остальное). Фиксированная версия - на Godbolt с clang и MSV C. Раньше я увеличил LIMIT в 10 раз, чтобы убедиться, что частота ЦП успевает подняться до максимального значения в турбо-режиме большую часть временного диапазона, но отменил это изменение, поэтому тестирование mo_release заняло бы только секунды, а не минуты.
Установка LIMIT для проверки определенного общего количества циклов TS C может помочь выйти в более согласованное время . Это все еще не учитывает время, когда писатель заблокирован, но в целом должен выполняться, который занимает очень много времени с меньшей вероятностью.
У вас также много очень чрезмерных сложные вещи происходят, если вы просто пытаетесь измерить задержку между потоками.
( Как происходит связь между ЦП? )
У вас есть оба потока читают _total, который писатель обновляет каждый раз, вместо того, чтобы просто сохранять флаг, когда все будет готово. Таким образом, у писателя есть потенциальная машина для очистки памяти от чтения этой переменной, записанной другим потоком.
У вас также есть приращение atomi c RMW _counter в считывателе, даже если эта переменная является частной для читатель. Это может быть обычная глобальная переменная c, которую вы читаете после reader.join(), или, что еще лучше, локальная переменная, которую вы сохраняете только в глобальной после l oop. (Простой не-atomi c global, вероятно, все равно будет сохраняться в памяти на каждой итерации, а не храниться в регистре, из-за хранилищ релизов. И поскольку это крошечная программа, все глобальные переменные, вероятно, находятся рядом с каждым другое, и, вероятно, в той же строке кэша.)
std::vector также не требуется . __rdtsc() не будет равным нулю, если он не оборачивается вокруг 64-битного счетчика 1 , поэтому вы можете просто использовать 0 в качестве контрольного значения в скаляре uint64_t, что означает пустой. Или, если вы исправите блокировку, чтобы считыватель не мог повторно войти в критическую секцию без поворота писателя, вы можете удалить эту проверку.
Сноска 2: Для эталонной частоты TS ~ 4 ГГц C , это 2 ^ 64/10 ^ 9 секунд, что достаточно близко к 2 ^ 32 секундам ~ = 136 годам, чтобы обернуть TS C. Обратите внимание, что эталонная частота TS C равна не текущей тактовой частоте ядра; это фиксированное значение для данного процессора. Обычно близка к номинальной частоте «стикера», а не к максимальному турбо.
Кроме того, имена с начальным _ зарезервированы в глобальной области видимости в ISO C ++. Не используйте их для собственных переменных. (И, как правило, нигде. Вы можете использовать вместо этого завершающий символ подчеркивания, если хотите.)