Uno de los puntos de venta de las estructuras de datos inmutables es que son paralelizables automáticamente. Si no se produce ninguna mutación, las referencias a una estructura de datos funcional se pueden pasar entre hilos sin ningún bloqueo.¿Las estructuras de datos funcionales/inmutables aún pueden ser útiles para la concurrencia en un contexto no relacionado con la basura?
Comencé a pensar cómo se implementarían las estructuras de datos funcionales en C++. Supongamos que tenemos un recuento de referencias en cada nodo de nuestra estructura de datos. (Las estructuras de datos funcionales comparten estructura entre miembros antiguos y actualizados de una estructura de datos, por lo que los nodos no pertenecen exclusivamente a una estructura de datos particular.)
El problema es que si los recuentos de referencia se actualizan en diferentes subprocesos, entonces nuestros datos la estructura ya no es segura para subprocesos. Y asociar un mutex a cada nodo es costoso y frustra el propósito de utilizar estructuras de datos inmutables para la concurrencia.
¿Hay alguna manera de hacer que las estructuras de datos inmutables simultáneas funcionen en C++ (y otros entornos no recolectados)?
No soy experto en esto, pero puede almacenar recuentos de referencia por subproceso, y solo colocar un bloqueo en ellos para comprobar si todos los subprocesos han llegado a cero de referencia en un nodo. Pero estoy seguro de que hay soluciones más elegantes que esto o quizás el recuento de referencias en general. – sinelaw
Aquí hay una popular estructura de datos inmutables para C++ http://www.sgi.com/tech/stl/Rope.html – ybungalobill
Puede ver las implementaciones de 'shared_ptr', que enfrenta exactamente el mismo problema con la necesidad de un hilo eficiente- cuenta de referencia segura. –