Newsgroup: it.comp.dotnet
Titolo: Garbage collector: quando interviene?

[Cross post su it.comp.dotnet e it.comp.java]
Salve,
ho scritto in C++ un algoritmo che costruisce un albero, se non si verifica 
una certa condizione lo distrugge, e ne ricostruisce uno più grande.
Il tutto ripetuto finché non si verifica un'altra condizione.
Utilizzando il distruttore e delete riesco a deallocare tutta la memoria 
prima che parta la costruzione del nuovo albero.
Ma in C# e Java, dovendomi affidare alla gestione automatica della memoria 
che cosa accadrebbe? So che posso invocare il GC manualmente, ma chi mi 
garantisce che agisca subito sull'albero?
Considerando che la radice iniziale è sempre la stessa (è lo stesso nodo), 
magari man mano che il nuovo albero viene costruito, il GC dealloca i nodi 
del vecchio?
E se il nuovo albero venisse costruito partendo da una radice diversa dalla 
precedente, in quale momento il GC deallocherebbe l'albero vecchio?
L'albero può occupare anche oltre un gigabyte.
Grazie 


Quanto scrivo vale solo per dotnet.
Il criterio generale per tutti i GC è che loro riescono a gestire le 
allocazioni/deallocazioni in modo più efficiente di quanto  puoi fare 
tu.
Se fai un ciclo di allocazioni/disallocazioni in raw win32 scoprirai 
che le allocazioni hanno un costo alto, costo che il GC cerca di 
minimizzare con un altra fondamentale ottimizzazione: Il CLR cerca di 
mantenere tutto ciò che è in generazione 0 e 1 dentro la cache L2, 
rendendo ancora più performante l'esecuzione del tuo codice.
Per capire a fondo il meccanismo ci vorrebbe mezza giornata di talk con 
una serie di esempi che mi sono preparato nel tempo.
Per farla corta il GC è giustamente non-deterministico perché lui può 
decidere in modo più efficiente.
Il principio su cui si basa il GC del CLR è che le allocazioni fatte 
più di recente saranno in tutta probabilità quelle disallocate prima.
In pratica il GC alloca degli ephemeral segment (pezzi di memoria di 
lunghezza fissa, al momento di 16MB) all'interno dei quali viene 
spostato un puntatore per allocare memoria. La collection serve a 
'deframmentare' i buchi lasciati da disallocazioni 'random'.
Detto questo, il tuo algoritmo fa esattamente ciò che si aspetta il GC. 
E se tu ad ogni loop disallochi tutto, la disallocazione non sarà altro 
che spostare il puntatore indietro mantenendo in memoria il "costoso" 
segmento di 16MB (fino a quando il GC non decide che conviene 
rilasciarlo, decisione che dipende da una serie di fattori che 
tralascio).
Se invece hai una singola allocazione superiore a circa 85K (cifra su 
cui non ti devi fossilizzare e passiva di cambiamenti in future 
versioni) va direttamente in LOH (Large Object Heap) che sta in 
Generazione 2 e non è soggetta a 'deframmentazione' durante la 
collection.
Questo significa che:
- se le tue allocazioni sono grosse, fatti un pool di memoria per tutto 
il loop e poi rilascia.
- se le tue allocazioni sono piccole, non abbondare mai in dimensioni 
di allocazione (come si faceva in C/C++) perché migliori le performance 
se sta tutto in L2
Ci sarebbe molto altro da dire ma l'unica cosa saggia da fare è di 
misurare e vedere tu stesso quali sono le condizioni migliori 
(ovviamente devi fare cicli molto lunghi per avere risultati 
accettabili)
Buon lavoro
-- 
Raffaele Rialdi  
http://www.iamraf.net
Weblog: 
http://blogs.ugidotnet.org/raffaele
Microsoft MVP profile 
https://mvp.support.microsoft.com/profile/raffaele
UGIdotNET - 
http://www.ugidotnet.org/

 Quanto scrivo vale solo per dotnet.
[CUT]
Grazie per la risposta.
Cosa intendi di preciso con Generazione 0, 1, 2 etc..? 

 Cosa intendi di preciso con Generazione 0, 1, 2 etc..?
È il modo in cui funziona il GC del framework. C'è un'ottima 
spiegazione sul libro di Richter (CLR via C#).
In due parole le allocazioni più giovani stanno in gen0 man mano che 
passa tempo e restano in memoria passano in gen1 e infine in gen2. 
Queste tre generazioni sono soggette alla garbage collection 
('deframmentazione' + disallocazione) mentre la speciale LOH non è 
soggetta a collection.


 tempo e restano in memoria passano in gen1 e infine in gen2.
Allora l'avevo intuito :D 

 garantisce che agisca subito sull'albero?
parlando di java e della implementazione hotspot: nel momento in cui
l'albero viene dereferenziato viene candidato per il gc, per il tuo
applicativo l'heap torna libera e virtualmente pronta per la nuova
allocazione senza bisogno ne di aspettare il passaggio del gc ne di
invocarlo manualmente.
il grosso problema di fare questi continui cicli di allocazione sono
le performance. il modello gc della hotspot è organizzato in modo
generazionale proprio per ridurre l'area di memoria su cui
intervenire, da una parte la cosiddetta "young generation" dove
vengono creati i nuovi oggetti e dall'altra la "tenured generation"
dove vengono via via spostati gli oggetti "sopravvissuti" (poi ci
sarebbe la "perm generation" ma questa è un'altra storia). ad ogni
passaggio il gc dealloca la memoria degli oggetti candidati nell'eden
e sposta i sopravvissuti verso la generazione successiva, liberando
quindi spazio per i nuovi oggetti. in automatico interviene solo
quando c'è bisogno, cioè quando c'è carenza di spazio nell'eden,
perché su heap di gigabytes il passaggio del gc costa caro in termini
di tempo cpu. il problema è che facendo cicli continui di allocazione/
deallocazione di giga di oggetti tu poni sempre le condizioni per cui
il gc deve intervenire e ogni volta spazza a tappeto tutto l'eden.
ciò premesso, arrivo alle conclusioni:
- chiamare il gc manualmente non guadagni nulla in termini di utilizzo
di memoria mentre ci smeni in termini di ottimizzazione di utilizzo.
in altre parole il gc sa da se quando deve intervenire ed è meglio
fidarsi
- se devi allocare e deallocare giga di oggetti è molto meglio se
predisponi una cache permanente.
- dietro al tuning del gc c'è un mondo, vale la pena di documentarsi
se si hanno a cuore le performaces.

 predisponi una cache permanente.
Allocare all'inizio e deallocare alla chiusura del programma? 

 Allocare all'inizio e deallocare alla chiusura del programma?
usare un pool di oggetti preallocati invece di riallocarli ogni volta.
naturalmente la butto lì e non so se sia applicabile nel tuo caso.

 naturalmente la butto lï¿œ e non so se sia applicabile nel tuo caso.
Per quanto riguarda .net, la preallocazione ï¿œ preferibile solo se le 
singole allocazioni vanno in LOH (>85K). Per vedere se vanno in LOH la 
cosa piï¿œ facile ï¿œ usare perfmon e visualizzare il grafico delle varie 
generazioni.
Diversamente si ottengono generalmente prestazioni migliori lasciando 
fare tutto al GC.
Come valutarlo? Misurando il tuo contesto specifico.


 naturalmente la butto lě e non so se sia applicabile nel tuo caso.
Si tratta di un algoritmo che calcola tutti i percorsi (minimi) per 
raggiungere da un punto A, un punto B all'interno di un labirinto.
Ho scritto due versioni ed una tiene in memoria l'albero precedente e usa le 
foglie come radici dei sotto alberi che poi saranno creati, costruendo un 
albero piů grande. Il programma risulta essere sensibilmente piů veloce 
rispetto a quello che distrugge e ricrea continuamente, ma tenere in memoria 
tutte quelle foglie fa consumare molta piů memoria. 

 generazioni.
Ma per valutare le dimensioni di una singola allocazione non basta una 
sizeof dell'oggetto che viene allocato? 

 dell'oggetto che viene allocato?
Non ti conviene farlo dinamicamente.
La strategia migliore è quella di predisporre un pool di blob per 
quelle allocazioni che sono decisamente più grosse di circa 85K.
Il pool può essere una lista/dictionary/set/... di blocchi di memoria 
che riutilizzi ad ogni giro. A te sta l'onere di cancellarlo (se serve) 
e di aggiungere nuove allocazioni qualora sia necessario.
Alla fine butti via tutto e il numero di allocazioni/disallocazioni 
sarà inferiore con conseguente miglioramento delle prestazioni (che 
devi misurare per vedere se ha senso nel tuo caso).
Tieni conto che se i blocchi sono grossi e finiscono in LOH, non sono 
comunque soggetti al passo di 'deframmentazione' del GC che è il passo 
più oneroso del GC (finalizzazione a parte che non dovrebbe avere luogo 
nel tuo caso).


 raggiungere da un punto A, un punto B all'interno di un labirinto.
Per curiosità cosa usi, Dijkstra, Floyd-Warshall (pesato) o cosa?


 Per curiosità cosa usi, Dijkstra, Floyd-Warshall (pesato) o cosa?
No. Praticamente è un algoritmo che avevo scritto per cercare tutte le 
occorrenze di una parola all'interno di una matrice, tenendo conto del fatto 
che le lettere fossero adiacenti (in una delle 8 circostanti insomma) e che 
non fossero usate più di una volta. Poi su un forum lessi di un utente 
appassionato di intelligenza artificiale, che aveva sviluppato un algoritmo 
per i labirinti e mi sono accorto che il mio poteva essere applicato a quel 
caso, poiché un percorso del labirinto si può rappresentare anche come una 
stringa del tipo P[spazio][spazio][spazio]...[spazio]A dove P e A sono i 
punti di partenza e arrivo.
Sicuramente sarà ottimizzabile, ma confrontandolo con l'algoritmo scritto da 
quell'utente, i miei (quello veloce e quello che consuma meno memoria) sono 
molto più veloci e trovano tutte le soluzioni minime. Solo che ovviamente 
per labirinti molto grandi nascono problemi relativi all'uso della memoria. 
Magari la soluzione sarebbe utilizzare uno degli algoritmo da te citati, ma 
mi chiedo se con quelli la soluzione trovata è solo una o se si trovano 
tutte. 


Non discuto sulla bontà del codice che hai scritto ma gli algoritmi che 
ho citato hanno alle spalle una soluzione matematica che garantisce di 
trovare il percorso minimo in differenti condizioni. Guarda anche 
quello di Kruskal.
Eulero a parte, gli algoritmi di ottimizzazione moderni sono nati 
durante la guerra e successivamente utilizzati nel campo 
commerciale/finanziario.
Quello che un dev può fare non è altro che la ricerca alla migliore 
implementazione di un modello matematico che difficilmente può essere 
superato.
Personalmente ti consiglio di dare un'occhiata almeno a quei due 
algoritmi (Dijkstra probabilmente è il più semplice per il tuo caso) e 
vedere quanto differisce la performance.
Per trovare tutte le possibili soluzioni ti dovrebbe bastare cambiare 
opportunamente i costi associati agli archi.


 opportunamente i costi associati agli archi.
Questi algoritmi agiscono su grafi già costruiti in cui i costi degli archi 
sono differenti.
L'algoritmo che ho scritto io analizza la matrice e crea un albero in cui la 
distanza massima tra la radice e una foglia è la distanza minima tra i due 
punti. Inoltre un eventuale grafo in cui ogni nodo rappresenterebbe una 
cella della matrice, avrebbe tutti i costi degli archi uguali a 1 e questo 
forse creerebbe qualche problema nella ricerca di tutte le soluzione.
Su wikipedia leggo che: l'algoritmo di Floyd-Warshall calcola lo shortest 
path per tutte le coppie di un grafo pesato.
A me servirebbero tutti gli shortest path per ogni coppia.
Ma aggiungo anche che non conoscendo bene l'argomento (praticamente ho letto 
qualcosa solo su quello di Dijkstra), probabilmente ho una visione limitata 
delle applicazioni di tali algoritmi ad un caso come il mio.
Direi che siamo OT, anche se questi argomenti nel mondo della 
programmazione, in fondo sono sempre IT :D 

 A me servirebbero tutti gli shortest path per ogni coppia.
Volevo dire per una coppia (a scelta). 

 in fondo sono sempre IT :D
La modifica per trovare tutti le possibili soluzioni non dovrebbe 
essere complicata. Qui trovi un po' di idee:
http://stackoverflow.com/questions/2819347/dijkstras-algorithm-to-find-all-the-shortest-paths-possible
In particolare guarda questo link:
http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf


 
http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf
Un bel documento sull'argomento.
Grazie