atomic_queue
1.0.0
C ++ 14 Очередь с несколькими продюсерами-мультиплевыми потребителями на основе круглого буфера и std::atomic .
Разработанный с целью минимизации задержки между одним потоком, втягивающим элемент в очередь, и другой нитью, вытаскивающей его из очереди.
Он был разработан, протестирован и сравнивал на Linux, но должен поддерживать любые платформы C ++ 14, которые реализуют std::atomic . Сообщается как совместимая с Windows, но непрерывные интеграции, размещенные GitHub, в настоящее время настроены только для платформы x86_64 на Ubuntu-20.04 и Ubuntu-22.04. Получите запросы, чтобы расширить непрерывные интеграции для работы на других архитектурах, и/или платформы приветствуются.
При минимизации задержки хорошая конструкция - это не при том, что нечего добавить, а скорее, когда нечего удалить, как иллюстрируют эти очереди.
Минимизация задержки естественным образом максимизирует пропускную способность. Низкая латентная взаимная - высокая сквозная, в идеальном математическом и практическом инженерном смысле. Низкая задержка несовместима с любыми задержками и/или пакетированием, которые разрушают оригинальный (аппаратный) глобальный порядок времени событий, выдвинутых в одну очередь различными потоками. Максимизация пропускной способности, с другой стороны, может быть выполнена за счет задержки путем задержки и отрыва нескольких обновлений.
Основным принципом дизайна эти очереди следуют минимализм , который приводит к такому выбору дизайна, как:
push / pop , ссылка/указатель на элементы в очереди не может быть получена.Влияние каждого из этих небольших вариантов дизайна самостоятельно едва измеримо, но их общее воздействие намного больше, чем простая сумма воздействий компонентов, также известный как Super-Scalar Compounding или Synergy. Синергия, возникающая в связи с объединением нескольких этих небольших вариантов дизайна вместе, - это то, что позволяет процессорам работать при пиковой емкости наименьших препятствий.
Эти варианты дизайна также являются ограничениями:
Приложения с ультра-низкой задержкой нуждаются только в этом и ничего более. Минимализм окупается, см. Пропускную способность и контрольные показатели задержки.
Несколько других хорошо известных и популярных поточных контейнеров используются для справки в критериях:
std::mutex - кольцевой буфер с фиксированным размером со std::mutex .pthread_spinlock - кольцевой буфер с фиксированным размером с pthread_spinlock_t .boost::lockfree::spsc_queue -Очередь без продюсера без ожидания из библиотеки Boost.boost::lockfree::queue -без блокировки с несколькими продюсерами-мультиплевыми очередями из библиотеки Boost.moodycamel::ConcurrentQueue -Очередь без блокировки с несколькими продюсерами-мультиплевыми потребителями, используемая в неблокирующем режиме. Эта очередь предназначена для максимизации пропускной способности за счет задержки и отказа от глобального порядок времени элементов, выдвинутых в одну очередь по разным потокам. Это не эквивалентно другим очереди, сравнимым здесь в этом отношении.moodycamel::ReaderWriterQueue -беззаконный очередь с одним продюсером-кансором, используемая в неблокирующем режиме.xenium::michael_scott_queue -беззаботная очередь многопродуктивно-мульти-потребителей, предложенная Майклом и Скоттом (эта очередь аналогична boost::lockfree::queue , которая также основана на том же предложении).xenium::ramalhete_queue -беззаконный многопродуктор-мульти-потребительская очередь, предложенная Рамалхетом и Корреей.xenium::vyukov_bounded_queue -ограниченная многопродуктивная очередь-пособие на основе версии, предложенной Вюкова.tbb::spin_mutex - заблокированный кольцевой буфер с фиксированным размером с tbb::spin_mutex из строительных блоков Intel.tbb::concurrent_bounded_queue - одноименная очередь, используемая в неблокирующем режиме из строительных блоков Intel.Представленные контейнеры представляют собой шаблоны классов только для заголовков, здание/установка не требуется.
git clone https://github.com/max0x7ba/atomic_queue.git
atomic_queue/include (используйте полный путь) к включенным путям вашей системы сборки.#include <atomic_queue/atomic_queue.h> в вашем источнике C ++. vcpkg install atomic-queue
Следуйте официальному руководству о том, как потреблять пакеты Conan. Детали, конкретные для этой библиотеки, доступны в Conancenter.
Представленные контейнеры представляют собой шаблоны класса только для заголовков, которые требуют только #include <atomic_queue/atomic_queue.h> , здание/установка не требуется.
Здание необходимо для запуска тестов и тестов.
git clone https://github.com/cameron314/concurrentqueue.git
git clone https://github.com/cameron314/readerwriterqueue.git
git clone https://github.com/mpoeter/xenium.git
git clone https://github.com/max0x7ba/atomic_queue.git
cd atomic_queue
make -r -j4 run_benchmarks
Бланка также требует, чтобы библиотека Intel TBB была доступна. Предполагается, что он установлен в /usr/local/include и /usr/local/lib . Если он установлен в другом месте, вы можете изменить cppflags.tbb и ldlibs.tbb в Makefile .
AtomicQueue - кольцевой буфер с фиксированным размером для атомных элементов.OptimistAtomicQueue -более быстрый кольцевой буфер с фиксированным размером для атомных элементов, которые заняты, когда пустые или полные. Это AtomicQueue , используемая с push / pop вместо try_push / try_pop .AtomicQueue2 -кольцевой буфер с фиксированным размером для неатомных элементов.OptimistAtomicQueue2 -более быстрый кольцевой буфер с фиксированным размером для неатомических элементов, которые заняты, если пустые или полные. Это AtomicQueue2 , используемый с push / pop вместо try_push / try_pop . Эти контейнеры имеют соответствующую AtomicQueueB , OptimistAtomicQueueB , AtomicQueueB2 , версии OptimistAtomicQueueB2 , где размер буфера указан в качестве аргумента конструктору.
Полностью заказанный режим поддерживается. В этом режиме потребители получают сообщения в том же заказе FIFO, которые были опубликованы. Этот режим поддерживается для функций push и pop , но не для версий try_ . На Intel X86 полностью заказанный режим имеет 0 стоимости по состоянию на 2019 год.
Поддерживается режим однопродукции-капитала. В этом режиме не требуются дорогие атомные инструкции по модификации чтения-модификации-записи, только самые дешевые атомные нагрузки и магазины. Это значительно улучшает пропускную способность очереди.
Типы элементов Queue-ytry полностью поддерживаются. Например, очередь элементов std::unique_ptr<T> будет AtomicQueue2B<std::unique_ptr<T>> или AtomicQueue2<std::unique_ptr<T>, CAPACITY> .
Шаблоны класса очередей предоставляют следующие функции члена:
try_push - добавляет элемент к концу очереди. Возвращает false , когда очередь полна.try_pop - удаляет элемент с передней части очереди. Возвращает false , когда очередь пуста.push (оптимист) - добавляет элемент к концу очереди. Занятые ожидания, когда очередь полна. Быстрее, чем try_push , когда очередь не полна. Необязательно производители FIFO очереди и общий заказ.pop (оптимист) - Удаляет элемент с передней части очереди. Занятые ожидания, когда очередь пуста. Быстрее, чем try_pop , когда очередь не пуста. Необязательно FIFO потребительские очереди и общий заказ.was_size - Возвращает количество бессоснутых элементов во время вызова. Государство, возможно, изменилось к моменту проверки возврата.was_empty - Возвращает true , если контейнер был пуст во время вызова. Государство, возможно, изменилось к моменту проверки возврата.was_full - возвращает true если контейнер был заполнен во время вызова. Государство, возможно, изменилось к моменту проверки возврата.capacity - возвращает максимальное количество элементов, которые может удержать очередь. Атомные элементы - это те, для которых std::atomic<T>{T{}}.is_lock_free() возвращает true , и, когда доступны функции C ++ 17, std::atomic<T>::is_always_lock_free оценивается в true во время компиляции. Другими словами, процессор может загружать, хранить и сравнивать и обменивать такие элементы атомно изначально. На x86-64 такие элементы являются стандартными арифметическими и указательными типами C ++.
Очерки для атомных элементов оставляют одно значение, чтобы служить пустым элементным маркером NIL , его значение по умолчанию составляет 0 . Значение NIL не должно быть перемещено в очередь, и в функциях push есть утверждение assert для защиты от этого в режиме отладки. Позволяет элементу NIL в очередь в режиме выпуска, что приводит к неопределенному поведению, таким как тупики и/или утерянные элементы очереди.
Обратите внимание, что оптимизм - это выбор потока управления операцией модификации очередей, а не типа очереди. Оптимистский push является самым быстрым, когда очередь не заполнена большую часть времени, оптимистичный pop - когда очередь не пуста большую часть времени. Оптимистичные и не так операции могут быть смешаны без ограничений. OptimistAtomicQueue в тестах использует только оптимистский push и pop .
См. Пример. CC для примера использования.
Operations push и try_push Synchronize-With (как определено в std::memory_order ) с любой последующей работой pop или try_pop того же объекта очереди. Это означает, что:
push / try_push , которая представляет собой операцию memory_order::release . Тот тот же заказ памяти, что и std::mutex::unlock .pop - try_pop , которая представляет собой операцию memory_order::acquire . Тот же порядок памяти, что и std::mutex::lock .push / try_push элемента в очередь, становятся видимыми в потоке потребителя, который pop / try_pop этого конкретного элемента. Доступные очереди здесь используют массив кольцевого буфера для хранения элементов. Емкость очереди фиксируется во время компиляции или времени строительства.
В сценарии производства с несколькими продюсерами-мультиплевыми потребителями емкость кольца должна быть установлена на максимальный ожидаемый размер очереди. Когда кольцевой буфер становится полным, это означает, что потребители не могут употреблять элементы достаточно быстро. Исправление для этого является любым:
push и pop всегда несут некоторые дорогие циклы процессоров, чтобы поддерживать целостность состояния очереди в атомной/последовательной/изолированной форме по сравнению с другими темами, и эти затраты увеличиваются супер-линейно по мере роста спора очереди. Продюсер, выпадение нескольких небольших элементов или элементов, полученных в результате одного события в одно сообщение в очереди, часто является разумным решением.Использование размера массива кольцевого буфера Power-2 позволяет несколько важных оптимизаций:
% SIZE оператора. Остаток бинарного оператора % обычно генерирует инструкцию процессора дивизии, которая не дешевая, но используя повороты размера 2-й andN -производителей вместе с M потребителями, конкурирующими в последующих элементах в одной и той же линии кэша кольцевого буфера в худшем случае, это только один производитель, конкурирующий с одним потребителем (педантично, когда количество процессоров не больше, чем количество элементов, которые могут поместиться в одной линии кэша). Эта оптимизация лучше масштабируется с количеством производителей и потребителей, а также размер элементов. С низким количеством производителей и потребителей (до 2 из каждых в этих критериях) отключение этой оптимизации может привести к лучшей пропускной способности (но более высокая дисперсия между пробегами). Контейнеры используют тип unsigned для размера и внутренних индексов. На платформе x86-64 unsigned шириной 32-разрядной, а size_t -64-разрядная ширина. 64-битные инструкции используют дополнительный префикс инструкции, что приводит к немного большему давлению на кеш инструкции процессора и фронтальный. Следовательно, 32-разрядные индексы unsigned знака используются для максимизации производительности. Это ограничивает размер очереди до 4 294 967 295 элементов, что, по -видимому, является разумным жестким ограничением для многих приложений.
В то время как атомные очереди могут использоваться с любыми типами подвижных элементов (включая std::unique_ptr ), для лучшей пропускной способности и задержки элементы очереди должны быть дешевыми для копирования и без блокировки (например, unsigned или T* ), так что операции push и pop завершают самые быстрые.
Концептуально , операция push или pop делает два атомных шага:
head , потребители увеличивают индекс tail . Каждый слот доступен только одним производителем и одним потребительским потоком.NIL , потребительская загрузка из слота меняет его состояние на NIL . Слот - это прядил для одного производителя и одного потребительского потока. Эти очереди ожидают, что поток, выполняющий push или pop может выполнить шаг 1, а затем быть предварительно выполненным, прежде чем завершить шаг 2.
Алгоритм не содержит блокировки, если есть гарантированный прогресс в масштабе системы. Эти гарантированные очередь прогресс по всей системе по следующим свойствам:
push не зависит от любого предыдущего push . Неполный (преуспевший) push одним потоком производителя не влияет на push любого другого потока.pop не зависит от любого предыдущего pop . Неполный (преуспевший) pop по одному потребительскому потоку не влияет на pop любого другого потока.push из одного потока производителя влияет только на один потребительский поток, который pop элемент из этого конкретного слота очереди. Все остальные pop не затронуты.pop из одной потребительской потока влияет только на одну нить производителя push элемент в этот конкретный слот очереди, ожидая, что он был поглощен давным-давно, в довольно маловероятном сценарии, который производители обернулись вокруг всего кольцевого буфера, в то время как этот потребитель не завершил свою pop . Все остальные потоки push S и pop -s не затронуты. Преодоление потока по потоке задач Linux-это то, что ни один процесс пользовательского пространства не может быть в состоянии влиять или избежать, в противном случае любое/каждое злонамеренное приложение будет использовать это.
Тем не менее, есть несколько вещей, которые можно сделать, чтобы свести к минимуму предотвращение критических приложений миссии:
SCHED_FIFO для ваших потоков, например, chrt --fifo 50 <app> . Поток с более высоким приоритетом SCHED_FIFO или обработчик прерываний ядра все еще могут предотвратить ваши потоки SCHED_FIFO .SCHED_OTHER с его динамически скорректированными приоритетами побеждает цель использования этих очередей.SCHED_FIFO в реальном времени.taskset . Люди часто предлагают ограничить ожидание занятости с помощью последующего вызова std::this_thread::yield() / sched_yield / pthread_yield . Тем не менее, sched_yield - это неправильный инструмент для блокировки, потому что он не связывается с ядром ОС, чего ждет поток, так что планировщик потока ОС никогда не может запланировать вызову, чтобы возобновить в нужное время, когда общее состояние изменилось (если нет других потоков, которые могут работать на этом ядре CPU, так что вызывающий нонглер непосредственно). См. Раздел «Примечания» в man sched_yield и потоке ядра Linux о sched_yield и Spinlocks для получения более подробной информации.
В Linux есть Mutex Type PTHREAD_MUTEX_ADAPTIVE_NP , который занят заблокированным мутексом для ряда итераций, а затем делает блокирующий SYSCALL в ядро, чтобы обезвредить резьбу для ожидания. В критериях это был худший исполнитель, и я не мог найти способ сделать его лучше, и именно поэтому он не включен в тесты.
На процессорах Intel можно использовать 4 регистры управления отладкой для мониторинга области памяти Spinlock для доступа к записи и подождать, используя select (и его друзья) или sigwait (см. perf_event_open и uapi/linux/hw_breakpoint.h для получения более подробной информации). Официант Spinlock может приостановить себя с помощью select или sigwait до тех пор, пока состояние Spinlock не будет обновлено. Но есть только 4 из этих регистров, так что такое решение не масштабировалось.
Просмотреть пропускные и задержки.
Есть несколько поведений ОС, которые усложняют сравнительный анализ:
SCHED_FIFO в реальном времени 50 используется для отключения квантового истечения срока планировщика и создания потоков, не подлежащих обучению с помощью более низких приоритетных процессов/потоков.benchmarks , выполняется не менее 33 раза. Художественные диаграммы отображают средние значения. В диаграмме подсказка инструментов также отображается стандартное отклонение, минимальные и максимальные значения. Концентрация производительности однопродуктивных очередей-с потребительских очередей boost::lockfree::spsc_queue , moodycamel::ReaderWriterQueue и эти очередь в режиме с одним продуктом-с потребителями должны быть идентичными, потому что они реализуют точно одинаковый алгоритм, используя точно одинаковую атомальную нагрузку и инструкции хранить. boost::lockfree::spsc_queue , сравниваемая в то время, не имела оптимизации для минимизации конфликта кэша L1D, неустойчивости холодной ветви или трубопроводов из тонких проблем, заметных только в сгенерированном коде сборки.
У меня есть доступ только к нескольким машинах x86-64. Если у вас есть доступ к различному оборудованию, не стесняйтесь отправлять выходной файл scripts/run-benchmarks.sh и я включу ваши результаты на страницу тестов.
Когда доступны огромные страницы, тесты используют 1x1gb или 16x2mb огромные страницы для очередей, чтобы минимизировать промахи TLB. Чтобы позволить огромным страницам сделать один из:
sudo hugeadm --pool-pages-min 1GB:1
sudo hugeadm --pool-pages-min 2MB:16
В качестве альтернативы, вы можете включить прозрачные огромные страницы в вашей системе и использовать огромный распределитель с огромным планом, такой как TCMalloc.
По умолчанию, Linux Scheduler Drottles в режиме реального времени потребляет 100% процессора и это наносит ущерб для сравнения. Полную информацию можно найти в планировании групп в реальном времени. Чтобы отключить дросселирование ниток в реальном времени:
echo -1 | sudo tee /proc/sys/kernel/sched_rt_runtime_us >/dev/null
N потоки производителей проталкивают 4-байтовое целое число в одну и ту же очередь, n потребительских потоков вытаскивают целые числа из очереди. Все производители публикуют 1 000 000 сообщений в общей сложности. Общее время для отправки и получения всех сообщений измеряется. Трингум выполняется от 1 производителя и 1 потребителя до (total-number-of-cpus / 2) производителей / потребителей для измерения масштабируемости различных очередей.
Один поток публикует целое число в другую ветку через одну очередь и ждет ответа из другой очереди (всего 2 очереди). Бесчфы измеряют общее время 100 000 пинг-понгов, лучших из 10 пробежек. Споры минимальны здесь (1-продюсер-1-потребитель, 1 элемент в очереди), чтобы иметь возможность достичь и измерить самую низкую задержку. Сообщает среднее время в обратном пути.
Вклад более чем приветствуется. .editorconfig и .clang-format могут использоваться для автоматического сопоставления форматирования кода.
Некоторые книги по предмету многопоточного программирования я нашел довольно поучительным:
Copyright (C) 2019 Maxim Egorushkin. MIT Лицензия. Смотрите полную лицензию в лицензии на файл.
