c++ - Atomic shared_ptr para la lista enlazada individualmente sin bloqueo

data-structures shared-ptr

Question

Me pregunto si es posible crear un puntero compartido seguro para subprocesos sin bloqueo para cualquiera de las arquitecturas "comunes", como x64 o ARMv7 / ARMv8.

En una charla sobre la programación sin bloqueo en cppcon2014 , Herb Sutter presentó una implementación (parcial) de una lista enlazada individualmente sin bloqueo. La implementación parece bastante simple, pero se basa en una implementación atomic shared_ptr que aún no existe en la biblioteca estándar o en el uso de las funciones especializadas std::atomic... Esto es especialmente importante ya que las llamadas push / pop individuales invocan potencialmente múltiples cargas / almacenes compare_exchange y operaciones de compare_exchange .

El problema que veo (y creo que algunas de las preguntas en la conversación fueron en la misma dirección) es que para que esta sea una verdadera estructura de datos sin bloqueo, esas operaciones atómicas tendrían que estar sin bloqueo. No conozco ninguna implementación de biblioteca estándar para las funciones std::atomic... que no tenga bloqueo y, al menos con una búsqueda breve en Google / SO, tampoco encontré una sugerencia de cómo implementar un Especialización sin bloqueo para std::atomic<std::shared_ptr> .

Ahora, antes de perder mi tiempo en esto, quería preguntar:

• ¿Sabe, si es posible escribir un puntero compartido atómico y sin bloqueo en absoluto?
• ¿Ya hay algunas implementaciones que he pasado por alto y, idealmente, son incluso compatibles con lo que cabría esperar de un std::atomic<std::shared_ptr> ? Para la cola mencionada se requeriría especialmente una operación CAS .
• Si no hay forma de implementar esto en las arquitecturas actuales, ¿ve algún otro beneficio en la implementación de Herb en comparación con una lista enlazada "normal" que está protegida por un bloqueo?

Para referencia, aquí está el código de Herb Sutter (podría contener errores tipográficos de mi parte):

template<class T> 
class slist {
    struct Node { T t;  std::shared_ptr<Node> next; };
    std::atomic<std::shared_ptr<Node>> head;        
public:
    class reference{
        std::shared_ptr<Node> p;
    public:
        reference(std::shared_ptr<Node> p_){}
        T& operator*(){ return p->t; }
        T* operator->(){ return &p->t; }
    };
    auto find(T t) const {
        auto p = head.load();
        while (p && p-> != t) {
            p = p - next;
        }
        return reference(move(p));
    }
    void push_front(T t) {
        auto p = std::make_shared<Node>();
        p->t = t;
        p->next = head;
        while (!head.compare_exchange_weak(p->next, p)) {}
    }
    void pop_front() {
        auto p = head.load();
        while (p && !head.compare_exchange_weak(p, p - next)) { ; }
    }
};

Tenga en cuenta que, en esta implementación, se puede acceder / modificar una sola instancia de un shared_ptr mediante múltiples subprocesos diferentes. Se puede leer / copiar, restablecer e incluso eliminar (como parte de un nodo). Por lo tanto, no se trata de si múltiples shared_ptr pueden usar múltiples objetos shared_ptr diferentes (que administran el mismo objeto) sin una condición de carrera, esto ya es cierto para las implementaciones actuales y es requerido por el estándar, sino que se trata de acceso simultáneo a una sola instancia de puntero, que es, para los punteros compartidos estándar, no más seguro para subprocesos que las mismas operaciones en los punteros sin formato.

Para explicar mi motivación:
Esta es principalmente una cuestión académica. No tengo la intención de implementar mi propia lista sin bloqueo en el código de producción, pero el tema me parece interesante y, a primera vista, la presentación de Herb parece ser una buena introducción. Sin embargo, mientras pensaba en esta pregunta y en el comentario de @ sehe sobre mi respuesta, recordé esta conversación, lo examiné de nuevo y me di cuenta de que no tiene mucho sentido llamar a la implementación de Herb sin bloqueo, si las operaciones primitivas requieren bloqueos ( que actualmente hacen). Así que me preguntaba si esto es solo una limitación de las implementaciones actuales o un defecto fundamental en el diseño.

Answer 1

Es posible escribir un ptr compartido sin bloqueo ya que lo único que necesita cambiar es el conteo. El ptr en sí solo se copia, por lo que no se necesita un cuidado especial aquí. Al eliminar, esta debe ser la última instancia, por lo que no existen otras copias en otros subprocesos para que nadie incremente al mismo tiempo.
Pero dicho esto, std :: atomic> sería algo muy especializado ya que no es exactamente un tipo primitivo.

He visto algunas implementaciones de listas sin bloqueo, pero ninguna de ellas era de punteros compartidos. Estos contenedores generalmente tienen un propósito especial y, por lo tanto, existe un acuerdo sobre su uso (cuando / who crea / elimina), por lo que no es necesario usar punteros compartidos.
Además, los punteros compartidos introducen una sobrecarga que es contraria a nuestros objetivos de baja latencia que nos llevaron al dominio sin bloqueo en primer lugar.

Entonces, volviendo a su pregunta, creo que es posible, pero no veo por qué hacer eso.
Si realmente necesitas algo como eso, una variable miembro refCount podría servir mejor.

No veo ningún beneficio específico en la implementación específica de Herb, tal vez excepto la académica, pero las listas sin bloqueo tienen la motivación obvia de no tener un bloqueo. A menudo sirven como colas o simplemente para compartir una colección de nodos entre hilos que son alérgicos a los bloqueos.
Tal vez deberíamos preguntarle a Herb ... ¿Herb? ¿estas escuchando?

EDITAR: siguiendo todos los comentarios a continuación, he implementado una lista enlazada individualmente sin bloqueo. La lista es bastante compleja para evitar que se eliminen los ptrs compartidos mientras se accede a ellos. Es demasiado grande para publicar aquí, pero aquí están las ideas principales:
- La idea principal es esconder las entradas eliminadas en un lugar separado, un recolector de basura, para hacerlas inaccesibles a acciones posteriores.
- Un recuento de ref atómico se incrementa en la entrada a cada función ( push_front , pop_front y front ) y se decrementa automáticamente en la salida. Al disminuir a cero, se incrementa el contador de versiones. Todo en una instrucción atómica.
- Cuando un ptrs compartido necesita borrarse, en pop_front , se inserta en un GC. Hay un GC por número de versión. El GC se implementa utilizando una lista sin bloqueo más simple que solo puede push_front o pop_all . He creado un búfer circular de 256 GC, pero se puede aplicar algún otro esquema.
- El GC de una versión se vacía en el incremento de la versión y luego los ptrs compartidos eliminan los titulares.
Por lo tanto, si llama a pop_front, sin que se ejecute nada más, el recuento de ref se incrementa a 1, el ptr frontal compartido se empuja en GC [0], el recuento de ref a cero y la versión a 1, GC [0] se vacía. disminuye la ptr compartida que hicimos estallar y posiblemente elimina el objeto que posee.

Ahora, escribe un shared_ptr sin bloqueo. Creo que esto es factible. Aquí están las ideas que pensé:
- Puede tener un tipo de bloqueo de giro utilizando los bits bajos del puntero al portador, por lo que puede desreferenciarlo solo después de haberlo bloqueado. Puedes usar diferentes bits para inc / dec, etc. Esto es mucho mejor que bloquear todo.
El problema aquí es que el ptr compartido en sí mismo se puede eliminar, por lo que todo lo que contenga debería proporcionar alguna protección desde el exterior, como la lista vinculada.
- Puedes tener algún registro central de punteros compartidos. Esto no sufre el problema anterior, pero sería difícil escalar sin picos de latencia de vez en cuando.

Para resumir, actualmente creo que toda esta idea es discutible. Si encuentra algún otro enfoque que no tenga grandes problemas, tendré mucha curiosidad de saberlo :)
¡Gracias!

Answer 2

Estoy agregando esto como respuesta, ya que es demasiado largo para caber en un comentario:

Algo a tener en cuenta. No se necesita un shared_ptr sin bloqueo para implementar estructuras de datos sin bloqueo / sin espera.

La razón por la que Sutter usa shared_ptr en su presentación es porque la parte más complicada de escribir estructuras de datos sin bloqueo no es la sincronización, sino la recuperación de memoria: no podemos eliminar nodos mientras que otros subprocesos pueden acceder a ellos, por lo que tenemos que filtrar A ellos y los reclamamos después. Una implementación de shared_ptr sin bloqueo esencialmente proporciona recuperación de memoria "libre" y hace que los ejemplos de código sin bloqueo sean aceptables, especialmente en el contexto de una presentación por tiempo limitado.

Por supuesto, tener un atomic_shared_ptr libre de bloqueo como parte del estándar sería una gran ayuda. Pero no es la única forma de recuperar la memoria para estructuras de datos sin bloqueo, existe la ingenua implementación de mantener una lista de nodos que se eliminarán en los puntos de inactividad de la ejecución (solo funciona en escenarios de baja contienda), indicadores de peligro, balanceo su propio recuento de referencias atómicas utilizando cuentas divididas

En cuanto al rendimiento, @mksteve es correcto, no se garantiza que el código de bloqueo supere las alternativas basadas en bloqueo a menos que se ejecute en un sistema altamente paralelo que ofrezca verdadera concurrencia. Su objetivo es habilitar la máxima concurrencia y, debido a eso, lo que generalmente obtenemos es que los hilos hacen menos esperas al costo de realizar más trabajo.

PD: Si esto es algo que le interesa, debería considerar echarle un vistazo a C ++ Concurrency in Action de Anthony Williams. Dedica todo un capítulo a escribir código sin bloqueo / sin espera, que ofrece un buen punto de partida, a través de las implementaciones de la pila y la cola sin bloqueo.

Answer 3

• ¿Sabe, si es posible escribir un puntero compartido atómico y sin bloqueo en absoluto?

• ¿Ya hay algunas implementaciones que he pasado por alto y, idealmente, son incluso compatibles con lo que cabría esperar de un std :: atomic?

Creo que std::atomic_... ofrece una forma de implementación, donde slist realizaría consultas atómicas especiales en shared_ptr. El problema de esta separación en dos clases (std :: atomic y std :: shared_ptr) es que cada una tiene restricciones que deben cumplirse para poder funcionar. La separación de clases hace que el conocimiento de constricciones compartidas sea imposible.

En slist, que conoce ambos elementos, puede ayudar a la situación y, por lo tanto, probablemente funcionarán las funciones atómicas.

• Si no hay forma de implementar esto en las arquitecturas actuales, ¿ve algún otro beneficio en la implementación de Herb en comparación con una lista enlazada "normal" que está protegida por un bloqueo?

De Wikipedia: algoritmo de no bloqueo el propósito de la naturaleza de bloqueo libre, es garantizar que se realice algún progreso al menos por un hilo.

Esto no ofrece una garantía de mejor rendimiento que una implementación bloqueada, pero sí garantiza que no se producirán interbloqueos.

Imagina que T requería un bloqueo para realizar una copia, esto también podría haber sido propiedad de algunas operaciones fuera de la lista. Entonces, si fuera de su propiedad, sería posible un punto muerto, y se llamó a una implementación de slist basada en bloqueo.

Creo que CAS se implementa en std::compare_exchange_weak , por lo que sería independiente de la implementación.

Los actuales algoritmos sin bloqueo para estructuras complejas (por ejemplo, vector, mapa) tienden a ser significativamente menos eficientes que los algoritmos de bloqueo, Dr Dobbs: estructuras de datos sin bloqueo, pero el beneficio ofrecido (rendimiento mejorado del hilo) mejoraría significativamente el rendimiento de las computadoras, que tienden a Para tener un gran número de CPU inactivos.

Investigaciones adicionales sobre los algoritmos pueden identificar nuevas instrucciones que podrían implementarse en las CPU del futuro, para darnos un rendimiento sin esperas y una mejor utilización de los recursos informáticos.