Есть ли готовая к производству очередь без блокировок или хеш-реализация на C ++ [закрыто]

80

Я довольно много искал в Google безблокировочную очередь в C ++. Я нашел код и несколько проб, но ничего, что мне удалось скомпилировать. Также приветствуется хеш-код без блокировки.

РЕЗЮМЕ: Пока у меня нет положительного ответа. Не существует «готовой к производству» библиотеки, и, что удивительно, ни одна из существующих библиотек не соответствует API контейнеров STL.

КРАСНЫЙ МЯГКИЙ ADAIR
источник
4
Visual Studio 2010 содержит очередь без блокировок в <concurrent_queue.h>
Рик,
2
Обратите внимание, что, как ни странно, термин «без блокировок» не обязательно означает отсутствие блокировок. См. Одно определение на en.wikipedia.org/wiki/Non-blocking_algorithm .
Кристофер Джонсон
8
Ничего себе вопрос, в котором спрашивается, как решить распространенную, но сложную проблему в многопоточном программировании, которая имеет множество решений, вызвала много дискуссий и заработала массу положительных отзывов ... Затем 9 лет спустя вы закрываете ее как не по теме. Спасибо за ваш вклад в StackOverflow, Натан Оливер, сэр E_net4 the Wise Downvoter, Жан-Франсуа Фабр, Machavity и gre_gor / s
muusbolla
1
Я бы сказал, что люди, которые закрывали вопрос, наверное, этого не понимают.
Дерф Скрен

Ответы:

40

Начиная с версии 1.53, boost предоставляет набор структур данных без блокировок , включая очереди, стеки и очереди с одним производителем / одним потребителем (т. Е. Кольцевые буферы).

Новая звезда
источник
boost :: lockfree :: queue работает только с типами POD и в большинстве случаев не совсем полезен. Я уверен, что если бы существовал способ обеспечить более гибкую структуру, boost ввел бы его.
rahman
1
@rahman, где с этим проблема? Если вы хотите передать что-либо еще, особенно объекты с непрозрачными, возможно, блокирующими побочными эффектами, вы не поняли всей цели дизайна без блокировок.
Ichthyo
Почему boost предоставляет очередь и стек без блокировок, основанные на связном списке. Но они не предоставляют свободный связанный список?
Deqing
25

Отправной точкой могут быть статьи Херба Саттера DDJ либо для одного производителя и потребителя, либо для нескольких . Код, который он дает (встроенный, начиная со второй страницы каждой статьи), использует тип шаблона atomic <T> в стиле C ++ 0x; которые вы можете имитировать с помощью межпроцессной библиотеки Boost.

Код повышения скрыт в глубине межпроцессной библиотеки, но, прочитав соответствующий файл заголовка (atomic.hpp), реализации необходимых операций сравнения и замены в системах, с которыми я знаком, выглядят неплохо.

Стив Гилхэм
источник
1
Стив, меня также интересуют атомарные реализации Boost, но они, похоже, находятся в разделе "Interprocess" / и не документированы. Насколько безопасно их использовать? Благодаря!
Ким Грасман,
Я очень хорошо знаю статьи Херба Саттера - где вы нашли источники? Они не публикуются DDJ или на его сайте (а может я слепой?).
RED SOFT ADAIR,
1
Код встроен в те статьи, которые начинаются на соответствующих вторых страницах.
Стив Гилхэм,
3
Если вам нужен действительно свободный от блокировок код для нескольких разработчиков или потребителей, то меня нет. Пример очереди с несколькими производителями Саттера не является свободным от блокировки - есть блокировка для сериализации производителей и блокировка для сериализации потребителей. Если вы сможете его найти, меня это тоже заинтересует.
Стив Гилхэм,
1
На tim.klingt.org/git?p=boost_lockfree.git есть проект boost :: lockfree ; что вы можете посмотреть. Одна из его целей - предоставить версию атомарных примитивов, отличную от :: details ::.
sstock
17

Да!

Я написал очередь безблокировочного . Он имеет Особенности ™:

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

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

Предостережения:

  • Только для архитектуры с одним производителем и одним потребителем (т.е. два потока)
  • Тщательно протестирован на x86 (-64) и должен работать на ARM, PowerPC и других процессорах, где выровненные целые числа с собственным размером, а загрузка и хранение указателей являются, естественно, атомарными, но не тестировались в полевых условиях на процессорах не x86 (если один, чтобы проверить это, дайте мне знать)
  • Не знаю, нарушаются ли какие-либо патенты (используйте на свой страх и риск и т. Д.). Обратите внимание, что я спроектировал и реализовал его сам с нуля.
Кэмерон
источник
2
Звучит очень хорошо, но для использования реальной многопоточности требуется несколько производителей и / или несколько потребителей.
RED SOFT ADAIR
2
@RED: зависит от приложения. Единственный производитель / потребитель - все, что мне было нужно, так что это все, что я построил ;-)
Кэмерон
@Cameron: Отличный материал! Вы сравнивали свою очередь с глупостью ProducerConsumerQueue в Facebook ? Я сделал это, используя ваш тестовый код, и он, похоже, значительно превосходит ваш RWQ и SPSC Дмитрия. Я использую OS X 10.8.3 с процессором Core 2 Duo с тактовой частотой 3,06 ГГц (T9900) и скомпилировал код с помощью Clang с -O3. Я сделал это, потому что сейчас смотрю на очередь с одним производителем / одним потребителем для одного из моих проектов, и я считал ваш кандидат :)
Андре Невес,
@ André: Я только что проверил :-) Безумие Facebook немного быстрее моего при удалении из пустой очереди и немного медленнее при удалении из непустой очереди в одном потоке. Скорость всех остальных операций почти такая же (это было с g ++ -O3 на виртуальной машине). Какой размер вы используете для очереди безумия? (Я использовал MAX.) У меня и Дмитрия оба растут по мере необходимости, в то время как глупая операция исправлена ​​- и, конечно, самая быстрая операция постановки в очередь - это когда нет места и она просто терпит неудачу. Глядя на код, кажется, что Folly's использует те же идеи, что и я, но без возможности изменения размера.
Кэмерон
@ André: О, еще одна вещь, о которой я забыл упомянуть - с моим кодом теста тест "Raw empty remove" выполняет, безусловно, большинство итераций (поскольку он настолько прост, что требуется больше для получения измеримого результата), что имеет тенденцию чтобы непропорционально повлиять на окончательные "средние числа операций в секунду". Множители (и плоские временные значения) обычно более полезны. В любом случае, на этих скоростях все эти очереди будут достаточно быстрыми, если они на самом деле используются для чего-то более значительного, чем мои глупые синтетические тесты ;-)
Кэмерон
15

Facebook Folly, похоже, имеет свободные от блокировки структуры данных, основанные на C ++ 11 <atomic>:

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

Ура!

Андре Невес
источник
У них также есть очередь MPMC. что, по их утверждению, «блокирует необязательно». Похоже, что он не входит в их обычную документацию, не уверен, рекомендуется ли его использовать.
Расти Шеклфорд
10

Проверив большинство приведенных ответов, я могу только заявить:

Ответ - НЕТ .

Не существует такого права, которое можно было бы использовать прямо из коробки.

КРАСНЫЙ МЯГКИЙ ADAIR
источник
4
100% правильно. Я пришел к тому же результату с помощью группы новостей comp.programming.threads. Одна из причин заключается в том, что область незаблокированных структур данных является патентным минным полем. Так что даже коммерческие библиотеки, такие как Intel, избегают этого.
Lothar
Это C, а не C ++. Пожалуйста, прочтите вопросы перед голосованием вниз.
RED SOFT ADAIR
Извинения. Я отмечаю, что SO не позволит мне отменить мой голос, поскольку считает, что голосование слишком старое. Я думаю, разработчикам SO нужно больше делать - кажется, они добавляют все больше бесполезных действий.
3
Почему этот ответ получил столько голосов. Вопрос легко редактируется. Или это может быть в комментарии.
пользователь
6

Самое близкое, что мне известно, - это односвязные списки Windows с блокировкой . Конечно, это только Windows.

Неманья Трифунович
источник
Вау - похоже, это так. Мне нужно время, чтобы проверить это (пока не могу), но я вернусь к вам.
RED SOFT ADAIR,
Interlocked Singly Linked List - замечательный инструмент, но, к сожалению, это не FIFO.
ali_bahoo 01
Насколько я помню, это не тот список. Вы не можете отвязать произвольные элементы; единственное, что вы можете сделать, это удалить весь список. Возможно, с тех пор это продвинулось ...
5

Если у вас есть очередь / FIFO с несколькими производителями / одним потребителем, вы можете легко сделать одну LockFree с помощью SLIST или тривиального стека Lock Free LIFO. У вас есть второй «частный» стек для потребителя (который также может быть реализован в виде SLIST для простоты или любой другой модели стека по вашему выбору). Потребитель извлекает элементы из частного стека. Всякий раз, когда частный LIFO исчерпывается, вы выполняете Flush, а не Pop из совместно используемого параллельного SLIST (захват всей цепочки SLIST), а затем проходите по списку Flushing по порядку, помещая элементы в частный стек.

Это работает для одного производителя / одного потребителя и для нескольких производителей / одного потребителя.

Однако это не работает для случаев с несколькими потребителями (с одним или несколькими производителями).

Кроме того, что касается хеш-таблиц, они являются идеальным кандидатом для «чередования», при котором хеш просто разделяется на сегменты, имеющие блокировку на сегменты кеша. Вот как это делает параллельная библиотека Java (с использованием 32 полос). Если у вас есть облегченная блокировка чтения-записи, к хэш-таблице можно получить одновременный доступ для одновременного чтения, и вы остановитесь только тогда, когда запись происходит на оспариваемых полосах (и, возможно, если вы разрешите увеличение хеш-таблицы).

Если вы свертываете свои собственные, убедитесь, что ваши блокировки чередуются с записями хэша, а не помещают все свои блокировки в массив рядом друг с другом, чтобы у вас меньше шансов получить ложное совместное использование.

Адисак
источник
Спасибо за Ваш ответ. Я ищу "готовое к производству" решение / шаблон на C ++. Я не хочу кататься самостоятельно. Вы знаете такую ​​реализацию?
RED SOFT ADAIR,
4

Я могу немного опоздать с этим.

Отсутствие решений (в заданном вопросе) в основном связано с важной проблемой в C ++ (до C ++ 0x / 11): C ++ не имеет (не имеет) модели параллельной памяти.

Теперь, используя std :: atomic, вы можете контролировать проблемы с упорядочением памяти и правильно выполнять операции сравнения и замены. Я сам написал реализацию безблокирующей очереди Майкла и Скотта (PODC96) с использованием C ++ 11 и указателей опасностей Майкла (IEEE TPDS 2004), чтобы избежать проблем с ранним освобождением и ABA. Он работает нормально, но это быстрая и грязная реализация, и я не удовлетворен фактическими характеристиками. Код доступен в битбакете: LockFreeExperiment

Также возможно реализовать очередь без блокировок без указателей опасности, используя двойные слова CAS (но 64-битные версии будут возможны только на x86-64 с использованием cmpxchg16b), у меня есть сообщение в блоге об этом (с непроверенным кодом для очереди) здесь : Реализация общего двойного слова для сравнения и замены для x86 / x86-64 (блог LSE).

Мой собственный тест показал мне, что очередь с двойной блокировкой (также в статье Майкла и Скотта 1996 г.) работает так же, как и безблокировочная (я не достиг достаточного количества конфликтов, поэтому заблокированные структуры данных имеют проблемы с производительностью, но мой тест слишком легкий для сейчас), а параллельная очередь из TBB Intel кажется даже лучше (в два раза быстрее) для относительно небольшого числа (в зависимости от операционной системы, под FreeBSD 9, самая низкая граница, которую я нашел до сих пор, это число составляет 8 потоков на i7 с 4-мя ht-ядрами и, следовательно, 8-ю логическими ЦП) потоков и очень странным поведением (время выполнения моего простого теста увеличилось с секунд до часов!)

Еще одно ограничение для свободных от блокировок очередей в соответствии со стилем STL: наличие итераторов в блокируемых очередях не имеет смысла.

Марван Бурелль
источник
3

А затем появились строительные блоки Intel Threading . И какое-то время это было хорошо.

PS: вы ищете concurrent_queue и concurrent_hash_map

Эдуард А.
источник
6
Это не без блокировки. См. Software.intel.com/en-us/forums/intel-threading-building-blocks/…
RED SOFT ADAIR
1
Я знаю, что строго придерживается принципа lock-free, но я, тем не менее, думал, что это может помочь OP с его проблемой, так как lock-free вещь - это просто деталь реализации. Я думал, он ищет коллекции, которые хорошо работают с одновременным доступом.
Эдуард А.
Lock-free вещь - это не просто деталь реализации. Это совсем другой зверь.
arunmoezhi
1

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

Тобиас
источник
Для меня не имеет смысла, почему доступен распределитель памяти. Просто используйте структуры данных с внутренними указателями (вы знаете старый добрый способ, пока не сошли с ума с контейнерами и не потеряли навыки даже для реализации простых хеш-таблиц).
Lothar
1

Следующее - из статьи Херба Саттера о Очереди без одновременной блокировки http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1 . Я сделал некоторые изменения, например, переупорядочил компилятор. Для компиляции этого кода требуется GCC v4.4 +.

#include <atomic>
#include <iostream>
using namespace std;

//compile with g++ setting -std=c++0x

#define CACHE_LINE_SIZE 64

template <typename T>
struct LowLockQueue {
private:
    struct Node {
    Node( T* val ) : value(val), next(nullptr) { }
    T* value;
    atomic<Node*> next;
    char pad[CACHE_LINE_SIZE - sizeof(T*)- sizeof(atomic<Node*>)];
    };
    char pad0[CACHE_LINE_SIZE];

// for one consumer at a time
    Node* first;

    char pad1[CACHE_LINE_SIZE
          - sizeof(Node*)];

// shared among consumers
    atomic<bool> consumerLock;

    char pad2[CACHE_LINE_SIZE
          - sizeof(atomic<bool>)];

// for one producer at a time
    Node* last;

    char pad3[CACHE_LINE_SIZE
          - sizeof(Node*)];

// shared among producers
    atomic<bool> producerLock;

    char pad4[CACHE_LINE_SIZE
          - sizeof(atomic<bool>)];

public:
    LowLockQueue() {
    first = last = new Node( nullptr );
    producerLock = consumerLock = false;
    }
    ~LowLockQueue() {
    while( first != nullptr ) {      // release the list
        Node* tmp = first;
        first = tmp->next;
        delete tmp->value;       // no-op if null
        delete tmp;
    }
    }

    void Produce( const T& t ) {
    Node* tmp = new Node( new T(t) );
    asm volatile("" ::: "memory");                            // prevent compiler reordering
    while( producerLock.exchange(true) )
        { }   // acquire exclusivity
    last->next = tmp;         // publish to consumers
    last = tmp;             // swing last forward
    producerLock = false;       // release exclusivity
    }

    bool Consume( T& result ) {
    while( consumerLock.exchange(true) )
        { }    // acquire exclusivity
    Node* theFirst = first;
    Node* theNext = first-> next;
    if( theNext != nullptr ) {   // if queue is nonempty
        T* val = theNext->value;    // take it out
        asm volatile("" ::: "memory");                            // prevent compiler reordering
        theNext->value = nullptr;  // of the Node
        first = theNext;          // swing first forward
        consumerLock = false;             // release exclusivity
        result = *val;    // now copy it back
        delete val;       // clean up the value
        delete theFirst;      // and the old dummy
        return true;      // and report success
    }
    consumerLock = false;   // release exclusivity
    return false;                  // report queue was empty
    }
};

int main(int argc, char* argv[])
{
    //Instead of this Mambo Jambo one can use pthreads in Linux to test comprehensively
LowLockQueue<int> Q;
Q.Produce(2);
Q.Produce(6);

int a;
Q.Consume(a);
cout<< a << endl;
Q.Consume(a);
cout<< a << endl;

return 0;
}
энтузиазм
источник
4
Это не без блокировки. Конечно, он не использует блокировку, предоставляемую операционной системой, но способ, которым он вращается (например) на "atomic <bool> consumerLock", определенно является поведением блокировки. Если поток выйдет из строя, пока он удерживает одну из этих блокировок, работа будет невозможна. Так говорит даже сам Херб (я думаю, на странице 4 этой статьи).
Джеймс Каксесе
0

Я написал это в какой-то момент, вероятно, еще в 2010 году, я уверен, с помощью разных ссылок. Это несколько производителей, один потребитель.

template <typename T>
class MPSCLockFreeQueue 
{
private:
    struct Node 
    {
        Node( T val ) : value(val), next(NULL) { }
        T value;
        Node* next;
    };
    Node * Head;               
    __declspec(align(4)) Node * InsertionPoint;  //__declspec(align(4)) forces 32bit alignment this must be changed for 64bit when appropriate.

public:
    MPSCLockFreeQueue() 
    {
        InsertionPoint = new Node( T() );
        Head = InsertionPoint;
    }
    ~MPSCLockFreeQueue() 
    {
        // release the list
        T result;
        while( Consume(result) ) 
        {   
            //The list should be cleaned up before the destructor is called as there is no way to know whether or not to delete the value.
            //So we just do our best.
        }
    }

    void Produce( const T& t ) 
    {
        Node * node = new Node(t);
        Node * oldInsertionPoint = (Node *) InterLockedxChange((volatile void **)&InsertionPoint,node);
        oldInsertionPoint->next = node;
    }

    bool Consume( T& result ) 
    {
        if (Head->next)
        {
            Node * oldHead = Head;
            Head = Head->next;
            delete oldHead;
            result = Head->value;
            return true;
        }       
        return false;               // else report empty
    }

};
кудрявый
источник