Быстрая реализация C ++ для одного производителя

Question

Я ищу реализацию FIFO для одного производителя, которая бы работала быстрее, чем обычная блокировка-запись-разблокировка-сигнал / waitForSignal-блокировка-чтение-разблокировка.Я ищу что-то, поддерживаемое большинством операционных систем POSIX (хорошо подходит для x86), написанное на C или C ++.

Я не собираюсь передавать что-то большее, чем указатель.

Я не обязательно привязан к идее без блокировки, но я хочу что-то быстрое и правильное.В одной из статей, которые я прочитал по этому вопросу, упоминался подход с двумя очередями, который показался мне интересным, но с тех пор я не смог найти много информации об этом.

Из проведенного мной исследования,0mq (который предположительно использует структуру без блокировки для своей схемы inproc: //) выглядит как наиболее привлекательный вариант.При этом я хотел бы убедиться, что ничего не пропустил, прежде чем идти по этому пути.

Еще одна альтернатива может включать использование очереди сообщений POSIX, но, похоже, это будетмедленно для потока <-> поток связи;правда ли это?

Любая реализация очереди без блокировки одного производителя с одним производителем в C? кажется уместной, но принятый ответ там на самом деле не столько перечисление существующих библиотек, сколькоэто «преждевременная оптимизация - это плохо».

Answer 1

Возможно, вы захотите взглянуть на нить Intel Building Building Blocks. Они основаны на примитивах, предоставляемых атомарными операциями пользовательского режима x86, а также потоками pthreads или Win32, и предоставляют быстрые, эффективные, шаблонные структуры данных. Одновременная очередь среди многих.

Answer 2

В дополнение к другим ответам здесь (и в этом очень связанном вопросе ), я воспользуюсь этой возможностью для бесстыдного плагина моей собственной супербыстрой реализации C ++очереди ожидания одного производителя с одним производителемОн:

• Использует семантику перемещения C ++ 11
• Увеличивается по мере необходимости (но только если вы этого хотите)
• Обеспечивает управление памятью без блокировки дляэлементы (с использованием предварительно выделенных смежных блоков)
• Автономный (два заголовка плюс лицензия и readme)
• Компилируется в MSVC2010 +, Intel ICC 13 и GCC 4.7.2 (и долженработать под любым полностью совместимым компилятором C ++ 11)

Это доступно на GitHub под упрощенной лицензией BSD (не стесняйтесь его разветвлять!).

Сопоставимая очередь Очередь Facebook Folly , которая может быть немного быстрее, но не поддерживает рост по мере необходимости (имеет фиксированный размер).

Answer 3

Проблема в том, что POSIX не включает API (который я знаю) для операций с блокировкой. На самом деле, не все платформы поддерживают одни и те же операции для программирования без блокировок (некоторые используют сравнение и замена, некоторые используют условную нагрузку, связанную с хранилищем).

Тем не менее, единственная сложная часть в создании очереди без единого потребителя без блокировки (поддержка нескольких производителей тривиальна) - это обработка проблемы ABA, и это действительно не должно быть проблемой.

Вам нужен односвязный список для продюсеров, к которым можно добавить (prepend to). У потребителя есть локальная очередь, когда она исчерпана, он берет весь список производителей и переворачивает его, создавая новую локальную очередь. Windows SList API является примером.

Answer 4

Просто наткнулся на это: CDS (параллельные структуры данных) сегодня вечером.

CDS (Concurrent Data Structures) - это библиотека шаблонов C ++ без блокировок и детальных алгоритмов. Он содержит коллекцию параллельных структур данных: очереди, карты, схему восстановления указателя опасности и многие другие

Я должен сказать, что я только немного прошел / готовлю его к созданию / сцене (это было не так просто, как мне бы хотелось), но ... вам может быть интересно взглянуть на себя. 1009 *