Торопиться не надо… (Про спинлоки)
Из к\ф Кавказская пленница
После небольшой статьи про особенности при работе с кэшем мне в личку прилетело несколько замечаний про работу спинлоков и приглашение на собес от пчелайнов, приятно, что чисто технические статьи читают не только технари… лирика. Возвращаясь к обсуждению спинлоков, вышедших за рамки хабра, если это вызвало интерес, почему бы не написать про работу с этими примитивами синхронизации. Тема действительно интересная, да и разработчики придумали более десятка разновидностей спинлоков под разные вкусы и нужды. Все опять будет с тестами и примерами работы. @tbl Линус действительно прав, в юзерспейсе спинлоки «зло злющее», но есть нюансы…
Мое первая встреча со спинлоком в жизни (на самом деле нет, но раньше я об этом не задумывался) произошла в прачечной общежития альма матер (ИТМО) — это было сродни лотерее плюс тактика пустынных сусликов, которые высматривают хищника. В прачечной стояло 5 стиральных машин и два сушильных автомата плюс табличка с временем записи, сначала надо записаться в конец очереди и поставить время когда придешь, потом к этому времени прийти (что тоже не всегда удавалось), но прийдя вовремя ты понимаешь, что все стиральные машины еще (уже) забиты чьей-то одеждой, и в очереди может быть плюс-минус несколько человек. Тут можно посидеть-подождать, пока странные китайцы из комнаты напротив соседи вытащат свои вещи, или можно уйти в комнату и спуститься минут через десять, надеясь, что никто «умный» не перескочит через свою очередь. На третий подход стиральная машина оказывается свободна и наконец вещи загружены, теперь можно вернуться на полчаса в комнату и дождаться окончания стирки или подождать тут-же играя в змейку на новеньком nokia 3310. Поход в комнату может окончиться тем, что влажная одежда будет лежать в общей корзине «свежепостиранных вещей», тот же квест надо пройти с сушильным автоматом, только их два и количество проверок рандомное, потому что на сушилки таблички с записью нет. Проверяем сушилки каждые полчаса, и вуаля… через три часа и «сэм-восэм» походов белье чистое, а компенсацией за потерянное время комплектом идет чей-то желтый носок со слоником, который обнаруживается уже в комнате. Вот так можно ощутить себя человеком-спинлоком со временем проверки плюс-минус десять минут, а ресурсом будет стиральная машина.
Есть два типа ожидания ресурса, блокирующее и неблокирующее.
Блокирующее ожидание (mutex, critical section) остановит поток до освобождения ресурса на уровне ОС, это полезно, потому что при блокировка реализована средствами самой ОС и потребляет незначительные ресурсы компьютера. Также планировщик может учитывать приоритеты такого ожидания, или приоритеты потоков, использующих это ожидение. Такая блокировка оставляет процессор свободным для выполнения других задач, включая любые другие задачи, даже те, которые непосредственно владеют блокировкой. Однако стоит все это дорого по времени, в основном изза блокировки потоков-претендентов на уровне ОС. Такие блокировки, мьютексы/критические секции следует использовать, когда время выполнения работы значительно больше затрат на остановку потока, например, операции ввода-вывода, обращение к ядерным функциям ОС или стирка в прачечной университетской общаги. Если интересно, работу мьютексов можно будет обсудить чуть позже, а пока про спинлоки.
Неблокирующее ожидание (spinlock) будет проверять некоторое условие в бесконечном цикле. Это тоже полезно, потому что может возобновить работу потока на следующем такте процессора, это ничего не стоит ОС и требует минимальных усилий со стороны разработчика, и абсолютно непрозрачно планировщику, который видит только активную работу кучи тредов. Еще бОльшим недостатком будет то, что активный поток может в худшем случае не дать cpu выполнять другую работу. Если задача в потоке требует длительных вычислений, то остальные потоки потратят непропорционально много времени на ожидание, а не на его выполнение, при этом занимая процессор как обычные потоки. Как правило, спинлок используется для коротких защит, например, при чтении или записи критической структуры данных.
Разработчики придумали достаточное количество спинлоков, давайте посмотрим как это все работает.
Реализация в лоб
Начнем с простой реализации, атомарная переменная выступает гарантом ожидания (на самом деле можно написать такой код, который сломает это условие и спинлок работать не будет, но это другая история). Использование атомарной переменной делает операцию чтения-изменения-записи текущего состояния блокировки неделимой (т. е. чтение состояния переменной, изменение его на другое и запись его в память — это одна операция, во время которой поток не может быть прерван). Если не использовать атомарную переменную, составляющие операции чтение-изменение-записи могут быть приостановлены, что приведет к одновременному захвату блокировки несколькими потоками. В C++ вообще любая операция считается неатомарной до тех пор, пока это не будет явно указано прозводителем компилятора и аппаратной платформы — даже обычное присваивание pod типов.
struct naive_spinlock_tas {
std::atomic locked{false};
#define do_nothing
void lock() { for (; locked.exchange(true) ;) do_nothing; }
void unlock() { locked.store(false); }
}; Код бенчмарка
void naive_spinlock_inc(naive_spinlock_tas &s, s64 &val) {
for (int i = 0; i < 100000; i++) {
s.lock();
val++;
s.unlock();
}
}
static void naive_spinlock_bench(benchmark::State &s) {
const u32 bench_threads = s.range(0);
s64 val = 0;
std::vector thread_pool;
thread_pool.reserve(bench_threads);
naive_spinlock_tas sl;
for (auto stage : s) {
for (u32 i = 0u; i < bench_threads; i++) {
thread_pool.emplace_back([&] { naive_spinlock_inc(sl, val); });
}
for (auto &thread : thread_pool)
thread.join();
thread_pool.clear();
}
}
BENCHMARK(naive_spinlock_bench)
->RangeMultiplier(2)
->Range(1, std::thread::hardware_concurrency())
->UseRealTime()
->Unit(benchmark::kMillisecond); ----------------------------------------------------------------------------
Benchmark Time CPU Iterations
----------------------------------------------------------------------------
naive_spinlock_bench/1/real_time 1.49 ms 0.066 ms 471
naive_spinlock_bench/2/real_time 6.31 ms 0.143 ms 109
naive_spinlock_bench/4/real_time 23.7 ms 0.000 ms 28
naive_spinlock_bench/8/real_time 86.4 ms 0.000 ms 9
naive_spinlock_bench/16/real_time 349 ms 0.000 ms 2
naive_spinlock_bench/24/real_time 670 ms 0.000 ms 1
// Просто посчитать в два раза больше будет быстрее, чем в двух потоках
---------------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------------
naive_spinlock_bench/1/real_time 2.46 ms 0.053 ms 294Если мы хотели сделать какую-то работу и понадеялись, что удвоение количества потоков уменьшит время выполнения, то видим что этого не произошло. Вместо этого, 2-поточный тест занимает в 3 раза больше времени, чем однопоточный. С оговоркой конечно, тест очень синтетический, но показывает возможный тренд при работе с данными, которые плохо параллелятся. Причины такого поведения я разобрал в прошлой статье — при обновлении атомарной переменной происходит сброс и обновление кэшлинии в других ядрах, которые с ней работают. При такой реализации спинлока, получаем что промахиваются 2 запроса из 3 в кэше
124,334,591 L1-dcache-loads # 14.438 M/sec
78,181,819 L1-dcache-load-misses # 62.88% of all L1-dcache hits Спинлок получше
struct better_naive_spinlock_ttas {
std::atomic locked{false};
#define do_nothing
void lock() {
while (true) {
if (!locked.exchange(true)) return;
while (locked.load()) do_nothing;
}
}
void unlock() { locked.store(false); }
}; Попробуем избавиться от кэшмисов и увеличить полезную работу блокировки, для этого не будем постоянно пробовать изменить переменную, а дождемся её освобождения. Когда переменная освободится пробуем заново, потому что ктото может заблокировать её раньше. Все что мы сделали, это заменили атомарную попытку записи на чтение. Это хорошо тем, что доступные только для чтения копии кэша могут одновременно существовать в нескольких разных ядрах без дополнительных затрат. Локальную копию атомарной переменной ядро читает из собственнлого кэша L1, порядок освобождения блокировки становится уведомительным и снижается число промахов кэша.
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------------------------
better_naive_spinlock_bench/1/real_time 1.53 ms 0.066 ms 475
better_naive_spinlock_bench/2/real_time 6.79 ms 0.267 ms 117
better_naive_spinlock_bench/4/real_time 18.9 ms 0.000 ms 36
better_naive_spinlock_bench/8/real_time 44.5 ms 0.000 ms 16
better_naive_spinlock_bench/16/real_time 106 ms 0.000 ms 7
better_naive_spinlock_bench/24/real_time 246 ms 0.000 ms 31,296,553,727 L1-dcache-loads # 253.267 M/sec
80,252,055 L1-dcache-load-misses # 6.22% of all L1-dcache hitsПоложительно это сказалось и на времени выполнения, на двух потоках этого не видно, но начиная с 4 и более потоков видим значительное снижение времени выполнения каждого потока. Относительно небольшое изменение в коде привело к росту производительности, тем не менее есть еще возможности для улучшения.
Торопиться вредно
Смотрю на реализацию ожидания и понимаю, что вычитывать каждый такт значение блокировки нет смысла, поток выполняет некоторую работу, которая занимает время. Возьмем условные 24 ядра, положим что поток выполняет сложные вычисления (перебор массива) и не будем на это время опрашивать блокировку.
struct waiting_spinlock_ttas {
std::atomic locked{false};
#define do_nothing
void lock() {
for (;;) {
if (!locked.exchange(true)) return;
for (; locked.load();){
for (volatile s32 i = 0; i < 24 * 100 ; i += 1) do_nothing;
}
}
}
void unlock() { locked.store(false); }
}; Эта оптимизация значительно уменьшает время выполнения потока, мы дали cpu возможность делать то, что он умеет — считать… volatile тут нужен, чтобы не дать компилятору выкинуть этот цикл, который просто ждет и жжет электричество.
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------------------------
waiting_spinlock_ttas_bench/1/real_time 1.50 ms 0.000 ms 477
waiting_spinlock_ttas_bench/2/real_time 3.34 ms 0.224 ms 209
waiting_spinlock_ttas_bench/4/real_time 8.01 ms 0.000 ms 84
waiting_spinlock_ttas_bench/8/real_time 26.5 ms 0.000 ms 26
waiting_spinlock_ttas_bench/16/real_time 73.0 ms 0.000 ms 9
waiting_spinlock_ttas_bench/24/real_time 116 ms 0.000 ms 6вместо do_nothing можно подставить инструкцию _mm_pause (), убираем volatile за ненадобностью, тогда ожидание будет еще менее агрессивным, что конечно же положительно скажется на перфе. Чем меньше работы мы делаем, тем больше работы мы делаем :)
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------------------------
waiting_spinlock_mmps_bench/1/real_time 1.50 ms 0.000 ms 460
waiting_spinlock_mmps_bench/2/real_time 2.95 ms 0.135 ms 231
waiting_spinlock_mmps_bench/4/real_time 5.59 ms 0.124 ms 126
waiting_spinlock_mmps_bench/8/real_time 11.3 ms 0.504 ms 62
waiting_spinlock_mmps_bench/16/real_time 22.9 ms 1.01 ms 31
waiting_spinlock_mmps_bench/24/real_time 34.9 ms 0.781 ms 20Понимание того, как наши потоки взаимодействуют друг с другом, имеет решающее значение для поиска возможностей оптимизации. Но и в текущей реализации есть еще место для улучшения. Смотрим что там с кэшмисами — менее одного процента, а мы всего лишь убрали агрессивное чтение данных из кэша.
16,743,277,459 L1-dcache-loads # 1266.561 M/sec
86,735,606 L1-dcache-load-misses # 0.51% of all L1-dcache hitsКомпиляторы очень умные, но они не сделают за нас анализ области применения, также есть инструкции которые они вставляют очень редко, вроде _mm_pause ().
Можно ли лучше?
Можно, но уже появляются нюансы, нужно смотреть сам алгоритм, где применяется спинлок. Для конкретного случая с инкрементом переменной будет полезным разнести проверки блокировок по времени, что будет если два потока попробуют захватить блокировку в один момент? Оба проверят что блокировка активна и уйдут в ожидание на одинаковое время, с большой долей вероятности они также выйдут в одинаковое время и опять столкнутся. Чем больше таких потоков, тем меньше вероятность нормальной работы. Это можно избежать если выбирать случайное время ожидания.
struct random_spinlock_ttas {
std::atomic locked{false};
std::uniform_int_distribution dist;
std::mt19937 rng;
random_spinlock_ttas() {
rng.seed(std::random_device()());
dist = std::uniform_int_distribution(1024, 2048);
}
void lock() {
for (;;) {
if (!locked.exchange(true)) return;
for (; locked.load();){
s32 backoff_iters = dist(rng);
for (int i = 0; i < backoff_iters; ++i) _mm_pause();
}
}
}
void unlock() { locked.store(false); }
}; Бенчмарк показывает, что мы выиграли еще 10% времени выполнения. Но бенчмарк и тесты не гарантируют такого же результата в приложении. Я привел этот пример, чтобы показать что знание области применения блокировки укажет на возможности для оптимизации конкретных случаев, но нет гарантии, что применение такой блокировки в общих алгоритмах приведет к похожему результату.
------------------------------------------------------------------------------------
Benchmark Time CPU Iterations
------------------------------------------------------------------------------------
random_spinlock_ttas_bench/1/real_time 1.52 ms 0.028 ms 568
random_spinlock_ttas_bench/2/real_time 2.80 ms 0.157 ms 274
random_spinlock_ttas_bench/4/real_time 5.63 ms 0.131 ms 135
random_spinlock_ttas_bench/8/real_time 10.5 ms 0.414 ms 73
random_spinlock_ttas_bench/16/real_time 19.5 ms 0.434 ms 36
random_spinlock_ttas_bench/24/real_time 29.9 ms 1.04 ms 23Анализ данных по кэшмисам дает понимаение, за счет чего получено снижение времени выполнения потока. Обновление переменной в кэше L1 еще менее агрессивное (0.42% промахов), меньше накладных расходов и задержек, за счет чего cpu выполняет больше работы. Это не так наглядно на малом количестве потоков, но с ростом их числа становится все более заметно.
17,543,234,558 L1-dcache-loads # 1296.631 M/sec
74,638,504 L1-dcache-load-misses # 0.42% of all L1-dcache hitsЧто не так с этой реализацией спинлока
В погоне за лучшим временем выполнения можно испортить общую картину, ведь потоки выполняют какую-то нужную работу. Попытки снизить время ожидания в потоке, приведут к «ненамеренной приоритезации» потоков, которые получили меньше время ожидания. Например в спинлоке со случайным временем ожидания приоритет получат те потоки, чье время ожидания меньше. В случае с постоянным временем ожидания приоритет получают потоки, которые пришли раньше, этот эффект называет «starvation» — голодание, некоторым потокам достается значительно меньше времени выполнения. В любой реализации спинлока на основе активного ожидания этот эффект будет проявляться больше или меньше, и часть потоков будут простаивать. Можно частично поправить эту ситуацию, взяв на себя задачу планировщика, но опять же это нюансы и надо понимать ЧТО мы делаем и какое поведение хотим получить в итоге. Чтобы потоки не мигрировали, надо закрепить поток за конкретным ядром. Если панировщик свободен в выборе ядра для потока, то при зажатой спинблокировке на одном ядре могут крутиться несколько потоков друг за другом увеличивая общее время выполнение. Когда потоки распределены по ядрам, то они получает свой таймфрейм практически в порядке очереди на этом ядре, меньше затрат на перенос контекста между ядрами. Негативным эффектом такого подхода будет грубое вмешательство в работу планировщика (это не всегда плохо, по рассказам коллег на PS5 ужасный планировщик)
В большинстве игровых движков потоки звука, рендера, ввода-вывода закреплены за конкретными ядрами для избежания сайдэффектов миграции.
Переписав код бенчмарка с установкой аффинити для потока
for (auto stage : s) {
for (u32 i = 0u; i < bench_threads; i++) {
thread_pool.emplace_back([&] { waiting_spinlock_affn_inc(sl, val); });
SetThreadAffinityMask(thread_pool.back().native_handle(), DWORD_PTR(1) << i);
}
for (auto &thread : thread_pool)
thread.join();
thread_pool.clear();
}получаем следующий результат, общее время выполнения снизилось для большого числа потоков. Но там уже вылезают эффекты обновления данных в кэшах ядер (сравниваем эти данные с waiting_spinlock_mmps_bench), которые нивелируют эффект от растаскивания потоков по ядрам
-----------------------------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------------------------
waiting_spinlock_affn_bench/1/real_time 1.59 ms 0.000 ms 580
waiting_spinlock_affn_bench/2/real_time 2.70 ms 0.000 ms 254
waiting_spinlock_affn_bench/4/real_time 6.18 ms 0.138 ms 113
waiting_spinlock_affn_bench/8/real_time 9.81 ms 0.781 ms 80
waiting_spinlock_affn_bench/16/real_time 19.9 ms 0.000 ms 34
waiting_spinlock_affn_bench/24/real_time 30.7 ms 0.710 ms 22Не все спинлоки одинаково полезны
Есть ряд задач, где использование спинлока на основе активного ожидания вредно или вообще недопустимо (например задачи параллельной загрузки данных), когда выполнение следующего этапа зависит от результатов вычислений предыдущего (раскинутого по нескольким потокам). Чтобы обеспечить равномерный доступ к ресурсу (например файловая система), надо организовать такой спинлок который не зависит от скорости его блокировки, а предоставляет последовательный доступ к ресурсу каждому из потоков. _ReadWriteBarrier() вызов нужен, чтобы компилятор гарантированно вызвал unlock () после lock (), не напортачив при включенной оптимизации.
struct ticket_spinlock_ttas {
std::atomic waiter{0};
volatile u16 dish{0};
void lock() {
auto my_dish = waiter.fetch_add(1);
#define do_nothing _mm_pause()
while (dish != my_dish) do_nothing;
}
void unlock() {
_ReadWriteBarrier();
dish = dish + 1;
}
}; Спинлок на основе тикетов дает возможность потокам спокойно ждать блокировки. Общая производительность конечно пострадает, по сравнению любой другой реализацией, но каждый тред получил свой таймфрейм для работы. Время выполнения — не единственная метрика на которую надо ориентироваться, во многих задачах нужен компромисс между временем выполнения и общим прогрессом, особенно это проявляется на связанных задачах, когда начало одних зависит от завершения других.
-----------------------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------------------
ticket_spinlock_bench/1/real_time 1.45 ms 0.024 ms 651
ticket_spinlock_bench/2/real_time 11.9 ms 0.000 ms 67
ticket_spinlock_bench/4/real_time 53.5 ms 0.000 ms 10
ticket_spinlock_bench/8/real_time 220 ms 0.000 ms 3
ticket_spinlock_bench/16/real_time 635 ms 0.000 ms 1
ticket_spinlock_bench/24/real_time 905 ms 0.000 ms 1Реализацией из pthread
Для сравнения c миром честных блокировок ОС возьмем стандартную реализацию pthread (Windows) (https://github.com/GerHobbelt/pthread-win32), и запустим бенчмарк. Спинлок в pthread реализован через виндовый CRITICAL_SECTION, поэтому все радости накладных расходов в виде context switch, парковки тредов и работы планировщика в полном объеме.
pthread_spinlock_t sl;
pthread_spin_init(&sl, PTHREAD_PROCESS_PRIVATE);
void pthread_spinlock_inc(pthread_spinlock_t &sl, s64 &val) {
for (int i = 0; i < 100000; i++) {
pthread_spin_lock(&sl);
val++;
pthread_spin_unlock(&sl);
}
}Низкое время на одном потоке, объяснить не могу. Походу какие-то трюки ОС, когда нет претендентов на критическую секцию. На двух и более потоках результат близок к самой простой реализации, за тем исключением, что нет нагрузки на cpu, об этом я написал в начале статьи.
------------------------------------------------------------------------------
Benchmark Time CPU Iterations
------------------------------------------------------------------------------
pthread_spinlock_bench/1/real_time 0.70 ms 0.147 ms 826
pthread_spinlock_bench/2/real_time 6.07 ms 0.000 ms 115
pthread_spinlock_bench/4/real_time 22.3 ms 0.504 ms 31
pthread_spinlock_bench/8/real_time 119 ms 0.000 ms 6
pthread_spinlock_bench/16/real_time 341 ms 0.000 ms 2
pthread_spinlock_bench/24/real_time 606 ms 0.000 ms 1Вместо выводов
Для написания функционально правильной реализации спинлока требуется не так уж много в плане кода, но нужно тщательно обдумывать где она будет применяться, чтобы сделать ее с хорошей производительностью и/или гарантированными задержками. Библиотечная реализация (или общие реализации) не всегда является хорошим выбором для повышения производительности. Я уверен что изучив конкретную область применения, вы сможете написать собственную реализацию, которая лучше всего подходит для конкретной ситуации.
простой спинлок без ожидания — позволяет максимально быстро захватить ресурс и свободен от эффекта приоритезации;
спинлок с константным ожиданием позволяет потоку выполнять больше работы, не сильно нагружая cpu;
спинлоки с бэкофф и рандом ожиданием, позволяют написать простую приоритезацию;
тикет-спинлок распределяет ресурс справедливо между потоками.
