MPMCQueue

MPMCQueue.h

Ограниченная одновременная очередь с несколькими производителями и множеством потребителей, написанная на C++11.

Он закален в боях и ежедневно используется в производстве:

• В игровом движке Frostbite, разработанном Electronic Arts для следующих игр:
  • Гимн (2019)
  • Поле битвы V (2018)
  • ФИФА 18 (2017)
  • Безумная НФЛ 18 (2017)
  • Жажда скорости: Расплата (2017)
• В торговой инфраструктуре с низкой задержкой в ​​Charlesworth Research и Marquette Partners.

Его цитируют следующие статьи:

• Пэйчжао Оу и Брайан Демски. 2018. На пути к пониманию стоимости предотвращения результатов из воздуха. Учеб. Программа АКМ. Ланг. 2, OOPSLA, статья 136 (октябрь 2018 г.), 29 страниц. DOI: https://doi.org/10.1145/3276506.

Пример

MPMCQueue< int > q ( 10 );
auto t1 = std::thread([&] {
  int v;
  q. pop (v);
  std::cout << " t1 " << v << " n " ;
});
auto t2 = std::thread([&] {
  int v;
  q. pop (v);
  std::cout << " t2 " << v << " n " ;
});
q.push( 1 );
q.push( 2 );
t1.join();
t2.join();

Использование

• MPMCQueue<T>(size_t capacity);

  Создает новую MPMCQueue содержащую элементы типа T с capacity .

• void emplace(Args &&... args);

  Поставьте элемент в очередь, используя конструкцию на месте. Блокируется, если очередь заполнена.

• bool try_emplace(Args &&... args);

  Попробуйте поставить элемент в очередь, используя конструкцию на месте. Возвращает true в случае успеха и false если очередь заполнена.

• void push(const T &v);

  Поставьте элемент в очередь, используя конструкцию копирования. Блокируется, если очередь заполнена.

• template <typename P> void push(P &&v);

  Поставьте элемент в очередь, используя конструкцию перемещения. Участвует в разрешении перегрузки, только если std::is_nothrow_constructible<T, P&&>::value == true . Блокируется, если очередь заполнена.

• bool try_push(const T &v);

  Попробуйте поставить элемент в очередь, используя конструкцию копирования. Возвращает true в случае успеха и false если очередь заполнена.

• template <typename P> bool try_push(P &&v);

  Попробуйте поставить элемент в очередь, используя конструкцию перемещения. Участвует в разрешении перегрузки, только если std::is_nothrow_constructible<T, P&&>::value == true . Возвращает true в случае успеха и false если очередь заполнена.

• void pop(T &v);

  Удалите элемент из очереди, скопировав или переместив его в v . Блокируется, если очередь пуста.

• bool try_pop(T &v);

  Попробуйте исключить элемент из очереди, скопировав или переместив его в v . Возвращайте true в случае успеха и false если очередь пуста.

• ssize_t size();

  Возвращает количество элементов в очереди.

  Размер может быть отрицательным, если очередь пуста и ожидает хотя бы один читатель. Поскольку это параллельная очередь, ее размер является лишь приблизительным, пока все потоки чтения и записи не будут объединены.

• bool empty();

  Возвращает true, если очередь пуста.

  Поскольку это параллельная очередь, это всего лишь предположение, пока все потоки чтения и записи не будут объединены.

Все операции, кроме создания и разрушения, являются потокобезопасными.

Выполнение

В очереди:

1. Получите следующий билет записи у руководителя .
2. Подождите нашей очереди (2 * (тикет/емкость)) для записи слота (тикет % емкости).
3. Установите Turn = Turn + 1, чтобы сообщить читателям, что мы закончили писать.

Удаление из очереди:

1. Получите следующий билет чтения из хвоста .
2. Подождите нашей очереди (2 * (тикет/емкость) + 1) для чтения слота (% емкости билета).
3. Установите Turn = Turn + 1, чтобы сообщить авторам, что мы закончили чтение.

Ссылки:

• Дэниел Ороско, Элкин Гарсия, Риши Хан, Келли Ливингстон и Гуан Р. Гао . 2012. На пути к высокопроизводительным алгоритмам на многоядерных архитектурах. АКМ Транс. Архит. Код Оптим. 8, 4, статья 49 (январь 2012 г.), 21 стр. DOI: https://doi.org/10.1145/2086696.2086728.
• Дэйв Дайс . 2014. PTLQueue: масштабируемая очередь MPMC ограниченной емкости.
• Александр Отенко . US 8607249 B2: Система и способ для эффективной реализации параллельной очереди.
• Массимилиано Менегин, Давиде Пасетто, Хубертус Франке . 2012. Оценка производительности механизмов межпоточной связи в многоядерных/многопоточных архитектурах. DOI: https://doi.org/10.1145/2287076.2287098.
• Пол Э. Маккенни . 2010. Барьеры памяти: взгляд на аппаратное обеспечение для хакеров программного обеспечения.
• Дмитрий Вьюков . 2014. Ограниченная очередь MPMC.

Тестирование

Тестировать алгоритмы параллелизма сложно. Я использую два подхода для тестирования реализации:

• Однопоточная проверка того, что функциональность работает должным образом, включая правильность вызова конструктора и деструктора элемента.
• Многопоточный нечеткий тест, позволяющий убедиться, что все элементы правильно помещаются в очередь и удаляются из нее в условиях серьезной конкуренции.

TODO

• Добавьте поддержку распределителя, чтобы очередь могла использоваться с огромными страницами и общей памятью.
• Добавьте тесты и сравните с boost::lockfree::queue и другими.
• Используйте концепции C++20 вместо static_assert если они доступны.
• Используйте std::hardware_destructive_interference_size если доступно.
• Добавьте API для операций удаления из очереди с нулевым копированием и пакетного удаления из очереди.
• Добавить атрибуты [[nodiscard]]

О

Этот проект был создан Эриком Ригторпом <[email protected]>.