2012-03-22 16 views
5

¿Alguien tiene una lista de estimadores de regla aproximada para las diversas estructuras de datos? p.ej.Java: Estimaciones de la memoria de la estructura de datos

  • matrices
  • Listas
  • HashMaps
  • LinkedLists

Recuerdo haber visto algunos de estos cálculos arrojados alrededor en varios lugares, pero me parece que no puede encontrar uno ahora mismo.

Sé que es en realidad increíblemente complicado, especialmente para cosas como HashMaps, pero estoy buscando algo realmente difícil, como:

Memory(HashMap) = fixedOverhead + variableOverhead * tableSize + A*numKeys + B*numValues + Memory(allKeys) + Memory(allValues) 

por supuesto que va a variar mucho dependiendo de esto y eso, pero incluso una estimación aproximada dentro de un factor de 2 sería inmensamente útil.

+0

Sé que ya he respondido eso varias veces, pero ni siquiera puedo encontrar mis propias publicaciones. Esta es la versión realmente corta e incompleta de la zona activa: cada objeto tiene 2 palabras de sobrecarga y 8 bytes de alineación. las matrices tienen 4 bytes adicionales para el tamaño. El tamaño de referencia depende del bitness de JVM, pero existen oops comprimidos para heaps <32 gb en sistemas de 64 bits. – Voo

+0

Me pregunto si visualvm podría hacer esto por ti ... hay un generador de perfiles de memoria, pero nunca lo he usado. –

+0

No he podido encontrar tus respuestas para ello tampoco = D Si puedes encontrar una de tus respuestas anteriores que cubra esto, sería increíble. –

Respuesta

0

Esto es bastante aproximado, pero estas estimaciones deberían ser correctas. Estos son para las estructuras de datos básicas sin incluir variables de longitud o cualquier otro accesorio que tienda a ser incluido en Java.

donde tipoDatos es el tipo de datos que se almacenan

Array: (length n) 
    n*sizeOf(dataType) 

LinkedList: 
    n*(sizeOf(dataType)+sizeOf(pointer))+sizeOf(pointer[head pointer]) 

List: 
    Array-backed=SpaceEfficiency(Array) 
    LinkedList-backed=SpaceEfficiency(LinkedList) 

HashMap: with v values, k keys 
    v*sizeOf(valueDataType) 

Tree: k-way tree with n nodes 
    n*(sizeOf(nodeDataType)+(k*sizeOf(pointer)))+sizeOf(pointer[head pointer]) 

Graph: e edges, v vertices 
    AdjacencyList: 
     at most: v*((v*sizeOf(vertexDataType))+(e*sizeOf(pointer))) fully connected graph 
     at least: v*sizeOf(vertexDataType) disconnected graph 
    AdjacencyMatrix: 
     v^2*sizeOf(int) 
+0

Eso es útil, pero sé cómo analizar teóricamente esto también =). Son las constantes que me interesan: ¿qué (en bytes) es la sobrecarga por artículo en una matriz? en una lista enlazada? en un HashMap? ¿Cuál es la sobrecarga fija? Me gustaría algo un poco más detallado que esto, que es una notación asintótica sin ninguna de las constantes. –

+0

Estoy confundido sobre cómo todo lo que determinemos teóricamente es incluso un problema. Entonces, me refiero a que debería haber * no * gastos generales por artículo en una matriz, ¿verdad? la sobrecarga por artículo en una lista vinculada es solo la del puntero al siguiente nodo, la sobrecarga en un HashMap no existe (excepto por el espacio en la memoria para almacenar el código para hacer el algoritmo hash) porque es solo una matriz. ¿Estás buscando algo aún más específico que esto? Todo lo que se vuelve más específico es el resultado de las opciones de implementación de Java. ¿O es eso lo que estabas buscando? Lo encuentro bastante interesante: p – Drew

+0

El OP pregunta sobre las opciones de implementación de Java, @Mako. –

2

Esta tabla es bastante exhaustiva y trata con precisión las opciones de implementación de JDK medidas en bytes por entrada/elemento. Si desea hacerlo en su propia máquina, si está ejecutando en una máquina diferente, tal vez, este sitio de Google Code le permitirá descargar su fuente. http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures

0

Aquí es un programa simple, que solo consume RAM:

import java.util.*; 
/** 
    RamInit (c) GPLv3 

    @author Stefan Wagner 
    @date Do 22. Mär 08:40:40 CET 2012 

*/ 
public class RamInit 
{ 
    private java.lang.Object consumer; 

    public RamInit (char type, int size) 
    { 
     switch (type) 
     { 
      case 'a': Integer [] ai = new Integer [size]; 
       for (int i = 0; i < size; ++i) 
        ai[i] = i; 
       consumer = ai; 
       break; 
      case 'l': List<Integer> li = new ArrayList<Integer>(); 
       for (int i = 0; i < size; ++i) 
        li.add (i); 
       consumer = li; 
       break; 
      case 'h': HashMap <Integer, Integer> hm = new HashMap <Integer, Integer>(); 
       for (int i = 0; i < size; ++i) 
        hm.put (i, size - i); 
       consumer = hm; 
       break; 
      case 'L': LinkedList <Integer> ll = new LinkedList <Integer>(); 
       for (int i = 0; i < size; ++i) 
        ll.add (i);  
       consumer = ll;   
       break; 
      default: System.err.println ("invalid: " + type); 
     } 
    } 

    public static void main (String args[]) 
    { 
     char type = 'a'; 
     int size = 1000000; // 1M 
     if (args.length == 2) 
     { 
      type = args[0].charAt (0); 
      size = Integer.parseInt (args[1]); 
     } 
     try { 
      new RamInit (type, size); 
     } 
     catch (OutOfMemoryError oome) 
     { 
      System.exit (1); 
     } 
    } 
} 

Y aquí es un script muy simple para probarlo:

#!/bin/bash 

iterProg() { 
ram=$1 
maxram=$2 
typ=$3 
size=$4 
# echo java -Xmx${ram}M RamInit $typ $((size*1000*1000)) 
echo -n "." 
java -Xmx${ram}M RamInit $typ $((size*1000*1000)) && echo -en "\n"$typ $size ${ram}M || { 
    if (($ram==$maxram)) 
    then 
     # echo "fail" 
     return 
    else 
     iterProg $((ram+1)) $maxram $typ $size 
    fi 
    } 
} 

# try from 16 MB to 256 
for typ in {a,l,h,L}; do 
    for size in {1,2,4}; do 
    iterProg $((size*17+1)) 256 $typ $size 
    done 
done 

Es un iterador primitiva y debe ser reemplazado por algo más sofisticado, por ejemplo, si necesita 37 MB para llamar a RamInit con Collection a y elementos de 1M, debe comenzar por elementos de 2M con más de eso.

Y debe elegir los pasos en una búsqueda binaria, por ejemplo, si 20M es demasiado menor, compruebe 128, luego (20 + 128)/2, luego la media de eso, dependiendo del éxito o fracaso con el límite inferior o el límite superior.

Dado que un HashMap almacena 2 Ints por elemento, podría comenzar con aproximadamente el doble de List/Array/Vector. Sin embargo - veces vuela como una flecha, y al escribir, el resultado ha terminado:

bash iterRamFind.sh 
.. 
a 1 19M..... 
a 2 39M............... 
a 4 83M.. 
l 1 19M....... 
l 2 41M....................... 
l 4 91M.............................................. 
h 1 63M............................................................................................. 
h 2 127M........................................................................................................................................................................................... 
h 4 255M...................... 
L 1 39M................................................. 
L 2 83M............................................................................................... 
L 4 163 

El valor 17 explica a sí misma a partir de primeros experimentos. Como podemos ver, el tamaño aumenta de manera casi lineal.

Modificar el código para comprobar la influencia que utiliza Longs, depende de ustedes - supongo que va a terminar con un factor de 2.

0

En Infoq, there is a presentation InfoQ-11-nov-jvmperformance.mp3 de una Trabajador en twitter: Pdf-slides, Audio: mp3 y Video.

Trata mucho sobre colecciones y otros detalles del tamaño de los objetos en la JVM.

Cuestiones relacionadas