Profilleme ve Karşılaştırmalı Ölçüm

Önceki ders veri düzeninin bir döngünün bellek bedelini nasıl değiştirdiğini gösterdi, ama ders bir şeyi varsaydı: hangi döngünün önemli olduğunu önceden biliyorduk. Gerçek bir programda bu bilgi yoktur. Eniyilenecek yeri tahminle seçmek, önemli olmayan bir yere emek harcamanın en kısa yoludur. Bu ders, hangi yerin sıcak olduğunu ölçerek bulmayı anlatıyor. Kursun ölçtüğü soru yine aynı: düzenek bedeli nereye taşıyor? Cevabın sınıfı koşumdur: profilleme koşarken ödenen bir düzenektir ve sonucunu koşan program verir. M10/K03’te “kaç kez koştu” sorusunda sayı ölçünün kendisiydi; burada sayı kanıt aracıdır ve ders sınıf adıyla cevaplanır. Süre basılmaz: süre makineye ve yüke bağlıdır, sıcak nokta ise sayaçtan bulunur.

İki Yöntem: Enstrümantasyon ve Örnekleme

Bir profilleyici iki yoldan veri toplar. Enstrümantasyon, programın kendisine sayaç yerleştirmektir: her işlev girişinde ya da her döngü adımında bir sayaç artırılır, program bitince sayaçlar okunur. Sayım kesindir, çünkü her olay sayılır; ama sayaçlar koda dokunur, ölçülen program artık ölçülmemiş programdan farklıdır.

Örnekleme ise programın kodunu değiştirmez. Profilleyici programı belirli aralıklarla durdurur ve o anda hangi işlevin koştuğuna bakar; yeterince çok bakışta en sık görülen işlev sıcak noktadır. Örneklemenin yükü daha küçüktür ama sonucu yaklaşıktır ve zamanlamaya bağlıdır; aynı program iki koşuda biraz farklı dağılım verir. Bu derste örneklemeyi koşturmuyoruz, çünkü çıktısı koşuma bağlıdır; enstrümantasyonla çalışıyoruz, çünkü çıktısı sayıdır ve her koşuda aynıdır.

Örnekleme Bir İz Üzerinde

Örneklemenin modelini koşuma bağlamadan kurabiliriz. Programın her adımında hangi işlevin koştuğunu bir iz olarak düşünelim: iz, adım sırasıyla işlev kimliklerinin dizisidir. Örnekleyici bu izin her periyot. adımına bakar ve bulduğu kimliği sayar. Gerçek bir örnekleyici izi görmez, durdurduğu anda yalnızca o anki işlevi görür; burada iz önceden bilindiği için örneklemenin ne bulacağını hesaplayabiliriz. İz, yüz adım hazirla ve ardından 4950 adım ara koşan bir programa karşılık gelir: toplam 5050 adım.

Örnekleme iki şey yapar. Sıcak noktayı bulur, çünkü uzun süren işlev daha çok bakışa denk gelir. Ama sayımı kesin vermez: bakışlar izin belirli noktalarına düşer ve bu noktalar kaydırmaya bağlıdır. Aynı izi sıfırıncı adımdan başlayarak ya da otuz beşinci adımdan başlayarak örneklersek farklı sayılar elde ederiz. Sıcak nokta değişmez, ama kısa süren işlevin payı oynar.

// ornek.hpp — bir iz uzerinde periyodik ornekleme modeli
#pragma once
#include <array>
#include <cstddef>
#include <vector>

constexpr int ISLEV_HAZIRLA = 0;
constexpr int ISLEV_ARA = 1;

struct OrnekSayim {
    std::array<int, 2> adet{};
};

inline std::vector<int> iz_kur() {
    std::vector<int> iz;
    for (int i = 0; i < 100; ++i) iz.push_back(ISLEV_HAZIRLA);
    for (int i = 0; i < 4950; ++i) iz.push_back(ISLEV_ARA);
    return iz;
}

inline OrnekSayim ornekle(const std::vector<int>& iz, std::size_t periyot, std::size_t kaydirma) {
    OrnekSayim sayim;
    for (std::size_t i = kaydirma; i < iz.size(); i += periyot) ++sayim.adet[iz[i]];
    return sayim;
}

Periyot yetmiş seçildi. Bu sayı bir model parametresidir; gerçek bir örnekleyicinin aralığı zamanla ölçülür ve burada karşılığı yoktur. Kaydırma sıfır olduğunda bakışlar 0, 70, 140, … adımlarına düşer; yüz adımlık hazirla bölgesine iki bakış girer. Kaydırma otuz beş olduğunda bakışlar 35, 105, … adımlarına düşer ve bölgeye yalnızca biri girer. Sayıyı basan program yalnızca bu hesabı koşturur; hesabın sonucu her koşuda aynıdır, çünkü iz sabittir ve gerçek örneklemenin zamanlama gürültüsü modelde yoktur.

Sayaç Yerleştirmek

Aşağıdaki program yüz değerin içinde aynı olan çiftleri bulur. Üç işlem sayılır: hazirla, bir değerin üretilmesi; ara, iki değerin karşılaştırılması; ikiz, eşit çift bulunması. Sayaçlar bir Profil yapısında durur ve işlevlere parametre olarak geçilir; sonuç yalnızca program bitince okunur.

// profil.hpp — sayaclar ve profillenen islemler
#pragma once
#include <cstddef>
#include <vector>

struct Profil {
    long hazirla = 0;
    long ara = 0;
    long ikiz = 0;
};

inline int deger_hazirla(Profil& p, int i) {
    ++p.hazirla;
    return i % 50;
}

inline int ikizleri_say(const std::vector<int>& v, Profil& p) {
    int bulunan = 0;
    for (std::size_t i = 0; i < v.size(); ++i) {
        for (std::size_t j = i + 1; j < v.size(); ++j) {
            ++p.ara;
            if (v[i] == v[j]) {
                ++p.ikiz;
                ++bulunan;
            }
        }
    }
    return bulunan;
}

deger_hazirla i % 50 döndürür; yüz değer üretilince her değer iki kez bulunur. Bu yüzden elli çift beklenir. ikizleri_say iç içe iki döngüyle her çifti bir kez karşılaştırır; yüz değerde çift sayısı 100 * 99 / 2 = 4950 olur.

Sıcak Noktayı Eniyilemek: Önce ve Sonra

Sayaç ara işlemini gösterdi, ama bu yalnızca bir teşhistir. Teşhisin değeri, ardından yapılan değişikliği ölçebilmesidir. Eşit çiftleri bulmak için her çifti karşılaştırmak gerekmez: değerlerin kaç kez geçtiğini bir frekans tablosunda saymak ve her değer için c * (c - 1) / 2 hesaplamak aynı sayıyı verir. Yüz değeri bir kez gezmek yüz adımdır; elli kovayı bir kez gezmek elli adım daha ekler.

Karşılaştırma adil olsun diye iki yazım aynı sayaca, aynı girdiye ve aynı sonuç tipine sahiptir. ara burada “ana döngünün adımı” anlamına gelir: eski yazımda bir karşılaştırma, yenisinde bir değer okuma ya da bir kova toplama. İki yazımın adımları aynı cins işler değildir; bu yüzden sayı iki yazımın işlem sayısını karşılaştırır, süresini değil.

// eniyi.hpp — frekans tablosuyla ayni sonucu veren ikinci yazim
#pragma once
#include <algorithm>
#include <vector>

#include "profil.hpp"

inline int ikizleri_say_tablo(const std::vector<int>& v, Profil& p) {
    int en_buyuk = *std::max_element(v.begin(), v.end());
    std::vector<int> sayim(static_cast<std::size_t>(en_buyuk) + 1, 0);
    for (int x : v) {
        ++sayim[static_cast<std::size_t>(x)];
        ++p.ara;
    }
    int bulunan = 0;
    for (int c : sayim) {
        bulunan += c * (c - 1) / 2;
        ++p.ara;
    }
    return bulunan;
}

Yeni yazım yüz değeri bir kez ve elli kovayı bir kez gezer: 150 adım. Eski yazım 4950 adım atıyordu. İki yazım da elli çift buluyor; eniyileme sonucu değiştirmedi, yalnızca sıcak noktanın boyutunu küçülttü. Sayı iki yazımın işlem sayısını karşılaştırır. Sürenin düşüp düşmediği ise başka bir sorudur ve bu derste cevaplanmaz.

Karşılaştırmalı Ölçümün Kuralları

Profilleme bir programın içinde nerenin sıcak olduğunu söyler. Karşılaştırmalı ölçüm ise iki yazımı aynı soruya karşı yarıştırır. Süreyle yapıldığında dört kural gerekir ve hiçbiri kendiliğinden sağlanmaz. Birincisi ısınma: ilk koşu, önbellekleri ve tembel kurulan yapıları doldurduğu için sonraki koşulardan farklıdır; ilk koşu atılmalı ya da ayrıca raporlanmalıdır. İkincisi yineleme: tek bir koşu, o anki yüke bağlıdır; birçok koşunun dağılımına bakılmalıdır. Üçüncüsü aynı girdi: iki yazım farklı girdilerle ölçülürse fark girdiden de gelebilir. Dördüncüsü ölü kod silme: standart, gözlenebilir davranışı değiştirmeyen hesabın derleyici tarafından silinmesine izin verir; sonucu hiçbir yerde kullanılmayan bir hesap ölçülürken hiç koşmamış olabilir. Çözüm sonucu kullanmaktır: bir yere yazmak ya da basmak.

Bu derste süre basmıyoruz, ama dört kural sayaçla ölçerken de geçerlidir. İlk üçü aşağıda ayrı bir ölçüm programında uygulanır. Dördüncüsü için: aşağıdaki ikizleri_say işlevinin sonucu bulunan olarak döndürülüp basılır, böylece hesap silinemez.

Ölçümün Nerede Başladığı

Isınma kuralı, ölçümün nerede başladığının sonucu değiştirebileceğini söyler. Bunu sayaçla da gösterebiliriz. Bir tablo ilk sorguda kurulur, sonraki sorgularda hazır bulunur. Kurulum yüz adım, her sorgu on adımdır; ilk sorguyu ölçüme dahil etmek ya da etmemek sonucu değiştirir.

// tablo.hpp — ilk cagrida kurulan tablo ve sorgu adimlari
#pragma once
#include <vector>

struct Tablo {
    std::vector<int> deger;
    bool hazir = false;
};

inline long sorgula(Tablo& t, int bas) {
    long adim = 0;
    if (!t.hazir) {
        for (int i = 0; i < 100; ++i) {
            t.deger.push_back(i * i);
            ++adim;
        }
        t.hazir = true;
    }
    long toplam = 0;
    for (int k = 0; k < 10; ++k) {
        toplam += t.deger[bas + k];
        ++adim;
    }
    (void)toplam;
    return adim;
}

adim yerel bir sayaçtır: işlevin kendi adımlarını sayar ve her çağrıda yeniden sıfırdan başlar. Tablo hazir bayrağıyla ilk çağrıda kurulur; ikinci çağrıda bayrak doludur ve kurulum atlanır.

Isınma Kuralını Sayaçla Uygulamak

Dört kuraldan ilk üçü bir ölçüm programında şöyle görünür. Aynı girdi: her koşuda sorgula aynı bas=0 değeriyle çağrılır. Yineleme: beş koşu yapılır. Isınma: ilk koşu ayrı raporlanır ya da ortalamadan çıkarılır. Her koşuda tablo aynı nesnede kalır, yani ilk çağrı kurulumu yapar, sonrakiler yapmaz.

// olcum.hpp — yineleme, isinma ve ortalama adim
#pragma once
#include <vector>

#include "tablo.hpp"

struct IsinmaSonucu {
    long isinmasiz = 0;
    long isinmali = 0;
    int yineleme = 0;
};

inline IsinmaSonucu isinma_olc(int yineleme) {
    Tablo tablo;
    std::vector<long> adimlar;
    for (int i = 0; i < yineleme; ++i) adimlar.push_back(sorgula(tablo, 0));
    long hepsi = 0;
    long ilk_haric = 0;
    for (int i = 0; i < yineleme; ++i) {
        hepsi += adimlar[i];
        if (i > 0) ilk_haric += adimlar[i];
    }
    IsinmaSonucu sonuc;
    sonuc.yineleme = yineleme;
    sonuc.isinmasiz = hepsi / yineleme;
    sonuc.isinmali = ilk_haric / (yineleme - 1);
    return sonuc;
}

Isınmasız ortalama beş koşunun hepsini içerir: (110 + 10 + 10 + 10 + 10) / 5 = 30. Isınmalı ortalama ilk koşuyu atar: (10 + 10 + 10 + 10) / 4 = 10. İki sayı doğrudur, ama farklı şeyi ölçer: ilki “bu işlevi sıfırdan beş kez çağıran bir program ne öder”, ikincisi “hazır bir tabloya bir sorgunun maliyeti nedir”. Hangisinin hangi soruya cevap verdiğini yazmadan bir sayı vermek yanıltıcıdır.

Ölçüm: Sıcak Nokta Hangisi

Aşağıdaki program üç sayacı okur, en yüksek olanı sıcak nokta olarak seçer ve tabloyu iki kez sorgular.

// profil_olcumu.cpp — aracli profil ve tembel kurulan tablo
#include <iostream>
#include <vector>

#include "eniyi.hpp"
#include "olcum.hpp"
#include "ornek.hpp"
#include "profil.hpp"
#include "tablo.hpp"

int main() {
    Profil p;
    std::vector<int> v;
    for (int i = 0; i < 100; ++i) v.push_back(deger_hazirla(p, i));
    int bulunan = ikizleri_say(v, p);
    std::cout << "aracli profil kosum hazirla=" << p.hazirla << " ara=" << p.ara
              << " ikiz=" << p.ikiz << "\n";

    const char* sicak = "hazirla";
    long en_cok = p.hazirla;
    if (p.ara > en_cok) { sicak = "ara"; en_cok = p.ara; }
    if (p.ikiz > en_cok) { sicak = "ikiz"; en_cok = p.ikiz; }
    std::cout << "sicak nokta " << sicak << " bulunan=" << bulunan << "\n";

    long artis = p.hazirla + p.ara + p.ikiz;
    std::cout << "enstrumantasyon kosum artis=" << artis << "\n";

    std::vector<int> iz = iz_kur();
    OrnekSayim sifir = ornekle(iz, 70, 0);
    OrnekSayim otuzbes = ornekle(iz, 70, 35);
    std::cout << "ornekleme kosum kaydirma=0 hazirla=" << sifir.adet[ISLEV_HAZIRLA]
              << " ara=" << sifir.adet[ISLEV_ARA] << "\n";
    std::cout << "ornekleme kosum kaydirma=35 hazirla=" << otuzbes.adet[ISLEV_HAZIRLA]
              << " ara=" << otuzbes.adet[ISLEV_ARA] << "\n";

    Profil p2;
    int bulunan_tablo = ikizleri_say_tablo(v, p2);
    std::cout << "eniyileme kosum once=" << p.ara << " sonra=" << p2.ara
              << " bulunan=" << bulunan << "/" << bulunan_tablo << "\n";

    Tablo tablo;
    long ilk = sorgula(tablo, 0);
    long ikinci = sorgula(tablo, 10);
    std::cout << "tembel tablo kosum ilk=" << ilk << " ikinci=" << ikinci << "\n";

    IsinmaSonucu isinma = isinma_olc(5);
    std::cout << "isinma kosum isinmasiz=" << isinma.isinmasiz
              << " isinmali=" << isinma.isinmali << " yineleme=" << isinma.yineleme << "\n";
    return 0;
}

aracli profil kosum hazirla=100 ara=4950 ikiz=50
sicak nokta ara bulunan=50
enstrumantasyon kosum artis=5100
ornekleme kosum kaydirma=0 hazirla=2 ara=71
ornekleme kosum kaydirma=35 hazirla=1 ara=71
eniyileme kosum once=4950 sonra=150 bulunan=50/50
tembel tablo kosum ilk=110 ikinci=10
isinma kosum isinmasiz=30 isinmali=10 yineleme=5

EB18. Birinci satır üç sayacı verir: yüz değer hazırlandı, 4950 karşılaştırma yapıldı, 50 eşit çift bulundu. Sıcak nokta sayaçtan okunur: ara en büyük sayaçtır ve hazirla’nın kırk dokuz katından fazladır. Eniyilenecek yer ikizleri_say içindeki iç içe döngüdür; deger_hazirla ya da eşit çiftleri sayma değil. Bu seçimi yapan tahmin değil, sayaçtır.

EB19. İkinci satır bulunan=50 ile eşit çiftlerin sayısını basar. Sonucun basılması ölü kod silmeye karşı da bir güvencedir: hesap kullanıldığı için derleyicinin onu silmesi gözlenebilir davranışı değiştirirdi.

EB20. Sıfır kaydırmayla örnekleme hazirla=2 ara=71, otuz beş kaydırmayla hazirla=1 ara=71 verdi. Gerçekte yüz adım, 5050 adımın yaklaşık yüzde ikisidir ve iki koşu da hazirla’yı bu payın etrafında, ama farklı sayıda gördü. İki koşuda da sıcak nokta ara. Örneklemenin söylediği “hangisi sıcak” sorusunun cevabıdır; küçük işlevlerin payı için kaydırmaya bağlı bir yuvarlama hatası taşır.

EB21. Altıncı satır eniyilemenin işlem sayısını gösterir: once=4950, sonra=150. İkisi de bulunan=50 verdi; sonuç değişmedi. Önce ve sonra aynı girdiye ve aynı sayaca bağlı olduğu için karşılaştırma geçerlidir. Sayı süre değildir: iki yazım farklı cins adım atar ve süreyle ilgili hüküm vermek için bu sayı yetmez.

EB22. Isınmasız ortalama 30, ısınmalı ortalama 10; ikisi de aynı girdiyle ve beş yinelemeyle hesaplandı. Farkın kaynağı tek bir koşudur: kurulumu yapan ilk koşu. Beş yineleme bu bir koşunun payını ortalamada seyreltti ama silmedi. Yineleme ısınmanın yerini tutmaz; kurulumu yapan koşu ayrıca adlandırılmalıdır.

EB23. Enstrümantasyonun kendisi de iş yaptı: hazirla sayacı yüz, ara sayacı 4950, ikiz sayacı elli kez artırıldı; toplam artis=5100. Ölçülen program, ölçülmemiş programdan 5100 artış kadar farklıdır. Örnekleme kodu değiştirmediği için bu farkın çoğundan kaçınır; bedeli ise kesin sayımdan vazgeçmektir.

Sınırlayıcı Ölçüm

Bu dersin ölçtüğü düzenek, sayaçla sıcak noktayı bulmaktır; tembel tablo satırı onun sınırını gösterir. Aynı sorgula işlevi ilk çağrıda ilk=110 adım, ikincide ikinci=10 adım saydı: kurulum ilk ölçüme girdi, ikinciye girmedi. İki sorguyu karşılaştırıp “ikinci sorgu on bir kat az iş yapıyor” demek yanlış olurdu; kurulum bir kez ödeniyor ve sonra hazır bekliyor.

Bu, ölçümün başladığı yere bağlı olduğunu gösterir. Ölçüm ilk çağrıdan başlıyorsa tablonun kurulumu dahildir; ikinci çağrıdan başlıyorsa dahil değildir. İki sonuç da doğrudur, ama farklı sorulara cevap verir. Bir profilin sınırı şudur: sayaç ne sayıyorsa onu söyler; hangi koşuyu ölçüme aldığınız ise sonucu sizin seçimleriniz belirler. Bu yüzden her ölçümün yanında başlangıç noktası da yazılır.

Özet

• Bu dersin ölçtüğü düzenek bedeli koşum sınıfına taşır: profilleme koşarken ödenir ve sonucu koşan program verir; ölçü süre değil, sayaçtır.
• Enstrümantasyon koda sayaç yerleştirir ve kesin sayar ama koda dokunur; örnekleme kodu değiştirmez, yükü daha küçüktür ama sonucu yaklaşıktır.
• Sıcak nokta tahminden değil, sayaçtan bulunur: aracli profil üç sayaçtan ara sayacını 4950 ile en yüksek buldu.
• Karşılaştırmalı ölçüm ısınma, yineleme, aynı girdi ve ölü kod silme kurallarını ister; sonucu kullanmak son kurala karşı güvencedir.
• tembel tablo aynı işlevi ilk çağrıda 110, ikincide 10 adımda saydı: ölçümün nerede başladığı sonucu değiştirir, bu yüzden başlangıç noktası ölçümle birlikte yazılır.

Sonraki Adım

Profil sıcak noktayı bulduktan sonra bir başka bedel kalır: kod ne kadar sık yeniden derleniyor. Bir sonraki ders derleme süresini yönetmeyi açıyor: gizleme deyimi derlemeden kazandığını nereye ödüyor sorusuyla başlık bağımlılığını azaltacağız.