[JAVA]Bisogno di più memoria

[rayman2]

Ciao a tutti, sto facendo un certo progetto che consiste nel costruire un grafo per eseguire delle analisi sociometriche (Social Network Analysis) su un file di log abbastanza grosso.
Sto lavorando in Java con il Jung Framework (http://jung.sourceforge.net/) che per me è l'ideale dato che offre un sacco di metodi per manipolare modelli di dati a grafo ed implementa già molti degli algoritmi che mi servono.
Ho già implementato il parser del log ed il modello del grafo, che ha per nodi e per archi degli appositi oggetti Java che incapsulano tutte le informazioni di cui ho bisogno.
Il problema risiede nel fatto che il file di log dal quale parto per costruire il grafo occupa ben 4.2GB. Non tutti i dati del log sono poi utili per il grafo, molti vengono aggregati, ma nonostante questo la mia memoria di 2GB (ovviamente ho aumentato a dovere l'heap space della jvm) viene saturata e il programma termina con la più canonica "java.lang.OutOfMemoryError: Java heap space".
Mi chiedevo se c'è qualche modo, ovviamente a discapito delle prestazioni che tutto sommato non mi interessano dato che una volta costruito il grafo devo solo prendere delle statistiche e poi distruggerlo, per riuscire a lavorare sul progetto?
Immagino qualcosa tipo memoria virtuale o strutture dati molto efficienti (compresse?) dal punto di vista dell'occupazione della memoria a discapito del tempo di esecuzione.

Vi viene qualche idea? Grazie.

[cionci]

Sinceramente non conosco quel framework...io comunque partirei con il mantenere la struttura fisica in memoria, ma swappare i dati su disco.
Metti un flag in ogni nodo che indica se il nodo è in memoria o su disco e la posizione su disco. Al posto di un flag potresti utilizzare un wrapper con un po' di polimorfismo in modo da rendere trasparente la cosa.
Ovviamente dovresti implementare una politica LRU, in cui il wrapper tiene traccia del tempo in cui è avvenuto l'ultimo uso della risorsa. Anzi, più che del tempo io terrei traccia dell'ordine di utilizzo. Un contatore con un intero a 64 bit che conta ogni utilizzo, ogni tot secondi e/o quando hai un'eccezione di OutOfMemory fai lo swap su disco di tutti i dati non usati recentemente esclusi, ad esempio, gli ultimi 10.000.
Per swappare su disco sono comodissime le funzionalità di serializzazione/deserializzazione messe a disposizione dal framwork.
Un nodo deve essere riportato automaticamente in memoria quando vi si fa accesso

[rayman2]

Intanto grazie delle risposte.
Già che c'ero ho chiesto informazioni direttamente agli sviluppatori del framework i quali mi hanno detto, innanzitutto che se voglio sviluppare qualcosa del genere per loro me ne sarebbero grati (eheh).
Il secondo, un po' più concretamente, mi ha detto che il compito può risultare semplificato se riuscissi a trovare una libreria opensource già esistente "that will store java collections using nio (in particular, using memory mapping)", dato che i grafi sono implementati tramite Collection.
A parte che non ho ben capito cosa intenda, conoscete qualche progetto del genere? Ho googlato ovviamente ma non ho trovato nulla!
Inoltre riflettevo su quello che mi hai scritto. In effetti ogni nodo ha un nome che è una stringa di un certo numero di caratteri e un id che mi serve per distinguere i nodi. Se invece che la stringa memorizzassi solamente il numero di linea e l'offset d'inizio e di fine della stringa nel file di log, in modo da poter accedere a quello quando dovesse servire, potrebbe tradursi in un vantaggio in termini di memoria?
Ovvero, si tratterebbe di sostituire una media di circa 20 char per nodo con tre int (uno per la linea, uno per l'inizio della stringa, l'altro per la fine). Esiste un metodo efficiente per recuperare la stringa in un file del tipo: file.getString(line, start, end)???
Grazie!

[cionci]

Credevo che ogni nodo avesse molti dati, non solo 20 byte.
Quello che dici va bene, ma sostituire 20-25 byte della stringa con 8 byte cambia veramente poco nell'ordine di grandezza dei nodi che puoi tenere in memoria. Puoi sostituire direttamente tutto con
A questo punto devi agire in maniera diversa, dovresti andare a swappare direttamente la struttura e quindi andare a modificare internamente la libreria.

[rayman2]

beh, intanto farò un simpatico test per vedere quanto mi manca del file di log: se ho superato la metà, riuscire a farci stare anche solo il doppio dei nodi può risolvere il mio problema no?
Sapete qualcosa delle Collection con il memory mapping?

[cionci]

Prima ho lasciato una frase a metà
Puoi usare anche direttamente solo 8 byte o 4 byte, a seconda dei dettagli di implementazione.
Supponiamo di memorizzare tutte le stringhe in modo consecutivo all'interno di un file.
Per usare anche solo 8 byte. Nell'id inserisci la posizione della stringa all'interno del file, con questo dovrai fare un seek sul file per spostare la lettura all'inizio della stringa. In un altro int inserisci la lunghezza della stringa.
In alternativa puoi usare solo 4 byte, ma a questo punto devi lavorare sui bit e cercare di dimensionare il problema.
Ad esempio supponiamo che tu non possa avere stringhe più lunghe di 64 caratteri. Riservi quindi i 6 bit meno significativi nell'ID per la lunghezza della stringa. A questo punto ti rimangono 26 bit per la lunghezza, quindi il file con le stringhe non può essere più lungo di 2^26 byte (64 MB).
Volendo si può ovviare al problema imponendo che le stringhe all'interno del file possano essere memorizzate solo in posizioni multiple di 64, il resto viene riempito da spazi. In questo modo con 2^26 byte puoi tornare ad indirizzare comunque un file da 2^32 byte Per accedere al file ti basterà ottenere i 2^26 byte dalla parte alta dell'id, con i 6 bit della parte bassa a 0.
Ovviamente il massimo numero di modi che puoi avere è 2^26

[rayman2]

Domanda ingenua: ma se metto direttamente su un database il mapping: <id, name>? Non dovrebbe occuparsi lui dello swapping?
Altra domanda ingenua: sto facendo il famigerato test per vedere fino a dove riesco ad arrivare con il grafo attuale. Dato che ci mette delle ore per terminare, la domanda è: dato che l'oggetto del grafo è accessibile tramite la variabile g e che ad un certo punto dell'esecuzione un'operazione su di esso causerà l'eccezione di out of memory, posso circondare quest'operazione con un blocco try-catch per fare in modo che quando finisce la memoria il mio programma, prima di terminare, stampi a video un paio di statistiche sul grafo (tipo numero di nodi e numero di archi)? Il dubbio sta più che altro nel fatto che essendo la memoria piena temo che non abbia più risorse per fare queste semplici print.

Molto interessante l'idea del file di testo con i nomi utente, se sarò alle strette vedrò di gestirla così.

[cionci]

Suppongo che tu possa fare il catch, non ho idea di quanto possa fare in quell'occasione. Un po' di ram dovrebbe essere libera perché lo spazio occupato da un nodo ha una certa grandezza, in ogni caso ti conviene eliminare i nodi man mano che fai una statistica.
Riguardo al database: sicuramente può fare al caso tuo.

[rayman2]

me la vedo così: tengo il numero dei nodi e degli archi aggiornato durante l'esecuzione e quando capita l'eccezione faccio un bel: g = null; e mi libero della mappazza! Poi stampo le statistiche.

[cionci]

Originariamente inviato da rayman2

me la vedo così: tengo il numero dei nodi e degli archi aggiornato durante l'esecuzione e quando capita l'eccezione faccio un bel: g = null; e mi libero della mappazza! Poi stampo le statistiche.

Ok, ma ti conviene richiamare direttamente il garbage collector, perché non è detto che ti liberi istantaneamente della memoria allocata.
http://java.sun.com/javase/6/docs/ap...ystem.html#gc()

[banryu79]

Neppure "suggerendo" alla JVM di lanciare il GC hai quella garanzia...
Invece di aspettare l'eccezione potresti tenere d'occhio la memoria disponibile e se questa scende sotto un certo limite fissato a priori (che so, il 10%) allora ti comporti come hai descritto, cioè liberandoti della "mappazza" E suggerendo alla JVM di lanciare il GC.

[rayman2]

ho googlato un po' ma non ho capito come controllare il quantitativo di memoria occupata o, ancor meglio, generare un evento quando è quasi piena. Avete qualche link di riferimento?
Grazie

[banryu79]

java.lang.Runtime.freeMemory()
Dai un occhiata anche agli altri metodi della classe.

Il mio suggerimento potrebbe non fare al caso tuo, perchè prevede di utilizzare un thread come demone che ogni tot. secondi interroga la Runtime della JVM chiedendogli la memoria libera, verifica che non sia scesa sotto la "soglia minima", e ritorna.
Se invece si è scesi sotto la soglia minima, libera la memoria, eliminando la mappa e "suggerendo" alla JVM di fare garbage collection quanto prima.

Questo significa introdurre un (piccolo?) overhead nel tuo applicativo, con tutte le conseguenze del caso.

[rayman2]

Combinazione vuole che il mio programma, dopo sei ora circa di esecuzione, ha generato la sua eccezione proprio ora!
L'eccezione, come suggerito da banryu79, non è stata gestita ed infatti al posto delle mie statistiche ho ottenuto il messaggio:

Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded

Tra l'altro ho il sospetto che, nonostante credessi di avere l'heapspace settato a 2GB, l'eccezione sia stata generata prima. Quindi avrei bisogno ancora di qualche precisazione.
Il mio main è eseguito su una jvm 1.6 con sistema operativo ubuntu da Eclipse, con il file eclipse.ini configurato così:

-vmargs
-Xms40m
-Xmx2048m

La cosa ha senso oppure sono già partito col piede sbagliato?
Nel dubbio ho anche inserito, all'inizio del mio main il metodo:

System.out.println(java.lang.Runtime.getRuntime().maxMemory());

Che, se ho capito bene, dovrebbe indicarmi la quantità di byte che la jvm utilizzerà al massimo come memoria. Il risultato è stato: 640221184; nulla a che vedere con i famosi 2GB...

Parlando di overhead penso che tu ti riferisca a sprechi di tempo nel controllo della memoria libera: sicuramente ci saranno ma forse vale la pena introdurli in questa fase per capire un po' quanto sono lontano dalla mia meta. Potresti aiutarmi nell'implementazione di questo tipo di controllo? Non ho mai usato i thread in Java :$

Ultima ma non per importanza ho trovato questo thread (di un forum) sul forum di Ubuntu che riguarda un problema decisamente simile al mio. Non posso fare in modo che la jvm sfrutti anche la mia partizione di swap in modo trasparente?

Grazie di tutto, non credevo che la questione si sarebbe ampliata fino a questo punto ma vi ringrazio perché sto imparand diverse cose interessanti!

[banryu79]

@EDIT: più che freeMemory() sono utili maxMemory() e totalMemory().

[banryu79]

Potrebbe interessarti (e impegnarti parecchio) questo documento, nel quale ho letto di questo (non so se è il tuo caso, non si sa mai).

Qui c'è altro materiale

[banryu79]

Originariamente inviato da rayman2

Potresti aiutarmi nell'implementazione di questo tipo di controllo? Non ho mai usato i thread in Java :$

public final class MemoryManager
{
    final boolean IS_DEAMON = true;
    Timer timer;

    // per esempio:
    // delay = 5 * 60* 1000 == 5 min.
    // period = 10 * 1000 == 10 sec.
    public MemoryManager(int delay, int seconds)
    {
        timer = new Timer(IS_DEAMON);
        timer.scheduleAtFixedRate(new MemoryManagerTask,
            DELAY, PERIOD);
    }

    class MemoryManagerTask extends TimerTask
    {
        Runtime rt;
        double maxMemory;
        
        public MemoryManagerTask()
        {
            rt= Runtime.getRuntime();
            maxMemory = rt.maxMemory();
        }

        public void run()
        {
            double totalMemory = rt.totalMemory();
            if (totalMemory/maxMemory > 0.9)
            {
                double freeMemory = rt.freeMemory();
                if (freeMemory/totalMemory < 0.1)
                {
                    // distruggi la mappa
                    // chiama il GC
                }
            }
        }
    }
}

Usa i parametri del costruttore di MemoryManager per passare dall'esterno i valori che preferisci.
Io nel commento ho proposto 5 min. di "delay" iniziale prima di partire con il task, che poi viene eseguito ogni "period", se usi 10 sec. su un ora fa meno di 360 controlli (per via del delay iniziale, appunto).

i metodi tipo freeMemory() di Runtime tonano valori long; io li metto in double per poter fare le divisioni senza arrotondamenti, nelle condizioni degli if.

Ho scitto di fretta, possono esserci errori, (anche perchè ho scritto direttamente nell'editor del forum) ma la logica sarebbe:
dopo 5 minuti dall'inizio del timer, e da lì in poi ogni 10 secondi:
- controlla se la memoria attualmente allocata alla JVM supera il 90% della memoria massima permessa per l'allocazione alla JVM;
- se sì controlla se la memoria libera a disposizione della JVM è inferiore al 10% della memoria attualmente allocata;
- se sì fai quel che devi fare per tentare di liberare memoria.

[rayman2]

Non ho ancora avuto tempo di controllare i link che mi hai passato ma lo farò appena possibile perché potrebbero sicuramente risultare essenziali per capire.
Per capirci meglio ho stampato a video, prima di cominciare il lavorone, i seguenti dati:

System.out.println(Runtime.getRuntime().freeMemory());
System.out.println(Runtime.getRuntime().maxMemory());
System.out.println(Runtime.getRuntime().totalMemory());

Con il medesimo main, da Eclipse (configurato con il file eclipse.ini postato poco sopra) mi viene stampato il seguente output:

40436440
640221184
40960000

Mentre da riga di comando:

java -Xmx2048m -Xms2048m -jar WTAnalysis.jar
2114086488
2117664768
2117664768

Ora lo faccio andare questa notte e vediamo se riesco perlomeno a capire quanti nodi e quanti archi ho, quante linee di log ho letto e quante me ne rimangono ancora da leggere nel momento in cui finisce la ram. Ovviamente sto usando il tuo sistema per controllare la memoria ma impostando dei tempi un po' più lunghi dato che questa mattina ci ha messo 6 ore prima di raggiungere la pienezza, e sospetto che avesse la configurazione con 640MB di heap space (ora che ha 2GB potrebbe anche terminare!). Ora ho rimosso l'invocazione del garbage collector dato che al 90% di memoria occupata ho ancora tempo per stampare le statistiche e terminare l'esecuzione senza fare casini.
Una cosa non ho capito: perché due controlli? Non bastava:

if (freeMemory / totalMemory < 0.05)

Ancora una domanda: ho notato che mentre viene eseguito il thread, il main continua ad andare avanti; non sarebbe meglio mettere in pausa il thread del main mentre eseguo i controlli sulla memoria? E' di sicuro una perdita di tempo in più ma mi sembra che ne valga la pena per avere statistiche più precise.

Per ora non mi viene in mente nient'altro. Vediamo se 'stanotte riesco ad avere qualche info più precisa.
Grazie mille per ora!

P.S. il codice era pressoché perfetto eccetto per la linea che ti correggo qui sotto:

        timer.scheduleAtFixedRate(new MemoryManagerTask(), delay, period);

[Vincenzo1968]

Potresti indicizzare il file di log con un B+Tree. È una tecnica molto efficiente, e dal punto di vista delle prestazioni, e da quello della memoria. Viene utilizzata, nella maggior parte dei DBMS, per la realizzazione degli indici delle tabelle. Per esempio, con un buffer di 1 MB puoi effettuare la ricerca del record, in un file di circa 19 GB, con soli due o tre accessi al disco.

[wlog]

Ciao, ti spiego come faccio io:

A) Il mio file di swap è di 8 gb.

B) prevedo già durante la scrittura dell'algoritmo di quali dati avrò bisogno ed effettuo una operazione intelligente di caching: Divido i miei dati in blocchi logici da 1 gb ciascuno, e carico in memoria il blocco di cui ho bisogno, piu due blocchi adiacenti.

Devi però essere in grado di prevedere a priori una mappa logica che ti permetta di sapere, avendo un set di dati, quali sono i set di dati che è piu probabile che il processore usi, definendo questi contigui.

Ad esempio in una enorme matrici gli elementi contigui sono anche quelli fisicamente vicini, mentre in un algoritmo di ordinamento come il quicksort gli elementi contigui sono quelli piu lontani (di solito, poi piano piano che l'algoritmo va avanti succede l'opposto).

Con questo metodo sono riuscito a gestire fino a 64 gb di dati in una volta sola....