Bölüm 9 · Yazılımın içi · Ders 41

Çöp toplama: işaretle ve süpür

Köklerden ulaşılamayan nesneleri bulmak, döngüler dahil

Veri. Robotun gezinme yazılımı saatlerce çalışıyor ve sürekli yeni nesne yaratıyor: haritalar, yol planları, lidar tamponları, kamera kareleri. Bellekte 12 nesne var; programın hâlâ tuttuğu iki kök (gezinme ve sensörler) bunların bir kısmını gösteriyor. Robot yeni plan yapınca eski plan, eski yol ve eski hedef birbirini göstermeye devam ediyor ama artık kimse onlara ulaşamıyor. Bellek dolmadan bunları kim, nasıl bulacak?

12 nesne; kökler: gezinme ve sensörlerbellek 3260 KB / 3260 KB

1 / 26

Tohum (farklı grafik) 4

cop_toplama.pypython

import numpy as np
rng = np.random.default_rng(4)
N, roots = 12, [0, 1] # gezinme, sensörler
refs = [set() for _ in range(N)] # kim kimi gösteriyor
for i in range(9):
for j in rng.integers(0, 9, 2 if i in roots else 1):
if j != i: refs[i].add(int(j))
refs[9], refs[10], refs[11] = {10}, {11}, {9} # eski plan döngüsü
marked, stack = set(), list(roots) # köklerden başla
while stack: # işaretle
o = stack.pop()
if o not in marked:
marked.add(o); stack.extend(refs[o]) # işaretle, komşuları ekle
garbage = [o for o in range(N) if o not in marked] # süpür
rc = [sum(o in r for r in refs) for o in range(N)] # referans sayıları
for r in roots: rc[r] += 1
free, dead = [o for o in range(N) if rc[o] == 0], set()
while free: # referans sayımı
o = free.pop(); dead.add(o)
for j in refs[o]:
rc[j] -= 1
if rc[j] == 0: free.append(j)
print("süpürülen", garbage, "ref.sayımı:", sorted(dead))

Sahnedeki her sayı, aynı algoritmanın tarayıcında yapılan gerçek çalıştırmasından gelir (sabit tohum, her seferinde aynı sonuç). Python kodunu kendi bilgisayarında çalıştırırsan rastgele başlangıçlar farklı olacağı için sayılar biraz değişebilir.

Veri seti

Tüm veri setleri →

Bu dersin kodu verisini kendi içinde üretir; indirilecek dosya yok. Kodu yine de aşağıda tarayıcında çalıştırabilirsin.

Kodu tarayıcıda çalıştırPython · NumPy · matplotlib · Pyodide

Python ve NumPy bu sayfada, tarayıcında çalışır (Pyodide). Kodu değiştirip yeniden çalıştırabilirsin; dersin veri setleri çalışma klasöründe hazır. Kod matplotlib kullanırsa grafikler çıktının altında görünür, yazdığı dosyalar (ör. egitim_gecmisi.csv) indirilebilir.

cop_toplama.pypython

import numpy as np
rng = np.random.default_rng(4)
N, roots = 12, [0, 1]                         # gezinme, sensörler
refs = [set() for _ in range(N)]              # kim kimi gösteriyor
for i in range(9):
    for j in rng.integers(0, 9, 2 if i in roots else 1):
        if j != i: refs[i].add(int(j))
refs[9], refs[10], refs[11] = {10}, {11}, {9}  # eski plan döngüsü
marked, stack = set(), list(roots)            # köklerden başla
while stack:                                  # işaretle
    o = stack.pop()
    if o not in marked:
        marked.add(o); stack.extend(refs[o])  # işaretle, komşuları ekle
garbage = [o for o in range(N) if o not in marked]  # süpür
rc = [sum(o in r for r in refs) for o in range(N)]  # referans sayıları
for r in roots: rc[r] += 1
free, dead = [o for o in range(N) if rc[o] == 0], set()
while free:                                   # referans sayımı
    o = free.pop(); dead.add(o)
    for j in refs[o]:
        rc[j] -= 1
        if rc[j] == 0: free.append(j)
print("süpürülen", garbage, "ref.sayımı:", sorted(dead))

Kendi CSV’ni yükle

Çıktı

Çıktı burada görünecek.

Nasıl çalışır

Kökler, programın doğrudan tuttuğu nesnelerdir (yığındaki değişkenler, global değişkenler).
İşaretle: köklerden başlayıp her işaretçiyi izleyerek ulaşılan her nesneye işaret konur (bir dalga gibi yayılır).
Süpür: işareti olmayan her nesne silinir ve belleği geri verilir. Birbirini gösteren döngü de işaretsiz kalır, o da silinir.
Referans sayımı her nesnenin kaç kez gösterildiğini sayar ve sayaç 0 olunca siler. Döngüdeki her nesnenin sayacı en az 1 kalır: döngü sonsuza dek bellekte kalır (sızıntı).
Şunu dene: tohumu değiştir; grafik değişir, ama işaretle-süpür her seferinde tam olarak ulaşılamayanları siler, referans sayımı döngüyü hiç silemez.

Neden önemli

JVM, V8 (JavaScript), Go, .NET ve Python'un döngü toplayıcısı bu fikrin üzerine kuruludur; Python ayrıca referans sayımı da yapar, döngüler için ikisini birlikte kullanır. ROS 2 düğümleri gibi günlerce çalışan robot yazılımında asıl tehlike unutulmuş bir referanstır: bir listede tutulan eski kareler hep ulaşılabilir kalır ve hiçbir toplayıcı onları silemez.

ESOF 323, 11. hafta: robotlarda derin öğrenme →