ejemplos - java 8

Asignación y acceso a la matriz en la máquina virtual de Java y contención de memoria

Question

Observe la siguiente definición de una subclase de subprocesos (para su comodidad, se incluye el archivo fuente Java ejecutable completo al final de la pregunta):

final class Worker extends Thread {
    Foo[] array = new Foo[1024];
    int sz;

    public Worker(int _sz) {
        sz = _sz;
    }

    public void run() {
        //Foo[] arr = new Foo[1024];
        Foo[] arr = array;
        loop(arr);
    }

    public void loop(Foo[] arr) {
        int i = 0;
        int pos = 512;
        Foo v = new Foo();
        while (i < sz) {
            if (i % 2 == 0) {
                arr[pos] = v;
                pos += 1;
            } else {
                pos -= 1;
                v = arr[pos];
            }
            i++;
        }
    }
}

Explicación : el programa inicia -Dpar dichos subprocesos y establece el sz de cada subproceso en -Dsize / -Dpar , donde -Dsize y -Dpar se establecen a través de la línea de comandos cuando se ejecuta el programa. Cada objeto de hilo tiene una array campo que se inicializa con una nueva matriz de elementos de 1024 . El razonamiento es que queremos dividir una cantidad igual de trabajo entre un número diferente de subprocesos: esperamos que el programa se amplíe.

Cada hilo se inicia y se mide el tiempo necesario para completar todos los hilos. Hacemos múltiples mediciones para contrarrestar cualquier efecto relacionado con JIT, como se muestra a continuación. Cada hilo hace un bucle. Dentro del bucle, el hilo lee un elemento en la posición 512 en la matriz en iteraciones pares y escribe el mismo elemento en 512 en iteraciones impares. De lo contrario solo se modifican las variables locales.

El programa completo está abajo.

Análisis :

Probado con -verbose:gc - no hay recolección de basura durante la ejecución de este programa.

Ejecutar comando:

java -Xmx512m -Xms512m -server -Dsize=500000000 -Dpar=1 org.scalapool.bench.MultiStackJavaExperiment 7

CASO 1: Tiempos de ejecución para 1,2,4,8 hilos, en ese orden (7 repeticiones):

>>> All running times: [2149, 2227, 1974, 1948, 1803, 2283, 1878]
>>> All running times: [1140, 1124, 2022, 1141, 2028, 2004, 2136]
>>> All running times: [867, 1022, 1457, 1342, 1436, 966, 1531]
>>> All running times: [915, 864, 1245, 1243, 948, 790, 1007]

Mi pensamiento fue que la escala no lineal se debe a la contención de la memoria. Por cierto, las iteraciones tempranas en realidad funcionan mejor, esto puede deberse al hecho de que en diferentes iteraciones las matrices se asignan en diferentes áreas de memoria.

CASO 2: A continuación, comento la línea Foo[] arr = array en el método de ejecución del hilo y asigno una nueva matriz en el método run : Foo[] arr = new Foo[1024] . Mediciones:

>>> All running times: [2053, 1966, 2089, 1937, 2046, 1909, 2011]
>>> All running times: [1048, 1178, 1100, 1194, 1367, 1271, 1207]
>>> All running times: [578, 508, 589, 571, 617, 643, 645]
>>> All running times: [330, 299, 300, 322, 331, 324, 575]

Esta vez, todo se escala más o menos como se esperaba. No hubiera imaginado que la ubicación en la que se asignó la matriz juega ningún papel, pero obviamente lo hace de alguna manera. Mi pensamiento fue que las matrices se asignaron previamente tan cerca una de la otra que comenzó a suceder algo de contención de memoria.

CASO 3: Para verificar esta suposición, no he comentado la línea Foo[] arr = array nuevamente, pero esta vez inicialicé el campo de la array a un new Foo[32000] para asegurar que la ubicación en la memoria que se está escribiendo esté lo suficientemente lejos de cada otro. Entonces, aquí estamos usando la matriz asignada durante la creación del objeto de hilo nuevamente, la diferencia con CASE1 es que la matriz es más grande.

>>> All running times: [2113, 1983, 2430, 2485, 2333, 2359, 2463]
>>> All running times: [1172, 1106, 1163, 1181, 1142, 1169, 1188]
>>> All running times: [578, 677, 614, 604, 583, 637, 597]
>>> All running times: [343, 327, 320, 330, 353, 320, 320]

Entonces, la contención de la memoria parece ser la causa de esto.

La información de la plataforma:

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)

Pregunta : Esto es obviamente un problema de contención de memoria. Pero ¿por qué sucede esto?

1. ¿Está en marcha el análisis de escape? Si es así, ¿significa que toda la matriz se asigna en la pila cuando se crea en el método de run en CASE2? ¿Cuáles son las condiciones exactas para esta optimización de tiempo de ejecución? ¿Seguro que la matriz no está asignada en la pila para 1 millón de elementos?

2. Incluso si la matriz se asigna en la pila en lugar de asignarse en el montón, dos accesos de matriz por hebras diferentes deben dividirse por al menos 512 * 4bytes = 2kb incluso en CASE1, ¡donde sea que estén las matrices! Eso es definitivamente más grande que cualquier línea de caché L1. Si estos efectos se deben a un intercambio falso, ¿cómo pueden las escrituras en varias líneas de caché totalmente independientes afectar tanto al rendimiento? (Una suposición aquí es que cada matriz ocupa un bloque de memoria contiguo en la JVM, que se asigna cuando se crea la matriz. No estoy seguro de que esto sea válido. Otra suposición es que las escrituras de la matriz no llegan hasta el final memoria, pero L1 caché en su lugar, ya que Intel Xeon tiene una arquitectura ccNUMA (corríjame si me equivoco)

3. ¿Es posible que cada subproceso tenga su propia parte del montón local donde asigna nuevos objetos de forma independiente, y esto es la causa de una contención más baja cuando la matriz se asigna en el subproceso? Si es así, ¿cómo se recolecta esa área de la basura del montón si las referencias se comparten?

4. ¿Por qué el aumento del tamaño del arreglo a ~ 32000 elementos mejoró la escalabilidad (disminuyó la contención de la memoria)? ¿Qué es exactamente la causa de esto en la jerarquía de la memoria?

Por favor, sea preciso y respalde sus reclamaciones con referencias.

¡Gracias!

Todo el programa Java ejecutable:

import java.util.ArrayList;

class MultiStackJavaExperiment {

    final class Foo {
        int x = 0;
    }

    final class Worker extends Thread {
        Foo[] array = new Foo[1024];
        int sz;

        public Worker(int _sz) {
            sz = _sz;
        }

        public void run() {
            Foo[] arr = new Foo[1024];
            //Foo[] arr = array;
            loop(arr);
        }

        public void loop(Foo[] arr) {
            int i = 0;
            int pos = 512;
            Foo v = new Foo();
            while (i < sz) {
                if (i % 2 == 0) {
                    arr[pos] = v;
                    pos += 1;
                } else {
                    pos -= 1;
                    v = arr[pos];
                }
                i++;
            }
        }
    }

    public static void main(String[] args) {
        (new MultiStackJavaExperiment()).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 Worker(sz));
            threads.get(i).start();
        }
        for (int i = 0; i < par; i++) {
            try {
                threads.get(i).join();
            } catch (Exception e) {}
        }
    }

}

Answer 1

Creo que necesitas reducir tu código para que no esté haciendo muchas cosas incidentales, lo que podría ser un asunto confuso. Después de reducir el código, me queda claro que solo está accediendo a la misma ubicación de matriz cada vez. Es decir, la posición 512.

Si minimiza su código, reutilice sus hilos para que no los detenga / comience, obtendrá resultados mucho más reproducibles.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class MultiStackJavaExperiment {
    static final int size = Integer.getInteger("size", 500000000);

    public static void main(String... args) throws ExecutionException, InterruptedException {
        int par = 8;
        for (int s = 64; s <= 64 * 1024; s *= 2) {
            int times = args.length == 0 ? 1 : Integer.parseInt(args[0]);
            long[] measurements = new long[times];

            ExecutorService es = Executors.newFixedThreadPool(par);
            List<Future<?>> futures = new ArrayList<Future<?>>(times);
            for (int i = 0; i < times; i++) {
                long start = System.currentTimeMillis();
                final int sz = size / par;
                futures.clear();
                for (int j = 0; j < par; j++) {
                    final Object[] arr = new Object[s];
                    futures.add(es.submit(new Runnable() {
                        @Override
                        public void run() {
                            final int bits = 7, arraySize = 1 << bits;
                            int i = 0;
                            int pos = 32;
                            Object v = new Object();
                            while (i < sz) {
                                if (i % 2 == 0) {
                                    arr[pos] = v;
                                    pos += 1;
                                } else {
                                    pos -= 1;
                                    v = arr[pos];
                                }
                                i++;
                            }
                        }
                    }));
                }
                for (Future<?> future : futures)
                    future.get();

                long time = System.currentTimeMillis() - start;
//                System.out.println(i + ") Running time: " + time + " ms");
                measurements[i] = time;
            }
            es.shutdown();
            System.out.println("par = " + par + " arr.length= "+ s  + " >>> All running times: " + Arrays.toString(measurements));
        }
    }
}

Esto muestra que la distancia entre los valores de acceso importa. Al asignar una matriz a cada subproceso, utiliza diferentes TLAB (que espacian los datos en bloques)

par = 8 arr.length= 64 >>> All running times: [539, 413, 444, 444, 457, 444, 456]
par = 8 arr.length= 256 >>> All running times: [398, 527, 514, 529, 445, 441, 445]
par = 8 arr.length= 1024 >>> All running times: [419, 507, 477, 422, 412, 452, 396]
par = 8 arr.length= 4096 >>> All running times: [316, 282, 250, 232, 242, 229, 238]
par = 8 arr.length= 16384 >>> All running times: [316, 207, 209, 212, 208, 208, 208]
par = 8 arr.length= 65536 >>> All running times: [211, 211, 208, 208, 208, 291, 206]
par = 8 arr.length= 262144 >>> All running times: [366, 210, 210, 210, 210, 209, 211]
par = 8 arr.length= 1048576 >>> All running times: [296, 211, 215, 216, 213, 211, 211]

Si mueves la matriz dentro del hilo obtienes

par = 8 arr.length= 64 >>> All running times: [225, 151, 151, 150, 152, 153, 152]
par = 8 arr.length= 256 >>> All running times: [155, 151, 151, 151, 151, 151, 155]
par = 8 arr.length= 1024 >>> All running times: [153, 152, 151, 151, 151, 155, 152]
par = 8 arr.length= 4096 >>> All running times: [155, 156, 151, 152, 151, 155, 155]
par = 8 arr.length= 16384 >>> All running times: [154, 157, 152, 152, 158, 153, 153]
par = 8 arr.length= 65536 >>> All running times: [155, 157, 152, 184, 181, 154, 153]
par = 8 arr.length= 262144 >>> All running times: [240, 159, 166, 151, 172, 154, 160]
par = 8 arr.length= 1048576 >>> All running times: [165, 162, 163, 162, 163, 162, 163]

Apague la tabla con -XX:-UseTLAB y el mismo código le da a usted

par = 8 arr.length= 64 >>> All running times: [608, 467, 467, 457, 468, 461, 428]
par = 8 arr.length= 256 >>> All running times: [437, 437, 522, 512, 522, 369, 535]
par = 8 arr.length= 1024 >>> All running times: [394, 395, 475, 525, 470, 440, 478]
par = 8 arr.length= 4096 >>> All running times: [347, 215, 238, 226, 236, 204, 271]
par = 8 arr.length= 16384 >>> All running times: [291, 157, 178, 151, 150, 151, 152]
par = 8 arr.length= 65536 >>> All running times: [163, 152, 162, 151, 159, 159, 154]
par = 8 arr.length= 262144 >>> All running times: [164, 172, 152, 169, 160, 161, 160]
par = 8 arr.length= 1048576 >>> All running times: [295, 153, 164, 153, 166, 154, 163]

Answer 2

Solución

Ejecute la JVM con el -XX:+UseCondCardMark , disponible solo en JDK7. Esto resuelve el problema.

Explicación

Esencialmente, la mayoría de los entornos de pila administrada utilizan tablas de tarjetas para marcar las áreas de memoria en las que se produjeron las escrituras. Dichas áreas de memoria están marcadas como sucias en la tabla de cartas una vez que ocurre la escritura. Esta información es necesaria para la recolección de basura: no es necesario escanear las referencias de las áreas de memoria no sucias. Una tarjeta es un bloque de memoria contiguo, típicamente 512 bytes. Por lo general, una tabla de cartas tiene 1 byte para cada tarjeta: si se establece este byte, la tarjeta está sucia. Esto significa que una tabla de tarjetas con 64 bytes cubre 64 * 512 bytes de memoria. Y por lo general, el tamaño de la línea de caché hoy es de 64 bytes.

Por lo tanto, cada vez que se produce una escritura en un campo de objeto, el byte de la tarjeta correspondiente en la tabla de la tarjeta debe estar sucio. Una optimización útil en programas de un solo hilo es hacer esto simplemente marcando el byte relevante - hacer una escritura cada vez. Una alternativa de comprobar primero si el byte está establecido y una escritura condicional requiere una lectura adicional y un salto condicional, que es un poco más lento.

Sin embargo, esta optimización puede ser catastrófica en el caso de que haya múltiples procesadores escribiendo en la memoria, ya que las tarjetas vecinas que se escriben requieren una escritura en los bytes vecinos en la tabla de tarjetas. Por lo tanto, el área de memoria en la que se está escribiendo (la entrada en la matriz anterior) no está en la misma línea de caché, que es la causa habitual de la contención de memoria. La verdadera razón es que los bytes sucios que se escriben están en la misma línea de caché.

Lo que hace el indicador anterior es: implementa la escritura de bytes sucios de la tabla de la tarjeta al verificar primero si el byte ya está establecido, y configurarlo solo si no lo está. De esta manera, la contención de la memoria ocurre solo durante la primera escritura en esa tarjeta; después de eso, solo se producen lecturas en esa línea de caché. Como la línea de caché solo se lee, se puede replicar en varios procesadores y no tienen que sincronizarse para leerlo.

He observado que esta bandera aumenta el tiempo de ejecución en un 15-20% en el caso de 1 hilo.

La -XX:+UseCondCardMark se explica en esta publicación de blog y en este informe de error .

La discusión relevante de la lista de correo de concurrencia: Asignación de matrices y acceso en la JVM .