Andreas Rumpf (Araq), autore del linguaggio di programmazione Nim, ha annunciato un nuovo algoritmo di gestione della memoria chiamato YRC (pronunciato «Ürk»), che risolve uno dei problemi principali dei meccanismi esistenti in Nim: l'incapacità di gestire correttamente i riferimenti ciclici che attraversano i confini dei thread.
Prima dell'introduzione di YRC, gli algoritmi di gestione della memoria proposti in Nim presentavano i seguenti limiti: l'ARC non supportava la multithreading né la gestione dei cicli; l'Atomic ARC era thread-safe, ma non gestiva i riferimenti ciclici; l'ORC gestiva i riferimenti ciclici, ma poteva farlo correttamente solo all'interno di un singolo thread (utilizzando riferimenti condivisi tra i thread si verificavano perdite di memoria).
La proposta YRC combina la sicurezza dei thread e l'elaborazione dei cicli tra i thread utilizzando un approccio combinato: per i dati aciclici viene applicata una conta di riferimenti atomica, mentre per quelli ciclici viene utilizzato un barrier write, attivato solo durante l'assegnazione dei puntatori. Nella realizzazione proposta: il garbage collector viene avviato solo quando necessario (non ci sono pause stop-the-world); gli oggetti radice RC sono definiti esplicitamente e uniti una sola volta (non è necessario scansionare gli stack dei thread); si evita la rimozione multithreading durante l'iterazione (non c'è una fase di sweep globale); i mutatori leggono liberamente i dati; qualsiasi thread può avviare il garbage collector quando necessario (senza un thread GC dedicato).
YRC utilizza informazioni complete sugli eventi incRef/decRef, che i tradizionali garbage collector a tracciamento (tracing GC) scartano e devono poi recuperare tramite scansione degli stack e attraversamento del grafo. L'implementazione occupa solo 550 righe di codice e ha una verifica formale della sicurezza e dell'assenza di deadlock tramite specifiche in linguaggio TLA+ e una dimostrazione nell'ambiente Lean. YRC si posiziona come 'quasi l'ultimo garbage collector per cicli basato sul conteggio dei riferimenti' (la lettera Y precede la Z nell'alfabeto), oltre che come il garbage collector più semplice e thread-safe: secondo l'autore, non richiede numerosi meccanismi complessi tipici dei tradizionali garbage collector a tracciamento.
YRC offre la stessa API di ORC, con esecuzione dei distruttori durante la raccolta dei rifiuti. Il raccoglitore gestisce solo i sottogruppi di oggetti con cui lavorano i thread, senza toccare strutture dati non correlate (cache, oggetti a lunga durata) — un approccio simile a quello del "perfetto" raccoglitore di rifiuti generazionale senza utilizzare generazioni. Lo svantaggio principale è la performance: YRC mostra un rallentamento da 1,5 a 2,0 volte rispetto a ORC nel test di performance orcbench. L'autore considera ciò un prezzo accettabile per un'elaborazione completamente thread-safe dei riferimenti ciclici.
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 seri e non gestiva correttamente i cicli. Al momento della pubblicazione, è stato preparato un insieme di correzioni che risolve i principali errori. L'autore continua a configurare le euristiche per la raccolta e a correggere gli errori rimanenti, mantenendo il corretto algoritmo di base e la sua verifica formale.
Fonte: opennet.ru
