¿Existe una implementación de hash o cola sin bloqueo lista para producción en C ++ [cerrado]

80

He estado buscando en Google bastante una cola sin bloqueos en C ++. Encontré algo de código y algunas pruebas, pero nada que pudiera compilar. Un hash sin candados también sería bienvenido.

RESUMEN: Hasta ahora no tengo una respuesta positiva. No hay una biblioteca "lista para producción" y, sorprendentemente, ninguna de las bibliotecas existentes cumple con la API de los contenedores STL.

ADAIR SUAVE ROJO
fuente
4
Visual Studio 2010 contiene una cola sin bloqueos en <concurrent_queue.h>
Rick
1
Y hay un hash_map y unordered_map en code.msdn.com/concrtextras
Rick
2
Tenga en cuenta que, curiosamente, el término "sin candados" no significa necesariamente que no haya candados. Consulte en.wikipedia.org/wiki/Non-blocking_algorithm para obtener una definición.
Kristopher Johnson
8
Wow, una pregunta que pregunta cómo resolver un problema común pero difícil en la programación multiproceso que tiene múltiples soluciones, generó mucha discusión y obtuvo un montón de votos positivos ... Luego, 9 años después, lo cierra como fuera de tema. Gracias por su contribución a StackOverflow, NathanOliver, Sir E_net4 the Wise Downvoter, Jean-François Fabre, Machavity y gre_gor / s
muusbolla
1
Yo diría que la gente que cerró la pregunta probablemente no la entienda.
Derf Skren

Respuestas:

40

A partir de la versión 1.53, boost proporciona un conjunto de estructuras de datos sin bloqueo , que incluyen colas, pilas y colas de un solo productor / un solo consumidor (es decir, búferes de anillo).

Estrella nueva
fuente
boost :: lockfree :: queue solo funciona con tipos POD y la mayoría de las veces no es del todo útil. Estoy seguro de que si hubiera una forma de proporcionar una estructura más flexible, boost la habría introducido.
rahman
1
@rahman, ¿dónde está el problema con eso? Si desea pasar cualquier otra cosa, especialmente objetos con efectos secundarios opacos que posiblemente bloqueen, no ha entendido todo el propósito del diseño sin bloqueo.
Ichthyo
Por qué boost proporciona una cola y una pila sin bloqueos, ambas basadas en una lista vinculada. ¿Pero no están proporcionando una lista enlazada sin candados?
Deqing
25

El punto de partida sería cualquiera de los artículos DDJ de Herb Sutter para un solo productor y consumidor o para varios . El código que da (en línea comenzando en la segunda página de cada artículo) usa el tipo de plantilla atómica <T> estilo C ++ 0x; que puede imitar utilizando la biblioteca entre procesos de Boost.

El código de impulso está enterrado en las profundidades de la biblioteca entre procesos, pero después de leer el archivo de encabezado apropiado (atomic.hpp), las implementaciones para las operaciones necesarias de comparación e intercambio en los sistemas con los que estoy familiarizado parecen sólidas.

Steve Gilham
fuente
1
Steve, también estoy interesado en las implementaciones atómicas de Boost, pero parecen residir en los detalles de Interprocess y no están documentadas. ¿Son seguros de usar de todos modos? ¡Gracias!
Kim Gräsman
Conozco muy bien los artículos de Herb Sutter. ¿Dónde ha encontrado las fuentes? No son publicados por DDJ ni en su sitio (¿o tal vez soy ciego?).
RED SOFT ADAIR
1
El código está en línea en esos artículos comenzando en sus respectivas segundas páginas.
Steve Gilham
3
Si desea un código verdaderamente libre de bloqueo, para múltiples priducers o consumidores, entonces estoy fuera. El ejemplo de cola de múltiples productores de Sutter no está libre de bloqueos: hay un bloqueo para serializar productores y un bloqueo para serializar consumidores. Si puede encontrar uno, también me interesaría.
Steve Gilham
1
Hay un proyecto boost :: lockfree en tim.klingt.org/git?p=boost_lockfree.git ; que puedes mirar. Uno de sus objetivos es proporcionar una versión que no sea :: detalles :: de primitivas atómicas.
sstock
17

¡Si!

Yo escribí una cola sin bloqueo . Tiene Features ™:

  • Totalmente sin espera (sin bucles CAS)
  • Súper rápido (más de cien millones de operaciones de puesta en cola / retirada de cola por segundo)
  • Utiliza semántica de movimiento de C ++ 11
  • Crece según sea necesario (pero solo si lo desea)
  • Gestiona la memoria sin bloqueos para los elementos (utilizando bloques contiguos preasignados)
  • Independiente (dos encabezados más una licencia y un archivo Léame)
  • Se compila bajo MSVC2010 +, Intel ICC 13 y GCC 4.7.2 (y debería funcionar con cualquier compilador compatible con C ++ 11)

Está disponible en GitHub bajo la licencia BSD simplificada (¡no dude en bifurcarlo!).

Advertencias:

  • Solo para arquitectura de un solo productor y consumidor (es decir, dos subprocesos)
  • Probado exhaustivamente en x86 (-64), y debería funcionar en ARM, PowerPC y otras CPU donde los enteros de tamaño nativo alineados y las cargas de puntero y los almacenes son naturalmente atómicos, pero no se han probado en el campo en CPU que no son x86 (si alguien tiene uno para probarlo avísame)
  • No tengo idea de si se ha infringido alguna patente (utilice bajo su propio riesgo, etc.). Tenga en cuenta que lo diseñé e implementé yo mismo desde cero.
Cameron
fuente
2
Suena muy bien, pero se necesitan múltiples productores y / o múltiples consumidores para aprovechar el subproceso múltiple real.
RED SOFT ADAIR
2
@RED: Depende de la aplicación. Un solo productor / consumidor era todo lo que necesitaba, así que es todo lo que construí ;-)
Cameron
@Cameron: ¡Cosas geniales! ¿Ha comparado su cola con la locura de Facebook ProducerConsumerQueue ? Lo he hecho usando su código de referencia y parece superar dramáticamente tanto su RWQ como el SPSC de Dmitry. Estoy en OS X 10.8.3 con un Core 2 Duo de 3.06 GHz (T9900) y compilé el código usando Clang con -O3. Hice esto porque actualmente estoy viendo una cola de un solo productor / un solo consumidor para uno de mis proyectos y consideré el suyo como un candidato :)
André Neves
@ André: Acabo de verificar ahora :-) La locura de Facebook es un poco más rápida que la mía cuando se quita de una cola vacía, y un poco más lenta cuando se quita de una cola no vacía en un solo hilo. Todas las demás operaciones tienen casi exactamente la misma velocidad (esto fue con g ++ -O3 en una VM). ¿Qué tamaño estás usando para la cola de locura? (Usé MAX.) Tanto el mío como el de Dmitry crecen según sea necesario, mientras que el disparate es fijo y, por supuesto, la operación de puesta en cola más rápida es cuando no hay espacio y simplemente falla. Mirando el código, locura parece estar usando las mismas ideas que las mías, pero sin posibilidad de cambiar el tamaño.
Cameron
@ André: Oh, una cosa más que olvidé mencionar: con mi código de referencia, la referencia "Eliminación vacía sin procesar" hace, con mucho, la mayoría de las iteraciones (ya que es tan simple, se necesitan más para obtener un resultado medible), lo que tiende para afectar desproporcionadamente los números finales de "operaciones / s promedio". Los multiplicadores (y los valores de tiempo planos) son generalmente más útiles. De todos modos, a estas velocidades, todas estas colas serán lo suficientemente rápidas si en realidad se están utilizando para algo más sustancioso que mis estúpidos puntos de referencia sintéticos ;-)
Cameron
15

Folly de Facebook parece tener estructuras de datos sin bloqueo basadas en C ++ 11 <atomic>:

Me atrevería a decir que estos se utilizan actualmente en producción, por lo que supongo que podrían utilizarse con seguridad en otros proyectos.

¡Salud!

André Neves
fuente
También tienen una cola MPMC. que, según ellos, es "bloqueo opcional". Parece no ser parte de su documentación regular, no estoy seguro de si se recomienda su uso.
Rusty Shackleford
10

Después de haber verificado la mayoría de las respuestas dadas, solo puedo decir:

La respuesta es NO .

No existe tal cosa correcta que pueda usarse nada más sacarlo de la caja.

ADAIR SUAVE ROJO
fuente
4
100% correcto. Llegué al mismo resultado con la ayuda del grupo de noticias comp.programming.threads. Una razón es que el área de estructuras de datos libres de bloqueos es un campo minado de patentes. Así que incluso las bibliotecas comerciales como Intels lo están evitando.
Lothar
Esto es C, no C ++. Lea las preguntas antes de votar.
RED SOFT ADAIR
Disculpas Observo que SO no me permitirá deshacer mi voto ya que considera que el voto es demasiado antiguo. Creo que los desarrolladores de SO necesitan hacer más: parecen estar agregando un número cada vez mayor de comportamientos inútiles.
3
Por qué esta respuesta está recibiendo tantos votos a favor. La pregunta se puede editar fácilmente. O esto podría estar en un comentario.
usuario
6

Lo más parecido que conozco son las listas enlazadas individualmente entrelazadas de Windows . Por supuesto, solo es Windows.

Nemanja Trifunovic
fuente
Vaya, eso parece ser todo. Necesitaré algo de tiempo para comprobarlo (no puedo hacerlo actualmente) pero volveré contigo.
RED SOFT ADAIR
Interlocked Singly Linked List es una herramienta maravillosa, pero lamentablemente no es FIFO.
ali_bahoo
No es una lista adecuada, según recuerdo. No puede desvincular elementos arbitrarios; lo único que puede hacer es eliminar toda la lista. Tal vez ha pasado desde entonces ...
5

Si tiene una cola / FIFO de múltiples productores / consumidores individuales, puede crear fácilmente un LockFree usando SLIST o una pila LIFO de Lock Free trivial. Lo que hace es tener una segunda pila "privada" para el consumidor (que también se puede hacer como una SLIST para simplificar o cualquier otro modelo de pila que elija). El consumidor saca artículos de la pila privada. Siempre que se agota el LIFO privado, realiza un Flush en lugar de Pop off el SLIST concurrente compartido (agarrando toda la cadena SLIST) y luego recorre la lista Flushed en orden empujando los elementos a la pila privada.

Eso funciona para un solo productor / un solo consumidor y para múltiples productores / un solo consumidor.

Sin embargo, no funciona para casos de consumidores múltiples (ya sea con un solo productor o con múltiples productores).

Además, en lo que respecta a las tablas hash, son un candidato ideal para la "creación de bandas", que es simplemente dividir el hash en segmentos que tienen un bloqueo por segmentos de la caché. Así es como lo hace la biblioteca concurrente de Java (usando 32 rayas). Si tiene un bloqueo de lectura-escritura liviano, se puede acceder a la tabla hash simultáneamente para lecturas simultáneas y solo se detendrá cuando la escritura se produzca en franjas impugnadas (y posiblemente si permite el crecimiento de la tabla hash).

Si lanza el suyo, asegúrese de intercalar sus bloqueos con las entradas hash en lugar de poner todos sus bloqueos en una matriz uno al lado del otro para que sea menos probable que comparta información falsa.

Adisak
fuente
Gracias por tu respuesta. Estoy buscando una solución / plantilla "lista para producción" en C ++. No quiero rodar el mío. ¿Conoce tal implementación?
RED SOFT ADAIR
4

Puede que llegue un poco tarde a esto.

La ausencia de soluciones (en la pregunta que se hizo) se debe principalmente a un problema importante en C ++ (antes de C ++ 0x / 11): C ++ no tiene (tiene) ningún modelo de memoria concurrente.

Ahora, con std :: atomic, puede controlar los problemas de ordenación de la memoria y realizar operaciones adecuadas de comparación e intercambio. Yo mismo escribí una implementación de la cola sin bloqueo de Micheal & Scott (PODC96) usando C ++ 11 y los Hazard Pointers de Micheal (IEEE TPDS 2004) para evitar problemas tempranos libres y ABA. Funciona bien, pero es una implementación rápida y sucia y no estoy satisfecho con el rendimiento real. El código está disponible en bitbucket: LockFreeExperiment

También es posible implementar una cola sin bloqueo sin punteros de peligro usando CAS de palabras dobles (pero las versiones de 64 bits solo serán posibles en x86-64 usando cmpxchg16b), tengo una publicación de blog sobre eso (con código no probado para la cola) aquí : Implementación de comparación e intercambio genérico de palabras dobles para x86 / x86-64 (blog de LSE).

Mi propio punto de referencia me muestra que la cola de doble bloqueo (también en el documento de Micheal & Scott 1996) funciona tan bien como la que no tiene bloqueo (no he alcanzado la suficiente contención para que las estructuras de datos bloqueadas tengan problemas de rendimiento, pero mi banco es demasiado liviano para ahora) y la cola simultánea del TBB de Intel parece incluso mejor (dos veces más rápido) para un número relativamente pequeño (dependiendo del sistema operativo, en FreeBSD 9, el límite más bajo que he encontrado hasta ahora, este número es de 8 subprocesos en un i7 con 4 ht-core, y por lo tanto 8 CPU lógicas) de subprocesos y tienen un comportamiento muy extraño (¡el tiempo de ejecución de mi punto de referencia simple se mueve de segundos a horas!)

Otras limitaciones sobre las colas sin bloqueo siguiendo el estilo STL: tener iteradores en la cola sin bloqueo no tiene sentido.

Marwan Burelle
fuente
3

Y luego llegaron Intel Threading Building Blocks . Y durante un tiempo estuvo bien.

PD: está buscando concurrent_queue y concurrent_hash_map

Edouard A.
fuente
6
Esos no están libres de candados. Ver software.intel.com/en-us/forums/intel-threading-building-blocks/…
RED SOFT ADAIR
1
Lo sé, en el sentido estricto de libre de bloqueo, pero sin embargo pensé que podría ayudar al OP con su problema, ya que lo de libre de bloqueo es solo un detalle de implementación. Pensé que estaba buscando colecciones que funcionaran bien con acceso concurrente.
Edouard A.
Lo libre de bloqueo no es solo un detalle complementario. Es una bestia completamente diferente.
arunmoezhi
1

Hasta donde yo sé, todavía no existe tal cosa disponible públicamente. Un problema que debe resolver un implementador es que necesita un asignador de memoria sin bloqueo, que existe, aunque parece que no puedo encontrar el enlace en este momento.

Tobias
fuente
No tiene sentido para mí por qué hay disponible un asignador de memoria. Simplemente use estructuras de datos con punteros intrínsecos (ya conoce la vieja manera hasta que se volvió loco con los contenedores y perdió habilidades para incluso implementar Hashtables simples).
Lothar
1

Lo siguiente es del artículo de Herb Sutter sobre la cola sin bloqueo simultáneo http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1 . He realizado algunos cambios, como el reordenamiento del compilador. Se necesita GCC v4.4 + para compilar este código.

#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;
}
entusiasta friki
fuente
4
Esto no está libre de candados. Seguro que no usa un bloqueo proporcionado por el sistema operativo, pero la forma en que gira (por ejemplo) "atomic <bool> consumerLock" es definitivamente un comportamiento de bloqueo. Si un hilo falla mientras mantiene uno de esos bloqueos, no se puede hacer más trabajo. Incluso el propio Herb lo dice (creo que en la página 4 de ese artículo).
James Caccese
0

Escribí esto en algún momento probablemente en 2010, estoy seguro con la ayuda de diferentes referencias. Consumidor único de múltiples productores.

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
    }

};
genio de pelo rizado
fuente