¿Es posible implementar el mapa de bloqueo libre en C++
algorithm dictionary (6)
Estamos desarrollando una aplicación de red basada en C / S, encontramos que hay demasiados bloqueos que agregan a std :: map que el rendimiento del servidor empeoró.
Me pregunto si es posible implementar un mapa sin bloqueo, si es así, ¿cómo? ¿Hay algún código fuente abierto allí?
EDITAR: En realidad usamos std :: map para almacenar información de sockets, hicimos una encapsulación basada en la descripción del archivo de socket para incluir alguna otra información necesaria, como dirección IP, puerto, tipo de socket, tcp o udp, etc.
Para resumir, tenemos un mapa global que dice que es
map<int fileDescriptor, socketInfor*> SocketsMap,
luego, cada subproceso que se utiliza para enviar datos necesita acceder a SocketsMap, y deben agregar mutex antes de leer desde SocketsMap o escribir en SocketsMap, por lo que el nivel de concurrencia de toda la aplicación se reduciría considerablemente debido a la cantidad de bloqueos que se agregan a SocketsMap.
Para evitar el problema del nivel de concurrencia, tenemos dos soluciones: 1. almacenar cada socketInfor * por separado 2. usar algún tipo de mapa sin bloqueo.
Me gustaría encontrar algún tipo de mapa sin bloqueo, porque los cambios en los códigos requeridos por esta solución son mucho menores que los de la solución 1.
En realidad, hay una forma, aunque no lo he implementado yo mismo, hay un documento en un mapa sin candado que utiliza los punteros de peligro del eminente experto en C ++ Andrei Alexandrescu.
HashMap le conviene? Eche un vistazo a los bloques de creación de subprocesos de Intel ; tienen un interesante mapa concurrente. No estoy seguro de que esté libre de bloqueos, pero es de esperar que esté interesado en un buen rendimiento de multiproceso, no especialmente en el bloqueo de datos. También puedes consultar CityHash lib.
EDITAR:
En realidad, el mapa hash de TBB no está bloqueado
Me sorprende que nadie lo haya mencionado, pero Click Cliff ha implementado un hashmap sin espera en Java , que creo que podría ser portado a C ++,
Puede implementar el mapa utilizando un diseño optimista o memoria transaccional .
Este enfoque es especialmente efectivo si la posibilidad de que dos operaciones aborden el mapa de forma simultánea y una de ellas cambie su estructura es relativamente pequeña, y no desea la sobrecarga de bloqueo cada vez.
Sin embargo, de vez en cuando, se producirá una colisión, y tendrá que provocarlo de alguna manera (generalmente retrocediendo al último estado estable y volviendo a intentar las operaciones).
Si su hardware admite operaciones atómicas lo suficientemente buenas (esto se puede hacer fácilmente con la opción Comparar e intercambiar (CAS)) , donde cambia la referencia sola (y cuando cambia el mapa, trabaja en una copia del mapa, y no en el original, y configúralo como el principal solo cuando te comprometes).
Sí, he implementado un mapa desordenado sin bloqueo ( docs ) en C ++ utilizando el concepto de "Listas divididas en orden". Es un contenedor que se expande automáticamente y admite millones de elementos en un CAS de 64 bits sin problemas de ABA. En cuanto al rendimiento, es una beast (ver página 5). Ha sido ampliamente probado con millones de operaciones aleatorias.
Si usas C ++ 11, puedes echar un vistazo a AtomicHashMap de facebook/folly