Торопиться не надо… (Про спинлоки)

Из к\ф Кавказская пленницаИз к\ф Кавказская пленница

После небольшой статьи про особенности при работе с кэшем мне в личку прилетело несколько замечаний про работу спинлоков и приглашение на собес от пчелайнов, приятно, что чисто технические статьи читают не только технари… лирика. Возвращаясь к обсуждению спинлоков, вышедших за рамки хабра, если это вызвало интерес, почему бы не написать про работу с этими примитивами синхронизации. Тема действительно интересная, да и разработчики придумали более десятка разновидностей спинлоков под разные вкусы и нужды. Все опять будет с тестами и примерами работы. @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            3
1,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;

  • спинлоки с бэкофф и рандом ожиданием, позволяют написать простую приоритезацию;

  • тикет-спинлок распределяет ресурс справедливо между потоками.

З.Ы.

© Habrahabr.ru