Çöp Toplama

Önceki derste bırakma kararını programın kendisi verdi: b ve d bırakıldı ve yerleri geri alındı. Bu kararın iki yanlış biçimi vardır. Bırakılmayan bir blok, program bitene kadar kullanılamaz kalır. Bırakıldıktan sonra kullanılan bir adres ise başka bir isteğe verilmiş belleği okur ya da yazar. İkisi de kaynak metinde görünmez; ancak koşum sırasında ortaya çıkar.

Bu ders kararı programdan alıp çalışma zamanına devreden düzeni modeller. Devir bir ölçüt gerektirir — hangi nesnenin hâlâ gerekli olduğuna bakılarak değil, hangisine ulaşılabildiğine bakılarak karar verilir. İşaretle ve süpür yönteminin kendisi ile erişilebilirlik ölçütü bu katalogda daha önce, Eşzamansız JavaScript ve Çalışma Zamanı kursunun Bellek ve Başarım konusundaki Çöp Toplama dersinde kurulmuştur ve burada tekrarlanmaz. Bu dersin eklediği tek şey ölçümdür: devir kaç adıma mal oluyor ve o adım sayısı neye bağlı.

Taban, Kurulum ve Bedelin Adı

Soyutlamasız taban elle bırakmadır. Toplayıcı yoktur, tarama yoktur, duraklatma yoktur; bir bloğun ömrü program metninde yazılıdır. Bedeli koşumda değil, doğrulukta ödenir.

Kurulum bir izlemeli çöp toplayıcıdır. Kök kümesinden başlanır, başvurular izlenir, ulaşılan her nesne işaretlenir; işaretlenmemiş nesnelerin yeri geri alınır. Bedelin adı duraklatmadır (pause) ve bu derste duraklatma bir süre değil, bir adım sayısıdır: kaç nesne tarandı.

• BD13 — Nesne çizgesi ortak tanımın modelidir: 40 nesne, tohum 20260218, kök kümesi ilk üç nesne. Bağlantılar üreteçten gelir ve her koşumda aynıdır.
• BD14 — Bir nesnenin taranması bir adımdır; nesnenin boyutu ve taşıdığı bağlantı sayısı adım sayısını değiştirmez.
• BD15 — Toplama, program tamamen durdurulmuşken tek parça hâlinde yapılır. Artımlı ya da eşzamanlı toplama bu modelde yoktur.
• BD16 — Süpürme, işaretlenmemiş nesnelerin yerini geri almak için bütün nesne listesini bir kez dolaşır; bu da adım başına bir nesnedir.

"""M01/K05 ortak tanim (kesit): nesne cizgesi , erisilebilirlik ve isaretle-supur."""
TOHUM = 20260218


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def nesne_cizgesi(tohum=TOHUM, n=40, kok=3):
    r = uretec(tohum)
    baglanti = {i: [] for i in range(n)}
    for i in range(n):
        for _ in range(r(3)):
            h = r(n)
            if h != i and h not in baglanti[i]:
                baglanti[i].append(h)
    return baglanti, list(range(kok))


def isaretle_supur(baglanti, kokler):
    goruldu, yigit, tarama = set(), list(kokler), 0
    while yigit:
        d = yigit.pop()
        if d in goruldu:
            continue
        goruldu.add(d)
        tarama += 1
        for h in baglanti[d]:
            yigit.append(h)
    return {"erisilebilir": len(goruldu), "toplanan": len(baglanti) - len(goruldu),
            "tarama": tarama}


G, K = nesne_cizgesi()
print("nesne:", len(G), "| baglanti:", sum(len(v) for v in G.values()), "| kok:", len(K))
print("taban olcumu:", isaretle_supur(G, K))
print()
print("kok  erisilebilir  toplanan  isaretleme  supurme  toplam is  toplanan basina")
for kok in (1, 2, 3, 4, 6, 8, 12):
    g, k = nesne_cizgesi(kok=kok)
    r = isaretle_supur(g, k)
    toplam = r["tarama"] + len(g)
    print(f"{kok:3d}  {r['erisilebilir']:12d}  {r['toplanan']:8d}  {r['tarama']:10d}"
          f"  {len(g):7d}  {toplam:9d}  {toplam / r['toplanan']:15.2f}")

nesne: 40 | baglanti: 44 | kok: 3
taban olcumu: {'erisilebilir': 17, 'toplanan': 23, 'tarama': 17}

kok  erisilebilir  toplanan  isaretleme  supurme  toplam is  toplanan basina
  1             3        37           3       40         43             1.16
  2             7        33           7       40         47             1.42
  3            17        23          17       40         57             2.48
  4            19        21          19       40         59             2.81
  6            21        19          21       40         61             3.21
  8            23        17          23       40         63             3.71
 12            25        15          25       40         65             4.33

Üç sayı yan yana. Taban: elle bırakma, 0 tarama adımı, 0 duraklatma. Kurulum: üç köklü izlemeli toplayıcı, 40 nesnenin 17’si erişilebilir, 23’ü toplanıyor. Bedel: 17 adımlık duraklatma ve onu izleyen 40 adımlık süpürme geçişi, toplam 57 adım.

Erişilebilirliğin bir gezinme olduğuna dikkat edin: kök kümesinden başlayıp bağlantıları izleyen, gördüğünü bir daha ziyaret etmeyen bir dolaşma. Veri Yapıları kursundaki çizge gezinmesi burada yeniden tanımlanmıyor, doğrudan çağrılıyor; tek yenilik, ziyaret sayısının bir maliyet olarak sayılmasıdır.

Kök kümesinin ne olduğu da bu kursun kurduğu düzenden okunur. Bellek Düzeni dersindeki adres uzayında toplayıcının “başlangıç noktası” sayacağı yerler bellidir: her iş parçacığının kendi yığıtında duran yerel değişkenler, başlatılmış ve başlatılmamış veri bölmelerindeki küresel değişkenler ve o anda yazmaçlarda tutulan başvurular. Bu üçü, sürecin kendi kodunun elle verdiği bir liste değildir; adres uzayının yapısından okunur. Modelde aynı küme kok parametresidir ve büyüklüğü doğrudan bir maliyet kalemidir — kök sayısı arttıkça gezinme derinleşir. Kökler dışındaki hiçbir yerden başlanmaz; bu yüzden çizgede birbirine başvuran ama kökten kesilmiş bir nesne kümesi, kaç bağlantı taşırsa taşısın toplanır.

Duraklatma Neyle Orantılı

Tablonun ilk iki sütunu bir arada okunduğunda beklenmedik bir düzen çıkıyor. Kök sayısı 1 iken 37 nesne toplanıyor ve duraklatma 3 adım. Kök sayısı 12 iken yalnız 15 nesne toplanıyor ve duraklatma 25 adım. Toplanan çöp azaldıkça duraklatma büyüyor.

Bu ters ilişki bir tesadüf değildir, yöntemin tanımından çıkar: işaretleme yalnız erişilebilen nesneleri ziyaret eder. Ölü bir nesne hiç ziyaret edilmez — ona zaten ulaşılamıyordur. Aşağıdaki kurgu, ortak tanımın çizgesinden bağımsız olarak aynı ilişkiyi yalıtıyor: yaşayan nesne sayısı sabit tutulup ölü nesne sayısı otuz kat büyütülüyor.

"""Duraklatma neyle orantili: yasayan nesne sabit , cop degisken."""


def isaretle_supur(baglanti, kokler):
    goruldu, yigit, tarama = set(), list(kokler), 0
    while yigit:
        d = yigit.pop()
        if d in goruldu:
            continue
        goruldu.add(d)
        tarama += 1
        for h in baglanti[d]:
            yigit.append(h)
    return {"erisilebilir": len(goruldu), "toplanan": len(baglanti) - len(goruldu),
            "tarama": tarama}


def kurgu(yasayan, olu):
    """Yasayanlar kokten zincirle erisilir , olu nesneler kendi aralarinda baglidir."""
    baglanti = {i: [] for i in range(yasayan + olu)}
    for i in range(yasayan - 1):
        baglanti[i].append(i + 1)
    for j in range(yasayan, yasayan + olu):
        baglanti[j].append(yasayan + (j - yasayan + 1) % olu)
    return baglanti, [0]


print("yasayan  olu  toplam  isaretleme  supurme  toplanan")
for yasayan, olu in ((8, 32), (8, 152), (8, 992), (32, 8), (200, 8)):
    g, k = kurgu(yasayan, olu)
    r = isaretle_supur(g, k)
    print(f"  {yasayan:5d}  {olu:4d}  {len(g):6d}  {r['tarama']:10d}"
          f"  {len(g):7d}  {r['toplanan']:8d}")

yasayan  olu  toplam  isaretleme  supurme  toplanan
      8    32      40           8       40        32
      8   152     160           8      160       152
      8   992    1000           8     1000       992
     32     8      40          32       40         8
    200     8     208         200      208         8

İlk üç satırda yaşayan nesne sayısı 8’de sabit ve ölü nesne sayısı 32’den 992’ye çıkıyor; işaretleme adımı 8’de kalıyor. Son iki satırda ölü nesne sayısı 8’de sabit ve yaşayan nesne sayısı 32’den 200’e çıkıyor; işaretleme adımı 32’den 200’e çıkıyor. Dersin cümlesi budur: duraklatmanın uzunluğu toplanan çöple değil, yaşayan nesneyle orantılıdır.

Bunun pratik sonucu doğrudandır. Çok sayıda kısa ömürlü nesne üreten bir program toplayıcıya pahalıya mal olmaz; bu nesneler hiç ziyaret edilmez. Pahalı olan, uzun süre yaşayan büyük bir nesne yapısıdır — her toplamada baştan sona yeniden taranır ve hiçbir zaman toplanmaz.

Süpürmenin Payı

İşaretleme yaşayanla orantılıysa, süpürme de toplamla orantılıdır: işaretlenmemiş nesnelerin yerini geri almak için listenin tamamı bir kez dolaşılır. Tabloda süpürme sütunu her satırda 40’tır, çünkü nesne sayısı değişmiyor.

Toplam iş bu ikisinin toplamıdır ve son sütun onu toplanan nesne başına indirger. Kök sayısı 1 iken toplanan nesne başına 1,16 adım harcanıyor, kök sayısı 12 iken 4,33 adım. Aradaki fark 3,7 kattır ve tamamı yaşayan nesne sayısındaki artıştan gelir. Toplayıcının verimi, öbekte ne kadar çöp olduğuna bağlıdır — çöp ne kadar çoksa toplama o kadar ucuzdur.

Süpürme adımının bu modeldeki payı da not edilmelidir: üç köklü koşumda toplam işin 40’ı süpürme, 17’si işaretleme. Yani duraklatmanın büyük parçası taramadan değil, listeyi dolaşmaktan geliyor. Yeri geri alırken nesneleri yaşayanların yanına kopyalayan bir toplayıcı bu geçişi tamamen kaldırır ve yalnız 17 adım öder; karşılığında yaşayan her nesneyi taşımak ve ona giden her başvuruyu güncellemek zorunda kalır. Bu ödünleşim, önceki dersteki sıkıştırmanın aynısıdır.

Süpürmenin bir de görünmeyen ucu vardır. Yeri geri alınan 23 nesnenin baytları öbeğe geri döner, yani önceki dersin ayırıcısına teslim edilir; oradan sonra dış parçalanma kuralları işlemeye başlar. Toplayıcı hangi nesnenin öleceğini belirler, nereye hangi boyutta boşluk açılacağını ise ölüm sırası belirler. Bu yüzden çöp toplama, bir ayırıcının yerini almaz; onun üzerine kurulur ve önceki derste ölçülen kırıntı sorununu miras alır. Kopyalayan bir toplayıcının taşımayı göze almasının nedeni de budur: taşıdığı nesneleri uç uca dizerek ayırmayı yeniden tek bir sınır kaydırmasına indirger.

Duraklatmayı Bölmek

Tek parça hâlinde 17 adım süren bir duraklatma, işaretlemeyi parçalara bölüp aralarında programa sıra vererek küçültülebilir. Bedelsiz değildir: iki parça arasında program çalıştığı için nesne çizgesi değişebilir, dolayısıyla değişen bölgenin yeniden taranması gerekir.

• BD17 — Her kesintiden sonra 2 nesnenin yeniden taranması gerekir. Bu sayı modelin parametresidir; gerçek bir gerçekleştirimde programın kesinti sırasında ne kadar başvuru değiştirdiğine bağlı olurdu.

"""Artimli toplama: duraklatmayi bolmenin bedeli. Yasayan nesne 17 , toplam 40."""
YASAYAN = 17          # 01. blogun olctugu erisilebilir nesne sayisi
TOPLAM = 40
YENIDEN = 2           # her kesintiden sonra yeniden taranmasi gereken nesne

print("parca  duraklatma sayisi  en uzun duraklatma  isaretleme isi  toplam is")
for parca in (17, 8, 4, 2, 1):
    sayi = -(-YASAYAN // parca)
    isaretleme = YASAYAN + (sayi - 1) * YENIDEN
    print(f"{parca:5d}  {sayi:17d}  {min(parca, YASAYAN):18d}"
          f"  {isaretleme:14d}  {isaretleme + TOPLAM:9d}")

parca  duraklatma sayisi  en uzun duraklatma  isaretleme isi  toplam is
   17                  1                  17              17         57
    8                  3                   8              21         61
    4                  5                   4              25         65
    2                  9                   2              33         73
    1                 17                   1              49         89

En uzun duraklatma 17 adımdan 1 adıma iniyor, toplam iş 57 adımdan 89 adıma çıkıyor. Kazanılan şey toplam maliyet değil, maliyetin dağılımıdır: bir kerede 17 adım durmak yerine 17 kez birer adım duruluyor ve program aralarda ilerliyor. Yanıt süresine bakan bir ölçüt bunu iyileşme sayar; toplam işe bakan bir ölçüt 1,56 kat kötüleşme sayar. İkisi de doğrudur ve hangisinin önemli olduğu ölçüte bağlıdır — bu, kursun ikinci iddiasının bu derste ödendiği yerdir.

Ne Sıklıkta Toplanmalı

Toplayıcının ne zaman çalışacağı da bir karardır ve iki maliyeti karşı karşıya getirir. Erken toplamak öbeği küçük tutar ama toplayıcıyı sık çalıştırır; geç toplamak toplayıcıyı seyrek çalıştırır ama öbeğin en yüksek noktasını yükseltir.

• BD18 — Program 200 nesne üretiyor ve her nesne üretildikten 30 adım sonra erişilemez hâle geliyor. Ömür sabittir; gerçek bir programda dağılım olurdu.

"""Toplama sikligi: bellek tepesi ile toplayici isi arasindaki odunlesim."""
NESNE = 200           # kac nesne uretiliyor
OMUR = 30             # bir nesne uretildikten kac adim sonra erisilemez oluyor

print("her N ayirmada bir  toplama  isaretleme isi  supurme isi  en yuksek yerlesik")
for n in (10, 25, 50, 100, 200):
    yerlesik, tepe, toplama, isaretleme, supurme = [], 0, 0, 0, 0
    for t in range(NESNE):
        yerlesik.append(t)
        tepe = max(tepe, len(yerlesik))
        if (t + 1) % n == 0:
            yasayan = [i for i in yerlesik if t < i + OMUR]
            toplama += 1
            isaretleme += len(yasayan)
            supurme += len(yerlesik)
            yerlesik = yasayan
    print(f"{n:18d}  {toplama:7d}  {isaretleme:14d}  {supurme:11d}  {tepe:18d}")

her N ayirmada bir  toplama  isaretleme isi  supurme isi  en yuksek yerlesik
                10       20             570          740                  40
                25        8             235          405                  55
                50        4             120          290                  80
               100        2              60          230                 130
               200        1              30          200                 200

On ayırmada bir toplayan kurulum öbeği en fazla 40 nesnede tutuyor ve toplayıcıya 1310 adım ödetiyor. Yalnız sonda toplayan kurulum 230 adım ödüyor ama öbek 200 nesneye kadar büyüyor. Beş kat düşük bellek tepesi, 5,7 kat toplayıcı işi karşılığında alınıyor. Bu iki uç arasındaki her nokta geçerli bir seçimdir ve seçimi yapan şey, makinede belleğin mi yoksa işlemcinin mi kıt olduğudur.

Erişilebilir Olan Toplanmaz

Ölçüt “gerekli mi” değil, “ulaşılabiliyor mu” sorusudur ve bu ayrım toplayıcının çözmediği sorunu tanımlar. Kök sayısı 3’ten 12’ye çıktığında toplanan nesne 23’ten 15’e düşüyor; çizgede hiçbir şey değişmedi, yalnız köklerden ulaşılan bölge büyüdü. Bir programda bu, artık kullanılmayan bir nesneyi bir listede ya da bir eşlemede tutmaya karşılık gelir: nesne gereksizdir, erişilebilirdir ve toplanmaz.

Bu yüzden çöp toplama bellek sızıntısını ortadan kaldırmaz, sızıntının biçimini değiştirir. Elle bırakmada sızıntı unutulan bir bırakma çağrısıdır; izlemeli toplamada sızıntı, kökten kesilmeyen bir başvurudur. İkisinde de sızıntı bir program kusurudur ve tanısı programda aranır.

Özet

• İzlemeli toplayıcı, 40 nesnelik çizgede üç kökten 17 nesneye ulaşıyor ve 23 nesneyi topluyor; duraklatma 17 tarama adımı, süpürme 40 adım, toplam iş 57 adımdır.
• Yaşayan nesne sayısı sabitken ölü nesne sayısı 32’den 992’ye çıkarıldığında işaretleme adımı 8’de kalıyor; ölü sayısı sabitken yaşayan sayısı 32’den 200’e çıkarıldığında adım 32’den 200’e çıkıyor.
• Duraklatma toplanan çöple değil yaşayan nesneyle orantılıdır; toplanan nesne başına maliyet 1,16 adımdan 4,33 adıma çıkarken değişen tek şey yaşayan nesne sayısıdır.
• Süpürme geçişi toplam nesne sayısıyla orantılıdır ve bu modelde toplam işin büyük payıdır; kopyalayan bir toplayıcı bu geçişi kaldırır, karşılığında taşıma ve başvuru güncelleme öder.
• İşaretlemeyi parçalara bölmek en uzun duraklatmayı 17 adımdan 1 adıma indiriyor ama toplam işi 57’den 89 adıma çıkarıyor; toplama sıklığını artırmak bellek tepesini 200’den 40 nesneye indirirken toplayıcı işini 230 adımdan 1310 adıma çıkarıyor.
• Ölçüt gereklilik değil erişilebilirliktir; kökten kesilmeyen gereksiz bir nesne toplanmaz, bu yüzden toplayıcı sızıntıyı ortadan kaldırmaz.

Sonraki Adım

Bu üç ders belleğin üç ayrı sorusunu ölçtü ve üçünde de veri koşum bitince yok oldu. Bir sürecin ürettiği verinin çoğu ise koşumdan uzun yaşamak zorundadır ve bunun için baytların adlandırıldığı, dizinlere yerleştirildiği ve sabit boyutlu bloklara bölündüğü ikinci bir soyutlama gerekir. Sonraki ders dosya sistemini modeller: altı dosyanın 4741 baytı 512 baytlık bloklara yerleştirilir, boşa giden bayt sayılır ve blok boyu süpürülerek iç parçalanma ile dosya düğümünün taşıması gereken blok listesi arasındaki ödünleşim ölçülür.