¿Qué significa "sucede antes fuertemente"?

9

La frase "sucede antes" se usa varias veces en el borrador del estándar C ++.

Por ejemplo: Terminación [basic.start.term] / 5

Si la finalización de la inicialización de un objeto con una duración de almacenamiento estático ocurre fuertemente antes de una llamada a std :: atexit (ver, [support.start.term]), la llamada a la función pasó a std :: atexit se secuencia antes de la llamada al destructor para el objeto. Si una llamada a std :: atexit ocurre fuertemente antes de la finalización de la inicialización de un objeto con duración de almacenamiento estático, la llamada al destructor para el objeto se secuencia antes de que la llamada a la función pase a std :: atexit . Si una llamada a std :: atexit ocurre fuertemente antes de otra llamada a std :: atexit, la llamada a la función pasada a la segunda llamada std :: atexit se secuencia antes de que la llamada a la función pase a primera llamada std :: atexit.

Y definido en Data racing [intro.races] / 12

Una evaluación A ocurre fuertemente antes de una evaluación D si, ya sea

(12.1) A se secuencia antes que D, o

(12.2) A se sincroniza con D, y tanto A como D son operaciones atómicas secuenciales consistentes ([atomics.order]), o

(12.3) hay evaluaciones B y C de manera que A se secuencia antes de B, B simplemente sucede antes de C y C se secuencia antes de D, o

(12.4) hay una evaluación B de manera que A ocurre fuertemente antes que B, y B sucede fuertemente antes de D.

[Nota: Informalmente, si A ocurre fuertemente antes que B, entonces A parece ser evaluado antes que B en todos los contextos. Sucede mucho antes de excluir las operaciones de consumo. - nota final]

¿Por qué se introdujo "fuertemente pasa antes"? Intuitivamente, ¿cuál es su diferencia y relación con "sucede antes"?

¿Qué significa "A parece ser evaluado antes que B en todos los contextos" en la nota?

(Nota: la motivación para esta pregunta son los comentarios de Peter Cordes bajo esta respuesta ).

Proyecto de presupuesto estándar adicional (gracias a Peter Cordes)

Orden y consistencia [atomics.order] / 4

Hay un único orden total S en todas las operaciones memory_order :: seq_cst, incluidas las cercas, que satisface las siguientes restricciones. Primero, si A y B son operaciones memory_order :: seq_cst y A sucede fuertemente antes que B, entonces A precede a B en S. Segundo, por cada par de operaciones atómicas A y B en un objeto M, donde A está ordenada por coherencia antes de B, S debe cumplir las siguientes cuatro condiciones:

(4.1) si A y B son ambas operaciones memory_order :: seq_cst, A precede a B en S; y

(4.2) si A es una operación memory_order :: seq_cst y B sucede antes de un memory_order :: seq_cst y Y, entonces A precede a Y en S; y

(4.3) si una cerca de memory_order :: seq_cst X ocurre antes de que A y B sea una operación memory_order :: seq_cst, X precede a B en S; y

(4.4) si una memoria_orden :: seq_cst cerca X ocurre antes de A y B sucede antes de una memoria_orden :: seq_cst cerca Y, entonces X precede a Y en S.

curioso
fuente
1
El borrador actual de la norma también hace referencia a "A sucede con fuerza antes que B" como una condición para una regla que solicita seq_cst, en Atomics 31.4 Orden y consistencia: 4 . Eso no está en el estándar C ++ 17 n4659 , donde 32.4 - 3 define la existencia de un único orden total de operaciones seq_cst consistentes con el orden "pasa antes" y los órdenes de modificación para todas las ubicaciones afectadas ; el "fuertemente" fue agregado en un borrador posterior.
Peter Cordes
2
@PeterCordes Creo que el comentario excluyendo el consumo, indicando que es HB "en todo contexto" / "fuerte" y hablando de llamadas a punteros de función es una especie de regalo muerto. Si un programa multiproceso llama atexit()en un subproceso y exit()en otro, no es suficiente que los inicializadores lleven solo una dependencia basada en el consumo solo porque los resultados difieren de si exit()fueron invocados por el mismo subproceso. Una respuesta anterior mía se refería a esta diferencia.
Iwillnotexist Idonotexist
@IwillnotexistIdonotexist ¿Puedes incluso salir de un programa de MT? ¿No es fundamentalmente una idea rota?
curioso
1
@curiousguy Ese es el propósito de exit(). Cualquier subproceso puede matar a todo el programa al salir, o el subproceso principal puede salir por return-ing. Resulta en la llamada de los atexit()controladores y la muerte de todos los hilos lo que sea que estuvieran haciendo.
Iwillnotexist Idonotexist

Respuestas:

5

¿Por qué se introdujo "fuertemente pasa antes"? Intuitivamente, ¿cuál es su diferencia y relación con "sucede antes"?

¡Prepárate para "simplemente sucede antes" también! Eche un vistazo a esta instantánea actual de cppref https://en.cppreference.com/w/cpp/atomic/memory_order

ingrese la descripción de la imagen aquí

Parece que "simplemente sucede antes" se agrega en C ++ 20.

Simplemente sucede antes

Independientemente de los hilos, la evaluación A simplemente sucede antes de la evaluación B si se cumple alguna de las siguientes condiciones:

1) A se secuencia antes de B

2) A se sincroniza con B

3) A simplemente sucede antes de X, y X simplemente sucede antes de B

Nota: sin las operaciones de consumo, las relaciones simplemente pasa antes y pasa antes son las mismas.

Entonces, Simply-HB y HB son iguales excepto por cómo manejan las operaciones de consumo. Ver HB

Sucede antes

Independientemente de los subprocesos, la evaluación A ocurre antes de la evaluación B si alguno de los siguientes es verdadero:

1) A se secuencia antes de B

2) Un subproceso ocurre antes de B

La implementación es necesaria para garantizar que la relación de antes de que ocurra sea acíclica, mediante la introducción de sincronización adicional si es necesario (solo puede ser necesario si está involucrada una operación de consumo, ver Batty et al)

¿Cómo difieren con respecto al consumo? Ver Inter-Thread-HB

Entre hilos pasa antes

Entre hilos, la evaluación A entre hilos ocurre antes de la evaluación B si alguno de los siguientes es verdadero

1) A se sincroniza con B

2) A se ordena por dependencia antes que B

3) ...

...

Una operación que es ordenada por dependencia (es decir, utiliza release / consume) es HB pero no necesariamente Simply-HB.

El consumo es más relajado que adquirir, así que si entiendo correctamente, HB está más relajado que Simply-HB.

Sucede fuertemente antes

Independientemente de los hilos, la evaluación A ocurre fuertemente antes de la evaluación B si se cumple alguna de las siguientes condiciones:

1) A se secuencia antes de B

2) A se sincroniza con B, y tanto A como B son operaciones atómicas secuencialmente consistentes

3) A se secuencia antes de X, X simplemente sucede antes de Y e Y se secuencia antes de B

4) A sucede fuertemente antes de X, y X sucede fuertemente antes de B

Nota: informalmente, si A sucede fuertemente antes de B, entonces A parece ser evaluado antes que B en todos los contextos.

Nota: fuertemente sucede antes de excluir las operaciones de consumo.

Por lo tanto, una operación de liberación / consumo no puede ser Strongly-HB.

La liberación / adquisición puede ser HB y Simply-HB (porque la liberación / adquisición se sincroniza con) pero no es necesariamente Strongly-HB. Porque Strongly-HB dice específicamente que A debe sincronizarse con B AND para ser una operación secuencialmente consistente.

                            Is happens-before guaranteed?

                        HB             Simply-HB          Strongly-HB

relaxed                 no                 no                 no
release/consume        yes                 no                 no      
release/acquire        yes                yes                 no
S.C.                   yes                yes                yes

¿Qué significa "A parece ser evaluado antes que B en todos los contextos" en la nota?

Todos los contextos: todos los subprocesos / todas las CPU ven (o "eventualmente estarán de acuerdo") el mismo orden. Esta es la garantía de la coherencia secuencial: un orden de modificación total global de todas las variables. Las cadenas de adquisición / liberación solo garantizan el orden de modificación percibido para los hilos que participan en la cadena. Los hilos fuera de la cadena teóricamente pueden ver un orden diferente.

No sé por qué se introdujeron Strongly-HB y Simply-HB. ¿Quizás para ayudar a aclarar cómo operar alrededor del consumo? Strongly-HB tiene buenas propiedades: si un subproceso observa que A sucede antes que B, sabe que todos los subprocesos observarán lo mismo.

La historia del consumo:

Paul E. McKenney es responsable de consumir estar en los estándares C y C ++. Consume garantiza el orden entre la asignación del puntero y la memoria a la que apunta. Fue inventado debido al DEC Alpha. El DEC Alpha podría desreferenciar especulativamente un puntero, por lo que también tenía una valla de memoria para evitar esto. El DEC Alpha ya no se fabrica y hoy en día ningún procesador tiene este comportamiento. El consumo está destinado a ser muy relajado.

Humphrey Winnebago
fuente
1
Caramba. Casi lamento haber hecho esa pregunta. Quiero volver a abordar los problemas sencillos de C ++ como las reglas de invalidación de iterador, búsqueda de nombres dependiente de argumentos, operadores de conversión definidos por el usuario de plantilla, deducción de argumentos de plantilla, cuando la búsqueda de nombres se ve en una clase base en un miembro de una plantilla, y cuando puede convertirse en una base virtual al comienzo de la construcción de un objeto.
curioso
Re: consumir. ¿Afirma que el destino de los pedidos de consumo está relacionado con el destino de DEC Alpha y no tiene ningún valor fuera de ese arco en particular?
curioso
1
Buena pregunta. Mirando más ahora, parece que consumir teóricamente podría dar un aumento de rendimiento para arcos débilmente ordenados como ARM y PowerPC. Dame más tiempo para investigarlo.
Humphrey Winnebago
1
Diría que consumir existe debido a todos los ISA débilmente ordenados que no sean Alpha. En Alpha asm, las únicas opciones son relajadas y adquirir (y seq-cst), no el orden de dependencia. mo_consumeestá destinado a aprovechar el orden de dependencia de datos en CPU reales y formalizar que el compilador no puede romper la dependencia de datos a través de la predicción de ramificación. por ejemplo, int *p = load(); tmp = *p;el compilador podría romperlo if(p==known_address) tmp = *known_address; else tmp=*p;si tuviera alguna razón para esperar que un cierto valor de puntero sea común. Eso es legal para relajarse pero no consumir.
Peter Cordes
@PeterCordes a la derecha ... los arcos con un orden débil tienen que emitir una barrera de memoria para adquirir, pero (en teoría) no para consumir. Parece que piensas que si el Alfa nunca existiera, ¿todavía habríamos consumido? Además, básicamente estás diciendo que consumir es una barrera de compilación elegante (o "estándar").
Humphrey Winnebago