c++ - ¿Cómo difieren las órdenes de memoria "adquirir" y "consumir" y cuándo es preferible "consumir"?

c++11 atomic

Question

El estándar C ++ 11 define un modelo de memoria (1.7, 1.10) que contiene ordenamientos de memoria , que son, aproximadamente, "secuencialmente consistentes", "adquirir", "consumir", "liberar" y "relajado". Del mismo modo, aproximadamente, un programa es correcto solo si no está libre de raza, lo que sucede si todas las acciones se pueden poner en el orden en el que ocurre una acción , antes de otra. La forma en que ocurre una acción X: antes de una acción Y es que cualquiera de las X se secuencia antes de Y (dentro de un hilo), o X entre hilos-sucede-antes de Y. La última condición se da, entre otros, cuando

• X se sincroniza con Y , o
• X está ordenado por dependencia antes de Y.

La sincronización ocurre cuando X es una tienda atómica con un orden de "liberación" en una variable atómica, e Y es una carga atómica con una ordenación "adquirida" en la misma variable. Ser dependiente-ordenado-antes ocurre para la situación análoga donde Y se carga con el orden "consumir" (y un acceso adecuado a la memoria). La noción de sincroniza- amplía transitoriamente la relación " sucede antes" transitoriamente a través de acciones secuenciadas -antes una de la otra dentro de una secuencia , pero siendo ordenada-dependencia-antes se extiende transitivamente solo a través de un subconjunto estricto de secuenciado-antes llamado -dependencia-porta , que sigue un gran conjunto de reglas, y notablemente se puede interrumpir con std::kill_dependency .

Ahora bien, ¿cuál es el propósito de la noción de "orden de dependencia"? ¿Qué ventaja proporciona sobre la secuencia más simple antes / sincroniza con el pedido? Dado que las reglas son más estrictas, supongo que se pueden implementar de manera más eficiente.

¿Puedes dar un ejemplo de un programa donde cambiar de lanzamiento / adquirir a lanzar / consumir es correcto y proporciona una ventaja no trivial? ¿Y cuándo std::kill_dependency proporcionaría una mejora? Los argumentos de alto nivel serían buenos, pero los puntos de bonificación para las diferencias específicas de hardware.

Answer 1

El consumo de carga es muy parecido a la adquisición de carga, excepto que induce las relaciones de ocurrencia antes de solo a las evaluaciones de expresión que dependen de los datos en el consumo de carga. Envolver una expresión con kill_dependency produce un valor que ya no conlleva una dependencia del consumo de carga.

El caso clave de uso es que el escritor construya una estructura de datos de forma secuencial y luego mueva un puntero compartido a la nueva estructura (usando un release o acq_rel atómico). El lector utiliza el consumo de carga para leer el puntero y lo desreferencia para llegar a la estructura de datos. La desreferencia crea una dependencia de datos, por lo que se garantiza que el lector verá los datos inicializados.

std::atomic<int *> foo {nullptr};
std::atomic<int> bar;

void thread1()
{
    bar = 7;
    int * x = new int {51};
    foo.store(x, std::memory_order_release);
}

void thread2()
{
    int *y = foo.load(std::memory_order_consume)
    if (y)
    {
        assert(*y == 51); //succeeds
        // assert(bar == 7); //undefined behavior - could race with the store to bar 
        // assert(kill_dependency(*y) + bar == 58) // undefined behavior (same reason)
        assert(*y + bar == 58); // succeeds - evaluation of bar pulled into the dependency 
    }
}

Hay dos razones para proporcionar consumo de carga. La razón principal es que las cargas ARM y Power están garantizadas para consumir, pero requieren cercas adicionales para convertirlas en adquisiciones. (En x86, todas las cargas son adquiridas, por lo que el consumo no proporciona ventaja de rendimiento directo en la compilación ingenua). La razón secundaria es que el compilador puede mover operaciones posteriores sin dependencia de datos hasta antes del consumo, lo que no puede hacer por una adquisición . (Permitir tales optimizaciones es la gran razón para construir todo este orden de memoria en el lenguaje).

Envolver un valor con kill_dependency permite calcular una expresión que depende del valor a mover antes del consumo de carga. Esto es útil, por ejemplo, cuando el valor es un índice en una matriz que se leyó previamente.

Tenga en cuenta que el uso del consumo da como resultado una relación de pasar antes que ya no es transitiva (aunque todavía se garantiza que sea acíclica). Por ejemplo, la tienda a la bar pasa antes de la tienda a foo, lo que sucede antes de la desreferencia de y , que ocurre antes de la lectura de la bar (en la afirmación comentada), pero el almacenamiento en la bar no ocurre antes de la lectura de bar Esto conduce a una definición bastante más complicada de pasar-antes, pero se puede imaginar cómo funciona (comenzar con secuenciada-antes, luego propagarse a través de cualquier número de release-consume-dataDependency o release-acquire-sequence-Before-links)

Answer 2

Jeff Preshing tiene una excelente publicación de blog que responde esta pregunta. No puedo agregar nada por mi cuenta, pero creo que cualquier persona que se pregunte acerca de consumir frente a adquirir debe leer su publicación:

http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/

Muestra un ejemplo específico de C ++ con el correspondiente código ensamblado de referencia en tres arquitecturas diferentes. En comparación con memory_order_acquire , memory_order_consume ofrece potencialmente una aceleración de 3x en PowerPC, una aceleración de 1.6x en ARM y una aceleración insignificante en x86, que de todos modos tiene una gran consistencia. El truco es que a partir de cuando lo escribió, solo GCC en realidad trató la semántica de consumo de forma diferente a adquirir, y probablemente debido a un error. No obstante, demuestra que hay una aceleración disponible si los escritores del compilador pueden descubrir cómo aprovecharla.

Answer 3

Me gustaría registrar un hallazgo parcial, a pesar de que no es una respuesta real y no significa que no habrá una gran recompensa por una respuesta adecuada.

Después de mirar a 1.10 por un tiempo, y en particular la nota muy útil en el párrafo 11, creo que esto no es realmente tan difícil. La gran diferencia entre synchronizes-with (de ahora en adelante: s / w) y dependency-ordered-before (dob) es que una relación de happen-before se puede establecer concatenando sequence-before (s / b) y s / w arbitrariamente, pero no es así para dob. Tenga en cuenta que una de las definiciones de inter-thread sucede antes :

A sincroniza: con X y X se secuencia antes de B

¡Pero la declaración análoga para A está ordenada por dependencia antes de que falte X !

Entonces con lanzamiento / adquisición (es decir, s / w) podemos ordenar eventos arbitrarios:

A1    s/b    B1                                            Thread 1
                   s/w
                          C1    s/b    D1                  Thread 2

Pero ahora considere una secuencia arbitraria de eventos como este:

A2    s/b    B2                                            Thread 1
                   dob
                          C2    s/b    D2                  Thread 2

En esta secuencia, sigue siendo cierto que A2 ocurre antes de C2 (porque A2 es s / b B2 y B2 inter-hilo pasa antes de C2 a causa de dob, pero podríamos argumentar que en realidad nunca se puede decir!). Sin embargo, no es cierto que ocurre A2 antes de D2 . Los eventos A2 y D2 no están ordenados uno con respecto al otro, a menos que realmente sostenga que C2 lleva dependencia a D2 . Este es un requisito más estricto, y sin ese requisito, A2 -to- D2 no se puede ordenar "a través" del par de publicación / consumo.

En otras palabras, un par de publicación / consumo solo propaga un orden de acciones que llevan una dependencia de una a la siguiente. Todo lo que no es dependiente no se ordena a través del par de publicación / consumo.

Además, tenga en cuenta que el orden se restaura si agregamos un par final de lanzamiento / adquisición más fuerte:

A2    s/b    B2                                                         Th 1
                   dob
                          C2    s/b    D2                               Th 2
                                             s/w
                                                    E2    s/b    F2     Th 3

Ahora, según la regla citada, D2 inter-thread ocurre antes que F2 , y por lo tanto también lo hacen C2 y B2 , y entonces ocurre A2 -antes que F2 . Pero tenga en cuenta que todavía no hay pedidos entre A2 y D2 - el orden es solo entre eventos A2 y posteriores .

En resumen y al cerrar, el transporte de dependencia es un subconjunto estricto de la secuencia general, y los pares de publicación / consumo proporcionan un orden solo entre las acciones que tienen dependencia. Siempre que no se requiera un ordenamiento más sólido (por ejemplo, al pasar por un par de liberación / adquisición), existe teóricamente un potencial de optimización adicional, ya que todo lo que no está en la cadena de dependencia puede reordenarse libremente.

Tal vez aquí hay un ejemplo que tiene sentido?

std::atomic<int> foo(0);

int x = 0;

void thread1()
{
    x = 51;
    foo.store(10, std::memory_order_release);
}

void thread2()
{
    if (foo.load(std::memory_order_acquire) == 10)
    {
        assert(x == 51);
    }
}

Como está escrito, el código es libre de raza y la afirmación se mantendrá, porque el par de publicación / adquisición ordene la tienda x = 51 antes de la carga en la afirmación. Sin embargo, al cambiar "adquirir" por "consumir", esto ya no sería cierto y el programa tendría una carrera de datos en x , ya que x = 51 no tiene dependencia en la tienda para foo . El punto de optimización es que esta tienda se puede reordenar libremente sin preocuparse por lo que está haciendo, porque no hay dependencia.

Answer 4

Ordenamiento de dependencia de datos fue introducido por N2492 con el siguiente razonamiento:

Hay dos casos de uso significativos en los que el borrador actual de trabajo (N2461) no admite una escalabilidad cercana a la posible en algunos componentes de hardware existentes.

• acceso de lectura a estructuras de datos concurrentes raramente escritas

Las estructuras de datos concurrentes raramente escritas son bastante comunes, tanto en los kernels del sistema operativo como en las aplicaciones de tipo servidor. Los ejemplos incluyen estructuras de datos que representan estados externos (como tablas de enrutamiento), configuración de software (módulos cargados actualmente), configuración de hardware (dispositivo de almacenamiento actualmente en uso) y políticas de seguridad (permisos de control de acceso, reglas de firewall). Las relaciones de lectura a escritura que exceden de mil millones a uno son bastante comunes.

• semántica publicación-suscripción para publicación mediada por puntero

Gran parte de la comunicación entre hilos está mediada por punteros, en la que el productor publica un puntero a través del cual el consumidor puede acceder a la información. El acceso a esa información es posible sin una semántica de adquisición completa.

En tales casos, el uso del ordenamiento de dependencias de datos entre subprocesos ha resultado en aceleraciones de orden de magnitud y mejoras similares en la escalabilidad en máquinas que admiten el ordenamiento de dependencias de datos entre subprocesos. Tales aceleraciones son posibles porque tales máquinas pueden evitar las costosas adquisiciones de cerraduras, instrucciones atómicas o vallas de memoria que de otro modo se requieren.

énfasis mío

el caso de uso motivador presentado allí es rcu_dereference() del kernel de Linux