2012-03-22 13 views
5

Qualcuno ha un elenco di stimatori approssimativi per le varie strutture di dati? per esempio.Java: stime della memoria della struttura dei dati

  • Array
  • liste
  • HashMaps
  • LinkedLists

Ricordo di aver visto alcune di queste stime gettati in giro in vari luoghi, ma io non riesco a trovare uno adesso.

So che è in realtà incredibilmente complicato, soprattutto per le cose come HashMaps, ma sto cercando qualcosa di davvero grezzi, come:

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

naturalmente che sarà variano molto a seconda di ciò e questo, ma anche una stima approssimativa di un fattore-di-2 sarebbe immensamente utile.

+0

So che ho già risposto diverse volte ma non riesco nemmeno a trovare i miei post per questo. Ecco la versione molto breve e incompleta per l'hotspot: Ogni oggetto ha 2 parole in testa e 8 byte allineati. gli array hanno un 4 byte aggiuntivo per la dimensione. Le dimensioni di riferimento dipendono da JVM bitness, ma esistono oops compressi per heap <32 gb su sistemi a 64 bit. – Voo

+0

Mi chiedo se visualvm potrebbe fare questo per te ... c'è un profiler di memoria, ma non l'ho mai usato. –

+0

Non sono riuscito a trovare le risposte per questo = D Se riesci a trovare una delle tue vecchie risposte che copre questo sarebbe fantastico. –

risposta

0

Questo è piuttosto approssimativo, ma queste stime dovrebbero essere corrette. Questi sono per le strutture di dati bare-bones senza includere variabili di lunghezza o altri extra che tendono ad essere inclusi in Java.

dove dataType è il tipo di dati che vengono memorizzati

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

Questo è utile ma so come analizzare teoricamente anche questa roba =). Sono le costanti a cui sono interessato: cosa (in byte) è il sovraccarico per articolo in un array? in una lista collegata? in una HashMap? Qual è l'overhead fisso? Mi piacerebbe qualcosa di leggermente più dettagliato di questo, che è in effetti una notazione asintotica senza nessuna delle costanti. –

+0

Sono confuso su come tutto tranne quello che determiniamo teoricamente sia anche un problema. Quindi intendo che dovrebbe esserci * no * overhead per articolo in un array giusto? il sovraccarico per elemento in una lista collegata è solo quello del puntatore al nodo successivo, il sovraccarico in una HashMap è inesistente (tranne lo spazio in memoria per memorizzare il codice per eseguire l'algoritmo di hash) perché è solo un array. Stai cercando qualcosa di ancora più specifico di questo? Tutto ciò che diventa più specifico è il risultato delle scelte di implementazione di Java. O è quello che stavi cercando? Sto trovando questo piuttosto interessante: p – Drew

+0

L'OP sta chiedendo le scelte di implementazione di Java, @Mako. –

0

Ecco un semplice programma, che ha appena consuma 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); 
     } 
    } 
} 

E qui è uno script molto semplice per provarlo:

#!/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 

È un iteratore primitivo e deve essere sostituito da qualcosa di più sofisticato - per esempio se hai bisogno di 37MB per chiamare RamInit con gli elementi Collection a e 1M, dovresti iniziare per elementi 2M con qualcosa in più.

E dovresti scegliere i passaggi in una ricerca binaria, ad esempio se 20M è troppo basso, verifica 128, quindi (20 + 128)/2, quindi la media di quello, a seconda del successo o dell'errore con il limite inferiore o il limite superiore.

Poiché una HashMap memorizza 2 Ints per elemento, potrebbe iniziare con la dimensione approssimativa di Lista/Matrice/Vettore. Tuttavia - tempo vola come una freccia, e durante la scrittura, il risultato è finito:

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 

Il valore 17 si spiega da primi esperimenti. Come possiamo vedere, le dimensioni aumentano in modo quasi lineare.

Modificare il codice per verificare l'influenza che si utilizza Longs, spetta a voi - Credo che si finirà con un fattore di 2.

0

On Infoq, there is a presentation InfoQ-11-Nov-jvmperformance.mp3 da un worker su twitter: diapositive Pdf, Audio: mp3 e video.

Si occupa molto delle raccolte e di altri dettagli delle dimensioni degli oggetti nella JVM.

Problemi correlati