Cosa devo fare per consentire a GC di liberare la memoria non utilizzata in OCaml?

Question

Sto facendo un punto di riferimento per mergesort e quicksort.

Ho implementato Random_list.create, Mergesort.sort_list e Quicksort.sort_list. Possiamo supporre che le tre funzioni siano correttamente implementate e che le implementazioni non siano importanti in questa domanda.

Quello che voglio chiedere riguarda OCaml's GC.

---

Ecco il mio codice di riferimento:

let _ = 
    let l = Random_list.create 10000000 in 

    let len1 = List.length (Mergesort.sort_list l) in 
    Printf.printf "mergesort done for %d elements" len1; 

    let len2 = List.length (Quicksort.sort_list l) in 
    Printf.printf "quicksort done for %d elements" len2 

Se faccio funzionare il codice di cui sopra, che mi dice Fatal error: exception Out_of_memory dopo mergesort done for 10000000 elements.

Ha esaurito la memoria, nessun problema. anche l'output mi dice Out_of_memory si è verificato dopo il successo mergesort.

---

Poi quello che ho fatto contempla il codice e di test separatamente:

let _ = 
     let l = Random_list.create 10000000 in 
     let len1 = List.length (Mergesort.sort_list l) in 
     Printf.printf "mergesort done for %d elements" len1 

e poi

let _ = 
     let l = Random_list.create 10000000 in 
     let len2 = List.length (Quicksort.sort_list l) in 
     Printf.printf "quicksort done for %d elements" len2 

Sia funziona bene senzaOut_of_memory.

---

Ecco la mia domanda:

dal mio codice di riferimento, Sì, ho fatto i tipi di serie: Mergesort e poi Quicksort.

Durante l'esecuzione, dovrebbero essere creati 3 elenchi principali: l e l'elenco da un fusore e l'elenco da quicksort.

Tuttavia, l'elenco creato da mergesort deve essere GCed prima di quicksort, giusto? e quella lista non ha alcun riferimento ad essa, giusto?

Prima di quicksort, c'è solo un elenco principale che è l'originale l, giusto?

Perché genera ancora l'errore Out_of_memory?

Answer 1

Penso che il problema risieda nel fatto che si stanno utilizzando elenchi molto grandi. Il garbage collector mantiene due mucchio diverso per gestire memoria:

• Un minore mucchio per piccoli oggetti/breve durata.
• A mucchio maggiore per oggetti di lunga durata.

L'heap minore viene cancellato regolarmente e, se un oggetto è attivo abbastanza a lungo, viene promosso all'heap principale.

Tuttavia, oggetti molto grandi vanno direttamente all'heap principale. Il problema è che l'heap principale richiede di arrestare il mondo, vale a dire bloccare l'applicazione. Pertanto, la raccolta dell'heap principale viene eseguita in diversi passaggi per garantire che l'applicazione non venga interrotta per un lungo periodo e che non venga eseguita abbastanza spesso come una raccolta di heap minore.

Forse nel tuo caso l'elenco merge_sort non viene ancora raccolto quando si avvia l'ordinamento rapido, e quindi tutti e 3 gli elenchi sono presenti nella memoria allo stesso tempo.

Si può chiedere il GC di fare una collezione importante completo per vedere se si risolve il problema:

let _ = 
    let l = Random_list.create 10000000 in 

    let len1 = List.length (Mergesort.sort_list l) in 
    Printf.printf "mergesort done for %d elements" len1; 

    Gc.full_major(); 

    let len2 = List.length (Quicksort.sort_list l) in 
    Printf.printf "quicksort done for %d elements" len2 

Answer 2

E 'difficile concludere senza vedere il codice, ma potrebbe essere che nel primo programma, ci sono dei puntatori a Mergesort.sort_list l e Quicksort.sort_list l nel frame dello stack, impedendo che il primo elenco venga rimosso dalla garbage collection, mentre nel secondo caso lo stack frame viene deallocato tra i due let _ = ...?