tecnologia - ¿Por qué leer un documento volátil y escribir en un miembro de campo no es escalable en Java?

significado de la palabra escalable

Question

Observe el siguiente programa escrito en Java (sigue la versión completa ejecutable, pero la parte importante del programa se encuentra en el fragmento un poco más adelante):

import java.util.ArrayList;
/** A not easy to explain benchmark.
*/
class MultiVolatileJavaExperiment {
public static void main(String[] args) {
(new MultiVolatileJavaExperiment()).mainMethod(args);
}
int size = Integer.parseInt(System.getProperty("size"));
int par = Integer.parseInt(System.getProperty("par"));
public void mainMethod(String[] args) {
int times = 0;
if (args.length == 0) times = 1;
else times = Integer.parseInt(args[0]);
ArrayList < Long > measurements = new ArrayList < Long > ();
for (int i = 0; i < times; i++) {
long start = System.currentTimeMillis();
run();
long end = System.currentTimeMillis();
long time = (end - start);
System.out.println(i + ") Running time: " + time + " ms");
measurements.add(time);
}
System.out.println(">>>");
System.out.println(">>> All running times: " + measurements);
System.out.println(">>>");
}
public void run() {
int sz = size / par;
ArrayList < Thread > threads = new ArrayList < Thread > ();
for (int i = 0; i < par; i++) {
threads.add(new Reader(sz));
threads.get(i).start();
}
for (int i = 0; i < par; i++) {
try {
threads.get(i).join();
} catch (Exception e) {}
}
}
final class Foo {
int x = 0;
}
final class Reader extends Thread {
volatile Foo vfoo = new Foo();
Foo bar = null;
int sz;
public Reader(int _sz) {
sz = _sz;
}
public void run() {
int i = 0;
while (i < sz) {
vfoo.x = 1;
// with the following line commented
// the scalability is almost linear
bar = vfoo; // <- makes benchmark 2x slower for 2 processors - why?
i++;
}
}
}
}

Explicación : El programa es realmente muy simple. Carga enteros size y par de las propiedades del sistema (pasa a jvm con el indicador -D ) - estas son la longitud de entrada y el número de subprocesos para usar más tarde. A continuación, analiza el primer argumento de la línea de comando que indica el tiempo que se tarda en repetir el programa (queremos asegurarnos de que el JIT ha hecho su trabajo y de que tiene mediciones más confiables).

El método de run se llama en cada repetición. Este método simplemente inicia subprocesos par , cada uno de los cuales realizará un ciclo con iteraciones de size / par . El cuerpo del hilo se define en la clase Reader . Cada repetición del ciclo lee un miembro volátil vfoo y asigna 1 a su campo público. Después de eso, vfoo se lee una vez más y se asigna a una bar campo no volátil .

Observe cómo la mayoría de las veces el programa está ejecutando el cuerpo del bucle, por lo que la run en el hilo es el foco de este punto de referencia:

 final class Reader extends Thread {
volatile Foo vfoo = new Foo();
Foo bar = null;
int sz;
public Reader(int _sz) {
sz = _sz;
}
public void run() {
int i = 0;
while (i < sz) {
vfoo.x = 1;
// with the following line commented
// the scalability is almost linear
bar = vfoo; // <- makes benchmark 2x slower for 2 processors - why?
i++;
}
}
}

Observaciones : Corriendo java -Xmx512m -Xms512m -server -Dsize=500000000 -Dpar=1 MultiVolatileJavaExperiment 10 en una

Ubuntu Server 10.04.3 LTS
8 core Intel(R) Xeon(R) CPU X5355 @2.66GHz
~20GB ram
java version "1.6.0_26"
Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)

Recibo los siguientes momentos:

>>> All running times: [821, 750, 1011, 750, 758, 755, 1219, 751, 751, 1012]

Ahora, configurando -Dpar=2 , obtengo:

>>> All running times: [1618, 380, 1476, 1245, 1390, 1391, 1445, 1393, 1511, 1508]

Aparentemente, esto no se escala por alguna razón. Esperaba que la segunda salida fuera el doble de rápida (aunque parece estar en una de las primeras iteraciones, 380ms ).

Curiosamente, al comentar la línea bar = vfoo (que ni siquiera se supone que es una escritura volátil), se obtienen los siguientes tiempos para -Dpar establecido en 1,2,4,8 .

>>> All running times: [762, 563, 563, 563, 563, 563, 570, 566, 563, 563]
>>> All running times: [387, 287, 285, 284, 283, 281, 282, 282, 281, 282]
>>> All running times: [204, 146, 143, 142, 141, 141, 141, 141, 141, 141]
>>> All running times: [120, 78, 74, 74, 81, 75, 73, 73, 72, 71]

Se escala perfectamente.

Análisis : En primer lugar, no hay ciclos de recolección de basura aquí (también he agregado -verbose:gc para verificar esto).

Obtengo resultados similares en mi iMac.

Cada hilo está escribiendo en su propio campo, y diferentes instancias de objetos Foo que pertenecen a diferentes subprocesos no parecen estar terminando en las mismas cachelines: agregar más miembros a Foo para aumentar su tamaño no cambia las medidas. Cada instancia de objeto de subproceso tiene campos más que suficientes para llenar la línea de caché L1. Entonces esto probablemente no es un problema de memoria.

Lo siguiente que pensé fue que el JIT podría estar haciendo algo raro, porque las primeras iteraciones generalmente se escalan como se esperaba en la versión no comentada, así que lo comprobé imprimiendo el ensamblaje (consulte esta publicación sobre cómo hacerlo ).

java -Xmx512m -Xms512m -server -XX:CompileCommand=print,*Reader.run MultiVolatileJavaExperiment -Dsize=500000000 -Dpar=1 10

y obtengo estas 2 salidas para las 2 versiones para el método Jitted run en Reader . La versión comentada (correctamente escalable):

[Verified Entry Point]
0xf36c9fac: mov %eax,-0x3000(%esp)
0xf36c9fb3: push %ebp
0xf36c9fb4: sub $0x8,%esp
0xf36c9fba: mov 0x68(%ecx),%ebx
0xf36c9fbd: test %ebx,%ebx
0xf36c9fbf: jle 0xf36c9fec
0xf36c9fc1: xor %ebx,%ebx
0xf36c9fc3: nopw 0x0(%eax,%eax,1)
0xf36c9fcc: xchg %ax,%ax
0xf36c9fd0: mov 0x6c(%ecx),%ebp
0xf36c9fd3: test %ebp,%ebp
0xf36c9fd5: je 0xf36c9ff7
0xf36c9fd7: movl $0x1,0x8(%ebp)
---------------------------------------------
0xf36c9fde: mov 0x68(%ecx),%ebp
0xf36c9fe1: inc %ebx ; OopMap{ecx=Oop off=66}
;*goto
; - org.scalapool.bench.MultiVolatileJavaExperiment$Reader::run@21 (line 83)
---------------------------------------------
0xf36c9fe2: test %edi,0xf7725000 ; {poll}
0xf36c9fe8: cmp %ebp,%ebx
0xf36c9fea: jl 0xf36c9fd0
0xf36c9fec: add $0x8,%esp
0xf36c9fef: pop %ebp
0xf36c9ff0: test %eax,0xf7725000 ; {poll_return}
0xf36c9ff6: ret
0xf36c9ff7: mov $0xfffffff6,%ecx
0xf36c9ffc: xchg %ax,%ax
0xf36c9fff: call 0xf36a56a0 ; OopMap{off=100}
;*putfield x
; - org.scalapool.bench.MultiVolatileJavaExperiment$Reader::run@15 (line 79)
; {runtime_call}
0xf36ca004: call 0xf6f877a0 ; {runtime_call}

La bar = vfoo no bar = vfoo (no escalable, más lenta):

[Verified Entry Point]
0xf3771aac: mov %eax,-0x3000(%esp)
0xf3771ab3: push %ebp
0xf3771ab4: sub $0x8,%esp
0xf3771aba: mov 0x68(%ecx),%ebx
0xf3771abd: test %ebx,%ebx
0xf3771abf: jle 0xf3771afe
0xf3771ac1: xor %ebx,%ebx
0xf3771ac3: nopw 0x0(%eax,%eax,1)
0xf3771acc: xchg %ax,%ax
0xf3771ad0: mov 0x6c(%ecx),%ebp
0xf3771ad3: test %ebp,%ebp
0xf3771ad5: je 0xf3771b09
0xf3771ad7: movl $0x1,0x8(%ebp)
-------------------------------------------------
0xf3771ade: mov 0x6c(%ecx),%ebp
0xf3771ae1: mov %ebp,0x70(%ecx)
0xf3771ae4: mov 0x68(%ecx),%edi
0xf3771ae7: inc %ebx
0xf3771ae8: mov %ecx,%eax
0xf3771aea: shr $0x9,%eax
0xf3771aed: movb $0x0,-0x3113c300(%eax) ; OopMap{ecx=Oop off=84}
;*goto
; - org.scalapool.bench.MultiVolatileJavaExperiment$Reader::run@29 (line 83)
-----------------------------------------------
0xf3771af4: test %edi,0xf77ce000 ; {poll}
0xf3771afa: cmp %edi,%ebx
0xf3771afc: jl 0xf3771ad0
0xf3771afe: add $0x8,%esp
0xf3771b01: pop %ebp
0xf3771b02: test %eax,0xf77ce000 ; {poll_return}
0xf3771b08: ret
0xf3771b09: mov $0xfffffff6,%ecx
0xf3771b0e: nop
0xf3771b0f: call 0xf374e6a0 ; OopMap{off=116}
;*putfield x
; - org.scalapool.bench.MultiVolatileJavaExperiment$Reader::run@15 (line 79)
; {runtime_call}
0xf3771b14: call 0xf70307a0 ; {runtime_call}

Las diferencias en las dos versiones están dentro de --------- . Esperaba encontrar instrucciones de sincronización en el ensamblado que pudieran explicar el problema de rendimiento, mientras que algunas instrucciones adicionales de shift , mov y inc podrían afectar las cifras absolutas de rendimiento, no veo cómo podrían afectar la escalabilidad.

Entonces, sospecho que esto es algún tipo de problema de memoria relacionado con el almacenamiento en un campo de la clase. Por otro lado, también me inclino a creer que el JIT hace algo divertido, porque en una iteración el tiempo medido es el doble de rápido, como debería ser.

¿Alguien puede explicar lo que está pasando aquí? Sea preciso e incluya referencias que respalden sus reclamos.

¡Gracias!

EDITAR:

Aquí está el bytecode para la versión rápida (escalable):

public void run();
LineNumberTable:
line 77: 0
line 78: 2
line 79: 10
line 83: 18
line 85: 24
Code:
Stack=2, Locals=2, Args_size=1
0: iconst_0
1: istore_1
2: iload_1
3: aload_0
4: getfield #7; //Field sz:I
7: if_icmpge 24
10: aload_0
11: getfield #5; //Field vfoo:Lorg/scalapool/bench/MultiVolatileJavaExperiment$Foo;
14: iconst_1
15: putfield #8; //Field org/scalapool/bench/MultiVolatileJavaExperiment$Foo.x:I
18: iinc 1, 1
21: goto 2
24: return
LineNumberTable:
line 77: 0
line 78: 2
line 79: 10
line 83: 18
line 85: 24
StackMapTable: number_of_entries = 2
frame_type = 252 /* append */
offset_delta = 2
locals = [ int ]
frame_type = 21 /* same */

La versión lenta (no escalable) con bar = vfoo :

public void run();
LineNumberTable:
line 77: 0
line 78: 2
line 79: 10
line 82: 18
line 83: 26
line 85: 32
Code:
Stack=2, Locals=2, Args_size=1
0: iconst_0
1: istore_1
2: iload_1
3: aload_0
4: getfield #7; //Field sz:I
7: if_icmpge 32
10: aload_0
11: getfield #5; //Field vfoo:Lorg/scalapool/bench/MultiVolatileJavaExperiment$Foo;
14: iconst_1
15: putfield #8; //Field org/scalapool/bench/MultiVolatileJavaExperiment$Foo.x:I
18: aload_0
19: aload_0
20: getfield #5; //Field vfoo:Lorg/scalapool/bench/MultiVolatileJavaExperiment$Foo;
23: putfield #6; //Field bar:Lorg/scalapool/bench/MultiVolatileJavaExperiment$Foo;
26: iinc 1, 1
29: goto 2
32: return
LineNumberTable:
line 77: 0
line 78: 2
line 79: 10
line 82: 18
line 83: 26
line 85: 32
StackMapTable: number_of_entries = 2
frame_type = 252 /* append */
offset_delta = 2
locals = [ int ]
frame_type = 29 /* same */

Cuanto más experimento con esto, me parece que esto no tiene nada que ver con los volátiles: tiene algo que ver con escribir en los campos de objetos. Mi corazonada es que esto es, de alguna manera, un problema de contención de memoria, algo con cachés y uso compartido falso, aunque no hay ninguna sincronización explícita en absoluto.

EDICION 2:

Curiosamente, cambiar el programa de esta manera:

final class Holder {
public Foo bar = null;
}
final class Reader extends Thread {
volatile Foo vfoo = new Foo();
Holder holder = null;
int sz;
public Reader(int _sz) {
sz = _sz;
}
public void run() {
int i = 0;
holder = new Holder();
while (i < sz) {
vfoo.x = 1;
holder.bar = vfoo;
i++;
}
}
}

resuelve el problema de escalado Aparentemente, el objeto Holder anterior se crea después de que se inicia el subproceso, y probablemente esté asignado en un segmento diferente de la memoria, que luego se modifica al mismo tiempo, en lugar de modificar la bar campo en el objeto de subproceso, que de alguna manera está "cerca" en memoria entre diferentes instancias de subprocesos.

Answer 1

Corto: aparentemente, la respuesta es compartir falsamente debido al marcado de la tarjeta para el GC.

Una explicación más extensa se da en esta pregunta:

Asignación y acceso de matriz en Java Virtual Machine y contención de memoria

Answer 2

Editar: esta respuesta no resistió las pruebas.

No tengo forma de probar esto ahora (no hay CPU multinúcleo en esta máquina), pero aquí hay una teoría: las instancias de Foo pueden no estar en las mismas líneas de caché, pero quizás las instancias de Reader están.

Esto significa que la ralentización podría explicarse por la bar escribir en, en lugar de la lectura de foo , porque escribir en la bar invalidaría esa línea de caché para el otro núcleo y causaría muchas copias entre cachés. Al comentar la bar escribir en (que es la única escritura en un campo de Reader en el ciclo) se detiene la desaceleración, lo cual es consistente con esta explicación.

Editar: Según este artículo , el diseño de memoria de los objetos es tal que la referencia de bar sería el último campo en el diseño del objeto Reader . Esto significa que es probable aterrizar en la misma línea de caché que el siguiente objeto en el Heap. Como no estoy seguro del orden en que se asignan los nuevos objetos en el Heap, sugerí en el siguiente comentario que se incluyeran los dos tipos de objetos "calientes" con referencias, que serían efectivos para separar los objetos (Al menos, espero que voluntad, pero depende de cómo los campos del mismo tipo se ordenan en la memoria).

Answer 3

En realidad, no está escribiendo en un campo volátil por lo que el campo volátil se puede almacenar en caché en cada hilo.

El uso de volátiles previene algunas optimizaciones del compilador y en una micro-referencia, puede ver una gran diferencia relativa.

En el ejemplo anterior, la versión comentada es más larga porque tiene un bucle desplegado para colocar dos iteraciones en un bucle real. Esto puede casi duplicar el rendimiento.

Cuando se usa volátil, puede ver que no se está desenrollando ningún bucle.

Por cierto: puede eliminar una gran cantidad de código en su ejemplo para que sea más fácil de leer. ;)

Answer 4

Esto es lo que creo que está sucediendo (tenga en cuenta que no estoy familiarizado con HotSpot):

0xf36c9fd0: mov 0x6c(%ecx),%ebp ; vfoo
0xf36c9fd3: test %ebp,%ebp ; vfoo is null?
0xf36c9fd5: je 0xf36c9ff7 ; throw NullPointerException (I guess)
0xf36c9fd7: movl $0x1,0x8(%ebp) ; vfoo.x = 1
0xf36c9fde: mov 0x68(%ecx),%ebp ; sz
0xf36c9fe1: inc %ebx ; i++
0xf36c9fe2: test %edi,0xf7725000 ; safepoint on end of loop
0xf36c9fe8: cmp %ebp,%ebx ; i < sz?
0xf36c9fea: jl 0xf36c9fd0
0xf3771ad0: mov 0x6c(%ecx),%ebp ; vfoo
0xf3771ad3: test %ebp,%ebp ; vfoo is null?
0xf3771ad5: je 0xf3771b09 ; throw NullPointerException (I guess)
0xf3771ad7: movl $0x1,0x8(%ebp) ; vfoo.x = 1
0xf3771ade: mov 0x6c(%ecx),%ebp ; /
0xf3771ae1: mov %ebp,0x70(%ecx) ; / bar = vfoo
0xf3771ae4: mov 0x68(%ecx),%edi ; sz
0xf3771ae7: inc %ebx ; i++
0xf3771ae8: mov %ecx,%eax ;
0xf3771aea: shr $0x9,%eax ; ??? / Probably replaced later
0xf3771aed: movb $0x0,-0x3113c300(%eax) ; ??? / by some barrier code?
0xf3771af4: test %edi,0xf77ce000 ; safepoint
0xf3771afa: cmp %edi,%ebx ; i < sz ?
0xf3771afc: jl 0xf3771ad0 ;

La razón por la que creo que el código anterior representa una barrera es que al tomar NullPointerException, la versión escalable tiene un XCHG , que actúa como una barrera, mientras que la versión no escalable tiene un NOP allí.

El fundamento sería que debe haber un vfoo antes de ordenar entre la carga inicial de vfoo y unir el hilo. En el caso volátil, la barrera estaría dentro del circuito, por lo que no necesitaría estar en otro lugar. Lo que no entiendo es por qué XCHG no se usa dentro del ciclo. ¿Tal vez la detección en tiempo de ejecución del soporte de MFENCE?

Answer 5

Probemos hacer que la JVM se comporte un poco más "consistentemente". El compilador JIT realmente está arrojando comparaciones de ejecuciones de prueba; así que deshabilitemos el compilador JIT usando -Djava.compiler=NONE . Esto definitivamente introduce un golpe de rendimiento, pero ayudará a eliminar la oscuridad y los efectos de las optimizaciones del compilador JIT.

La recolección de basura presenta su propio conjunto de complejidades. -XX:+UseSerialGC recolector de basura en serie usando -XX:+UseSerialGC . Desactivemos también colecciones de basura explícitas y -verbose:gc -XX:+DisableExplicitGC algunos registros para ver cuándo se realiza la recolección de elementos no utilizados -verbose:gc -XX:+DisableExplicitGC . Finalmente, obtengamos el montón suficiente asignado usando -Xmx128m -Xms128m .

Ahora podemos ejecutar la prueba usando:

java -XX:+UseSerialGC -verbose:gc -XX:+DisableExplicitGC -Djava.compiler=NONE -Xmx128m -Xms128m -server -Dsize=50000000 -Dpar=1 MultiVolatileJavaExperiment 10

Ejecutar la prueba varias veces muestra que los resultados son muy consistentes (estoy usando Oracle Java 1.6.0_24-b07 en Ubuntu 10.04.3 LTS con una CPU Intel (R) Core (TM) 2 Duo P8700 @ 2.53GHz), promediando algún lugar alrededor de 2050 milisegundos. Si hago un comentario sobre la línea bar = vfoo , estoy promediando de manera consistente unos 1280 milisegundos. Ejecutar la prueba usando -Dpar=2 resultados con un promedio de aproximadamente 1350 milisegundos con bar = vfoo y alrededor de 1005 milisegundos con el comentario.

+=========+======+=========+
| Threads | With | Without |
+=========+======+=========+
| 1 | 2050 | 1280 |
+---------+------+---------+
| 2 | 1350 | 1005 |
+=========+======+=========+

Miremos ahora el código y veamos si podemos encontrar alguna razón por la cual el multi-threading es ineficiente. En Reader.run() , calificar la variable con this según corresponda ayudará a aclarar qué variables son locales:

int i = 0;
while (i < this.sz) {
this.vfoo.x = 1;
this.bar = this.vfoo;
i++;
}

Lo primero que debe tenerse en cuenta es que el ciclo while contiene cuatro variables a las que se hace referencia a través de this . Esto significa que el código está accediendo al grupo de constante de tiempo de ejecución de la clase y realizando la verificación de tipo (a través de la instrucción getfield bytecode). Cambiemos el código para tratar de eliminar el acceso al conjunto de constantes de tiempo de ejecución y ver si obtenemos algún beneficio.

final int mysz = this.sz;
int i = 0;
while (i < mysz) {
this.vfoo.x = 1;
this.bar = this.vfoo;
i++;
}

Aquí, estamos usando una variable mysz local para acceder al tamaño del bucle y solo accediendo a sz través de this una vez, para la inicialización. Ejecutar la prueba, con dos subprocesos, promedia unos 1295 milisegundos; un pequeño beneficio, pero uno, no obstante.

Mirando el ciclo while, ¿realmente necesitamos hacer referencia a this.vfoo dos veces? Las dos lecturas volátiles crean dos bordes de sincronización que la máquina virtual (y el hardware subyacente, para el caso) necesitan administrar. Digamos que queremos un borde de sincronización al principio del ciclo while y no necesitamos dos, podemos usar lo siguiente:

final int mysz = this.sz;
Foo myvfoo = null;
int i = 0;
while (i < mysz) {
myvfoo = this.vfoo;
myvfoo.x = 1;
this.bar = myvfoo;
i++;
}

Esto promedia unos 1122 milisegundos; todavía está mejorando. ¿Qué hay de eso this.bar referencia de this.bar ? Dado que estamos hablando de varios subprocesos, digamos que los cálculos en el ciclo while es de lo que queremos obtener beneficios de subprocesos múltiples y this.bar es la forma en que comunicamos nuestros resultados a otros. Realmente no queremos configurar this.bar hasta que el ciclo while haya terminado.

final int mysz = this.sz;
Foo myvfoo = null;
Foo mybar = null;
int i = 0;
while (i < mysz) {
myvfoo = this.vfoo;
myvfoo.x = 1;
mybar = myvfoo;
i++;
}
this.bar = mybar;

Lo que nos da unos 857 milisegundos en promedio. Todavía hay esa referencia final this.vfoo en el ciclo while. Asumiendo de nuevo que el bucle while es de lo que queremos beneficio de subprocesos múltiples, vamos a mover this.vfoo fuera del ciclo while.

final int mysz = this.sz;
final Foo myvfoo = this.vfoo;
Foo mybar = null;
int i = 0;
while (i < mysz) {
myvfoo.x = 1;
mybar = myvfoo;
i++;
}
final Foo vfoocheck = this.vfoo;
if (vfoocheck != myvfoo) {
System.out.println("vfoo changed from " + myvfoo + " to " + vfoocheck);
}
this.bar = mybar;

Ahora promediamos unos 502 milisegundos; los promedios de prueba de un solo subproceso alrededor de 900 milisegundos.

¿Entonces qué nos dice esto? Al extrapolar referencias de variables no locales fuera del ciclo while, se han obtenido importantes beneficios de rendimiento tanto en las pruebas de subprocesos simples como dobles. La versión original de MultiVolatileJavaExperiment estaba midiendo el costo de acceder a variables no locales 50,000,000 de veces, mientras que la versión final está midiendo el costo de acceder a variables locales 50,000,000 de veces. Al usar variables locales, aumenta la probabilidad de que la Máquina Virtual Java y el hardware subyacente puedan administrar los cachés de hilos de manera más eficiente.

Finalmente, hagamos las pruebas normalmente usando (aviso, utilizando un tamaño de bucle de 500,000,000 en vez de 50,000,000):

java -Xmx128m -Xms128m -server -Dsize=500000000 -Dpar=2 MultiVolatileJavaExperiment 10

La versión original tiene un promedio de 1100 milisegundos y la versión modificada tiene un promedio de 10 milisegundos.