Хабр Курсы для бэкендеров
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 33
Дошёл пока только до этого:
несвоевременное вытеснение потока после захвата критической секции
И вопрос: а если бы там не было критической секции, его бы не вытеснило? Или вытеснило бы с гораздо меньшей вероятностью? Или что? Непонятно.
Речь шла не о вероятности вытеснения как таковой, а последствиях вытеснения в неудачный момент при использовании классического подхода на мьютексах.
Так чем же последствия в этом случае хуже, чем последствия вытеснения на таком же участке аналогичного кода с lock-free вариантом?
Я отнюдь не спорю, я лишь хочу, чтобы вы четко и ясно объяснили различия.
Разница в том, что вытесненный поток, исполняющий lock-free алгоритм над разделяемой между потоками структуре, не провоцирует блокировку (внужденный уход в спячку) других потоков, конкурирующих за доступ к этой структуре.
Прошу пояснить саму причину этого вопроса - из текста статьи был не понятен сценарий, при котором вытесненный поток, владеющий мьютексом (или критической секцией) блокирует остальные потоки, которым нужен тот же самый ресурс?
Я исходил из того, что проблематика эта известная, поэтому считал, что достаточно упомянуть сам сценарий, который является основным мотивом применения lock-free структур.
Разница в том, что вытесненный поток, исполняющий lock-free алгоритм над разделяемой между потоками структуре, не провоцирует блокировку (внужденный уход в спяку) других потоков, конкурирующих за доступ к этой структуре.
Если говорить об абстрактных конях в вакууме, то есть некий общий ресурс R, к которому хотят обратиться потоки T1, T2, T3. На “тяжелых” примитивах синхронизации T1 захватывает замок ресурса R после чего ОС снимает T1 с CPU. Когда потоки T2 и T3 пытаются захватить тот же самый замок ресурса R, то ОС их приостанавливает и ставит в очередь. Полезной работы T2 и T3 не делают пока T1 не проснется и не освободит замок R.
В случае с lock-free T1 начинает операцию с R и выставляет какие-то атомарные флаги, которые говорят, что R в данный момент принадлежит T1. После чего ОС снимает T1 с CPU. Когда потоки T2 и T3 захотят получить доступ к R они увидят те самые атомарные флаги, выставленные T1 и войдут в цикл ожидания. Однако, полезной работы T2 и T3 не делают, пока T1 не проснется и не освободит R.
С этой точки зрения нет особой разницы, будут ли T2 и T3 честно спать в каких-то очередях ОС, или же они будут крутить циклы с чтением атомиков.
Поэтому сделаное в статье введение и вызывает вопрос, озвученный @dyadyaSerezha.
В случае с lock-free T1 начинает операцию с R и выставляет какие-то атомарные флаги, которые говорят, что R в данный момент принадлежит T1. После чего ОС снимает T1 с CPU. Когда потоки T2 и T3 захотят получить доступ к R они увидят те самые атомарные флаги, выставленные T1 и войдут в цикл ожидания. Однако, полезной работы T2 и T3 не делают, пока T1 не проснется и не освободит R.
Спасибо, теперь вопрос понятен.
Ответ: в случае lock-free T1 никогда не переводит общую структуру в такое состояние, в котором структура "принадлежит" выделенному потоку. В любой момент времени структура доступна конкурирующим потокам Tn согласно обещанной модели потоковой безопасности.
Например, drain_stack является MPMC-структурой (Multiple Producers / Multiple Consumers), т.е. произвольное количество потоков могут одновременно писать и читать из этой структуры.
Далее, mpsc_queue обеспечивает уже другую дисциплину - Multiple Producers / Single Consumer. Писать в эту очередь может произвольное количество потоков, а читать только один (либо требуется синхронизация на стороне чтения).
И даже в случае SPSC сценария (один писатель и один читатель), всё еще присутствует межпоточная конкуренция за ресурс между писателем и читателем, пусть даже конкуренция за каждую из операций записи и чтения ограничена одним участником.
Поэтому сделаное в статье введение и вызывает вопрос
Про введение понятно, оно заведомо ограничено по объёму, и ставит целью кратко обрисовать проблематику.
Вызывает ли дополнительные вопросы материал, начинающийся со слов "хотелось бы принципиально другого поведения: чтобы поток, положивший элемент в очередь, физически не мог заблокировать того, кто пытается положить следующий или прочитать имеющийся"?
Вызывает ли дополнительные вопросы материал, начинающийся со слов “хотелось бы принципиально другого поведения: чтобы поток, положивший элемент в очередь, физически не мог заблокировать того, кто пытается положить следующий или прочитать имеющийся”?
Это вряд ли ко мне вопрос.
С моей колокольни тут важнее бы поставить акцент на то, про какую блокировку идет речь – блокировка потока на уровне ОС (т.е. физическая) или же на уровне прикладной логики (т.е. логическая).
Т.к. с точки зрения прикладной логики пока поток крутится на атомарных чтениях в ожидании пока очередь перестанет быть пустой, то логически он заблокирован и полезной работы не делает.
Соответственно, тут важный вопрос: если очередь пуста, мы ничего полезного не делаем, а тупо жгем электричесво в цикле на атомарном чтении, то в чем выгода от использования lock-free в сравнении с “тяжелыми” и “честными” примитивами? И если статья вводная, то можно было бы пару слов сказать, чтобы эти самые выгоды lock-free явным образом озвучить.
"Голая" очередь spsc_queue ничего не знает про распределение ресурсов ОС. Её задача — обеспечить максимум пропускной способности когда данные есть.
Если данных нет, крутиться в цикле 10 GOTO 10 и жечь электричество — это удел либо HFT-систем, либо не до конца проработанных библиотек. Пример — популярный логгер quill. В базовых сценариях он именно так себя и ведет: ему монопольно отдают целое ядро процессора, и он полирует пустую очередь в своём spin-wait. В реальном телекоме (например, в софте для базовых станций, не буду покаывать пальцем, хотя ты в курсе, о ком речь) такое встречается сплошь и рядом просто потому, что низкоуровневой оптимизацией там часто некому заняться. Да и в целом выглядит так, что всем несколько пофик - высокоуровневые спецы там лишние, потому что код надо будет обслуживать армией "обычных разработчиков" - такова забавная политика отечественного софтостроения.
В масштабируемой архитектуре поверх очереди садится компонент spsc_channel, который решает эту проблему через ленивый протокол arm / disarm:
Когда читатель видит, что очередь пуста, он не крутится в цикле бесконечно (для HFT обычно ограничивают холостые обороты в 10 микросекунд - за это время успевает "остыть" память, т.е. дальше жечь ресурсы обычно нет смысла по причине особенностей современного железа). Читатель переводит канал в состояние
arm(«взводит курок») и делает финальную проверку.Если данных всё еще нет, читатель уходит в сон на системном примитиве (будь то futex, event, семафор, поток со множеством сокетов на epoll/IOCP), освобождая ресурсы другим страждущим.
Писатель на своем горячем пути просто бросает данные в блоки. Он выполняет системный вызов пробуждения (wake) только тогда, когда видит флаг
arm(то есть знает, что читатель точно спит и его точно надо пнуть).
В итоге получаем лучшее из обоих миров:
На горячем пути (всплеск трафика): Полный lock-free, ноль системных вызовов, даже минимум interlocked-операций и невероятная пропускная способность, от озвучивания цифр которой икают те, "кто в теме".
В моменты "простоя" (собщения приходят реже, чем раз в 20+ микросекунд): канал отдаёт ресурсы другим участникам, которые за столь ужаcно долгое время (по меркам lock-free) успевают сделать массу полезной работы.
Т.е.за цену базовой механики многих популярных диспетчеров можно выполнить вообще всю полезную бизнес-логику.
А освободившиеся ресурсы можно отдать под числодробления (тоже правильно организовав граф скольжения данных, ес-но), т.е. под то, для чего современные мощности и нужны, собсно.
«Тяжелые» примитивы (вроде std::mutex / std::condition_variable) на горячем пути неприменимы, потому что любой mutex при конкуренции уводит поток в контекст-свитч ядра ОС. Это потеря от 500 до 2000 нс на каждое переключение, если произошло столкновение на критической секции. В грамотно раскиданном lock-free за время одного такого системного "вздоха" успевается обслужиться сотни прикладных сообщений.
Про детальную математику протокола arm/disarm и защиту от гонок в момент засыпания подробно будет. Оно того стоит, ИМХО. Очень просто, сама идея "на поверхности", но в реальном софте применяется на удивление редко.
Т.е. в сухом остатке речь идет о стоимости “пробуждения” нити, которая была вынуждена ждать. В случае, если мы честно физически заснули на “тяжелом” примитиве ОС, то разбудить заснувший тред дорого. Тогда как если вместо “сна” мы в цикле делаем опрос, то при обнаружении готовности (не пустоты) очереди мы тут же начинаем обработку без дополнительных дорогих телодвижений.
Эти рассуждения зависят от реальный таймингов операций. Да, регулярный заход в ядро и обратно на одном и том же примитиве — примерно микросекунда (плюс‑минус полтора раза), если редко — уже под 5–10 микросекунд.
Доступ к горячей памяти — почти ноль наносекунд (от долей одной до полутора). Доступ к остывающей ухудшается ступеньками, смотря из какого уровня кеша успели улететь. Причём, улетают тоже ступеньками — через 10 микросекунд деградация из L1 в L2, через 40–50 микросекунд деградация до L3, через 100+ микросекунд гарантированно вымывает из кеша проца.
Поэтому, простое спин‑ожидание даёт аж ничего. Да, чтение одной изолированной ячейки из холодной RAM — это под 100 наносекунд. Но в реальном приложении поток обрабатывает не одно число, а графы объектов. В зависимости от лейаута в памяти чтение сообщения порой превращается в последовательный обход цепочки указателей. Если эти структуры успели остыть, то каждый прыжок по ссылке генерирует свой независимый промах мимо кэша. В итоге суммарная задержка на расковыривание холодного и кучерявого бизнес‑объекта (банально просмотр строки длиннее 15 символов, то есть которая уже в куче) легко набегает на 4–5 микросекунд при средних паузах и улетает далеко за 10 микросекунд, если данные совсем вымыло из кэша.
Это сопоставимо с ценой захода в ядро ОС, что делает ожидание на примитивах сигнализации легальным и оно же диктует способ борьбы с ситуацией, если хочется тру спин‑лока: в HFT‑системах на спин‑ожиданиях гоняют по кругу так называемые «warmup»‑вызовы — это проход по реальному коду обработки приходящего пакета с флагом «warmup», то есть вся цепочка делает что и должна, но конечный результат никуда не отправляет или отправляет в юзер‑спейсный драйвер тоже с пометкой warup. И только тогда по приходу пакета можно уложиться в субмикросекундный полный цикл.
===
И да, любые такие рассуждения дожны отталкиваться от системы оценок - что именно мы оптимизируем? Если общую производительность, то увод простаивающего потока вычислений в сон - обязательная опция ради освобождения ресурсов. А когда оптимизируют только latency, выжимая лишние пару сотен наносекунд за счёт деградации общего throughput системы - я такое расточительство видел исключительно и только в HFT, и оно имеет смысл только если брокерские сервера физически ОЧЕНЬ близко расположены к серверами биржи - желательно в соседних стойках, как и организованы многие деривативные эти ипподромы лохотроны. ))
При этом, можно на архитектурном уровне так раскидать примитивы синхронизации, что они будут обслуживать "сразу всех" - например, как привязка кучи сокетов к одному потоку, тогда стоимость вечно горячего примитива сигнализации становится минимально возможной - до микросекунды, и основные тормоза получаются уже такие, на которые мы не можем повлиять - это простые тормоза простого доступа к памяти у остывших блоков.
Спасибо, вот теперь всё вроде понятно. Но порадовало это:
Если данных нет, крутиться в цикле 10 GOTO 10 и жечь электричество — это удел либо HFT-систем…
Вау, HFT на Фортране, это круто)
Моя статья описывает и решает ровно ту же проблему - объединить преимущества lockfree с блокировка и.
По моему опыту это ситуация либо надуманная пугалка (критические секции маленькие => вероятность ухода из критической секции низка) или корне-кейс (свойство алгоритма таково, что критические секции большие).
Абсолютно верно. Нас интересует только вероятность столкновения, а это отношение длительности окна потенциального конфликта к периоду обращений.
Поэтому, если обращение к ресурсу относительно редкое (относительно длительности этого обращения), то современные критические секции, исполняющие основную работу в user-кольце, показывают себя замечательно.
Для задачи передачи сообщений между потоками лучше подходят wait-free алгоритмы. Например, циклический буфер с барьерами памяти. А у вас пишущие треды постоянно пишут и читают одну и ту же кеш линию с соответствующими последствиями. Плюс связный список люто фрагментируется и кушает память.
Про это будет отдельная статья, но прямо сейчас уже можно посмотреть исходник spsc-очереди. У простой круговой очереди есть свой "фатальный недостаток", который требует обыгрывания. Показанная реализация spsc-очереди вообще не использует interlocked-операции и на x86/x64 код работает на простых ассемблерных инструкциях mov.
И да, утверждение про wait-free достаточно сильное. В теории wait-free для MPSC существует и даже как-то работает... ))
Но на практике, в реальном высоконагруженном продакшене, истинный wait-free для MPSC неэффективен из-за логики координации писателей. Попытка гарантировать wait-free для писателей накладывает свой оверхед на координацию потоков, из-за чего очередь начинает проигрывать обычному lock-free с CAS-циклом.
Одним словом, в обычном сценарии, когда в очередь пишут единицы потоков (2-4), да еще с соблюдением рекомендаций из данной статьи (делать как можно больше полезного с локальными данными между обращениями, например, проверить неблокирующий сокет насчёт следующего пакета, особенно это полезно с user-space драйверами, дающими буквально десятки-сотни ns задержек от аппаратуры), выбор однозначен и был обкатан более чем десятилетием реальной эксплуатации в самом требовательном к задержкам современном сегменте IT.
Зато в "тепличном" сценарии spsc, т.е. когда координация писателей не нужна, wait-free spsc-очередь показывает фантастические ~2 млдр элементов в секунду (перекачка данных между потоками) на моём не самом новом PC. Обычный кольцевой буфер так не сможет из-за постоянных промахов по кэшу.
И вдогонку, wait-free алгоритмы можно рассматривать как подмножество lock-free алгоритмов, поэтому они будут даны в одном цикле статей.
Не надо писателей координировать, надо для каждой пары тредов иметь отдельную spsc очередь. А читатель может выгребать сообщения из них в любом нужном ему порядке. Так можно хоть mpmc каналы организовывать.
Чем больше полезного ты делаешь в cas цикле, тем больше вероятность, что это полезное окажется бесполезным из-за конфликта и придется повторять.
Откуда вы взяли кэш промахи у кольцевого буфера? Там все обращения к памяти предсказуемо последовательны и не пересекаются между потоками.
wait-free гарантии более строгие, чем lock-free, но это не делает их алгоритмы подмножествами друг друга. Они вообще о разном. Первые избегают конкуренции, что позволяет обоим потокам работать на максимуме возможного, в то время как вторые толпятся вокруг общей памяти, впустую тратя ресурсы на попытки что-то записать.
Не надо писателей координировать, надо для каждой пары тредов иметь отдельную spsc очередь. А читатель может выгребать сообщения из них в любом нужном ему порядке.
Это уже вопрос организации высокоуровневого графа обработки на основе имеющихся примитивов. Когда таких очередей более одной, то на каждой из них происходит опрос-ветвление. В реальных сценариях круговорота элементов из пула, т.е. производитель посылает блок памяти потребителю, тот обрабатывает и возвращает обратно в пул производителю, хорошо показала себя схема MPSC, потому что каждый может слать данные любому и получать обратно тоже от любого.
Но да, в некоторых сценариях (заведомо известное малое количество каналов, обычно 2-4 под спаренные +fall-back мультикасты), такая схема может быть немногим лучше MPSC, особенно если под такую задачу выделить ядро, которое никогда не уходит в спячку. Тут классический выбор между масштабируемостью и достижением субмикросекундных выигрышей за счёт отказа от оного.
Повторюсь, все "строительные блоки" для такой схемы есть, это уже сугубо архитектурная специфика под конкретные условия (выбранную функцию оптимизации системы).
Откуда вы взяли кэш промахи у кольцевого буфера?
Из замеров, причём задолго до того, как LMAX начал сам себя рекламировать и обманывать индустрию тем, что его решение лучшее. Это не так. Просто сама это индустрия не торопится делиться наработками.
Проблематика простого кругового буфера я-ля Disruptor:
Маленький кольцевой буфер стопорит писателя;
Большой кольцевой буфер постоянно инвалидирует кеш и имеет дело с холодной памятью;
Можно допилить алгоритм до возможности роста кругового буфера, но это будут лишние такты на каждую операцию и уменьшить буфер затем будет нельзя;
Однажды выросший на пике трафика маленький буфер потом до конца работы сервиса будет вести себя как большой буфер.
Чем больше полезного ты делаешь в cas цикле, тем больше вероятность, что это полезное окажется бесполезным из-за конфликта и придется повторять.
Если посмотреть на пакетную амортизацию показанной MPSC-очереди, которая забирает данные пачками, то более строго процесс на всплеске трафика выглядит так:
читатель забирает пачку через interlocked-операцию, эта операция "дорогая", потому что требует когерентности с писателем;
далее читатель разгребает свою пачку, в это время писатель пишет новые данные через CAS на каждй элемент;
Де-факто для писателя CAS оказывается дорогим только для первой операции после модицикации линейки кеша читателем (порядка 16-21 нс для соседа по гипертредингу или 40-60 нс для соседних ядер);
Остальные CAS-операции по кеш-линии, продолжащей принадлежать писателю, выходят "дешёвыми" - порядка 4-6 нс.
Т.е., строго говоря, амортизация затрат в схеме "забирать порциями" происходит как на стороне читателя, так и на стороне писателя. В статье это не отражено, т.к. это совсем уже тонкости, но кто углубится в происходящее, тот и сам увидит, что линия кеша принадлежит писателю монопольно в тот промежуток времени, пока читатель разгребает свою пачку.
Для сравнения, простой mov из/в ячейку кеша холодной (некогерентной) памяти занимает тоже порядка 20-40 нс - это если память уже в L1, но просто была "только что изменена" другим ядром.
Итого, когда читатель в круговом буфере догоняет писателя - они начинают бодаться за одну линейку кеша, поочерёдно задерживая друг друга, и стоимость получается мало отличима от простого CAS.
От хорошо спроектированной системы ожидается, чтобы читатель не тормозил писателя. Т.е., всей схеме более выгодно, чтобы читатель отставал от писателя хотя бы на две линейки кеша (если на одну, то он будет неизбежно набегать на первый элемент, пока писатель пишет последний).
В этом и состоит ловушка некоторых синтетических тестов, когда измеряют latency самой очереди в отрыве от остального: минимальное отставание читателя “сугубо по цифрам” обеспечивает минимальное latency, но при этом сам поток писателя начинает тормозить, что не измеряется такими тестами. Т.е., система в целом начинает работать хуже.
На монотонном графике нагрузок эта область видится как паразитное плоское плато на графике, которое тем шире, чем дешевле работа на стороне читателя в сравнении с писателем, и это тоже диктует сугубо архитектурные решения - какую часть работы выполнять на стороне писателя, а какую на стороне читателя.
"Срыв" с этого плато и выход на в разы более высокую производительность происходит скачкообразно - когда писателю удаётся на пару линий кеша оторваться от читателя.
Вдогонку, насчёт дефрагментации на интрузивных блоках. Тесты показывают полнейшую индифирентность к этому, зато чутко реагируют на степень разогрева памяти.
Например, возвращённый обратно в пул писателя блок памяти изымается из пула по дисциплине LIFO (сам пул - это и есть показанная mpsc-очередь, но работающая в режиме LIFO), т.е. для новой порции данных берётся самый горячий блок. В итоге, в устоявшемся режиме между участниками курсируют два самых разогретых блока памяти, где затраты на разыменование косвенной связи буферов в современной предвыборке и отсутствии промахов ветвления составляют что-то около 0.4 нс в среднем (т.е. почти всегда ноль - в этом и состоит работа предвыборки конвейера).
(выглядит как заявка на небольшую поясняющую статью, но мне кажется, что круг любопытных к таким тонкостям будет совсем узок)
Можно допилить алгоритм до возможности роста кругового буфера, но это будут лишние такты на каждую операцию и уменьшить буфер затем будет нельзя;
Лишние такты там только при переполнении. У писателя при этом есть выбор:
Подождать и сделать тем временем что-то другое (обратное давление).
Послать сообщение в другую, более свободную очередь (балансировка).
Создать ещё одну очередь и последним элементом закинуть ссылку на неё, тогда читатель, когда выгребет первую, переключится на следующую.
Если посмотреть на пакетную амортизацию показанной MPSC-очереди
линия кеша принадлежит писателю монопольно в тот промежуток времени, пока читатель разгребает свою пачку
Это так лишь в SPSC очереди.
Итого, когда читатель в круговом буфере догоняет писателя - они начинают бодаться за одну линейку кеша, поочерёдно задерживая друг друга, и стоимость получается мало отличима от простого CAS.
То есть в худшем случае будет стоимость одной CAS операции. В то время как CAS цикл в худшем случае даёт ситуацию, что читатель может вообще никогда не суметь прочитать данные из-за того, что они постоянно меняются писателями.
Вдогонку, насчёт дефрагментации на интрузивных блоках. Тесты показывают полнейшую индифирентность к этому, зато чутко реагируют на степень разогрева памяти.
Можно ссылку на эти тесты?
Это так лишь в SPSC очереди.
Я ждал этого замечания. ))
Когда стоимость операции помещения элемента в очередь составляет единицы наносекунд, то фактические столкновения писателей получаются довольно редкими. Высокооптимизированные сетевые API забирают каждый в своём потоке обычно не одно сообщение, а сразу несколько (обычно подписка на несколько мультикаст каналов) и запихивают их в очередь. И вот это запихивание нескольких элементов в очередь со стороны писателя почти всегда монопольное из-за своей малой длительности.
Т.е., дисциплина MPSC не означает, что происходят постоянные бодания, она означает гарантии.
Это как с ABA - в реальной работе она может не проявить себя ни разу часами и даже сутками. Но когда проявит - создаст ошибку. Т.е., все средства борьбы с ABA работают бОльшую часть времени вхолостую. Так и механика обыгрывания множества потенциальных писателей большую часть времени работают вхолостую, но обеспечивает корректность в редких случаях их столкновения.
То есть в худшем случае будет стоимость одной CAS операции.
Для писателя в MPSC ответ "да". Я лишь обратил внимание, что стоимость CAS-операции не константа, а зависит от фактического "бодания" за линейку кеша с разницей примерно в 5 раз.
В то время как CAS цикл в худшем случае даёт ситуацию, что читатель может вообще никогда не суметь прочитать данные из-за того, что они постоянно меняются писателями.
В показанном drain_stack читатель забирает всю пачку безусловным exchange.
Причём, я как раз экспериментирую со второй сигнатурой рядом, где забор пачки происходит как relaxed и без предварительного if - это для возможности расписать сценарий (при надобности), когда читатель уход в спячку не сразу, а после некоторого spin-ожидания.
Это для тех сценариев, где работа на стороне читателя очень дешевая, т.е. где вычислительная загрузка обоих плеч недостаточно сбалансирована - в таких сценариях читатель часто уходит в спячку и проигрывает по пропускной способности вариантам, где между потоками работает в разы более медленная очередь.
Т.е. вот вам приколы - более быстрое решение может замедлить всю систему, если неправильно её приготовить. ))
Можно ссылку на эти тесты?
https://github.com/dmitry-valyukov/wxl/blob/main/wxl.async/benchmarks/spsc_queues_benchmark.cpp
Собрать:
tools\build.ps1 -Config Release -Define WXL_BUILD_BENCHMARKS=ON -Target wxl.async.spsc-queues-benchmarkЗапустить:
build\x64\wxl.async\benchmarks\Release\wxl.async.spsc-queues-benchmark.exe
Чем больше писателей одновременно пишут и чем чаще они это делают, тем больше вероятность вызвать голодание читателя. CAS гарантирует прогресс лишь при равноправных участниках. Читатель же должен иметь больший приоритет, но это невыразимо в CAS семантике.
В циклическом буфере не нужны никакие CAS операции. Там как раз нет никакого бодания - каждый спокойно пишет в свою область памяти.
А сами не хотите запустить и выложить результаты?
Читатель же должен иметь больший приоритет, но это невыразимо в CAS семантике.
На это уже был дан ответ: "В показанном drain_stack читатель забирает всю пачку безусловным exchange."
В циклическом буфере не нужны никакие CAS операции. Там как раз нет никакого бодания - каждый спокойно пишет в свою область памяти.
Для схемы со множеством писателей (MPSC) обойтись без синхронизации резервирования позиций никак. Это требует либо CAS-цикла, либо атомарного инкремента (fetch_add). Поскольку на многих платформах прямого аппаратного fetch_add нет, его приходится выражать через тот же CAS-цикл, как я показал в статье (именно по этой причине и показал).
Т.е., твои рассуждения стоит скорректировать: «На платформах, где присутствует атомарный инкремент, дисциплину MPSC для круговой очереди можно реализовать без цикла ожидания CAS».
Т.е., для RISC-V начального уровня, ядер ARM версий до 8.1, MIPS с расширениями уровня 1 и прочих эти рассуждения не верны.
А сами не хотите запустить и выложить результаты?
Будет целая статья с разбором.
Подождите, а где САМОЕ ГЛАВНОЕ при использовании lock-free структур:
у вас в процессоре CAS или LL-SC (в первом случае у вас атомарные операции с гарантированным, пусть и медленным продвижением с вычислениями прямо в кэше, во втором - исполнение атомарной секциии может, и будет прерываться и уходить на переисполнение при завершением конкурирующей секции).
Не хотелось бы писать в статьях то, что пишут на всех углах. Целью было дать то, что обычно опускают.
Если возникнет интерес к методам обхода ABA, то разница между CAS и LL/SC обязательно будет подсвечена. Тем более, что она чудесно иллюстрирует принцип «ничего не бывает даром». Но по моему многолетнему опыту, глубокое погружение в микро‑тонкости ассемблера интересно немногим. А кому интересно - те и сами прекрасно справляются.
Зато конкретные приёмы, алгоритмы, общие подходы (в том числе уже архитектурного плана) и метрики из реальных сценариев — это всё не просто интересно, но и полезно на практике. Бери да используй как сам код, так и готовые знания. Ценностью является не понимание механики работы отдельной аппаратной инструкции, а то, какую пользу из неё можно извлечь на макро‑уровне.
Любое современное ноу‑хау в области lock‑free — это почти никогда не сами эти структуры (в этой области уже давно слишком «натоптано», и что‑то принципиально новое изобрести сложно) - это всегда удачно найденные точки приложения их в конкретных системах.
Моя цель — расширить кругозор интересующихся и сразу же дать возможность пощупать готовые решения. Отсюда необходимость хотя бы озвучить проблематику, а следом — принятые способы обыгрывания, подводные камни и их небесплатность: разруливание ABA (ручками либо за счёт слепоты LL/SC‑механизма), false‑sharing, дорогое обращение к ядру, мифы про всемогущий spin‑wait и так далее.
По всем этим вещам в тексте и обсуждених специально дано немного материала, почти «просто упоминание». Кому надо — найдёт и погрузится с нужной ему глубиной, это открытая информация (в идеале - самостоятельно погонять бенмарки, которые нарисовать под свои сценарии). Но без этих упоминаний теряется причинно‑следственная связь «проблема => решение (и почему именно такое)».
Глубокого рассмотрения популярных lock‑free структур в статьях не будет, хотя неглубокий их обзор в конце цикла дать можно. В отрыве от контекста они заведомо унылы — показывают не самые впечатляющие результаты в тестах, но зато обыгрывают более широкий круг сценариев (вроде MPMC). Угу, обратить внимание на этот trade‑off будет полезно.
И заодно показать, что иногда сам граф обработки данных имеет смысл затачивать под не самые удобные для программирования, но приятные железу структуры. Т.е. показать сам принцип, каким образом «ноу‑хау» рождается внутри реальной продакшен‑системы. Ключевое - почти всегда небесплатно. Чем-то приходится жертвовать. ))
причём тут "глубокое рассмотрение" - сами атомики работают по-разному на CAS / LL-CS архитектурах.
При этом это "по-разному" влияет на наблюдаемое поведение.
Это не просто "одни операции быстрее \ другие медленнее" - это одни алгоритмы показываются себя хорошо на одной архитектуре \ другие на другой.
Поэтому кода вы пишите: вот это хороший алгоритм (ну ок, с переключаемым списком в принципе норм) - было бы желательно указать на какой модели атомарных операций он хороший.
причём тут "глубокое рассмотрение" - сами атомики работают по-разному на CAS / LL-CS архитектурах.
Это не просто "одни операции быстрее \ другие медленнее" - это одни алгоритмы показываются себя хорошо на одной архитектуре \ другие на другой.
Для показанных в статье сниппетов кода практической разницы нет - между чтением ячейки и последующим CAS над ней в текущем потоке ничего не происходит.
Согласен с твоим утверждением и могу его дополнить - заметная разница CAS и LL/CS есть при обслуживании ABA, но статья не фокусируется на этом. Формат статьи - туториал. Т.е. фокус на том, как пользоваться имеющимися прикладными объектами и почему они вообще нужны. "Подводные камни" перечислены, т.е. координаты для любопытствующих даны.
Повторюсь, известные-популярные алгоритмы рассмотрены не будут, об этом и так на всех углах можно почитать. Целью было поделиться той информацией, которой обычно не делятся.
Пауза (
core::cpu_pause())
Для серверов может и достаточно, но для клиентского кода есть 2 паузы: быстрая типа mm_pause, когда частота ЦП не меняется, и более медленная через таймеры или WFE инструкцию на ARM, тогда ЦП может понизить частоту, меньше греться и не визжать вентиляторами.
Второй тип паузы нужен, когда поток постоянно обрабатывает задачи, но в какой-то момент появляется пауза до 1мс, тогда как переключение потоков или минимальный Sleep(1) на винде заниет 1/64с (около 15мс).
drain_stack
Тут все упирается в выделение памяти для ноды, обычно мелкие аллокации попадают в зарезервированную память в каждом потоке, но рано или поздно они дернут ядро с глоабльным мьютексом. Я сталкивался с тем, что из-за аллокаций алгоритм без синхронизаций вообще не масштабировался более 4 потоков.
Я делал похожие структуры через фиксированный буфер и атомарный счетчик размера, буфер переключается также свопом указателей.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Lock‑free по нарастающей