Gecikme Eniyilemesi

Önceki ders belirteci saydı ve önbelleğin onu on beş kata kadar düşürebildiğini gösterdi. Tablonun hiçbir sütunu kullanıcının beklediği şeyi ölçmüyordu. Oysa bir destek yardımcısında en görünür ölçüt budur ve onu belirleyen tek kaldıraç önbellek değildir.

Bekleme, ham süre olarak yazılamaz: aynı kod başka bir makinede başka bir sayı verir. Yazılabilen şey yapıdır. Bir isteğin yanıtı kaç ardışık çağrı bekliyor, o çağrılar aynı anda mı yoksa peş peşe mi yapılıyor, ve her çağrının giriş belirteci ne kadar. Bu ders üç kurulumu — küçük bağlam, büyük bağlam ve iki aşamalı çağrı — bu iki eksende karşılaştırır ve her birinin doğruluğunu yanına yazar. Sonra iki kurulum daha ekler, çünkü gecikmeyi düşürmenin iki ayrı yolu daha vardır ve ikisi de bedelsiz değildir.

• UK17. Kod bir benzeticidir; gerçek bir uç nokta çağrılmaz. Dağarcık, sorular ve yanıltıcı ek cümleler kurgudur, tohum 20260218.
• UK18. Bekleme adım ile sayılır. Bir çağrı 1 + giriş // 60 adım tutar: uzun giriş daha uzun bekletir.
• UK19. Dört gecikme sınıfı vardır. Tek çağrı: bir istek için tek bir çağrı beklenir. Zincir: ikinci çağrı birincinin yanıtını bekler. Paralel: iki çağrı aynı anda gönderilir, bekleme geç bitenindir. Toplu: çağrı bir yığının parçasıdır ve yığın dolana kadar beklenir.
• UK20. Ucuz ön süzgeç modelin dışındadır, hiç belirteç harcamaz ve dağarcıktan tek bir belge seçer. Parça sayımı yaptığı için yanıltıcı ek cümlelere takılır.
• UK21. Dağarcığın tamamı isteme konduğunda model belgeleri karşılaştırabildiği için anahtar öbeğini bütün olarak eşleştirir; bu, büyük bağlamın doğruluk üstünlüğünün kaynağıdır.
• UK22. İki aşamalı kurulumda birinci aşama, verilen belgenin yeterli olup olmadığını da bildirir. Bu bildirim onda bir yanılır; yalnız yetersiz denen istekler ikinci aşamaya tırmanır.
• UK23. Doğru yanıt, hem doğru belgeye dayanan hem etiketi doğru olan yanıttır.
• UK24. İş yükü 120 adımda 240 istektir, adım başına iki; otuz soru sırayla dolaşılır.
• UK25. Toplu kurulumda yığın boyu sekizdir; koşum sonunda eksik kalan yığın son adımda gönderilir.

Bağlamın Boyutu Hem Beklemeyi Hem Doğruluğu Belirler

Önce dağarcık, sorular ve iki seçim yordamı kurulur: ucuz ön süzgeç ile dağarcığın tamamının istemde olduğu durum. Ardından bir kolay ve bir yanıltıcı soru üzerinde ikisi yan yana konur.

# BENZETICI -- KURGUDUR. Gercek bir uc nokta cagrilmaz. Dagarcik, sorular ve
# yaniltici ek cumleler kurgudur, tohum 20260218.
TOHUM, M32 = 20260218, 0xFFFFFFFF
BIRIM = 60                       # bir adimin tasidigi giris belirteci


def uretec(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def sonraki():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return sonraki


def belirtecle(m):
    b = []
    for s in m.lower().replace(",", " , ").split():
        while len(s) > 5:
            b.append(s[:5])
            s = s[5:]
        b.append(s)
    return b


def izno(m):
    h = 2166136261
    for c in m:
        h = ((h ^ ord(c)) * 16777619) & M32
    return h


KONU = ["fatura", "ariza", "sayac", "tarife", "kesinti"]
BELGE = [("FT1", "fatura tutari", "fatura tutari hesap donemi ve gecikme farki"),
         ("FT2", "fatura odemesi", "fatura odemesi yontemleri ve borc gorunumu"),
         ("AR1", "ariza kaydi", "ariza kaydi acma ve ekip yonlendirme yordami"),
         ("AR2", "baglanti bozuklugu", "baglanti bozuk oldugunda uygulanan denetim"),
         ("SY1", "sayac endeksi", "sayac endeks okumasi ve duzeltme yordami"),
         ("SY2", "sayac degisimi", "sayac degisimi randevu kurallari ve sure taahhudu"),
         ("TA1", "tarife basamagi", "tarife basamaklari ve abone tipine gore ucret"),
         ("TA2", "tarife degisikligi", "tarife degisikligi basvurusu ve gecerlilik"),
         ("KS1", "planli kesinti", "planli kesinti duyurusu ve takip kurallari"),
         ("KS2", "mahalle kesintisi", "mahallede kesinti bildirimi ve donus suresi")]
BELGE = [{"kod": k, "konu": KONU[i // 2], "anahtar": a, "metin": m}
         for i, (k, a, m) in enumerate(BELGE)]
KALIP = ["{a} konusunda ne yapmam gerekiyor",
         "{a} icin gecerli kural nedir",
         "{a} ile ilgili son durum ne"]
SORU = []
for i, b in enumerate(BELGE):
    for j, k in enumerate(KALIP):
        m = k.format(a=b["anahtar"])
        if (i + j) % 3 == 1:                       # yaniltici ek cumle
            m += " " + BELGE[(i + 4) % 10]["metin"].split(" ve ")[-1]
        SORU.append({"b": i, "konu": b["konu"], "metin": m})
TAM = " ; ".join(f"{b['kod']} {b['metin']}" for b in BELGE)
YON = "Soruyu verilen belgeye dayanarak yanitla . Etiket ve belge kodu yaz . Belge: "


def sec(soru, tam):
    """tam=False: ucuz on suzgec (parca sayimi). tam=True: dagarcik istemde
    oldugundan model anahtar obegini butun olarak eslestirebilir."""
    st, p = belirtecle(soru["metin"]), []
    for b in BELGE:
        x = sum(t in belirtecle(b["metin"]) for t in st)
        if tam and all(t in st for t in belirtecle(b["anahtar"])):
            x += 8.0
        p.append(x)
    e = sorted(range(10), key=lambda i: (-p[i], i))
    return e[0], p[e[0]] - p[e[1]]


def cagir(soru, baglam, tohum=TOHUM, sira=0):
    """KURGU uc nokta. Verilen baglami okur; giris belirteci baglamla buyur."""
    bel = belirtecle(YON + baglam + " . Soru: " + soru["metin"])
    r = uretec((tohum ^ izno(soru["metin"])) + 7919 * sira)
    return (soru["konu"] if r() > 0.08 else KONU[int(r() * 5)]), len(bel)


def adim(g):
    return 1 + g // BIRIM


print("belge", len(BELGE), ", soru", len(SORU), ", tam dagarcik",
      len(belirtecle(TAM)), "belirtec")
z = sum(sec(s, False)[0] == s["b"] for s in SORU)
g = sum(sec(s, True)[0] == s["b"] for s in SORU)
print(f"dogru belgeye ulasan: on suzgec {z}/{len(SORU)} , tam dagarcik {g}/{len(SORU)}")
for j in (0, 8):
    s0 = SORU[j]
    i0, i1 = sec(s0, False)[0], sec(s0, True)[0]
    gk, gb = cagir(s0, BELGE[i0]["metin"])[1], cagir(s0, TAM)[1]
    print(f"\nsoru : {s0['metin']}")
    print(f"  dogru {BELGE[s0['b']]['kod']} , on suzgec {BELGE[i0]['kod']} , "
          f"tam dagarcik {BELGE[i1]['kod']}")
    print(f"  kucuk baglam {gk} belirtec -> {adim(gk)} adim ; "
          f"buyuk baglam {gb} belirtec -> {adim(gb)} adim")

belge 10 , soru 30 , tam dagarcik 121 belirtec
dogru belgeye ulasan: on suzgec 25/30 , tam dagarcik 30/30

soru : fatura tutari konusunda ne yapmam gerekiyor
  dogru FT1 , on suzgec FT1 , tam dagarcik FT1
  kucuk baglam 44 belirtec -> 1 adim ; buyuk baglam 154 belirtec -> 3 adim

soru : ariza kaydi ile ilgili son durum ne abone tipine gore ucret
  dogru AR1 , on suzgec TA1 , tam dagarcik AR1
  kucuk baglam 46 belirtec -> 1 adim ; buyuk baglam 156 belirtec -> 3 adim

İki sorunun karşılaştırılması ödünleşimin kaynağını gösteriyor. Kolay soruda iki yol da aynı belgeye ulaşıyor ve küçük bağlam üçte bir beklemeyle aynı işi yapıyor. Yanıltıcı sorudaysa ek cümle bir tarife belgesinin sözcüklerini taşıyor; parça sayan ön süzgeç TA1 diyor, oysa doğru belge AR1. Dağarcığın tamamı istemdeyken bu yanılma olmuyor, çünkü model anahtar öbeğini bütün olarak eşleştirebiliyor. Otuz soruda ön süzgeç 25’ini, tam dağarcık 30’unu doğru belgeye bağlıyor.

Bekleme tarafında da tablo nettir: küçük bağlam 44 belirteçle bir adım, büyük bağlam 154 belirteçle üç adım. İkisi de aynı gecikme sınıfındadır — tek çağrı — ama bekleme üç katıdır. Sınıf tek başına bir ölçü değildir; sınıfın içindeki bekleme giriş belirteciyle büyür.

Beş Kurulumun Sınıf ve Doğruluk Tablosu

Beş kurulum aynı akışta koşturulur. İki aşamalı kurulumda birinci aşama ucuz çağrıdır ve verilen belgenin yeterli olup olmadığını da bildirir; yetersiz diyenler ikinci aşamaya tırmanır. Paralel kurulumda iki çağrı aynı anda gönderilir. Sonuncusunda tırmanan istekler sekizli yığınlarda toplanır.

def akis():
    """120 adimda 240 istek, adim basina iki; sorular sirayla dolasilir."""
    return [(a, SORU[(2 * a + j) % len(SORU)]) for a in range(120) for j in (0, 1)]


def asama1(soru, tohum, sira):
    """Ucuz asama: on suzgecin verdigi tek belge . Model belgenin yeterli olup
    olmadigini da bildirir; bu bildirim onda bir yaniliyor."""
    i, _ = sec(soru, False)
    e, g = cagir(soru, BELGE[i]["metin"], tohum, sira)
    r = uretec((tohum ^ izno(soru["metin"])) + 31 * sira + 5)
    yeterli = (i == soru["b"]) != (r() < 0.10)
    return i, e, g, yeterli


def asama2(soru, tohum, sira):
    i, _ = sec(soru, True)
    e, g = cagir(soru, TAM, tohum, sira)
    return i, e, g


def kosum(kurulum, tohum=TOHUM):
    s = dict.fromkeys(("dogru", "giris", "cagri", "bekle", "tirman"), 0)
    sinif, yigin, n = {}, [], 0
    for a, soru in akis():
        n += 1
        i, e, g, yeterli = asama1(soru, tohum, n)
        if kurulum == "kucuk":
            s["giris"] += g
            s["cagri"] += 1
            s["bekle"] += adim(g)
            sinif["tek cagri"] = sinif.get("tek cagri", 0) + 1
            s["dogru"] += i == soru["b"] and e == soru["konu"]
            continue
        if kurulum == "buyuk":
            i2, e2, g2 = asama2(soru, tohum, n)
            s["giris"] += g2
            s["cagri"] += 1
            s["bekle"] += adim(g2)
            sinif["tek cagri"] = sinif.get("tek cagri", 0) + 1
            s["dogru"] += i2 == soru["b"] and e2 == soru["konu"]
            continue
        if kurulum == "paralel":                       # iki cagri ayni anda
            i2, e2, g2 = asama2(soru, tohum, n)
            s["giris"] += g + g2
            s["cagri"] += 2
            if yeterli:
                s["bekle"] += adim(g)
                sinif["paralel-erken"] = sinif.get("paralel-erken", 0) + 1
                s["dogru"] += i == soru["b"] and e == soru["konu"]
            else:
                s["bekle"] += max(adim(g), adim(g2))
                sinif["paralel"] = sinif.get("paralel", 0) + 1
                s["dogru"] += i2 == soru["b"] and e2 == soru["konu"]
            continue
        s["giris"] += g                                # iki asamali kurulumlar
        s["cagri"] += 1
        if yeterli:
            s["bekle"] += adim(g)
            sinif["tek cagri"] = sinif.get("tek cagri", 0) + 1
            s["dogru"] += i == soru["b"] and e == soru["konu"]
            continue
        s["tirman"] += 1
        i2, e2, g2 = asama2(soru, tohum, n)
        s["giris"] += g2
        s["cagri"] += 1
        s["dogru"] += i2 == soru["b"] and e2 == soru["konu"]
        if kurulum == "iki":
            s["bekle"] += adim(g) + adim(g2)
            sinif["zincir"] = sinif.get("zincir", 0) + 1
        else:                                          # ikinci asama yigin halinde
            yigin.append((a, adim(g), adim(g2)))
            if len(yigin) == 8:
                for a0, b1, b2 in yigin:
                    s["bekle"] += b1 + (a - a0) + b2
                sinif["toplu"] = sinif.get("toplu", 0) + 8
                yigin = []
    for a0, b1, b2 in yigin:                           # kosum sonunda kalan yigin
        s["bekle"] += b1 + (119 - a0) + b2
        sinif["toplu"] = sinif.get("toplu", 0) + 1
    return (s["dogru"] / n, s["bekle"] / n, s["giris"], s["cagri"], s["tirman"] / n,
            " , ".join(f"{k} {v / n:.4f}" for k, v in sorted(sinif.items())))


KURULUM = (("kucuk baglam", "kucuk"), ("buyuk baglam", "buyuk"),
           ("iki asamali", "iki"), ("paralel", "paralel"),
           ("iki asamali + toplu", "toplu"))
print("kurulum              dogru  bekleme  giris  cagri  tirmanan")
for ad, k in KURULUM:
    a = kosum(k)
    print(f"{ad:<19} {a[0]:.4f}  {a[1]:>7.4f}  {a[2]:>5}  {a[3]:>5}  {a[4]:>8.4f}")
print("\ngecikme sinifi dagilimi:")
for ad, k in KURULUM:
    print(f"  {ad:<19} {kosum(k)[5]}")
print("\nikinci kosum (tohum 20260219), dogru / bekleme / tirmanan:")
for ad, k in KURULUM:
    a = kosum(k, TOHUM + 1)
    print(f"  {ad:<19} {a[0]:.4f} / {a[1]:.4f} / {a[4]:.4f}")

kurulum              dogru  bekleme  giris  cagri  tirmanan
kucuk baglam        0.7750   1.0000  10376    240    0.0000
buyuk baglam        0.9292   3.0000  36976    240    0.0000
iki asamali         0.9167   1.7500  19716    300    0.2500
paralel             0.9167   1.5000  47352    480    0.0000
iki asamali + toplu 0.9167   3.5542  19716    300    0.2500

gecikme sinifi dagilimi:
  kucuk baglam        tek cagri 1.0000
  buyuk baglam        tek cagri 1.0000
  iki asamali         tek cagri 0.7500 , zincir 0.2500
  paralel             paralel 0.2500 , paralel-erken 0.7500
  iki asamali + toplu tek cagri 0.7500 , toplu 0.2500

ikinci kosum (tohum 20260219), dogru / bekleme / tirmanan:
  kucuk baglam        0.7792 / 1.0000 / 0.0000
  buyuk baglam        0.9250 / 3.0000 / 0.0000
  iki asamali         0.9083 / 1.6375 / 0.2125
  paralel             0.9083 / 1.4250 / 0.0000
  iki asamali + toplu 0.9083 / 3.3583 / 0.2125

İlk iki satır takasın uçlarıdır. Küçük bağlam en hızlı, en ucuz ve en yanlış olandır: bekleme 1,0000 adım, giriş 10376, doğruluk 0,7750. Büyük bağlam doğruluğu 0,9292‘ye çıkarıyor ve karşılığında beklemeyi üçe, giriş belirtecini 3,56 kata katlıyor. İki koşum farkı her iki satırda da 0,0042; aradaki 0,1542’lik doğruluk farkı bu farkın otuz katından fazla, yani tartışmasız ölçülmüştür.

Üçüncü satır iki aşamalı kurulumdur ve tablonun en dengeli satırıdır. İsteklerin 0,2500‘ü ikinci aşamaya tırmanıyor; geri kalan dörtte üç tek çağrıda bitiyor. Sonuç: bekleme 1,7500, yani büyük bağlamın 0,5833‘ü; giriş belirteci 19716, yani 0,5332‘si. Ödenen bedel iki kalemdir. Birincisi 60 ek çağrıdır (240’tan 300’e). İkincisi doğruluktur: 0,9292’den 0,9167’ye, yani 0,0125. Bu kayıp iki koşum farkının yaklaşık üç katıdır ve ölçülmüş sayılır, ama küçük bağlamın 0,1542’lik kaybının yanında küçük kalır. Tırmanma bildiriminin onda bir yanılması tam olarak buraya düşüyor.

Gecikmeyi Neyle Satın Aldığın

Dördüncü satır aynı doğruluğa daha kısa beklemeyle ulaşıyor: 1,5000 adım. Nedeni sınıf dağılımında yazılı — burada zincir yok, iki çağrı aynı anda gidiyor, dolayısıyla tırmanan istek ucuz çağrının bir adımını ikinci kez ödemiyor. Kazanç 0,2500 adımdır. Bedel sütununda duruyor: 480 çağrı ve 47352 giriş belirteci. Bu, iki aşamalının 2,40 katı ve büyük bağlamın bile 1,28 katı. Paralel kurulum, en pahalı kurulumun da üstüne çıkarak, hiçbir doğruluk kazanmadan yalnız bekleme satın alıyor. Gecikmeyi kısaltmanın bir yolu her zaman vardır; sorulacak soru, hangi sütunun karşılığında.

Son satır kursun ikinci iddiasının bu konudaki üçüncü örneğidir. Tırmanan istekleri sekizli yığınlarda göndermek doğruluğu değiştirmiyor (0,9167) ve giriş belirtecini de değiştirmiyor (19716) — çağrı sayısı bile aynı. Değişen tek şey beklemedir ve 1,7500’den 3,5542’ye çıkmıştır. Toplu kurulum, tabloda en yavaş satırdır; büyük bağlamın tek çağrısından bile yavaştır. Nedeni açıktır: yığının dolması beklenirken ilk giren istek boşuna oturur. Toplu çağrı bir verim düzeneğidir, bir gecikme düzeneği değildir; gecikme ölçütüne bakılmadan açıldığında ölçütü iki katına çıkarır.

İkinci koşum satırları bu okumayı doğruluyor. Tırmanan pay 0,2500’den 0,2125’e düşüyor ve bekleme sayıları onunla birlikte iniyor (1,7500 yerine 1,6375, 3,5542 yerine 3,3583). Yani iki aşamalı kurulumun bekleme kazancı tırmanma payına bağlıdır ve o pay koşumdan koşuma oynar. Sabit olan tek şey sıralamadır: paralel her koşumda en kısa, toplu her koşumda en uzun beklemeyi veriyor.

Özet

• Bekleme ham süre olarak değil, gecikme sınıfı ve adım sayısı olarak yazılır; küçük ve büyük bağlam aynı sınıftadır (tek çağrı) ama beklemeleri 1,0000 ve 3,0000 adımdır.
• Ucuz ön süzgeç otuz sorunun 25’ini doğru belgeye bağlıyor, dağarcığın tamamı 30’unu; küçük bağlamın doğruluğu 0,7750, büyük bağlamınki 0,9292.
• İki aşamalı kurulum isteklerin 0,2500’ünü zincire taşıyarak beklemeyi büyük bağlamın 0,5833’üne, giriş belirtecini 0,5332’sine indiriyor ve doğruluktan 0,0125 veriyor.
• Paralel kurulum beklemeyi 1,5000’e çekiyor ama 47352 giriş belirteciyle büyük bağlamın 1,28 katına çıkıyor: doğruluk kazanmadan yalnız bekleme satın alınıyor.
• İkinci aşamayı yığın hâlinde göndermek doğruluğu, belirteci ve çağrı sayısını hiç değiştirmeden beklemeyi 1,7500’den 3,5542’ye çıkarıyor; toplu çağrı bir gecikme düzeneği değildir.
• İki aşamalı kurulumun bekleme kazancı tırmanma payına bağlıdır ve o pay koşumdan koşuma 0,2500 ile 0,2125 arasında oynuyor.

Sonraki Adım

Üç derste dayanıklılık, önbellek ve gecikme ayrı ayrı ölçüldü ve her birinin yanına bir belirteç toplamı yazıldı: 10376, 19716, 47352. Bu sayılar bir kurulumu öbürüyle karşılaştırmaya yetiyor, ama tek bir soruyu yanıtlamıyor — bu toplam kimin arasında paylaşıldı. İki yüz kırk isteğin hepsi ortalama kadar mı harcadı, yoksa toplamın önemli bir bölümünü birkaç istek mi yuttu. Bir bütçe ortalamayla tutulmaz: ortalamanın altında kalan bir hattın en pahalı yüzde biri, tek başına bütçeyi aşabilir ve bu, toplamlara bakan hiçbir tabloda görünmez. Sonraki ders maliyeti istek başına yazar ve dağılımın kuyruğuna bakar.