ventajas tablas tabla resolucion programacion las implementacion hashing funcion desventajas colisiones codigo aplicaciones c++ stl lock-free

tablas - ¿Hay una implementación lista para la cola lista para la producción o hash en C++?



tablas hash en java (15)

Estuve buscando en Google una cola libre de bloqueos en C ++. Encontré algunos códigos y algunas pruebas, pero nada de lo que pude compilar. Un hash sin bloqueo también sería bienvenido.

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

¡Sí!

Escribí una cola libre de bloqueos . Tiene Features ™:

  • Totalmente libre de espera (sin bucles CAS)
  • Súper rápido (más de cien millones de enqueue / dequeue operaciones por segundo)
  • Usa la semántica del movimiento de C ++ 11
  • Crece según sea necesario (pero solo si lo desea)
  • Realiza una gestión de memoria sin bloqueos para los elementos (utilizando bloques contiguos asignados previamente)
  • Stand-alone (dos encabezados más una licencia y un archivo Léame)
  • Compila bajo MSVC2010 +, Intel ICC 13 y GCC 4.7.2 (y debería funcionar bajo cualquier compilador C ++ 11 totalmente compatible)

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

Advertencias:

  • Solo para arquitectura de un solo productor de un solo productor (es decir, dos hilos)
  • Completamente probado en x86 (-64), y debería funcionar en ARM, PowerPC y otras CPU donde los enteros nativos y las cargas y almacenes de punteros nativos alineados son naturalmente atómicos, pero no se han probado en el campo en CPUs que no sean x86 (si alguien tiene uno para probarlo, házmelo saber)
  • No tiene idea de si se infringen las patentes (se usa bajo su propio riesgo, etc.). Tenga en cuenta que sí lo diseñé e implementé desde cero.

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

La respuesta es NO .

No existe tal cosa que pueda usarse de manera inmediata.

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 proporciona (en línea, comenzando en la segunda página de cada artículo) utiliza el tipo de plantilla atómica <T> del estilo C ++ 0x; que puede imitar usando la biblioteca de Boost interprocess.

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

Escribí esto en algún momento, probablemente en 2010, estoy seguro de que con la ayuda de diferentes referencias. Es consumidor individual multiproducto.

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 } };

Lo siguiente es del artículo de Herb Sutter sobre Concurrent lock free Queue http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1 . He realizado algunos cambios, como el reordenamiento del compilador. Uno 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; }

Puedo llegar un poco tarde en esto.

La ausencia de soluciones (cuando se formuló la pregunta) se debe principalmente a un problema importante en C ++ (antes de C ++ 0x / 11): C ++ tiene (no tiene) un modelo de memoria concurrente.

Ahora, usando std :: atomic, puede controlar los problemas de ordenación de la memoria y tener operaciones de comparación e intercambio correctas. Me he escrito una implementación de la cola libre de cerrojo de Micheal & Scott (PODC96) utilizando C ++ 11 y Hazard Pointers de Micheal (IEEE TPDS 2004) para evitar problemas iniciales de ABA y gratuitos. Está funcionando bien, pero es una implementación rápida y sucia, y no estoy satisfecho con las actuaciones reales. El código está disponible en bitbucket: LockFreeExperiment

También es posible implementar la cola sin bloqueo sin punteros con palabras dobles CAS (pero las versiones de 64 bits solo serán posibles en x86-64 usando cmpxchg16b), aquí tengo una publicación del blog (con código no probado para la cola) aquí : Implementación de comparación y intercambio genéricos de doble palabra 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 igual que la sin bloqueo (no he alcanzado suficiente contención para que las estructuras de datos bloqueadas tengan problemas de rendimiento, pero mi banco es demasiado liviano ahora) y la cola concurrente de TBB de Intel parece incluso mejor (dos veces más rápido) para un número relativamente pequeño (dependiendo del sistema operativo, bajo FreeBSD 9, el límite más bajo que he encontrado hasta ahora, este número es de 8 hilos 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 simple punto de referencia se mueve de segundos a horas!)

Otra limitación sobre las colas sin bloqueos que siguen el estilo STL: tener iteradores en la cola libre de bloqueo no tiene sentido.

Que yo sepa, aún no hay tal cosa públicamente disponible. Un problema que un implementador necesita resolver es que necesita un asignador de memoria sin bloqueo, que existe, aunque parece que no puedo encontrar el enlace ahora mismo.

Si tiene un Queue / FIFO multiproducto / consumidor único, puede crear fácilmente un LockFree utilizando SLIST o una pila trivial sin bloqueo de LIFO. Lo que debes hacer es tener una segunda pila "privada" para el consumidor (que también se puede hacer como SLIST por simplicidad o cualquier otro modelo de pila que elijas). El consumidor saca elementos de la pila privada. Cada vez que se expone el LIFO privado, realiza una descarga en lugar de desconectar el SLIST concurrente compartido (capturando toda la cadena SLIST) y luego recorre la lista Lavado en orden empujando los elementos a la pila privada.

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

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

Además, en lo que respecta a las tablas hash, son un candidato ideal para "striping", que es simplemente dividir el hash en segmentos que tienen un bloqueo por segmentos de la memoria caché. Así es como lo hace la biblioteca concurrente de Java (usando 32 bandas). Si tiene un bloqueo ligero de lector-escritor, se puede acceder concurrentemente a la tabla hash para lecturas simultáneas y solo se parará cuando se produzca escritura en bandas impugnadas (y posiblemente si permite aumentar la tabla hash).

Si tira el suyo, asegúrese de intercalar sus bloqueos con las entradas de hash en lugar de poner todos los bloqueos en una matriz uno al lado del otro, por lo que es menos probable que compartan falsamente.

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

Me atrevería a decir que actualmente se usan en producción, así que supongo que podrían usarse con seguridad en otros proyectos.

¡Aclamaciones!