studio - matriz dinamica java

¿En qué punto vale la pena reutilizar las matrices en Java?

Question

¿Qué tan grande debe ser un buffer en Java antes de que valga la pena reutilizarlo?

O, dicho de otra forma: puedo asignar, usar y descartar objetos byte [] en repetidas ocasiones O ejecutar un grupo para conservarlos y reutilizarlos. Podría asignar una gran cantidad de pequeños búferes que se descartan a menudo, o unos pocos grandes que no se descartan. ¿En qué tamaño es más barato agruparlos que reasignarlos, y cómo se comparan las pequeñas asignaciones con las grandes?

EDITAR:

Ok, parámetros específicos. Digamos una CPU Intel Core 2 Duo, la última versión de VM para OS de su elección. Esta pregunta no es tan vaga como parece ... un pequeño código y un gráfico podrían responderla.

EDIT2:

Has publicado muchas buenas reglas generales y discusiones, pero la pregunta realmente pregunta por los números. ¡Publiquelos (y codifique también)! La teoría es genial, pero la prueba son los números. No importa si los resultados varían de un sistema a otro, solo estoy buscando una estimación aproximada (orden de magnitud). Nadie parece saber si la diferencia de rendimiento será un factor de 1.1, 2, 10 o 100+, y esto es algo que importa. Es importante para cualquier código Java trabajar con grandes arreglos: redes, bioinformática, etc.

Sugerencias para obtener un buen punto de referencia:

1. Calentar el código antes de ejecutarlo en el punto de referencia. Todos los métodos deben llamarse al menos 1000 10000 veces para obtener la optimización JIT completa.
2. Asegúrese de que los métodos comparativos se ejecuten durante al menos 1 10 segundos y use System.nanotime si es posible, para obtener sincronizaciones precisas.
3. Ejecutar benchmark en un sistema que solo ejecuta aplicaciones mínimas
4. Ejecute el benchmark 3-5 veces e informe todo el tiempo, para que veamos qué tan consistente es.

Sé que esta es una pregunta vaga y algo exigente. Verificará esta pregunta regularmente, y las respuestas recibirán comentarios y se clasificarán constantemente. Las respuestas flojas no lo harán (ver abajo los criterios) Si no tengo respuestas completas, adjuntaré una recompensa. De todos modos, podría recompensar una muy buena respuesta con un poco más.

Lo que sé (y no necesito repetir):

• La asignación de memoria Java y el GC son rápidos y cada vez más rápidos.
• La agrupación de objetos solía ser una buena optimización, pero ahora perjudica el rendimiento la mayor parte del tiempo.
• La agrupación de objetos "normalmente no es una buena idea a menos que los objetos sean caros de crear". Yadda yadda.

Lo que NO sé

• ¿Qué tan rápido debo esperar que las asignaciones de memoria se ejecuten (MB / s) en una CPU estándar moderna?
• ¿Cómo afecta el tamaño de la asignación la tasa de asignación?
• ¿Cuál es el punto de equilibrio para el número / tamaño de las asignaciones frente a la reutilización en un grupo?

Rutas a una respuesta ACEPTABLE (cuantos más mejor):

• Un documento técnico reciente que muestra las cifras de asignación y GC en las CPU modernas (reciente como el año pasado, JVM 1.6 o posterior)
• Código para un micro-benchmark conciso y correcto que puedo ejecutar
• Explicación de cómo y por qué las asignaciones afectan el rendimiento
• Ejemplos del mundo real / anécdotas de probar este tipo de optimización

El contexto:

Estoy trabajando en una biblioteca que agrega soporte de compresión LZF a Java. Esta biblioteca amplía las clases H2 DBMS LZF, agregando niveles de compresión adicionales (más compresión) y compatibilidad con las secuencias de bytes de la biblioteca C LZF. Una de las cosas en las que estoy pensando es si vale la pena intentar reutilizar los almacenamientos intermedios de tamaño fijo utilizados para comprimir / descomprimir flujos. Los almacenamientos intermedios pueden ser ~ 8 kB, o ~ 32 kB, y en la versión original son ~ 128 kB. Los almacenamientos intermedios se pueden asignar una o más veces por transmisión. Estoy tratando de descubrir cómo quiero manejar los almacenamientos intermedios para obtener el mejor rendimiento, con la vista puesta en el multihilo potencial en el futuro.

Sí, la biblioteca SERÁ lanzada como fuente abierta si alguien está interesado en usar esto.

Answer 1

Creo que la respuesta que necesita está relacionada con el "orden" (medición de espacio, no de tiempo) del algoritmo.

Copiar archivo de ejemplo

Por ejemplo, si quiere copiar un archivo, necesita leerlo desde una salida de entrada y escribir en una salida de salida. El orden TIME es O (n) porque el tiempo será proporcional al tamaño del archivo. Pero el orden SPACE será O (1) porque el programa que necesitarás ocupará una cantidad fija de memoria (solo necesitarás un buffer fijo). En este caso, está claro que es conveniente reutilizar el mismo búfer al que creó una instancia al comienzo del programa.

Relacione la política de almacenamiento intermedio con su estructura de ejecución de algoritmo

Por supuesto, si su algoritmo necesita un suministro interminable de búferes y cada búfer tiene un tamaño diferente, probablemente no pueda volver a utilizarlos. Pero te da algunas pistas:

• intenta arreglar el tamaño de los buffers (incluso sacrificando un poco de memoria).
• Intenta ver cuál es la estructura de la ejecución: por ejemplo, si estás utilizando Algoritmo de Algoritmo y tus búferes están relacionados con cada nodo, tal vez solo necesites O (log n) búferes ... para que puedas hacer una estimación educada del espacio requerido.
• Además, si necesita diferentes almacenamientos intermedios pero puede organizar las cosas para compartir diferentes segmentos de la misma matriz ... tal vez sea una mejor solución.
• Cuando libera un búfer, puede agregarlo a un grupo de búferes. Ese grupo puede ser un montón ordenado por los criterios de "ajuste" (los almacenamientos intermedios que más se ajustan deben ser los primeros).

Lo que trato de decir es que no hay una respuesta fija. Si creó una instancia de algo que puede reutilizar ... probablemente sea mejor reutilizarlo. La parte difícil es encontrar la forma de hacerlo sin incurrir en gastos generales de administración del búfer. Aquí es cuando el análisis del algoritmo es útil.

Espero eso ayude... :)

Answer 2

Cuando es más grande que el espacio joven.

Si su matriz es más grande que el espacio joven local de subprocesos, se asigna directamente en el espacio antiguo. La recolección de basura en el viejo espacio es mucho más lenta que en el espacio joven. Entonces, si su matriz es más grande que el espacio joven, podría tener sentido reutilizarla.

En mi máquina, 32kb excede el espacio joven. Entonces tendría sentido reutilizarlo.

Answer 3

Encontré este hilo y, como estaba implementando un Floyd-Warshall conectividad de pares Floyd-Warshall en un gráfico con mil vértices, traté de implementarlo en ambos sentidos (reutilizando matrices o creando nuevas) y verificando el tiempo transcurrido .

Para el cálculo necesito 1000 matrices diferentes de tamaño 1000 x 1000, por lo que parece una prueba decente.

Mi sistema es Ubuntu Linux con la siguiente máquina virtual.

java version "1.7.0_65"
Java(TM) SE Runtime Environment (build 1.7.0_65-b17)
Java HotSpot(TM) 64-Bit Server VM (build 24.65-b04, mixed mode)

La reutilización de matrices fue aproximadamente un 10% más lenta (tiempo promedio de ejecución en 5 ejecuciones de 17354 ms frente a 15708 ms. No sé si aún sería más rápido en caso de que la matriz fuera mucho más grande.

Aquí está el código relevante:

private void computeSolutionCreatingNewMatrices() {
    computeBaseCase();
    smallest = Integer.MAX_VALUE;
    for (int k = 1; k <= nVertices; k++) {
        current = new int[nVertices + 1][nVertices + 1];
        for (int i = 1; i <= nVertices; i++) {
            for (int j = 1; j <= nVertices; j++) {
                if (previous[i][k] != Integer.MAX_VALUE && previous[k][j] != Integer.MAX_VALUE) {
                    current[i][j] = Math.min(previous[i][j], previous[i][k] + previous[k][j]);
                } else {
                    current[i][j] = previous[i][j];
                }
                smallest = Math.min(smallest, current[i][j]);
            }
        }
        previous = current;
    }
}

private void computeSolutionReusingMatrices() {
    computeBaseCase();
    current = new int[nVertices + 1][nVertices + 1];
    smallest = Integer.MAX_VALUE;
    for (int k = 1; k <= nVertices; k++) {            
        for (int i = 1; i <= nVertices; i++) {
            for (int j = 1; j <= nVertices; j++) {
                if (previous[i][k] != Integer.MAX_VALUE && previous[k][j] != Integer.MAX_VALUE) {
                    current[i][j] = Math.min(previous[i][j], previous[i][k] + previous[k][j]);
                } else {
                    current[i][j] = previous[i][j];
                }
                smallest = Math.min(smallest, current[i][j]);
            }
        }
        matrixCopy(current, previous);
    }
}

private void matrixCopy(int[][] source, int[][] destination) {
    assert source.length == destination.length : "matrix sizes must be the same";
    for (int i = 0; i < source.length; i++) {
        assert source[i].length == destination[i].length : "matrix sizes must be the same";
        System.arraycopy(source[i], 0, destination[i], 0, source[i].length);
    }        
}

Answer 4

Has olvidado mencionar algo sobre la seguridad de los hilos. Si varios subprocesos lo reutilizarán, tendrá que preocuparse por la sincronización.

Answer 5

Más importante que el tamaño del búfer es el número de objetos asignados y la memoria total asignada.

1. ¿El uso de memoria es un problema en absoluto? Si es una aplicación pequeña, puede que no valga la pena preocuparse.

La ventaja real de la puesta en común es evitar la fragmentación de la memoria. La sobrecarga para asignar / liberar memoria es pequeña, pero la desventaja es que si asigna repetidamente muchos objetos de muchos tamaños diferentes, la memoria se vuelve más fragmentada. El uso de un grupo evita la fragmentación.

Answer 6

Mirando un micro benchmark (código debajo) no hay diferencia apreciable en el tiempo en mi máquina sin importar el tamaño y las veces que se usa el arreglo (no estoy publicando los tiempos, puede ejecutarlo fácilmente en su máquina :-). Sospecho que esto se debe a que la basura está viva por tan poco tiempo que no hay mucho que hacer para la limpieza. La asignación de matrices debería ser una llamada a calloc o malloc / memset. Dependiendo de la CPU, esta será una operación muy rápida. Si las matrices sobrevivieron durante un tiempo más largo para pasar el área GC inicial (el vivero), entonces el tiempo para el que asignó varias matrices podría demorar un poco más.

código:

import java.util.Random;

public class Main
{
    public static void main(String[] args) 
    {
        final int size;
        final int times;

        size  = 1024 * 128;
        times = 100;

        // uncomment only one of the ones below for each run
        test(new NewTester(size), times);   
//        test(new ReuseTester(size), times); 
    }

    private static void test(final Tester tester, final int times)
    {
        final long total;

        // warmup
        testIt(tester, 1000);
        total = testIt(tester, times);

        System.out.println("took:   " + total);
    }

    private static long testIt(final Tester tester, final int times)
    {
        long total;

        total = 0;

        for(int i = 0; i < times; i++)
        {
            final long start;
            final long end;
            final int value;

            start = System.nanoTime();
            value = tester.run();
            end   = System.nanoTime();
            total += (end - start);

            // make sure the value is used so the VM cannot optimize too much
            System.out.println(value);
        }

        return (total);
    }
}

interface Tester
{
    int run();
}

abstract class AbstractTester
    implements Tester
{
    protected final Random random;

    {
        random = new Random(0);
    }

    public final int run()
    {
        int value;

        value = 0;

        // make sure the random number generater always has the same work to do
        random.setSeed(0);

        // make sure that we have something to return so the VM cannot optimize the code out of existence.
        value += doRun();

        return (value);
    }

    protected abstract int doRun();
}

class ReuseTester
    extends AbstractTester
{
    private final int[] array;

    ReuseTester(final int size)
    {
        array = new int[size];
    }

    public int doRun()
    {
        final int size;

        // make sure the lookup of the array.length happens once
        size = array.length;

        for(int i = 0; i < size; i++)
        {
            array[i] = random.nextInt();
        }

        return (array[size - 1]);
    }
}

class NewTester
    extends AbstractTester
{
    private int[] array;
    private final int length;

    NewTester(final int size)
    {
        length = size;
    }

    public int doRun()
    {
        final int   size;

        // make sure the lookup of the length happens once
        size = length;
        array = new int[size];

        for(int i = 0; i < size; i++)
        {
            array[i] = random.nextInt();
        }

        return (array[size - 1]);
    }
}

Answer 7

Olvidé que este es un sistema de memoria administrada.

En realidad, es probable que tengas una mentalidad equivocada. La forma adecuada de determinar cuándo es útil depende de la aplicación, el sistema en el que se ejecuta y el patrón de uso del usuario.

En otras palabras, solo haga un perfil del sistema, determine cuánto tiempo se está gastando en recolección de basura como un porcentaje del tiempo total de la aplicación en una sesión típica, y vea si vale la pena optimizar eso.

Probablemente descubrirás que ni siquiera se llama gc. Así que escribir código para optimizar esto sería una completa pérdida de tiempo.

con el gran espacio de memoria actual, sospecho que el 90% del tiempo no vale la pena hacerlo. Realmente no se puede determinar esto en función de los parámetros: es demasiado complejo. Solo perfil: fácil y preciso.

Answer 8

Respuesta corta: No almacenar en búfer.

Las razones son las siguientes:

• No lo optimices hasta que se convierta en un cuello de botella
• Si lo recicla, la sobrecarga de la gestión de la piscina será otro cuello de botella
• Intenta confiar en el JIT. En la última JVM, su matriz puede asignarse en STACK en lugar de HEAP.
• Créanme, los JRE generalmente los manejan más rápido y mejor que ustedes.
• Mantenlo simple, para facilitar la lectura y la depuración

Cuando deberías reciclar un objeto:

• solo si es pesado El tamaño de la memoria no lo hará pesado, pero sí lo son los recursos nativos y el ciclo de la CPU, cuyo costo finaliza y finaliza el ciclo de la CPU.
• Es posible que desee reciclarlos si son "ByteBuffer" en lugar de bytes []

Answer 9

Si quieres una respuesta simple, es que no hay una respuesta simple. Ninguna cantidad de respuestas de llamadas (y por implicación personas) "perezosas" va a ayudar.

¿Qué tan rápido debo esperar que las asignaciones de memoria se ejecuten (MB / s) en una CPU estándar moderna?

A la velocidad a la que la JVM puede cero memoria, suponiendo que la asignación no desencadena una recolección de basura. Si desencadena la recolección de basura, es imposible predecir sin saber qué algoritmo de GC se usa, el tamaño de pila y otros parámetros, y un análisis del conjunto de objetos no contaminantes de la aplicación a lo largo de la vida de la aplicación.

¿Cómo afecta el tamaño de la asignación la tasa de asignación?

Véase más arriba.

¿Cuál es el punto de equilibrio para el número / tamaño de las asignaciones frente a la reutilización en un grupo?

Si quieres una respuesta simple, es que no hay una respuesta simple.

La regla de oro es que cuanto más grande sea tu montón (hasta la cantidad de memoria física disponible), menor será el costo amortizado de GC para un objeto de basura. Con un recolector de basura de copia rápida, el costo amortizado de liberar un objeto de basura se acerca a cero a medida que el montón se hace más grande. El costo del GC en realidad está determinado por (en términos simplistas) el número y el tamaño de los objetos que no son basura con los que el GC tiene que lidiar.

Bajo la suposición de que su montón es grande, el costo del ciclo de vida de asignar y GC un objeto grande (en un ciclo de GC) se acerca al costo de poner a cero la memoria cuando se asigna el objeto.

EDITAR : Si todo lo que quiere son números simples, escriba una aplicación simple que asigne y descarte grandes almacenamientos intermedios y ejecútelo en su máquina con varios parámetros de GC y de montón y vea qué sucede. Pero tenga en cuenta que esto no le dará una respuesta realista porque los costos reales de GC dependen de los objetos que no son basura de una aplicación.

No voy a escribir un punto de referencia para ti porque sé que te daría respuestas falsas.

EDICION 2 : En respuesta a los comentarios de OP.

Por lo tanto, debería esperar que las asignaciones se ejecuten tan rápido como System.arraycopy, o un bucle de inicialización de matriz completamente JIT (aproximadamente 1 GB / s en mi último banco, pero dudo del resultado).

Teóricamente sí. En la práctica, es difícil medir de una manera que separe los costos de asignación de los costos de GC.

Por tamaño de pila, ¿está diciendo que asignar una mayor cantidad de memoria para el uso de JVM realmente reducirá el rendimiento?

No, estoy diciendo que es probable que aumente el rendimiento. Significativamente. (Siempre que no se encuentre con efectos de memoria virtual a nivel de sistema operativo).

Las asignaciones son solo para matrices, y casi todo lo demás en mi código se ejecuta en la pila. Debe simplificar la medición y predicción del rendimiento.

Tal vez. Francamente, creo que no obtendrás mucha mejoría al reciclar los buffers.

Pero si tiene la intención de seguir por esta ruta, cree una interfaz de agrupación de almacenamiento intermedio con dos implementaciones. El primero es un grupo de búferes real sin hilos que recicla búferes. El segundo es el pool ficticio que simplemente asigna un nuevo buffer cada vez que se llama alloc , y trata como un no-op. Finalmente, permita que el desarrollador de la aplicación elija entre las implementaciones de grupo a través de un método setBufferPool y / o parámetros de constructor y / o propiedades de configuración de tiempo de ejecución. La aplicación también debería poder proporcionar una clase / instancia de grupo de búferes de su propia creación.

Answer 10

Tenga en cuenta que los efectos de caché probablemente serán más un problema que el costo de "new int [size]" y su correspondiente colección. Reutilizar búferes es una buena idea si tiene una buena localidad temporal. La reasignación del búfer en lugar de reutilizarlo significa que puede obtener un trozo diferente de memoria cada vez. Como otros mencionaron, esto es especialmente cierto cuando tus buffers no encajan en la generación joven.

Si asigna pero luego no usa todo el búfer, también vale la pena volver a utilizarlo ya que no pierde el tiempo en poner a cero la memoria que nunca usa.

Answer 11

Una respuesta desde una dirección completamente diferente: deja que el usuario de tu biblioteca decida.

En última instancia, por optimizado que sea tu biblioteca, solo será un componente de una aplicación más grande. Y si esa aplicación más grande hace un uso poco frecuente de su biblioteca, no hay ninguna razón por la que deba pagar para mantener un conjunto de almacenamientos intermedios, incluso si ese grupo tiene solo unos cientos de kilobytes.

Por lo tanto, cree su mecanismo de agrupamiento como una interfaz y, basándose en algún parámetro de configuración, seleccione la implementación que usa su biblioteca. Establezca el valor predeterminado para que sea lo que sus pruebas de referencia determinen que es la mejor solución. ¹ Y sí, si usa una interfaz, deberá confiar en que la JVM será lo suficientemente inteligente como para realizar llamadas en línea. ²

(1) Por "punto de referencia", me refiero a un programa de larga duración que ejercita su biblioteca fuera de un generador de perfiles , pasándole una variedad de entradas. Los perfiladores son extremadamente útiles, pero también lo son la medición del rendimiento total después de una hora de reloj de pared. En varias computadoras diferentes con diferentes tamaños de almacenamiento dinámico y varias JVM diferentes, que se ejecutan en modos de uno o varios subprocesos.

(2) Esto puede llevarlo a otra línea de debate sobre el rendimiento relativo de los diversos códigos de operación de invocación .