java - ¿Podría el JIT colapsar dos lecturas volátiles como una en ciertas expresiones?

volatile memory-model

Question

Supongamos que tenemos un volatile int a . Un hilo hace

while (true) {
    a = 1;
    a = 0;
}

y otro hilo hace

while (true) {
    System.out.println(a+a);
}

Ahora, ¿sería ilegal que un compilador JIT emita un ensamblaje correspondiente a 2*a lugar de a+a ?

Por un lado, el propósito mismo de una lectura volátil es que siempre debe estar fresco de la memoria.

Por otro lado, no hay un punto de sincronización entre las dos lecturas, por lo que no puedo ver que sería ilegal tratar a+a atómicamente, en cuyo caso no veo cómo se rompería una optimización como 2*a la especificación

Las referencias a JLS serían apreciadas.

Answer 1

Por un lado, el propósito mismo de una lectura volátil es que siempre debe estar fresco de la memoria.

No es así como la especificación del lenguaje Java define la volatilidad. El JLS simplemente dice:

Una escritura en una variable volátil v (§8.3.1.4) se sincroniza con todas las lecturas subsiguientes de v por cualquier hilo (donde "subsiguiente" se define de acuerdo con el orden de sincronización).

Por lo tanto, una escritura en una variable volátil ocurre antes (y es visible para) cualquier lectura posterior de esa misma variable.

Esta restricción se cumple trivialmente para una lectura que no es posterior. Es decir, volatile solo garantiza la visibilidad de una escritura si se sabe que la lectura se produce después de la escritura.

Este no es el caso en su programa. Por cada ejecución bien formada que observe que a sea 1, puedo construir otra ejecución bien formada donde a se observe que es 0, simplemente mover la lectura después de la escritura. Esto es posible porque la relación de suceso antes se ve de la siguiente manera:

write 1   -->   read 1                    write 1   -->   read 1
   |              |                          |              |
   |              v                          v              |
   v      -->   read 1                    write 0           v
write 0           |             vs.          |      -->   read 0
   |              |                          |              |
   v              v                          v              v
write 1   -->   read 1                    write 1   -->   read 1                 

Es decir, todas las garantías de JMM para su programa son que a + a producirá 0, 1 o 2. Esto se cumple si a + a siempre produce 0. Al igual que el sistema operativo puede ejecutar este programa en un solo núcleo, y siempre interrumpa el subproceso 1 antes de la misma instrucción del bucle, se permite que la JVM reutilice el valor; después de todo, el comportamiento observable sigue siendo el mismo.

En general, mover la lectura a través de la escritura viola la coherencia antes de que suceda, porque alguna otra acción de sincronización está "en el camino". En ausencia de tales acciones de sincronización intermediarias, una lectura volátil puede satisfacerse desde un caché.

Answer 2

En mi respuesta original, argumenté en contra de la legalidad de la optimización sugerida. Respaldé esto principalmente a partir de la información del libro de cocina JSR-133 donde dice que una lectura volátil no debe ser reordenada con otra lectura volátil y donde dice que una lectura almacenada en caché debe tratarse como una reordenación. Sin embargo, la última afirmación está formulada con cierta ambigüedad, por lo que pasé por la definición formal de JMM donde no encontré tal indicación. Por lo tanto, ahora argumentaría que la optimización está permitida. Sin embargo, el JMM es bastante complejo y la discusión en esta página indica que este caso de esquina puede ser decidido de manera diferente por alguien con una comprensión más completa del formalismo.

Denotando el hilo 1 para ejecutar

while (true) {
  System.out.println(a // r_1 
    + a); // r_2
} 

y el hilo 2 para ejecutar:

while (true) {
  a = 0; // w_1
  a = 1; // w_2
}

Las dos lecturas r_i y dos escrituras w_i de a son acciones de sincronización, ya que es volatile (JSR 17.4.2). Son acciones externas ya que la variable a se usa en varios hilos. Estas acciones están contenidas en el conjunto de todas las acciones A Existe un orden total de todas las acciones de sincronización, el orden de sincronización que es consistente con el orden del programa para el subproceso 1 y el subproceso 2 (JSR 17.4.4). A partir de la definición de la sincronización con orden parcial, no hay borde definido para esta orden en el código anterior. Como consecuencia, el orden de suceder antes refleja solo la semántica intra-hilo de cada hilo (JSR 17.4.5).

Con esto, definimos W como una función vista por escritura donde W(r_i) = w_2 y una función escrita de valor V(w_i) = w_2 (JLS 17.4.6). Tomé algo de libertad y w_1 ya que hace que este esquema de prueba formal sea aún más simple. La pregunta es de esta ejecución propuesta E está bien formada (JLS 17.5.7). La ejecución propuesta E obedece a la semántica intra-hilo, es antes de ser consistente, obedece al orden sincronizado y cada lectura observa una escritura consistente. La verificación de los requisitos de causalidad es trivial (JSR 17.4.8). Tampoco veo por qué las reglas para las ejecuciones sin terminación serían relevantes ya que el bucle cubre todo el código discutido (JLS 17.4.9) y no necesitamos distinguir las acciones observables .

Por todo esto, no puedo encontrar ninguna indicación de por qué esta optimización estaría prohibida. Sin embargo, HotSpot VM no aplica volatile lecturas volatile como se puede observar con -XX:+PrintAssembly . Supongo que los beneficios de rendimiento son sin embargo menores y este patrón normalmente no se observa.

Observación: Después de ver la pragmática del modelo de memoria Java (varias veces), estoy bastante seguro de que este razonamiento es correcto.

Answer 3

Modificado un poco el Problema OP.

   volatile int a

    //thread 1
    while (true) {
        a = some_oddNumber;
        a = some_evenNumber;
    }

    // Thread 2 
    while (true) {
        if(isOdd(a+a)) {
            break;
        }
    }

Si el código anterior se ha ejecutado secuencialmente, entonces existe una Ejecución Consistente Secuencial válida que romperá el hilo2 mientras que el bucle .

Mientras que si el compilador optimiza a + a a 2a, entonces thread2 while loop nunca existirá .

Por lo tanto, la optimización anterior prohibirá una ejecución en particular si hubiera sido un código ejecutado secuencialmente.

Pregunta principal, ¿es esta optimización un problema?

Q.   Is the Transformed code Sequentially Consistent.

Respuesta Un programa está correctamente sincronizado si, cuando se ejecuta de manera secuencial y coherente, no hay carreras de datos. Consulte el Ejemplo 17.4.8-1 del capítulo 17 de JLS

   Sequential consistency: the result of any execution is the same as
   if the read and write operations by all processes were executed in
   some sequential order and the operations of each individual
   process appear in this sequence in the order specified by its
   program [Lamport, 1979].

   Also see http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.3

La consistencia secuencial es una fuerte garantía. La ruta de ejecución donde el compilador optimiza a + a como 2a también es una ejecución coherente secuencial válida . Así que la respuesta es sí.

  Q.   Is the code violates happens before guarantees.

Respuesta Consistencia secuencial implica que esto sucede antes de que la garantía sea válida aquí. Así que la respuesta es sí. JLS ref

Así que no creo que la optimización sea legalmente inválida al menos en el caso de OP. El caso en el que el subproceso 2 mientras enrolla los stucks en un infinte también es bastante posible sin la transformación del compilador.

Answer 4

Respuesta corta:

Sí, esta optimización está permitida. El colapso de dos operaciones de lectura secuencial produce el comportamiento observable de que la secuencia es atómica , pero no aparece como una reordenación de las operaciones. Cualquier secuencia de acciones realizadas en un solo hilo de ejecución puede ejecutarse como una unidad atómica. En general, es difícil garantizar que una secuencia de operaciones se ejecute de forma atómica, y rara vez se traduce en una ganancia de rendimiento porque la mayoría de los entornos de ejecución introducen una sobrecarga para ejecutar elementos de forma atómica.

En el ejemplo dado por la pregunta original, la secuencia de operaciones en cuestión es la siguiente:

read(a)
read(a)

Realizar estas operaciones de forma atómica garantiza que el valor leído en la primera línea es igual al valor leído en la segunda línea. Además, significa que el valor leído en la segunda línea es el valor contenido en el momento en que se ejecutó la primera lectura (y viceversa, porque ambas operaciones de lectura atómicas ocurrieron al mismo tiempo de acuerdo con el estado de ejecución observable del programa) . La optimización en cuestión, que está reutilizando el valor de la primera lectura para la segunda lectura, es equivalente al compilador y / o JIT que ejecuta la secuencia de forma atómica, y por lo tanto es válida.

Respuesta original más larga:

El modelo de memoria de Java describe las operaciones que utilizan un orden parcial de suceso antes que . Para expresar la restricción de que la primera lectura r1 y la segunda lectura r2 de a no pueden colapsarse, debe mostrar que es necesario que aparezca semánticamente alguna operación entre ellas.

Las operaciones en el hilo con r1 y r2 son las siguientes:

--> r(a) --> r(a) --> add -->

Para expresar el requisito de que algo (digamos y ) se encuentra entre r1 y r2 , debe exigir que r1 pase (antes de que y y y ocurra) antes de r2 . A medida que sucede, no hay ninguna regla donde aparezca una operación de lectura en el lado izquierdo de una relación de suceso antes . Lo más cerca que podría estar es diciendo que sucede y antes de r2 , pero el orden parcial permitiría que y también ocurriera antes de r1 , colapsando así las operaciones de lectura.

Si no existe un escenario que requiera que una operación caiga entre r1 y r2 , entonces puede declarar que nunca aparece ninguna operación entre r1 y r2 y no violar la semántica requerida del idioma. Usar una sola operación de lectura sería equivalente a esta afirmación.

Editar Mi respuesta está siendo rechazada, así que voy a entrar en detalles adicionales.

Aquí hay algunas preguntas relacionadas:

• ¿Se requiere el compilador de Java o JVM para contraer estas operaciones de lectura?

  No. Las expresiones a y a utilizadas en la expresión add no son expresiones constantes, por lo que no es necesario que se colapsen.

• ¿ Colapsa la JVM estas operaciones de lectura?

  A esto, no estoy seguro de la respuesta. Al compilar un programa y usar javap -c , es fácil ver que el compilador de Java no contrae estas operaciones de lectura. Desafortunadamente, no es tan fácil probar que la JVM no colapsa las operaciones (o aún más difícil, el propio procesador).

• ¿Debería la JVM colapsar estas operaciones de lectura?

  Probablemente no. Cada optimización lleva tiempo para ejecutarse, por lo que hay un equilibrio entre el tiempo que toma analizar el código y el beneficio que espera obtener. Algunas optimizaciones, como la eliminación de verificación de límites de matriz o la comprobación de referencias nulas, han demostrado tener amplios beneficios para aplicaciones del mundo real. El único caso en el que esta optimización particular tiene la posibilidad de mejorar el rendimiento es en los casos en que aparecen dos operaciones de lectura idénticas secuencialmente.

  Además, como lo muestra la respuesta a esta respuesta junto con las otras respuestas, este cambio en particular resultará en un cambio de comportamiento inesperado para ciertas aplicaciones que los usuarios pueden no desear.

Edición 2: con respecto a la descripción de Rafael de una afirmación de que dos operaciones de lectura no pueden ser reordenadas. Esta declaración está diseñada para resaltar el hecho de que el almacenamiento en caché de la operación de lectura en la siguiente secuencia podría producir un resultado incorrecto:

a1 = read(a)
b1 = read(b)
a2 = read(a)
result = op(a1, b1, a2)

Supongamos que inicialmente a y b tienen su valor predeterminado 0. Luego, ejecuta solo la primera read(a) .

Ahora supongamos que otro hilo ejecuta la siguiente secuencia:

a = 1
b = 1

Finalmente, suponga que el primer hilo ejecuta la línea read(b) . Si tuviera que almacenar en caché el valor leído originalmente de a , terminaría con la siguiente llamada:

op(0, 1, 0)

Esto no es correcto. Dado que el valor actualizado de a se almacenó antes de escribir en b , no hay forma de leer el valor b1 = 1 y luego leer el valor a2 = 0 . Sin almacenamiento en caché, la secuencia correcta de eventos lleva a la siguiente llamada.

op(0, 1, 1)

Sin embargo, si tuviera que hacer la pregunta "¿Hay alguna forma de permitir que la lectura de a archivo se almacene en caché?", La respuesta es sí. Si puede ejecutar las tres operaciones de lectura en la primera secuencia de hilos como una unidad atómica , entonces se permite el almacenamiento en caché del valor. Si bien la sincronización entre múltiples variables es difícil y rara vez proporciona una ventaja de optimización oportunista, ciertamente es posible encontrar una excepción. Por ejemplo, supongamos que a y b son cada uno de 4 bytes, y aparecen secuencialmente en la memoria con a alineación en un límite de 8 bytes. Un proceso de 64 bits podría implementar la secuencia de read(a) read(b) como una operación de carga atómica de 64 bits, lo que permitiría que el valor de a se almacene en caché (tratando las tres operaciones de lectura como una operación atómica en lugar de solo los primeros dos).

Answer 5

Según lo establecido en otras respuestas, hay dos lecturas y dos escrituras. Imagine la siguiente ejecución (T1 y T2 denotan dos subprocesos), utilizando anotaciones que coinciden con la siguiente declaración JLS:

• T1: a = 0 //W(r)
• T2: read temp1 = a //r_initial
• T1: a = 1 //w
• T2: read temp2 = a //r
• T2: print temp1+temp2

En un entorno concurrente, este es definitivamente un posible entrelazado de hilos. Su pregunta es entonces: ¿se le permitiría a la JVM hacer r observar W(r) y leer 0 en lugar de 1?

JLS # 17.4.5 estados:

Un conjunto de acciones A sucede antes de que sea consistente si para todas las lecturas r en A, donde W (r) es la acción de escritura vista por r, no es el caso que hb (r, W (r)) o que haya existe una escritura w en A tal que wv = rv y hb (W (r), w) y hb (w, r).

La optimización que proponga ( temp = a; print (2 * temp); ) violaría ese requisito. Por lo tanto, su optimización solo puede funcionar si no hay escritura intermedia entre r_initial r , lo que no se puede garantizar en un marco típico de múltiples hilos.

Como comentario adicional, tenga en cuenta, sin embargo, que no hay garantía de cuánto tiempo tomará para que las escrituras sean visibles desde el hilo de lectura. Véase, por ejemplo: Semántica detallada de la volatilidad con respecto a la puntualidad de la visibilidad .