[JAVA] Limite di elementi nelle collezioni di dati?

[Lim]

Ciao a tutti!

Mi sono da poco scontrato con un problema legato al numero di elementi memorizzabili nelle collezioni di dati in Java.
Consultando la documentazione e anche cercando nei motori di ricerca non ho trovato una risposta.

Vengo al problema:
Vorrei utilizzare un ArrayList (o anche altro, al momento non è poi così importante) per memorizzare centinaia di milioni (arrivando anche ai miliardi) di oggetti. Per fare delle prove, ho scritto poche banali righe di codice del tipo:

ArrayList<MyObject> list=new ArrayList<MyObject>();

int size=100000000;

for (int i=0;i<size;i++){
  
   list.add(new MyObject());
   
}

Sperimentalmente ho verificato che riesco ad istanziare circa 70-80 milioni di oggetti, ma a 90 milioni mi restituisce sempre un'eccezione:

Exception in thread "main" java.lang.reflect.InvocationTargetException
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:601)
at org.eclipse.jdt.internal.jarinjarloader.JarRsrcLoader.main(JarRsrcLoader.java:58)
Caused by: java.lang.OutOfMemoryError: Java heap space
at java.util.Random.<init>(Random.java:122)
at java.util.Random.<init>(Random.java:90)
at Ball.<init>(Ball.java:20)
at testArrayList.exec(testArrayList.java:49)
at testArrayList.main(testArrayList.java:26)


Premetto che ho preventivamente assegnato una dimensione massima per lo heap pari a 63GB, il test infatti viene lanciato su un server con 24 core e 65 GB di ram con Ubuntu server 12.10 e Java 1.7. Ho verificato inoltre quanta memoria viene consumata effettivamente quando si creano 70 milioni di oggetti ed è intorno ai 18GB.

In teoria in letteratura sostengono che il limite di elementi per un ArrayList è dato dal limite dell'int (circa 2 * 10^9 se non erro), ma io mi fermo molto prima!

Qualcuno ha qualche idea? Sto sottovalutando qualche aspetto?

[banryu79]

Ciao Lim.

Per quel che ne so, e per come hai descritto il problema nel tuo post, non credo affatto che dipenda da ArrayList. Non ci sono limiti nel numero di elementi che un ArrayList contiene (a parte il dicorso che hai fatto circa il range di interi rappresentabile dal tipo int usato internamente come contatore).

Il tuo errore è molto chiaro: hai una OutOfMemory!
Come hai fatto i conti per stabilire che 70 milioni di istanze di Ball infilate nell'ArrayList occupano 18 GB? Hai tenuto conto anche dello spazio occupato dalle reference?

Comunque ti consiglio di profilare/analizzare accuratamente la jvm in esecuzione, se puoi da remoto.
Conosci questi tools? -> http://www.oracle.com/webfolder/tech...CMD/index.html

Magari ti tornano utili (e in futuro, se avrai bisogno di chiedere aiuto potrai farlo fornendo dati molto precisi circa lo stato della tua vm nel tuo sistema).

[Lim]

Originariamente inviato da banryu79

Ciao Lim.

Il tuo errore è molto chiaro: hai una OutOfMemory!
Come hai fatto i conti per stabilire che 70 milioni di istanze di Ball infilate nell'ArrayList occupano 18 GB? Hai tenuto conto anche dello spazio occupato dalle reference?

Ho monitorato la situazione con un profiler (VisualVM) e con TOP e sembravano concordare sui 18GB di memoria totale occupata.

Proverò a seguire il tuo consiglio usando i tool che mi hai linkato.
Intanto grazie!

[sottovento]

Dicevi che riesci ad instanziare 70/80 milioni di oggetti prima del out of memory.

Cosa succede se ne istanzi 80 milioni (quindi senza out of memory), e poi riparti instanziandone ancore 80 milioni da inserire in una seconda array list?

E' una prova semplice, basta fare un copy&paste e cambiare il nome della seconda array list.

Cosa ti aspetti da questa prova?
Beh, io mi aspetterei
- se terminasse senza eccezioni, allora c'e' qualche limitazione nella arraylist e potrei pensare ad una struttura dati diversa per aggirare il problema;
- se l'eccezione capita ancora intorno ai 90 milioni di oggetti, controllerei l'allocazione iniziale della heap per java e penserei ad un secondo test...

[Lim]

Originariamente inviato da sottovento

Dicevi che riesci ad instanziare 70/80 milioni di oggetti prima del out of memory.

Cosa succede se ne istanzi 80 milioni (quindi senza out of memory), e poi riparti instanziandone ancore 80 milioni da inserire in una seconda array list?

E' una prova semplice, basta fare un copy&paste e cambiare il nome della seconda array list.

Cosa ti aspetti da questa prova?
Beh, io mi aspetterei
- se terminasse senza eccezioni, allora c'e' qualche limitazione nella arraylist e potrei pensare ad una struttura dati diversa per aggirare il problema;
- se l'eccezione capita ancora intorno ai 90 milioni di oggetti, controllerei l'allocazione iniziale della heap per java e penserei ad un secondo test...

Grazie per l'idea!
Ho fatto come mi hai suggerito e purtroppo si blocca comunque.
Ho utilizzato due ArrayList diverse e più o meno è riuscito a creare oltre gli 80 milioni di oggetti.
Secondo TOP l'occupazione della memoria era intorno ai 20GB totali. Lo Heap era stato settato a 63GB...

[sottovento]

Si blocca comunque nel senso che la prima serie di allocazioni e' ok mentre la seconda non e' portata a termine, giusto?
Beh, quanto meno sappiamo che non e' dovuto a limitazioni della ArrayList (si, non e' una consolazione).

Ah! Domanda stupida: stai creando un'applicazione, giusto? Non applet/servlet/...

Hai provato a chiedere a Java quanta memoria ha a disposizione, quanta libera, ...?

Runtime runtime = Runtime.getRuntime();  
  
long maxMemory = runtime.maxMemory();  
long allocatedMemory = runtime.totalMemory();  
long freeMemory = runtime.freeMemory();  
  
System.out.println("free memory: " + freeMemory / 1024);  
System.out.println("allocated memory: " + allocatedMemory / 1024);  
System.out.println("max memory: " + maxMemory /1024);  
System.out.println("total free memory: " +   (freeMemory + (maxMemory - allocatedMemory)) / 1024);

Potresti mettere queste righe in un metodo e richiamarlo man mano che procedono le allocazioni. Se poi le stampi in formato csv potresti tracciare un grafico e vedere come vanno le cose in maniera semplice. Poi, visti i risultati, potremmo cercare il test successivo

Originariamente inviato da Lim

Grazie per l'idea!
Ho fatto come mi hai suggerito e purtroppo si blocca comunque.
Ho utilizzato due ArrayList diverse e più o meno è riuscito a creare oltre gli 80 milioni di oggetti.
Secondo TOP l'occupazione della memoria era intorno ai 20GB totali. Lo Heap era stato settato a 63GB...

[sottovento]

Che stupido che sono! Dimenticavo una test importante: puoi provare cambiando la dimensione degli oggetti che vai ad allocare?

Qualcosa del genere:

public class Huge
{
    public static void main(String[] args)
    {
        ArrayList<byte[]> vect = new ArrayList<byte[]>();

        for (int i = 0; i < 1000000000; i++)
        {
            byte[] buf = new byte[4000000000];
            vect.add(buf);
        }
    }
}

L'out of memory lo possiamo ottenere non solo quando l'heap e' finita, ma anche quando non possiamo piu' permetterci di tenerci in pancia nuovi riferimenti ad oggetti. Almeno credo

Potresti provare a cambiare la quantita' di memoria che allochi ad ogni botta, e vedere fin dove riesci ad arrivare. Ho l'impressione che sia questo il motivo

[Lim]

Originariamente inviato da sottovento

Che stupido che sono! Dimenticavo una test importante: puoi provare cambiando la dimensione degli oggetti che vai ad allocare?

Qualcosa del genere:

public class Huge
{
    public static void main(String[] args)
    {
        ArrayList<byte[]> vect = new ArrayList<byte[]>();

        for (int i = 0; i < 1000000000; i++)
        {
            byte[] buf = new byte[4000000000];
            vect.add(buf);
        }
    }
}

L'out of memory lo possiamo ottenere non solo quando l'heap e' finita, ma anche quando non possiamo piu' permetterci di tenerci in pancia nuovi riferimenti ad oggetti. Almeno credo

Potresti provare a cambiare la quantita' di memoria che allochi ad ogni botta, e vedere fin dove riesci ad arrivare. Ho l'impressione che sia questo il motivo

Ho fatto questo test, e sono riuscito ad istanziare 2 miliardi di oggetti, dove ogni oggetto è un byte[1000].
Se incremento a byte[10000], ottengo nuovamente un out of memory anche con solo 100000 oggetti.
Ho notato che la massima occupazione di memoria prima di crollare arriva sempre intorno ai 16GB.

Avendo dimostrato che l'ArrayList si comporta bene fino a 2 miliardi di oggetti, il problema resta quello dell'out of memory, ma continuo a non capire come mai...

[sottovento]

e... cosa ti ha detto l'altro test, i.e. quello della memoria libera?

[Lim]

Originariamente inviato da sottovento

e... cosa ti ha detto l'altro test, i.e. quello della memoria libera?

L'altro test, eseguito sui miei oggetti originali ha restituito questi risultati:

Dopo aver creato 70 milioni di oggetti:
free memory: 3310245
allocated memory: 14661888
max memory: 14661888
total free memory: 3310245



Dopo aver creato altri 7 milioni di oggetti (per un totale di 77 milioni):
free memory: 1988232
allocated memory: 14661888
max memory: 14661888
total free memory: 1988232


Dopodiché mi ha restituito la solita eccezione.

[Braccop]

benche' non abbia la risposta al problema buco per dire che anni fa incappai in una cosa simile per poi scoprire che la massima dimensione di heap allocabile da un'applicazione windows 32 bit e' 2GB

benche' qui si parli di linux a 64 bit potrebbe comunque esserci qualche limitazione a livello di processi, thread o cose, comunque una limitazione imposta a priori dal sistema operativo

non e' detto che sia poi questo, ma e' uno spunto per ulteriori indagini

[demos88]

Beh... se continui a caricare in memoria è normale che a un certo punto ti si blocchi, e non dipende dal Java.
Riuscirai ad allocare tutta la ram libera più tutto lo swap...
Hai provato a verificare quanto swap massimo hai?
Il discorso vale sia su windows che linux

[sottovento]

E' davvero strano, oltre che interessante (per me ovviamente, visto che il problema e' tuo ).
Ho provato anche a cercare in rete, ma ho trovato solo banalita'.
Ci sono articoli interessanti come questo http://www.kdgregory.com/index.php?p...va.outOfMemory
che spiegano piu' dettagliatamente l'out of memory, ma non aiuta piu' di tanto nel caso in questione.

Ora purtroppo sono sotto pressione al lavoro a causa di alcuni gravi malfunzionamenti, dopo provo a cercare ancora.
Cmq e' ormai chiaro che l'out of memory non e' solo legato all'esaurimento della heap. Per esempio, nell'articolo di cui sopra viene spiegato come la frammentazione della memoria possa generare questa eccezione.
In effetti, potrebbe essere il tuo caso: all'inizio, quando ti ho suggerito la prova dell'allocazione del buffer mi immaginavo che all'aumentare della dimensione del singolo buffer si potesse allocare piu' memoria, fino alla saturazione.
Questo perche' nella mia ingenuita' pensavo che JVM tenesse traccia delle allocazioni effettuate, per esempio in una lista a dimensione fissa, quindi ci fosse un limite massimo sul numero di oggetti nel sistema, magari calcolato in partenza, in base alla heap disponibile.

In realta' hai avuto il risultato opposto: aumentando la dimensione del singolo oggetto hai ottenuto l'allocazione quantita' di memoria allocata MINORE di quanto hai ottenuto prima, allontanandoti dalla memoria massima disponibile.
Tutto porta a pensare che l'articolo abbia ragione: ci potrebbe essere un problema di frammentazione.

Il problema e'
- dimostrarlo o escluderlo (l'ipotesi fatta e' ancora un po' campata in aria)
- se il problema e' questo, come fare ad evitarlo.

Immagino che ci sia un modo per accedere ai parametri della JVM. Dovra' pur loggare una cosa del genere, o tener traccia della situazione attuale da qualche parte... cerchero' appena ho un momento libero

Originariamente inviato da Lim

L'altro test, eseguito sui miei oggetti originali ha restituito questi risultati:

Dopo aver creato 70 milioni di oggetti:
free memory: 3310245
allocated memory: 14661888
max memory: 14661888
total free memory: 3310245



Dopo aver creato altri 7 milioni di oggetti (per un totale di 77 milioni):
free memory: 1988232
allocated memory: 14661888
max memory: 14661888
total free memory: 1988232


Dopodiché mi ha restituito la solita eccezione.

[sottovento]

Sempre a proposito della frammentazione: l'articolo che ti ho proposto ha una sezione chiamata "OutOfMemoryError When There's Still Heap Memory Available".

Questo mi ha fatto venire in mente una prova semplicissima: potresti rifare le prove che gia' abbiamo effettuato (le tue o quelle suggerite dal sottoscritto) e PREALLOCARE l'ArrayList.
Come sai, c'e' il costruttore
ArrayList(int initialCapacity)
siccome sai gia' quanti elementi ci vuoi inserire, potremmo fare la prova usando questo.

L'idea non e' quella di risolvere il problema (magari!) ma di vedere le differenze di funzionamento rispetto ai casi precedenti. Sperando che ci siano differenze.

[banryu79]

Originariamente inviato da sottovento

Tutto porta a pensare che l'articolo abbia ragione: ci potrebbe essere un problema di frammentazione.

Il problema e'
- dimostrarlo o escluderlo (l'ipotesi fatta e' ancora un po' campata in aria)
- se il problema e' questo, come fare ad evitarlo.

E' una possibilità, ed era venuto in mente anche a me, ma non ci scommetterei.
Solo che fare ipotesi sulle cause del problema che sta esperendo Lim senza avere sottomano la situazione completa (piattaforma, versione e parametri della vm...) è dispendioso in termini di tempo perchè tocca tirare ipotesi alla cieca

Originariamente inviato da sottovento

Immagino che ci sia un modo per accedere ai parametri della JVM. Dovra' pur loggare una cosa del genere, o tener traccia della situazione attuale da qualche parte... cerchero' appena ho un momento libero

Questo potrebbe essere utile.

EDIT:
Per essere chiari, al posto di Lim io punterei a cercare di scovare e capire quale è il limite di RAM allocabile per la specifica implementazione di VM che sto usando, con il dato GC che sta usando, sulla specifica piattaforma che sto usando. Come fare? Per prima cosa uso tutti gli strumenti distrbuiti con il JDK che servono per estrarre tutte queste informazioni. Poi procedo facendo ricerche mirate. Come luoghi papabili personalmente comincerei a cercare sui forum di Oracle dedicati a Java e su stackoverflow, ad esempio.

Aggiungo questo link per Lim, non è direttamente collegato al problema qui esposto, però potrebbe tornargli utile:
http://stackoverflow.com/questions/4...-usage-in-java

[Lim]

Originariamente inviato da sottovento

Sempre a proposito della frammentazione: l'articolo che ti ho proposto ha una sezione chiamata "OutOfMemoryError When There's Still Heap Memory Available".

Questo mi ha fatto venire in mente una prova semplicissima: potresti rifare le prove che gia' abbiamo effettuato (le tue o quelle suggerite dal sottoscritto) e PREALLOCARE l'ArrayList.
Come sai, c'e' il costruttore
ArrayList(int initialCapacity)
siccome sai gia' quanti elementi ci vuoi inserire, potremmo fare la prova usando questo.

L'idea non e' quella di risolvere il problema (magari!) ma di vedere le differenze di funzionamento rispetto ai casi precedenti. Sperando che ci siano differenze.

Grazie a tutti per il supporto. Cercherò di leggermi al più presto gli articoli che mi avete suggerito.

Per quanto riguarda il preallocare l'ArrayList, già lo stavo facendo, tutti i risultati che ho postato riguardavano questa configurazione.


Per rispondere a demos88 invece, ho verificato che non usa swap (lo swap totale è 45GB e non lo usa mai durante l'esecuzione della classe di test)

[sottovento]

Lim
scusa ancora. Questo articolo (https://blogs.oracle.com/jrockit/ent...nted_is_my_ja), anche se un po' datato, presenta una piccola applicazione che potrebbe esserti utile per verificare se il problema e' effettivamente la frammentazione.

Tienici aggiornati, se ti va

Originariamente inviato da Lim

Grazie a tutti per il supporto. Cercherò di leggermi al più presto gli articoli che mi avete suggerito.

Per quanto riguarda il preallocare l'ArrayList, già lo stavo facendo, tutti i risultati che ho postato riguardavano questa configurazione.


Per rispondere a demos88 invece, ho verificato che non usa swap (lo swap totale è 45GB e non lo usa mai durante l'esecuzione della classe di test)

[Lim]

Originariamente inviato da sottovento

Lim
scusa ancora. Questo articolo (https://blogs.oracle.com/jrockit/ent...nted_is_my_ja), anche se un po' datato, presenta una piccola applicazione che potrebbe esserti utile per verificare se il problema e' effettivamente la frammentazione.

Tienici aggiornati, se ti va

Certo che vi terrò aggiornati!

P.S. il link non è completo, puoi rimandarmelo?

[sottovento]

L'indirizzo sembra "tagliato" ma riesco ad accederci cosi' (lo metto fra code tags in modo da evitare che sia modificato dal software del forum):

https://blogs.oracle.com/jrockit/entry/repost_how_fragmented_is_my_ja

[Lim]

Originariamente inviato da sottovento

L'indirizzo sembra "tagliato" ma riesco ad accederci cosi' (lo metto fra code tags in modo da evitare che sia modificato dal software del forum):

https://blogs.oracle.com/jrockit/entry/repost_how_fragmented_is_my_ja

Perfetto grazie mille!