c++ - ¿Qué hace `std:: kill_dependency` y por qué querría usarlo?

multithreading memory-model

Question

He estado leyendo sobre el nuevo modelo de memoria C ++ 11 y me he encontrado con la función std::kill_dependency (§29.3 / 14-15). Estoy luchando por entender por qué alguna vez querría usarlo.

Encontré un ejemplo en la propuesta N2664 pero no ayudó mucho.

Comienza mostrando el código sin std::kill_dependency . Aquí, la primera línea lleva una dependencia al segundo, que lleva una dependencia a la operación de indexación, y luego lleva una dependencia a la función do_something_with .

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[r2]);

Hay otro ejemplo que usa std::kill_dependency para romper la dependencia entre la segunda línea y la indexación.

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[std::kill_dependency(r2)]);

Por lo que puedo decir, esto significa que la indexación y la llamada a do_something_with no son dependencias ordenadas antes de la segunda línea. De acuerdo con N2664:

Esto permite al compilador reordenar la llamada a do_something_with , por ejemplo, realizando optimizaciones especulativas que predicen el valor de a[r2] .

Para hacer que la llamada a do_something_with el valor a[r2] sea ​​necesaria. Si, hipotéticamente, el compilador "sabe" que la matriz está llena de ceros, puede optimizar esa llamada a do_something_with(0); y reordene esta llamada relativa a las otras dos instrucciones según le plazca. Podría producir cualquiera de:

// 1
r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(0);
// 2
r1 = x.load(memory_order_consume);
do_something_with(0);
r2 = r1->index;
// 3
do_something_with(0);
r1 = x.load(memory_order_consume);
r2 = r1->index;

Es mi entendimiento correcto?

Si do_something_with sincroniza con otro hilo por algún otro medio, ¿qué significa esto con respecto al orden de la llamada x.load y este otro hilo?

Asumiendo que mi comprensión es correcta, todavía hay algo que me molesta: cuando estoy escribiendo código, ¿qué razones me llevarían a elegir matar a una dependencia?

Answer 1

Además de la otra respuesta, señalaré que Scott Meyers, uno de los líderes definitivos en la comunidad C ++, bashed memory_order_consume bastante fuerte. Básicamente dijo que creía que no tenía lugar en el estándar. Dijo que hay dos casos donde memory_order_consume tiene algún efecto:

• Arquitecturas exóticas diseñadas para admitir más de 1024 máquinas de memoria compartida.
• El DEC Alpha

Sí, una vez más, el DEC Alpha encuentra su camino hacia la infamia utilizando una optimización que no se ve en ningún otro chip hasta muchos años después en máquinas absurdamente especializadas.

La optimización particular es que esos procesadores permiten desreferenciar un campo antes de obtener realmente la dirección de ese campo (es decir, puede buscar x-> y ANTES incluso de buscar x, usando un valor predicho de x). Luego regresa y determina si x era el valor que esperaba. En el éxito, ahorró tiempo. En caso de falla, tiene que regresar y obtener x-> y otra vez.

Memory_order_consume le dice al compilador / arquitectura que estas operaciones tienen que suceder en orden. Sin embargo, en el caso más útil, uno terminará queriendo hacer (x-> yz), donde z no cambia. memory_order_consume obligaría al compilador a mantener xey en orden. kill_dependency (x-> y) .z le dice al compilador / arquitectura que puede reanudar tales reordenamientos nefastos.

Es probable que el 99.999% de los desarrolladores nunca trabaje en una plataforma donde esta función es necesaria (o tiene algún efecto).

Answer 2

Creo que esto permite esta optimización.

r1 = x.load(memory_order_consume);
do_something_with(a[r1->index]);

Answer 3

El caso de uso habitual de kill_dependency surge de lo siguiente. Supongamos que desea hacer actualizaciones atómicas a una estructura de datos compartida no trivial. Una forma típica de hacerlo es crear de manera no atómica algunos datos nuevos y oscilar atómicamente un puntero desde la estructura de datos a los datos nuevos. Una vez que haga esto, no va a cambiar los datos nuevos hasta que haya girado el puntero de él hacia otra cosa (y haya esperado a que todos los lectores abandonen). Este paradigma es ampliamente utilizado, por ejemplo, lectura-copia-actualización en el kernel de Linux.

Ahora, supongamos que el lector lee el puntero, lee los datos nuevos y vuelve más tarde y vuelve a leer el puntero, descubriendo que el puntero no ha cambiado. El hardware no puede decir que el puntero no se ha actualizado de nuevo, por lo que al consume semántica no puede usar una copia en caché de los datos, pero tiene que volver a leerla desde la memoria. (O para pensarlo de otra manera, el hardware y el compilador no pueden mover de forma especulativa la lectura de los datos antes de la lectura del puntero).

Aquí es donde kill_dependency viene al rescate. Al kill_dependency el puntero en una kill_dependency , crea un valor que ya no propagará la dependencia, permitiendo que los accesos a través del puntero utilicen la copia en caché de los datos nuevos.

Answer 4

El objetivo de memory_order_consume es garantizar que el compilador no realice ciertas desafortunadas optimizaciones que pueden romper los algoritmos sin bloqueos. Por ejemplo, considere este código:

int t;
volatile int a, b;

t = *x;
a = t;
b = t;

Un compilador conforme puede transformar esto en:

a = *x;
b = *x;

Por lo tanto, a puede no ser igual b. También puede hacer:

t2 = *x;
// use t2 somewhere
// later
t = *x;
a = t2;
b = t;

Al usar load(memory_order_consume) , requerimos que los usos del valor que se está cargando no se muevan antes del punto de uso. En otras palabras,

t = x.load(memory_order_consume);
a = t;
b = t;
assert(a == b); // always true

El documento estándar considera un caso en el que solo puede estar interesado en ordenar ciertos campos de una estructura. El ejemplo es:

r1 = x.load(memory_order_consume);
r2 = r1->index;
do_something_with(a[std::kill_dependency(r2)]);

Esto le indica al compilador que está permitido, efectivamente, hacer esto:

predicted_r2 = x->index; // unordered load
r1 = x; // ordered load
r2 = r1->index;
do_something_with(a[predicted_r2]); // may be faster than waiting for r2''s value to be available

O incluso esto:

predicted_r2 = x->index; // unordered load
predicted_a  = a[predicted_r2]; // get the CPU loading it early on
r1 = x; // ordered load
r2 = r1->index; // ordered load
do_something_with(predicted_a);

Si el compilador sabe que do_something_with no cambiará el resultado de las cargas para r1 o r2, puede incluso elevarlo completamente:

do_something_with(a[x->index]); // completely unordered
r1 = x; // ordered
r2 = r1->index; // ordered

Esto le permite al compilador un poco más de libertad en su optimización.