Andreas Rumpf (Araq), autore del linguaggio di programmazione Nim, ha annunciato un nuovo algoritmo di gestione della memoria YRC (si pronuncia «Ürk»), che risolve uno dei problemi principali dei meccanismi esistenti in Nim: l'impossibilità di gestire correttamente i riferimenti circolari che attraversano i confini dei thread.
Prima dell'arrivo di YRC, gli algoritmi di gestione della memoria proposti in Nim presentavano i seguenti limiti: ARC non supportava né la multithreading né la gestione dei cicli; Atomic ARC era thread-safe, ma non gestiva i riferimenti circolari; ORC gestiva i riferimenti circolari, ma poteva farlo correttamente solo all'interno di un singolo thread (l'uso di riferimenti condivisi tra thread portava a perdite di memoria).
L'YRC proposto combina la sicurezza nei thread e la gestione dei cicli tra i thread, grazie a un approccio combinato: per i dati aciclici si applica il conteggio atomico dei riferimenti, mentre per quelli ciclici viene utilizzato un barriera di scrittura, che si attiva solo al momento dell'assegnazione dei puntatori. Nella realizzazione proposta: il collector si attiva secondo necessità (assenza di pause stop-the-world); gli oggetti radice RC sono esplicitamente definiti e uniti una sola volta (non è necessaria la scansione degli stack dei thread); si evita la cancellazione multi-thread durante l'iterazione (nessuna fase globale di sweep); i mutatori possono leggere liberamente i dati; qualsiasi thread può avviare il garbage collector se necessario (senza un thread GC dedicato).
L'YRC utilizza informazioni complete sugli eventi incRef/decRef, che i tradizionali garbage collector traccianti (tracing GC) scartano e poi devono ripristinare attraverso la scansione degli stack e la traversata del grafo. L'implementazione richiede solo 550 righe di codice e ha una verifica formale della sicurezza e dell'assenza di deadlock attraverso una specifica in linguaggio TLA+ e una dimostrazione nell'ambiente Lean. L'YRC è posizionato come "quasi l'ultimo garbage collector ciclico basato sul conteggio dei riferimenti" (la lettera Y precede la Z nell'alfabeto), così come il garbage collector thread-safe più semplice — secondo l'autore, non richiede meccanismi complessi tipici dei tradizionali garbage collector traccianti.
YRC fornisce la stessa API di ORC, con esecuzione di distruttori durante la raccolta dei rifiuti. Il raccoglitore gestisce solo i sotto-grafi di oggetti con cui lavorano i thread, senza toccare strutture dati non correlate (cache, oggetti a lungo termine) — un approccio simile a un «ideale» raccoglitore di rifiuti generazionale senza l'utilizzo di generazioni. Il principale svantaggio è la performance: YRC mostra un rallentamento di 1.5-2.0 volte rispetto a ORC nel test di performance orcbench. L'autore considera questo un prezzo accettabile per una gestione completamente sicura dei thread delle referenze cicliche.
YRC è già disponibile nella versione di sviluppo di Nim e si attiva con il flag «—mm:yrc». Tuttavia, nei messaggi successivi, l'autore ha riconosciuto che l'implementazione iniziale conteneva errori gravi e non gestiva correttamente i cicli. Al momento della pubblicazione, è stato preparato un insieme di correzioni per risolvere i principali errori. L'autore continua a ottimizzare le euristiche di raccolta e a correggere gli errori rimanenti, mentre l'algoritmo di base e la sua verifica formale rimangono corretti.
Fonte: opennet.ru
