Andreas Rumpf (Araq), twórca języka programowania Nim, ogłosił nowy algorytm zarządzania pamięcią YRC (wymawiane „Ürk”), który rozwiązuje jeden z kluczowych problemów istniejących mechanizmów w Nim: niemożność prawidłowego przetwarzania cyklicznych odniesień przekraczających granice wątków.
Przed wprowadzeniem YRC w proponowanych algorytmach zarządzania pamięcią w Nim występowały następujące ograniczenia: ARC – nie wspierał ani wielowątkowości, ani przetwarzania cykli; Atomic ARC – był bezpieczny wątkowo, ale nie obsługiwał cyklicznych odniesień; ORC – przetwarzał cykliczne odniesienia, ale mogło to być zrobione poprawnie tylko w obrębie jednego wątku (przy użyciu wspólnych odniesień między wątkami dochodziło do wycieków pamięci).
Proponowane YRC łączy bezpieczeństwo wątkowe oraz przetwarzanie cykli między wątkami, poprzez zastosowanie kombinowanego podejścia: dla acyklicznych danych stosowany jest atomowy licznik odniesień, a dla cyklicznych – bariera zapisu (write barrier), która uruchamia się tylko w momencie przypisywania wskaźników. W zaproponowanej implementacji: kolektor uruchamiany jest w rzeczywistej potrzebie (brak pauz stop-the-world); korzenne obiekty RC są wyraźnie zdefiniowane i łączone raz (brak potrzeby skanowania stosów wątków); unika się wielowątkowego usuwania podczas iteracji (brak globalnej fazy sweep); mutatory mogą swobodnie odczytywać dane; każdy wątek może uruchomić zbieracz śmieci w razie potrzeby (bez dedykowanego wątku GC).
YRC wykorzystuje pełne informacje o zdarzeniach incRef/decRef, które tradycyjne zbieracze śmieci z śledzeniem (tracing GC) odrzucają, a następnie muszą odzyskiwać poprzez skanowanie stosów i przeszukiwanie grafu. Implementacja zajmuje jedynie 550 linii kodu i posiada formalną weryfikację bezpieczeństwa oraz braku martwych blokad poprzez specyfikację w języku TLA+ oraz dowód w narzędziu Lean. YRC jest pozycjonowany jako „prawie ostatni zbieracz cykli oparty na liczniku odniesień” (litera Y poprzedza Z w alfabecie), a także jako najprostszy zbieracz śmieci bezpieczny dla wątków — według twórcy nie wymaga wielu skomplikowanych mechanizmów typowych dla tradycyjnych zbieraczy śmieci z śledzeniem.
YRC zapewnia to samo API co ORC, z wykonywaniem destruktorów podczas zbierania śmieci. Zbieracz przetwarza tylko te podgrafy obiektów, z którymi pracują wątki, nie dotykając niezwiązanych struktur danych (cache, długowieczne obiekty) — podejście analogiczne do „idealnego” zbieracza śmieci generacyjnego bez użycia pokoleń. Główną wadą jest wydajność: YRC wykazuje spowolnienie o 1,5-2,0 razy w porównaniu do ORC w teście wydajności orcbench. Autor uznaje to za akceptowalną cenę za pełną bezpieczną przetwarzanie cyklicznych odniesień.
YRC jest już dostępny w wersji deweloperskiej Nim i może być włączony flagą „—mm:yrc”. Jednak w kolejnych wiadomościach autor przyznał, że początkowa implementacja zawierała poważne błędy i nie zbierała cykli poprawnie. W momencie publikacji przygotowano zestaw poprawek, które eliminują główne błędy. Autor kontynuuje dostosowywanie heurystyk zbierania i naprawianie pozostałych błędów, przy czym podstawowy algorytm i jego formalna weryfikacja pozostają poprawne.
Źródło: opennet.ru
