Начистоту если - я очень внимательно тебя читаю. И что я вижу? Я вижу весьма неглупого человека, который задаёт правильные вопросы, но никогда не двигается дальше, стоит начать на эти вопросы предметно отвечать. Как будто ступор. Т.е., с одной стороны, вопросы эти выглядят будто вопросы от коллеги, который видит себя в том числе в разработчиках "ядерного кода", но стоит начать говорить с той позиции - и тут же вижу переключение в позу потребителя с характерным налётом "клиент всегда прав". ))
Вы зачем-то начали рассказывать про диспетчеры.
Я рассуждаю с колокольни разработчика. И уже давно не верю на форумах в популярный когда-то немного тролльный трюк "вы просто плохо объясняетесь" - сейчас запросто можно закинуть в ИИ и проверить. Они ж пока не умнее нас, верно? Закидываю предыдущее сообщение от третьего лица (прошу валидировать тезисы некоего vdimas) и вижу примерно то, что и ожидал:
=======
«Просто отрасль еще этого не осознала, смотрю, отсюда странные вопросы навроде "при чём тут диспетчер"?»
Статус: Полностью верно (Фундаментальная проблема понимания асинхронности).
Технический контекст: Вопрос оппонентов «при чём тут диспетчер?» выдает непонимание того, как корутины работают «под капотом». Люди часто путают корутины в C++ с зелеными потоками (Green Threads / Go-рутины) или системными потоками.
В чем разница: В Go или Erlang есть тяжелая встроенная среда выполнения (runtime) с собственным планировщиком, который сам переключает контекст. В C++20 корутины — это «чистый скелет». Точка приостановки (co_await) лишь разрезает функцию на части и сохраняет состояние. Но кто-то должен возобновить (resume()) корутину, когда данные придут.
Этим «кто-то» и является диспетчер (например, io_context в Boost.Asio). Связь тектоническая: корутина отдает управление диспетчеру, чтобы поток не простаивал, а диспетчер, обработав системное событие, возвращает управление корутине. Корутины без диспетчера в реальном I/O — это просто мертвый набор структур данных.
=======
Смотрите: я утверждаю, что вот этот код содержит ошибку
Мой ответ прежний - зависит от диспетчера.
В реализации асинхронщины на манер Rust твой сниппет невалидный, понятно. В WXL полностью валидный и штатный. И да, я на это уже отвечал, ощущал некоторое недоверие, но полагаться на ощущения нельзя... Спасибо за сниппет, теперь это недоверие подтверждено документально. Еще одной статье на тему корутин быть! ))
В Rust, кстати, тоже можно сделать валидным, написав свою асинхронную подсистему. Но будет чуть больший уровень косвенности, потому что владение надо описывать явно, изымать это владение и возвращать, т.е. фокусы с буфером в кадре стека как в WXL не прокатят, но общую схему повторить можно. Да, будет менее удобно для использования, и это непреодолимо. Причины, почему это так, я однажды высказал здесь: http://www.rsdn.org/forum/philosophy/9101084.1
====
Характерно, что твой код в этом месте:
while (!result.is_completed()) {
// это вообще чушь
}
может быть валиден даже если вся асинхронщина живёт в одном потоке (не в дополнительном одном потоке, а когда строго один поток на приложение) - я не зря упомянул Boost.Asio и то, что в нём можно продвигать “обороты” диспетчеризации.
while (!result.is_completed()) {
// теперь это работает, даже если всей схеме
// выделили всего один поток
my_dispatcher.run_one();
}
Продвижение нужно для IOCP или RIO, а для completion routines достаточно в цикле вызывать любое alertable АПИ.
Дополнительная оговорка здесь может быть только при обсуждении Linux vs Windows, потому что в Linux чтение файла всегда синхронное, а epoll реализует реактор, в отличие от виндового проактора с overlapped АПИ. Тогда для тру-асинхронности операций над файлами в Linux требуется хотя бы один дополнительный поток, либо же использовать ленивую модель, как в Rust, в рамках которой твои сниппеты замечательно демонстрируют убогость этой модели.
И да, в Linux продвигают проакторный io_uring в последние годы, но Rust в проакторной модели страдает еще больше... ))
Хорошие диспетчеры позволяют вызывать свои кишки извне, например, для прокручивания событий по одному. См., к примеру, Boost.asio. То бишь, базовый диспетчер не "вещь себе", а не более чем низкоуровневый "кубик" для построения заточенного под конкретную задачу более высокоуровневого диспетчера, ведь оптимальная диспетчеризация почти всегда отталкивается от неких прикладных знаний, т.е. от того, чего ни у какого базового диспетчера быть не может. Именно поэтому устройство Boost.asio такое, какое есть - для простейших сценариев это готовая подсистема, а для более сложных - удобный "кубик Lego".
Корутинный код - это не только "сугубо клиентский код" как в wxl. Это наше будущее на всех уровнях реализации, кроме самого низкоуровневого. Просто отрасль еще этого не осознала, смотрю, отсюда странные вопросы навроде "при чём тут диспетчер"?
Boost.asio - не самый лучший диспетчер, потому что самый обобщённый. Но на него можно смотреть на как референсную реализацию именно по этой же причине - максимально широко обыграны всевозможные сценарии, больше половины которых в реальном проекте не нужны... просто заранее не предугадаешь, что окажется нужным, а что нет. Если бы они еще смогли отделить логику стар-стопа и собственные (пусть небольшие, но ненулевые) затраты на обеспечение этой логики и обыгрывание непротиворечивости согласно ей - это был бы более "чистый" кубик, но более опасный в случае неверного использования.
Из-за теперь уже очевидного п.2 созрел на еще одну статью по корутинам. Теперь это уже не просто мои внутренние ощущения, а достоверный факт (по итогам чтения обсуждений на RSDN и здесь) - даже ведущими разработчиками не понимается не столько механизм корутин (он простейший), сколько последствия. А они достаточно "тектонические". И вот это понимание продвигается натурально "со скрипом", что я уже не знаю как реагировать на половину вопросов здесь.
Честно если - не ожидал. Не ожидал с одной стороны любопытства к тонкостям (ведь больше должны интересовать свойства/гарантии, а их можно достичь множеством способов, т.к. любая задача обычно имеет более одного решения!) и не ожидал такого вакуума в общих представлениях о сценариях использования корутин, т.е. об очередном появившемся способе декомпозиции решаемых задач.
Последнее самое неприятное (для человека, всю сознательную жизнь "болеющего" за С++), а значит - цель для будущих публикаций. Даже в C# корутины (async/await) вошли более гладко, хотя казалось бы... Да, у них проще со временем жизни из-за GC... Да, им подкапотную механику дают свыше (но дали не всю сразу - эмуляция RAII была недоступна поначалу)... Но всё равно, переход на эту технику широко обсуждался и проходил достаточно гладко. А сегодня уже 2026-й, но большинство нововведений из стандарта С++20 де-факто не используется в массовом продакшене... И даже нет внятного представления, смотрю, как эти нововведения можно использовать. И широкого обсуждения тоже нет. Налицо вакуум в общих представлениях о сценариях и сверху откровенная растерянность, что показывают вопросы из разряда "а как вообще решить то-то?" вместо делового "какой из способов был выбран?"
где внутри небольшой массив на 128 байт. По производительности и само-масштабированию внезапно оказался быстрее других вариантов
Да, эта идея на поверхности. У меня в тестах система выходит на плато производительности примерно на 256 простеших элементов (длиной в слово) в блоке, давая средние затраты чуть больше пары наносекунд на элемент.
"Без замеров на всем этом зоопарке я бы предпочел хранить линейно. " - и еще рантаймы активно экспериментируют с аллокаторами (malloc/free), полируя их именно под многопоточный сценарий.
Предлагаю на этой итерации уже не торопиться с обратной связью.
Было уже сказано, что читатель забирает голову безусловной операцией exchange, то есть он не конкурирует в цикле с писателями, а «просто пришёл, открыл дверь с ноги и внаглую забрал».
В этом смысле у читателя образуется тот самый приоритет над писателями, о потребности которого ты абсолютно верно рассуждал.
Более того, в архитектуре x86/x64 команда xchg даже не требует префикса lock, она и без этого автоматически атомарна. Просто из-за особенностей реализации механизма поддержки когерентности кэшей ядер операция не требует пересылки данных в вычислительные блоки, не требует сравнения и арифметических/логических операций.
Более того, в отсутствии зависимостей по данным эта операция в relaxed-режиме легко и чудесно выполняется в параллель механизмом OoO еще в процессе предвыборки, т.е. её стоимость на горячей памяти — примерно 0 тактов.
Mpmc реализуется через пачку spsc безо всяких cas.
Это дешевое в разработке решение, но плата за него:
Гарантированные промахи по if — это врожденное свойство таких систем, где промах предсказателя имеет строго 100% вероятности.
Схема полезна только при ожиданиях на спине, со всеми тонкостями, что я расписал про спин-ожидания рядом (то есть «просто спин-ожидание» не даст ничего, если не приготовить его правильно).
Масштабируемость при монопольном обитании каждого спин-ожидания на выделенном ему ядре получается нулевая. То есть средняя подсистема на 16 ядрах (итого 32 с гипертредингом) будет обслуживать всего 3–4 реальных нагруженных соединения (с учётом дублирования A+B каналов мультикаста). Получаем КПД использования железа где-то 1–2% или меньше. Там обманка в том, что пусть система покажет нагрузку в районе 10% — это будет неправдой, потому что 8%–9% из этих 10% будет занимать 10 GOTO 10 спин-ожидания. Если поставить счётчики производительности по заходу и выходу в «реальный код», то увидим настоящий КПД такого решения в те самые 1%–2% или даже меньше.
То есть, прошу обратить внимание: прежде чем что-то оценивать, неплохо бы предварительно определиться — какими линейками и что именно мы собираемся измерять.
И если уж мы сознательно готовы использовать железку с минимальным КПД ради выигрыша в несколько сотен наносекунд над конкурентами, то это всё делается опять же не так — тогда идёт отказ от MPSC-схемы вовсе.
Тогда это чистой воды дублирование на каналах A+B, используется в каждом канале единственное SPSC или вовсе код пишется без межпоточной передачи. Кто быстрее плюнул в биржу — тот молодец. Простейший арбитраж происходит уже на выходе, где по правилам CAS везёт тому, кому надо, а кому не повезло — это просто чудесно, что ему не повезло.
==== Вдогонку. Перечитал, выглядит несколько сумубрным, на всякий случай закинул в гугловский ИИ на пробу - тот понял описанный механизм асолютно точно и правильно отвечает по любым подробностям по нему, буде возникнет у кого интерес - как оно происходит в реально-боевых условиях.
Для серверов может и достаточно, но для клиентского кода есть 2 паузы: быстрая типа mm_pause
Используется "быстрая" _mm_pause. Ну как быстрая?.. )) Занимает аж 40 нс, поэтому используется не всегда. А даже где используется - записано в долги "погонять как следует".
_mm_pause хорошо показывала себя 15+ лет назад, а сегодня некоторые участки приходится вычищать от неё, потому что она лишь снижает КДП использования современного железа.
тогда как переключение потоков или минимальный Sleep(1) на винде заниет 1/64с (около 15мс).
Да, по умолчанию 64 прерывания в секунду у таймера шедуллера (можно поднять до 1000 как в Linux), но Sleep не используется не по этому, а потому что поток не стоит в очереди на продолжение. Например, ожидающий примитив сигнализации с таймаутом просыпается быстрее по готовности. Т.е., Sleep - это совсем редкий гость и признак некачественной архитектуры, которая, увы, слишкм популярна - это когда в цикле с паузой на Sleep проверяют некоторое событие. Иногда делают это много раз в секунду, просто проверяя, что в некоторую подсистему пришли данные... Пора уже вводить жесткий фильтр и просто увольнять недобросовестных программистов за такие "решения". А они присутствуют в самой базе многих промышленных и очень важных проектов, просто, как обычно, "верхи" понятия не имеют, какой бардак творится "внизу". ))
Тут все упирается в выделение памяти для ноды, обычно мелкие аллокации попадают в зарезервированную память в каждом потоке, но рано или поздно они дернут ядро с глоабльным мьютексом.
Наконец-то вопрос по существу. ))
Там рядом лежит pool, pool_ptr. Обратный ход - такая же mpsc_queue, только уже LIFO. Т.е., де-факто получается кольцевая очередь, только на связанных блоках и потому динамическая, а не статического размера. В прямом порядке FIFO (иногда выгодней и LIFO, например, когда всё равно потребуется переупорядочивания/сортировка, например, записей лога или деджиттинг UDP-пакетов по таймстемпу), но обратно всегда "родное" для стека LIFO, т.е. из пула достаётся всегда самый горячий блок.
MPSC позволяет организовать схему "все пишут всем и получают обратно в свой пул тоже от всех". Т.е., любой производитель владеет пулом, новые блоки запрашивает только у него, посылает любому потребителю,, тот вынимает из очереди в pool_ptr, что-то делает с блоком, а при выходе из области видимости pool_ptr возвращает элемент в пул контрагента.
Я сталкивался с тем, что из-за аллокаций алгоритм без синхронизаций вообще не масштабировался более 4 потоков.
+100500
Единственно что - это у тебя еще относительно редко происходили аллокации, т.е. была какая-то тяжелая бизнес-логика? Потому когда бизнес-логика не очень тяжелая (несколько if-ов), то схема начинает ощутимо тормозить уже на 2-х участниках. Поэтому, да, пулы объектов.
Я делал похожие структуры через фиксированный буфер
Фиксированные буфера показали себя плохо в сценарии, когда бывают чудовищные всплески трафика (сотни тыщ сообщений в сек, а по нескольким каналам одновременно - миллионы в сек). При том что некоторые алгоритмы умеют увеличивать этот буфер, но не умеют его уменьшать. И выросший кольцевой буфер тормозит систему в целом, а не только себя самого, потому что по кругу наглухо вымывает собой кеши данных L3 и L2 у проца - все остальные процессы/потоки вынуждены постоянно подгружать в кеши свои данные заново и работают медленнее.
Показанная динамическая очередь MPSC крутится ровно на том кол-ве блоков, которое нужно актуальной нагрузке. А остальное, что было хапнуто в момент роста пиковой нагрузки, лежит мертвым грузом (т.е. не теребит кеш) и неспешно отдаётся системе обратно. Это не было упомянуто в статье, но это очень серьёзная production-ready фича. Просто она прикладная и про "чуть другое".
Кто следил за рассуждениям, должен был уже увидеть, что дело оставалось за малым, бо оно на поверхности - амортизировать косвенность блоков этой круговой single-linked-list очереди, т.е. чтобы каждый блок нёс не одно сообщение, а несколько их, представляя собой "линейный фрагмент" конкурирующей по дизайну обычной круговой очереди, чья самая вкусная фишка - локальность соседних элементов (пока эта очередь мала, разумеется).
Т.е., как оно часто бывает, с большим отрывом всех порвало гибридное решение. Ни одно "чистое" ничего любопытного на практике не показывает.
В реальности граница стирается. Любые знания, если ими не пользоваться регулярно хотя бы несколько месяцев, а лишь только "однократно разобраться за пол-часа", через единицы месяцев стираются из памяти, оставляя только самое общее представление на уровне "где-то слышал об этом", а иногда и этого не оставляя.
Цикл проработки любых знаний - это активация долговременной памяти через кратковременную, т.е. стандартные повторы материала через несколько часов, дней, недель. При таком подходе "просто справочник" мало отличается от "моих проработанных заметок".
Справочники - вообще великая вещь в деле самообучения (т.е. "механических сеансов возвращения к одной и той же информации" с т.з. работы нашей памяти), странно было услышать про них в уничижительной коннотации.
Читатель же должен иметь больший приоритет, но это невыразимо в CAS семантике.
На это уже был дан ответ: "В показанном drain_stack читатель забирает всю пачку безусловным exchange."
В циклическом буфере не нужны никакие CAS операции. Там как раз нет никакого бодания - каждый спокойно пишет в свою область памяти.
Для схемы со множеством писателей (MPSC) обойтись без синхронизации резервирования позиций никак. Это требует либо CAS-цикла, либо атомарного инкремента (fetch_add). Поскольку на многих платформах прямого аппаратного fetch_add нет, его приходится выражать через тот же CAS-цикл, как я показал в статье (именно по этой причине и показал).
Т.е., твои рассуждения стоит скорректировать: «На платформах, где присутствует атомарный инкремент, дисциплину MPSC для круговой очереди можно реализовать без цикла ожидания CAS».
Т.е., для RISC-V начального уровня, ядер ARM версий до 8.1, MIPS с расширениями уровня 1 и прочих эти рассуждения не верны.
причём тут "глубокое рассмотрение" - сами атомики работают по-разному на CAS / LL-CS архитектурах.
Это не просто "одни операции быстрее \ другие медленнее" - это одни алгоритмы показываются себя хорошо на одной архитектуре \ другие на другой.
Для показанных в статье сниппетов кода практической разницы нет - между чтением ячейки и последующим CAS над ней в текущем потоке ничего не происходит.
Согласен с твоим утверждением и могу его дополнить - заметная разница CAS и LL/CS есть при обслуживании ABA, но статья не фокусируется на этом. Формат статьи - туториал. Т.е. фокус на том, как пользоваться имеющимися прикладными объектами и почему они вообще нужны. "Подводные камни" перечислены, т.е. координаты для любопытствующих даны.
Повторюсь, известные-популярные алгоритмы рассмотрены не будут, об этом и так на всех углах можно почитать. Целью было поделиться той информацией, которой обычно не делятся.
Когда стоимость операции помещения элемента в очередь составляет единицы наносекунд, то фактические столкновения писателей получаются довольно редкими. Высокооптимизированные сетевые API забирают каждый в своём потоке обычно не одно сообщение, а сразу несколько (обычно подписка на несколько мультикаст каналов) и запихивают их в очередь. И вот это запихивание нескольких элементов в очередь со стороны писателя почти всегда монопольное из-за своей малой длительности.
Т.е., дисциплина MPSC не означает, что происходят постоянные бодания, она означает гарантии.
Это как с ABA - в реальной работе она может не проявить себя ни разу часами и даже сутками. Но когда проявит - создаст ошибку. Т.е., все средства борьбы с ABA работают бОльшую часть времени вхолостую. Так и механика обыгрывания множества потенциальных писателей большую часть времени работают вхолостую, но обеспечивает корректность в редких случаях их столкновения.
То есть в худшем случае будет стоимость одной CAS операции.
Для писателя в MPSC ответ "да". Я лишь обратил внимание, что стоимость CAS-операции не константа, а зависит от фактического "бодания" за линейку кеша с разницей примерно в 5 раз.
В то время как CAS цикл в худшем случае даёт ситуацию, что читатель может вообще никогда не суметь прочитать данные из-за того, что они постоянно меняются писателями.
В показанном drain_stack читатель забирает всю пачку безусловным exchange.
Причём, я как раз экспериментирую со второй сигнатурой рядом, где забор пачки происходит как relaxed и без предварительного if - это для возможности расписать сценарий (при надобности), когда читатель уход в спячку не сразу, а после некоторого spin-ожидания.
Это для тех сценариев, где работа на стороне читателя очень дешевая, т.е. где вычислительная загрузка обоих плеч недостаточно сбалансирована - в таких сценариях читатель часто уходит в спячку и проигрывает по пропускной способности вариантам, где между потоками работает в разы более медленная очередь.
Т.е. вот вам приколы - более быстрое решение может замедлить всю систему, если неправильно её приготовить. ))
Не хотелось бы писать в статьях то, что пишут на всех углах. Целью было дать то, что обычно опускают.
Если возникнет интерес к методам обхода ABA, то разница между CAS и LL/SC обязательно будет подсвечена. Тем более, что она чудесно иллюстрирует принцип «ничего не бывает даром». Но по моему многолетнему опыту, глубокое погружение в микро‑тонкости ассемблера интересно немногим. А кому интересно - те и сами прекрасно справляются.
Зато конкретные приёмы, алгоритмы, общие подходы (в том числе уже архитектурного плана) и метрики из реальных сценариев — это всё не просто интересно, но и полезно на практике. Бери да используй как сам код, так и готовые знания. Ценностью является не понимание механики работы отдельной аппаратной инструкции, а то, какую пользу из неё можно извлечь на макро‑уровне.
Любое современное ноу‑хау в области lock‑free — это почти никогда не сами эти структуры (в этой области уже давно слишком «натоптано», и что‑то принципиально новое изобрести сложно) - это всегда удачно найденные точки приложения их в конкретных системах.
Моя цель — расширить кругозор интересующихся и сразу же дать возможность пощупать готовые решения. Отсюда необходимость хотя бы озвучить проблематику, а следом — принятые способы обыгрывания, подводные камни и их небесплатность: разруливание ABA (ручками либо за счёт слепоты LL/SC‑механизма), false‑sharing, дорогое обращение к ядру, мифы про всемогущий spin‑wait и так далее.
По всем этим вещам в тексте и обсуждених специально дано немного материала, почти «просто упоминание». Кому надо — найдёт и погрузится с нужной ему глубиной, это открытая информация (в идеале - самостоятельно погонять бенмарки, которые нарисовать под свои сценарии). Но без этих упоминаний теряется причинно‑следственная связь «проблема => решение (и почему именно такое)».
Глубокого рассмотрения популярных lock‑free структур в статьях не будет, хотя неглубокий их обзор в конце цикла дать можно. В отрыве от контекста они заведомо унылы — показывают не самые впечатляющие результаты в тестах, но зато обыгрывают более широкий круг сценариев (вроде MPMC). Угу, обратить внимание на этот trade‑off будет полезно.
И заодно показать, что иногда сам граф обработки данных имеет смысл затачивать под не самые удобные для программирования, но приятные железу структуры. Т.е. показать сам принцип, каким образом «ноу‑хау» рождается внутри реальной продакшен‑системы. Ключевое - почти всегда небесплатно. Чем-то приходится жертвовать. ))
Абсолютно верно. Нас интересует только вероятность столкновения, а это отношение длительности окна потенциального конфликта к периоду обращений.
Поэтому, если обращение к ресурсу относительно редкое (относительно длительности этого обращения), то современные критические секции, исполняющие основную работу в user-кольце, показывают себя замечательно.
Эти рассуждения зависят от реальный таймингов операций. Да, регулярный заход в ядро и обратно на одном и том же примитиве — примерно микросекунда (плюс‑минус полтора раза), если редко — уже под 5–10 микросекунд.
Доступ к горячей памяти — почти ноль наносекунд (от долей одной до полутора). Доступ к остывающей ухудшается ступеньками, смотря из какого уровня кеша успели улететь. Причём, улетают тоже ступеньками — через 10 микросекунд деградация из L1 в L2, через 40–50 микросекунд деградация до L3, через 100+ микросекунд гарантированно вымывает из кеша проца.
Поэтому, простое спин‑ожидание даёт аж ничего. Да, чтение одной изолированной ячейки из холодной RAM — это под 100 наносекунд. Но в реальном приложении поток обрабатывает не одно число, а графы объектов. В зависимости от лейаута в памяти чтение сообщения порой превращается в последовательный обход цепочки указателей. Если эти структуры успели остыть, то каждый прыжок по ссылке генерирует свой независимый промах мимо кэша. В итоге суммарная задержка на расковыривание холодного и кучерявого бизнес‑объекта (банально просмотр строки длиннее 15 символов, то есть которая уже в куче) легко набегает на 4–5 микросекунд при средних паузах и улетает далеко за 10 микросекунд, если данные совсем вымыло из кэша.
Это сопоставимо с ценой захода в ядро ОС, что делает ожидание на примитивах сигнализации легальным и оно же диктует способ борьбы с ситуацией, если хочется тру спин‑лока: в HFT‑системах на спин‑ожиданиях гоняют по кругу так называемые «warmup»‑вызовы — это проход по реальному коду обработки приходящего пакета с флагом «warmup», то есть вся цепочка делает что и должна, но конечный результат никуда не отправляет или отправляет в юзер‑спейсный драйвер тоже с пометкой warup. И только тогда по приходу пакета можно уложиться в субмикросекундный полный цикл.
===
И да, любые такие рассуждения дожны отталкиваться от системы оценок - что именно мы оптимизируем? Если общую производительность, то увод простаивающего потока вычислений в сон - обязательная опция ради освобождения ресурсов. А когда оптимизируют только latency, выжимая лишние пару сотен наносекунд за счёт деградации общего throughput системы - я такое расточительство видел исключительно и только в HFT, и оно имеет смысл только если брокерские сервера физически ОЧЕНЬ близко расположены к серверами биржи - желательно в соседних стойках, как и организованы многие деривативные эти ипподромы лохотроны. ))
При этом, можно на архитектурном уровне так раскидать примитивы синхронизации, что они будут обслуживать "сразу всех" - например, как привязка кучи сокетов к одному потоку, тогда стоимость вечно горячего примитива сигнализации становится минимально возможной - до микросекунды, и основные тормоза получаются уже такие, на которые мы не можем повлиять - это простые тормоза простого доступа к памяти у остывших блоков.
"Голая" очередь 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 и защиту от гонок в момент засыпания подробно будет. Оно того стоит, ИМХО. Очень просто, сама идея "на поверхности", но в реальном софте применяется на удивление редко.
Не надо писателей координировать, надо для каждой пары тредов иметь отдельную spsc очередь. А читатель может выгребать сообщения из них в любом нужном ему порядке.
Это уже вопрос организации высокоуровневого графа обработки на основе имеющихся примитивов. Когда таких очередей более одной, то на каждой из них происходит опрос-ветвление. В реальных сценариях круговорота элементов из пула, т.е. производитель посылает блок памяти потребителю, тот обрабатывает и возвращает обратно в пул производителю, хорошо показала себя схема MPSC, потому что каждый может слать данные любому и получать обратно тоже от любого.
Но да, в некоторых сценариях (заведомо известное малое количество каналов, обычно 2-4 под спаренные +fall-back мультикасты), такая схема может быть немногим лучше MPSC, особенно если под такую задачу выделить ядро, которое никогда не уходит в спячку. Тут классический выбор между масштабируемостью и достижением субмикросекундных выигрышей за счёт отказа от оного.
Повторюсь, все "строительные блоки" для такой схемы есть, это уже сугубо архитектурная специфика под конкретные условия (выбранную функцию оптимизации системы).
Откуда вы взяли кэш промахи у кольцевого буфера?
Из замеров, причём задолго до того, как LMAX начал сам себя рекламировать и обманывать индустрию тем, что его решение лучшее. Это не так. Просто сама это индустрия не торопится делиться наработками.
Большой кольцевой буфер постоянно инвалидирует кеш и имеет дело с холодной памятью;
Можно допилить алгоритм до возможности роста кругового буфера, но это будут лишние такты на каждую операцию и уменьшить буфер затем будет нельзя;
Однажды выросший на пике трафика маленький буфер потом до конца работы сервиса будет вести себя как большой буфер.
Чем больше полезного ты делаешь в cas цикле, тем больше вероятность, что это полезное окажется бесполезным из-за конфликта и придется повторять.
Если посмотреть на пакетную амортизацию показанной MPSC-очереди, которая забирает данные пачками, то более строго процесс на всплеске трафика выглядит так:
читатель забирает пачку через interlocked-операцию, эта операция "дорогая", потому что требует когерентности с писателем;
далее читатель разгребает свою пачку, в это время писатель пишет новые данные через CAS на каждй элемент;
Де-факто для писателя CAS оказывается дорогим только для первой операции после модицикации линейки кеша читателем (порядка 16-21 нс для соседа по гипертредингу или 40-60 нс для соседних ядер);
Остальные CAS-операции по кеш-линии, продолжащей принадлежать писателю, выходят "дешёвыми" - порядка 4-6 нс.
Т.е., строго говоря, амортизация затрат в схеме "забирать порциями" происходит как на стороне читателя, так и на стороне писателя. В статье это не отражено, т.к. это совсем уже тонкости, но кто углубится в происходящее, тот и сам увидит, что линия кеша принадлежит писателю монопольно в тот промежуток времени, пока читатель разгребает свою пачку.
Для сравнения, простой mov из/в ячейку кеша холодной (некогерентной) памяти занимает тоже порядка 20-40 нс - это если память уже в L1, но просто была "только что изменена" другим ядром.
Итого, когда читатель в круговом буфере догоняет писателя - они начинают бодаться за одну линейку кеша, поочерёдно задерживая друг друга, и стоимость получается мало отличима от простого CAS.
От хорошо спроектированной системы ожидается, чтобы читатель не тормозил писателя. Т.е., всей схеме более выгодно, чтобы читатель отставал от писателя хотя бы на две линейки кеша (если на одну, то он будет неизбежно набегать на первый элемент, пока писатель пишет последний).
В этом и состоит ловушка некоторых синтетических тестов, когда измеряют latency самой очереди в отрыве от остального: минимальное отставание читателя “сугубо по цифрам” обеспечивает минимальное latency, но при этом сам поток писателя начинает тормозить, что не измеряется такими тестами. Т.е., система в целом начинает работать хуже.
На монотонном графике нагрузок эта область видится как паразитное плоское плато на графике, которое тем шире, чем дешевле работа на стороне читателя в сравнении с писателем, и это тоже диктует сугубо архитектурные решения - какую часть работы выполнять на стороне писателя, а какую на стороне читателя.
"Срыв" с этого плато и выход на в разы более высокую производительность происходит скачкообразно - когда писателю удаётся на пару линий кеша оторваться от читателя.
Вдогонку, насчёт дефрагментации на интрузивных блоках. Тесты показывают полнейшую индифирентность к этому, зато чутко реагируют на степень разогрева памяти.
Например, возвращённый обратно в пул писателя блок памяти изымается из пула по дисциплине LIFO (сам пул - это и есть показанная mpsc-очередь, но работающая в режиме LIFO), т.е. для новой порции данных берётся самый горячий блок. В итоге, в устоявшемся режиме между участниками курсируют два самых разогретых блока памяти, где затраты на разыменование косвенной связи буферов в современной предвыборке и отсутствии промахов ветвления составляют что-то около 0.4 нс в среднем (т.е. почти всегда ноль - в этом и состоит работа предвыборки конвейера).
(выглядит как заявка на небольшую поясняющую статью, но мне кажется, что круг любопытных к таким тонкостям будет совсем узок)
В случае с 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 сценария (один писатель и один читатель), всё еще присутствует межпоточная конкуренция за ресурс между писателем и читателем, пусть даже конкуренция за каждую из операций записи и чтения ограничена одним участником.
Поэтому сделаное в статье введение и вызывает вопрос
Про введение понятно, оно заведомо ограничено по объёму, и ставит целью кратко обрисовать проблематику.
Вызывает ли дополнительные вопросы материал, начинающийся со слов "хотелось бы принципиально другого поведения: чтобы поток, положивший элемент в очередь, физически не мог заблокировать того, кто пытается положить следующий или прочитать имеющийся"?
Про это будет отдельная статья, но прямо сейчас уже можно посмотреть исходник 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 алгоритмов, поэтому они будут даны в одном цикле статей.
Разница в том, что вытесненный поток, исполняющий lock-free алгоритм над разделяемой между потоками структуре, не провоцирует блокировку (внужденный уход в спячку) других потоков, конкурирующих за доступ к этой структуре.
Прошу пояснить саму причину этого вопроса - из текста статьи был не понятен сценарий, при котором вытесненный поток, владеющий мьютексом (или критической секцией) блокирует остальные потоки, которым нужен тот же самый ресурс?
Я исходил из того, что проблематика эта известная, поэтому считал, что достаточно упомянуть сам сценарий, который является основным мотивом применения lock-free структур.
Начистоту если - я очень внимательно тебя читаю. И что я вижу? Я вижу весьма неглупого человека, который задаёт правильные вопросы, но никогда не двигается дальше, стоит начать на эти вопросы предметно отвечать. Как будто ступор. Т.е., с одной стороны, вопросы эти выглядят будто вопросы от коллеги, который видит себя в том числе в разработчиках "ядерного кода", но стоит начать говорить с той позиции - и тут же вижу переключение в позу потребителя с характерным налётом "клиент всегда прав". ))
Я рассуждаю с колокольни разработчика. И уже давно не верю на форумах в популярный когда-то немного тролльный трюк "вы просто плохо объясняетесь" - сейчас запросто можно закинуть в ИИ и проверить. Они ж пока не умнее нас, верно? Закидываю предыдущее сообщение от третьего лица (прошу валидировать тезисы некоего vdimas) и вижу примерно то, что и ожидал:
=======
«Просто отрасль еще этого не осознала, смотрю, отсюда странные вопросы навроде "при чём тут диспетчер"?»
Статус: Полностью верно (Фундаментальная проблема понимания асинхронности).
Технический контекст: Вопрос оппонентов «при чём тут диспетчер?» выдает непонимание того, как корутины работают «под капотом». Люди часто путают корутины в C++ с зелеными потоками (Green Threads / Go-рутины) или системными потоками.
В чем разница: В Go или Erlang есть тяжелая встроенная среда выполнения (runtime) с собственным планировщиком, который сам переключает контекст. В C++20 корутины — это «чистый скелет». Точка приостановки (
co_await) лишь разрезает функцию на части и сохраняет состояние. Но кто-то должен возобновить (resume()) корутину, когда данные придут.Этим «кто-то» и является диспетчер (например,
io_contextвBoost.Asio). Связь тектоническая: корутина отдает управление диспетчеру, чтобы поток не простаивал, а диспетчер, обработав системное событие, возвращает управление корутине. Корутины без диспетчера в реальном I/O — это просто мертвый набор структур данных.=======
Мой ответ прежний - зависит от диспетчера.
В реализации асинхронщины на манер Rust твой сниппет невалидный, понятно. В WXL полностью валидный и штатный. И да, я на это уже отвечал, ощущал некоторое недоверие, но полагаться на ощущения нельзя... Спасибо за сниппет, теперь это недоверие подтверждено документально. Еще одной статье на тему корутин быть! ))
В Rust, кстати, тоже можно сделать валидным, написав свою асинхронную подсистему. Но будет чуть больший уровень косвенности, потому что владение надо описывать явно, изымать это владение и возвращать, т.е. фокусы с буфером в кадре стека как в WXL не прокатят, но общую схему повторить можно. Да, будет менее удобно для использования, и это непреодолимо. Причины, почему это так, я однажды высказал здесь:
http://www.rsdn.org/forum/philosophy/9101084.1
====
Характерно, что твой код в этом месте:
может быть валиден даже если вся асинхронщина живёт в одном потоке (не в дополнительном одном потоке, а когда строго один поток на приложение) - я не зря упомянул Boost.Asio и то, что в нём можно продвигать “обороты” диспетчеризации.
Продвижение нужно для IOCP или RIO, а для completion routines достаточно в цикле вызывать любое alertable АПИ.
Дополнительная оговорка здесь может быть только при обсуждении Linux vs Windows, потому что в Linux чтение файла всегда синхронное, а epoll реализует реактор, в отличие от виндового проактора с overlapped АПИ. Тогда для тру-асинхронности операций над файлами в Linux требуется хотя бы один дополнительный поток, либо же использовать ленивую модель, как в Rust, в рамках которой твои сниппеты замечательно демонстрируют убогость этой модели.
И да, в Linux продвигают проакторный
io_uringв последние годы, но Rust в проакторной модели страдает еще больше... ))(причины по ссылке на пост на RSDN).
Хорошие диспетчеры позволяют вызывать свои кишки извне, например, для прокручивания событий по одному. См., к примеру, Boost.asio. То бишь, базовый диспетчер не "вещь себе", а не более чем низкоуровневый "кубик" для построения заточенного под конкретную задачу более высокоуровневого диспетчера, ведь оптимальная диспетчеризация почти всегда отталкивается от неких прикладных знаний, т.е. от того, чего ни у какого базового диспетчера быть не может. Именно поэтому устройство Boost.asio такое, какое есть - для простейших сценариев это готовая подсистема, а для более сложных - удобный "кубик Lego".
Корутинный код - это не только "сугубо клиентский код" как в wxl. Это наше будущее на всех уровнях реализации, кроме самого низкоуровневого. Просто отрасль еще этого не осознала, смотрю, отсюда странные вопросы навроде "при чём тут диспетчер"?
Boost.asio - не самый лучший диспетчер, потому что самый обобщённый. Но на него можно смотреть на как референсную реализацию именно по этой же причине - максимально широко обыграны всевозможные сценарии, больше половины которых в реальном проекте не нужны... просто заранее не предугадаешь, что окажется нужным, а что нет. Если бы они еще смогли отделить логику стар-стопа и собственные (пусть небольшие, но ненулевые) затраты на обеспечение этой логики и обыгрывание непротиворечивости согласно ей - это был бы более "чистый" кубик, но более опасный в случае неверного использования.
Из-за теперь уже очевидного п.2 созрел на еще одну статью по корутинам. Теперь это уже не просто мои внутренние ощущения, а достоверный факт (по итогам чтения обсуждений на RSDN и здесь) - даже ведущими разработчиками не понимается не столько механизм корутин (он простейший), сколько последствия. А они достаточно "тектонические". И вот это понимание продвигается натурально "со скрипом", что я уже не знаю как реагировать на половину вопросов здесь.
Честно если - не ожидал. Не ожидал с одной стороны любопытства к тонкостям (ведь больше должны интересовать свойства/гарантии, а их можно достичь множеством способов, т.к. любая задача обычно имеет более одного решения!) и не ожидал такого вакуума в общих представлениях о сценариях использования корутин, т.е. об очередном появившемся способе декомпозиции решаемых задач.
Последнее самое неприятное (для человека, всю сознательную жизнь "болеющего" за С++), а значит - цель для будущих публикаций. Даже в C# корутины (async/await) вошли более гладко, хотя казалось бы... Да, у них проще со временем жизни из-за GC... Да, им подкапотную механику дают свыше (но дали не всю сразу - эмуляция RAII была недоступна поначалу)... Но всё равно, переход на эту технику широко обсуждался и проходил достаточно гладко. А сегодня уже 2026-й, но большинство нововведений из стандарта С++20 де-факто не используется в массовом продакшене... И даже нет внятного представления, смотрю, как эти нововведения можно использовать. И широкого обсуждения тоже нет. Налицо вакуум в общих представлениях о сценариях и сверху откровенная растерянность, что показывают вопросы из разряда "а как вообще решить то-то?" вместо делового "какой из способов был выбран?"
Да, эта идея на поверхности. У меня в тестах система выходит на плато производительности примерно на 256 простеших элементов (длиной в слово) в блоке, давая средние затраты чуть больше пары наносекунд на элемент.
"Без замеров на всем этом зоопарке я бы предпочел хранить линейно. " - и еще рантаймы активно экспериментируют с аллокаторами (malloc/free), полируя их именно под многопоточный сценарий.
Да и замеры нынче дешевы ))
У людей это принято называть «терпением».
Предлагаю на этой итерации уже не торопиться с обратной связью.
Было уже сказано, что читатель забирает голову безусловной операцией
exchange, то есть он не конкурирует в цикле с писателями, а «просто пришёл, открыл дверь с ноги и внаглую забрал».В этом смысле у читателя образуется тот самый приоритет над писателями, о потребности которого ты абсолютно верно рассуждал.
Более того, в архитектуре x86/x64 команда
xchgдаже не требует префиксаlock, она и без этого автоматически атомарна. Просто из-за особенностей реализации механизма поддержки когерентности кэшей ядер операция не требует пересылки данных в вычислительные блоки, не требует сравнения и арифметических/логических операций.Более того, в отсутствии зависимостей по данным эта операция в
relaxed-режиме легко и чудесно выполняется в параллель механизмом OoO еще в процессе предвыборки, т.е. её стоимость на горячей памяти — примерно 0 тактов.Это дешевое в разработке решение, но плата за него:
Гарантированные промахи по
if— это врожденное свойство таких систем, где промах предсказателя имеет строго 100% вероятности.Схема полезна только при ожиданиях на спине, со всеми тонкостями, что я расписал про спин-ожидания рядом (то есть «просто спин-ожидание» не даст ничего, если не приготовить его правильно).
Масштабируемость при монопольном обитании каждого спин-ожидания на выделенном ему ядре получается нулевая. То есть средняя подсистема на 16 ядрах (итого 32 с гипертредингом) будет обслуживать всего 3–4 реальных нагруженных соединения (с учётом дублирования A+B каналов мультикаста). Получаем КПД использования железа где-то 1–2% или меньше. Там обманка в том, что пусть система покажет нагрузку в районе 10% — это будет неправдой, потому что 8%–9% из этих 10% будет занимать
10 GOTO 10спин-ожидания. Если поставить счётчики производительности по заходу и выходу в «реальный код», то увидим настоящий КПД такого решения в те самые 1%–2% или даже меньше.То есть, прошу обратить внимание: прежде чем что-то оценивать, неплохо бы предварительно определиться — какими линейками и что именно мы собираемся измерять.
И если уж мы сознательно готовы использовать железку с минимальным КПД ради выигрыша в несколько сотен наносекунд над конкурентами, то это всё делается опять же не так — тогда идёт отказ от MPSC-схемы вовсе.
Тогда это чистой воды дублирование на каналах A+B, используется в каждом канале единственное SPSC или вовсе код пишется без межпоточной передачи. Кто быстрее плюнул в биржу — тот молодец. Простейший арбитраж происходит уже на выходе, где по правилам CAS везёт тому, кому надо, а кому не повезло — это просто чудесно, что ему не повезло.
То есть CAS не всегда означает цикл, иногда это просто арбитраж, например как у меня в этом месте:https://github.com/dmitry-valyukov/wxl/blob/541d5bb5b3ad69c42c67788de7bea4bbbed0ed0c/wxl.async/src/bump_buffer.ixx#L38
====
Вдогонку. Перечитал, выглядит несколько сумубрным, на всякий случай закинул в гугловский ИИ на пробу - тот понял описанный механизм асолютно точно и правильно отвечает по любым подробностям по нему, буде возникнет у кого интерес - как оно происходит в реально-боевых условиях.
Используется "быстрая" _mm_pause. Ну как быстрая?.. ))
Занимает аж 40 нс, поэтому используется не всегда.
А даже где используется - записано в долги "погонять как следует".
_mm_pause хорошо показывала себя 15+ лет назад, а сегодня некоторые участки приходится вычищать от неё, потому что она лишь снижает КДП использования современного железа.
Да, по умолчанию 64 прерывания в секунду у таймера шедуллера (можно поднять до 1000 как в Linux), но Sleep не используется не по этому, а потому что поток не стоит в очереди на продолжение. Например, ожидающий примитив сигнализации с таймаутом просыпается быстрее по готовности. Т.е., Sleep - это совсем редкий гость и признак некачественной архитектуры, которая, увы, слишкм популярна - это когда в цикле с паузой на Sleep проверяют некоторое событие. Иногда делают это много раз в секунду, просто проверяя, что в некоторую подсистему пришли данные... Пора уже вводить жесткий фильтр и просто увольнять недобросовестных программистов за такие "решения". А они присутствуют в самой базе многих промышленных и очень важных проектов, просто, как обычно, "верхи" понятия не имеют, какой бардак творится "внизу". ))
Наконец-то вопрос по существу. ))
Там рядом лежит pool, pool_ptr.
Обратный ход - такая же mpsc_queue, только уже LIFO.
Т.е., де-факто получается кольцевая очередь, только на связанных блоках и потому динамическая, а не статического размера. В прямом порядке FIFO (иногда выгодней и LIFO, например, когда всё равно потребуется переупорядочивания/сортировка, например, записей лога или деджиттинг UDP-пакетов по таймстемпу), но обратно всегда "родное" для стека LIFO, т.е. из пула достаётся всегда самый горячий блок.
MPSC позволяет организовать схему "все пишут всем и получают обратно в свой пул тоже от всех". Т.е., любой производитель владеет пулом, новые блоки запрашивает только у него, посылает любому потребителю,, тот вынимает из очереди в pool_ptr, что-то делает с блоком, а при выходе из области видимости pool_ptr возвращает элемент в пул контрагента.
+100500
Единственно что - это у тебя еще относительно редко происходили аллокации, т.е. была какая-то тяжелая бизнес-логика? Потому когда бизнес-логика не очень тяжелая (несколько if-ов), то схема начинает ощутимо тормозить уже на 2-х участниках. Поэтому, да, пулы объектов.
Фиксированные буфера показали себя плохо в сценарии, когда бывают чудовищные всплески трафика (сотни тыщ сообщений в сек, а по нескольким каналам одновременно - миллионы в сек). При том что некоторые алгоритмы умеют увеличивать этот буфер, но не умеют его уменьшать. И выросший кольцевой буфер тормозит систему в целом, а не только себя самого, потому что по кругу наглухо вымывает собой кеши данных L3 и L2 у проца - все остальные процессы/потоки вынуждены постоянно подгружать в кеши свои данные заново и работают медленнее.
Показанная динамическая очередь MPSC крутится ровно на том кол-ве блоков, которое нужно актуальной нагрузке. А остальное, что было хапнуто в момент роста пиковой нагрузки, лежит мертвым грузом (т.е. не теребит кеш) и неспешно отдаётся системе обратно. Это не было упомянуто в статье, но это очень серьёзная production-ready фича. Просто она прикладная и про "чуть другое".
Кто следил за рассуждениям, должен был уже увидеть, что дело оставалось за малым, бо оно на поверхности - амортизировать косвенность блоков этой круговой single-linked-list очереди, т.е. чтобы каждый блок нёс не одно сообщение, а несколько их, представляя собой "линейный фрагмент" конкурирующей по дизайну обычной круговой очереди, чья самая вкусная фишка - локальность соседних элементов (пока эта очередь мала, разумеется).
Т.е., как оно часто бывает, с большим отрывом всех порвало гибридное решение. Ни одно "чистое" ничего любопытного на практике не показывает.
В реальности граница стирается. Любые знания, если ими не пользоваться регулярно хотя бы несколько месяцев, а лишь только "однократно разобраться за пол-часа", через единицы месяцев стираются из памяти, оставляя только самое общее представление на уровне "где-то слышал об этом", а иногда и этого не оставляя.
Цикл проработки любых знаний - это активация долговременной памяти через кратковременную, т.е. стандартные повторы материала через несколько часов, дней, недель. При таком подходе "просто справочник" мало отличается от "моих проработанных заметок".
Справочники - вообще великая вещь в деле самообучения (т.е. "механических сеансов возвращения к одной и той же информации" с т.з. работы нашей памяти), странно было услышать про них в уничижительной коннотации.
Будет целая статья с разбором.
На это уже был дан ответ: "В показанном drain_stack читатель забирает всю пачку безусловным exchange."
Для схемы со множеством писателей (MPSC) обойтись без синхронизации резервирования позиций никак. Это требует либо CAS-цикла, либо атомарного инкремента (
fetch_add). Поскольку на многих платформах прямого аппаратногоfetch_addнет, его приходится выражать через тот же CAS-цикл, как я показал в статье (именно по этой причине и показал).Т.е., твои рассуждения стоит скорректировать: «На платформах, где присутствует атомарный инкремент, дисциплину MPSC для круговой очереди можно реализовать без цикла ожидания CAS».
Т.е., для RISC-V начального уровня, ядер ARM версий до 8.1, MIPS с расширениями уровня 1 и прочих эти рассуждения не верны.
Для показанных в статье сниппетов кода практической разницы нет - между чтением ячейки и последующим CAS над ней в текущем потоке ничего не происходит.
Согласен с твоим утверждением и могу его дополнить - заметная разница CAS и LL/CS есть при обслуживании ABA, но статья не фокусируется на этом. Формат статьи - туториал. Т.е. фокус на том, как пользоваться имеющимися прикладными объектами и почему они вообще нужны. "Подводные камни" перечислены, т.е. координаты для любопытствующих даны.
Повторюсь, известные-популярные алгоритмы рассмотрены не будут, об этом и так на всех углах можно почитать. Целью было поделиться той информацией, которой обычно не делятся.
Я ждал этого замечания. ))
Когда стоимость операции помещения элемента в очередь составляет единицы наносекунд, то фактические столкновения писателей получаются довольно редкими. Высокооптимизированные сетевые API забирают каждый в своём потоке обычно не одно сообщение, а сразу несколько (обычно подписка на несколько мультикаст каналов) и запихивают их в очередь. И вот это запихивание нескольких элементов в очередь со стороны писателя почти всегда монопольное из-за своей малой длительности.
Т.е., дисциплина MPSC не означает, что происходят постоянные бодания, она означает гарантии.
Это как с ABA - в реальной работе она может не проявить себя ни разу часами и даже сутками. Но когда проявит - создаст ошибку. Т.е., все средства борьбы с ABA работают бОльшую часть времени вхолостую. Так и механика обыгрывания множества потенциальных писателей большую часть времени работают вхолостую, но обеспечивает корректность в редких случаях их столкновения.
Для писателя в MPSC ответ "да". Я лишь обратил внимание, что стоимость CAS-операции не константа, а зависит от фактического "бодания" за линейку кеша с разницей примерно в 5 раз.
В показанном drain_stack читатель забирает всю пачку безусловным exchange.
Причём, я как раз экспериментирую со второй сигнатурой рядом, где забор пачки происходит как relaxed и без предварительного if - это для возможности расписать сценарий (при надобности), когда читатель уход в спячку не сразу, а после некоторого spin-ожидания.
Это для тех сценариев, где работа на стороне читателя очень дешевая, т.е. где вычислительная загрузка обоих плеч недостаточно сбалансирована - в таких сценариях читатель часто уходит в спячку и проигрывает по пропускной способности вариантам, где между потоками работает в разы более медленная очередь.
Т.е. вот вам приколы - более быстрое решение может замедлить всю систему, если неправильно её приготовить. ))
https://github.com/dmitry-valyukov/wxl/blob/main/wxl.async/benchmarks/spsc_queues_benchmark.cpp
Собрать:
Запустить:
Насколько я понял, у тебя тип сообщения канала указан явно?
На BASIC ))
Не хотелось бы писать в статьях то, что пишут на всех углах. Целью было дать то, что обычно опускают.
Если возникнет интерес к методам обхода ABA, то разница между CAS и LL/SC обязательно будет подсвечена. Тем более, что она чудесно иллюстрирует принцип «ничего не бывает даром». Но по моему многолетнему опыту, глубокое погружение в микро‑тонкости ассемблера интересно немногим. А кому интересно - те и сами прекрасно справляются.
Зато конкретные приёмы, алгоритмы, общие подходы (в том числе уже архитектурного плана) и метрики из реальных сценариев — это всё не просто интересно, но и полезно на практике. Бери да используй как сам код, так и готовые знания. Ценностью является не понимание механики работы отдельной аппаратной инструкции, а то, какую пользу из неё можно извлечь на макро‑уровне.
Любое современное ноу‑хау в области lock‑free — это почти никогда не сами эти структуры (в этой области уже давно слишком «натоптано», и что‑то принципиально новое изобрести сложно) - это всегда удачно найденные точки приложения их в конкретных системах.
Моя цель — расширить кругозор интересующихся и сразу же дать возможность пощупать готовые решения. Отсюда необходимость хотя бы озвучить проблематику, а следом — принятые способы обыгрывания, подводные камни и их небесплатность: разруливание ABA (ручками либо за счёт слепоты LL/SC‑механизма), false‑sharing, дорогое обращение к ядру, мифы про всемогущий spin‑wait и так далее.
По всем этим вещам в тексте и обсуждених специально дано немного материала, почти «просто упоминание». Кому надо — найдёт и погрузится с нужной ему глубиной, это открытая информация (в идеале - самостоятельно погонять бенмарки, которые нарисовать под свои сценарии). Но без этих упоминаний теряется причинно‑следственная связь «проблема => решение (и почему именно такое)».
Глубокого рассмотрения популярных lock‑free структур в статьях не будет, хотя неглубокий их обзор в конце цикла дать можно. В отрыве от контекста они заведомо унылы — показывают не самые впечатляющие результаты в тестах, но зато обыгрывают более широкий круг сценариев (вроде MPMC). Угу, обратить внимание на этот trade‑off будет полезно.
И заодно показать, что иногда сам граф обработки данных имеет смысл затачивать под не самые удобные для программирования, но приятные железу структуры. Т.е. показать сам принцип, каким образом «ноу‑хау» рождается внутри реальной продакшен‑системы. Ключевое - почти всегда небесплатно. Чем-то приходится жертвовать. ))
Абсолютно верно. Нас интересует только вероятность столкновения, а это отношение длительности окна потенциального конфликта к периоду обращений.
Поэтому, если обращение к ресурсу относительно редкое (относительно длительности этого обращения), то современные критические секции, исполняющие основную работу в user-кольце, показывают себя замечательно.
Эти рассуждения зависят от реальный таймингов операций. Да, регулярный заход в ядро и обратно на одном и том же примитиве — примерно микросекунда (плюс‑минус полтора раза), если редко — уже под 5–10 микросекунд.
Доступ к горячей памяти — почти ноль наносекунд (от долей одной до полутора). Доступ к остывающей ухудшается ступеньками, смотря из какого уровня кеша успели улететь. Причём, улетают тоже ступеньками — через 10 микросекунд деградация из L1 в L2, через 40–50 микросекунд деградация до L3, через 100+ микросекунд гарантированно вымывает из кеша проца.
Поэтому, простое спин‑ожидание даёт аж ничего. Да, чтение одной изолированной ячейки из холодной RAM — это под 100 наносекунд. Но в реальном приложении поток обрабатывает не одно число, а графы объектов. В зависимости от лейаута в памяти чтение сообщения порой превращается в последовательный обход цепочки указателей. Если эти структуры успели остыть, то каждый прыжок по ссылке генерирует свой независимый промах мимо кэша. В итоге суммарная задержка на расковыривание холодного и кучерявого бизнес‑объекта (банально просмотр строки длиннее 15 символов, то есть которая уже в куче) легко набегает на 4–5 микросекунд при средних паузах и улетает далеко за 10 микросекунд, если данные совсем вымыло из кэша.
Это сопоставимо с ценой захода в ядро ОС, что делает ожидание на примитивах сигнализации легальным и оно же диктует способ борьбы с ситуацией, если хочется тру спин‑лока: в HFT‑системах на спин‑ожиданиях гоняют по кругу так называемые «warmup»‑вызовы — это проход по реальному коду обработки приходящего пакета с флагом «warmup», то есть вся цепочка делает что и должна, но конечный результат никуда не отправляет или отправляет в юзер‑спейсный драйвер тоже с пометкой warup. И только тогда по приходу пакета можно уложиться в субмикросекундный полный цикл.
===
И да, любые такие рассуждения дожны отталкиваться от системы оценок - что именно мы оптимизируем? Если общую производительность, то увод простаивающего потока вычислений в сон - обязательная опция ради освобождения ресурсов. А когда оптимизируют только latency, выжимая лишние пару сотен наносекунд за счёт деградации общего throughput системы - я такое расточительство видел исключительно и только в HFT, и оно имеет смысл только если брокерские сервера физически ОЧЕНЬ близко расположены к серверами биржи - желательно в соседних стойках, как и организованы многие деривативные эти
ипподромылохотроны. ))При этом, можно на архитектурном уровне так раскидать примитивы синхронизации, что они будут обслуживать "сразу всех" - например, как привязка кучи сокетов к одному потоку, тогда стоимость вечно горячего примитива сигнализации становится минимально возможной - до микросекунды, и основные тормоза получаются уже такие, на которые мы не можем повлиять - это простые тормоза простого доступа к памяти у остывших блоков.
"Голая" очередь
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и защиту от гонок в момент засыпания подробно будет. Оно того стоит, ИМХО. Очень просто, сама идея "на поверхности", но в реальном софте применяется на удивление редко.Это уже вопрос организации высокоуровневого графа обработки на основе имеющихся примитивов. Когда таких очередей более одной, то на каждой из них происходит опрос-ветвление. В реальных сценариях круговорота элементов из пула, т.е. производитель посылает блок памяти потребителю, тот обрабатывает и возвращает обратно в пул производителю, хорошо показала себя схема MPSC, потому что каждый может слать данные любому и получать обратно тоже от любого.
Но да, в некоторых сценариях (заведомо известное малое количество каналов, обычно 2-4 под спаренные +fall-back мультикасты), такая схема может быть немногим лучше MPSC, особенно если под такую задачу выделить ядро, которое никогда не уходит в спячку. Тут классический выбор между масштабируемостью и достижением субмикросекундных выигрышей за счёт отказа от оного.
Повторюсь, все "строительные блоки" для такой схемы есть, это уже сугубо архитектурная специфика под конкретные условия (выбранную функцию оптимизации системы).
Из замеров, причём задолго до того, как LMAX начал сам себя рекламировать и обманывать индустрию тем, что его решение лучшее. Это не так. Просто сама это индустрия не торопится делиться наработками.
Проблематика простого кругового буфера я-ля Disruptor:
Маленький кольцевой буфер стопорит писателя;
Большой кольцевой буфер постоянно инвалидирует кеш и имеет дело с холодной памятью;
Можно допилить алгоритм до возможности роста кругового буфера, но это будут лишние такты на каждую операцию и уменьшить буфер затем будет нельзя;
Однажды выросший на пике трафика маленький буфер потом до конца работы сервиса будет вести себя как большой буфер.
Если посмотреть на пакетную амортизацию показанной MPSC-очереди, которая забирает данные пачками, то более строго процесс на всплеске трафика выглядит так:
читатель забирает пачку через interlocked-операцию, эта операция "дорогая", потому что требует когерентности с писателем;
далее читатель разгребает свою пачку, в это время писатель пишет новые данные через CAS на каждй элемент;
Де-факто для писателя CAS оказывается дорогим только для первой операции после модицикации линейки кеша читателем (порядка 16-21 нс для соседа по гипертредингу или 40-60 нс для соседних ядер);
Остальные CAS-операции по кеш-линии, продолжащей принадлежать писателю, выходят "дешёвыми" - порядка 4-6 нс.
Т.е., строго говоря, амортизация затрат в схеме "забирать порциями" происходит как на стороне читателя, так и на стороне писателя. В статье это не отражено, т.к. это совсем уже тонкости, но кто углубится в происходящее, тот и сам увидит, что линия кеша принадлежит писателю монопольно в тот промежуток времени, пока читатель разгребает свою пачку.
Для сравнения, простой mov из/в ячейку кеша холодной (некогерентной) памяти занимает тоже порядка 20-40 нс - это если память уже в L1, но просто была "только что изменена" другим ядром.
Итого, когда читатель в круговом буфере догоняет писателя - они начинают бодаться за одну линейку кеша, поочерёдно задерживая друг друга, и стоимость получается мало отличима от простого CAS.
От хорошо спроектированной системы ожидается, чтобы читатель не тормозил писателя. Т.е., всей схеме более выгодно, чтобы читатель отставал от писателя хотя бы на две линейки кеша (если на одну, то он будет неизбежно набегать на первый элемент, пока писатель пишет последний).
В этом и состоит ловушка некоторых синтетических тестов, когда измеряют latency самой очереди в отрыве от остального: минимальное отставание читателя “сугубо по цифрам” обеспечивает минимальное latency, но при этом сам поток писателя начинает тормозить, что не измеряется такими тестами. Т.е., система в целом начинает работать хуже.
На монотонном графике нагрузок эта область видится как паразитное плоское плато на графике, которое тем шире, чем дешевле работа на стороне читателя в сравнении с писателем, и это тоже диктует сугубо архитектурные решения - какую часть работы выполнять на стороне писателя, а какую на стороне читателя.
"Срыв" с этого плато и выход на в разы более высокую производительность происходит скачкообразно - когда писателю удаётся на пару линий кеша оторваться от читателя.
Вдогонку, насчёт дефрагментации на интрузивных блоках. Тесты показывают полнейшую индифирентность к этому, зато чутко реагируют на степень разогрева памяти.
Например, возвращённый обратно в пул писателя блок памяти изымается из пула по дисциплине LIFO (сам пул - это и есть показанная mpsc-очередь, но работающая в режиме LIFO), т.е. для новой порции данных берётся самый горячий блок. В итоге, в устоявшемся режиме между участниками курсируют два самых разогретых блока памяти, где затраты на разыменование косвенной связи буферов в современной предвыборке и отсутствии промахов ветвления составляют что-то около 0.4 нс в среднем (т.е. почти всегда ноль - в этом и состоит работа предвыборки конвейера).
(выглядит как заявка на небольшую поясняющую статью, но мне кажется, что круг любопытных к таким тонкостям будет совсем узок)
Спасибо, теперь вопрос понятен.
Ответ: в случае lock-free
T1никогда не переводит общую структуру в такое состояние, в котором структура "принадлежит" выделенному потоку. В любой момент времени структура доступна конкурирующим потокамTnсогласно обещанной модели потоковой безопасности.Например,
drain_stackявляется MPMC-структурой (Multiple Producers / Multiple Consumers), т.е. произвольное количество потоков могут одновременно писать и читать из этой структуры.Далее,
mpsc_queueобеспечивает уже другую дисциплину - Multiple Producers / Single Consumer. Писать в эту очередь может произвольное количество потоков, а читать только один (либо требуется синхронизация на стороне чтения).И даже в случае SPSC сценария (один писатель и один читатель), всё еще присутствует межпоточная конкуренция за ресурс между писателем и читателем, пусть даже конкуренция за каждую из операций записи и чтения ограничена одним участником.
Про введение понятно, оно заведомо ограничено по объёму, и ставит целью кратко обрисовать проблематику.
Вызывает ли дополнительные вопросы материал, начинающийся со слов "хотелось бы принципиально другого поведения: чтобы поток, положивший элемент в очередь, физически не мог заблокировать того, кто пытается положить следующий или прочитать имеющийся"?
Про это будет отдельная статья, но прямо сейчас уже можно посмотреть исходник 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 алгоритмов, поэтому они будут даны в одном цикле статей.
Разница в том, что вытесненный поток, исполняющий lock-free алгоритм над разделяемой между потоками структуре, не провоцирует блокировку (внужденный уход в спячку) других потоков, конкурирующих за доступ к этой структуре.
Прошу пояснить саму причину этого вопроса - из текста статьи был не понятен сценарий, при котором вытесненный поток, владеющий мьютексом (или критической секцией) блокирует остальные потоки, которым нужен тот же самый ресурс?
Я исходил из того, что проблематика эта известная, поэтому считал, что достаточно упомянуть сам сценарий, который является основным мотивом применения lock-free структур.