Önbellek Dostu Veri Düzeni

Önceki iki ders eşzamanlılığın bedelini ölçtü: kilit kaç kez alınıyor, bir yayın kaç eşgüdüm noktası istiyor. Bu ders tek bir iş parçacığına dönüyor, çünkü bellekte verinin nasıl dizildiği eşzamanlılık olmadan da bedeli değiştirir. İşlemci belleği tek tek bayt olarak değil, önbellek satırı denen sabit boyutlu bloklar halinde taşır. Bir değere dokunduğunuzda onunla birlikte çevresindeki komşu baytlar da yakın belleğe gelir. Komşularının bir kısmına yakında dokunacaksanız bu iyi bir takastır; dokunmayacaksanız taşınan baytların çoğu boşa gitmiştir. Kursun ölçtüğü soru yine aynı: düzenek bedeli nereye taşıyor? Bu dersin cevabı bellek sınıfıdır. Satır boyunu ve adresleri basmıyoruz, çünkü ikisi de makineye bağlıdır; ölçü, bir döngünün art arda dokunduğu iki değerin bellekte yan yana olup olmadığını sayar.

Yerellik

İki tür yerellik vardır. Uzamsal yerellik, bir değere dokunan programın yakında onun komşusuna da dokunacağı beklentisidir; dizinin elemanlarını sırayla gezmek bunun örneğidir. Zamansal yerellik, bir değere dokunan programın yakında aynı değere yeniden dokunacağı beklentisidir; bir döngü değişkeni ya da bir toplam bunun örneğidir. Önbellek satırı, uzamsal yerelliği ödüllendirir: satırda yan yana duran değerler tek bir taşımayla gelir.

Çok boyutlu dizilerde aynı fikir satır ve sütun sırası olarak görünür. C++’ta int tablo[satir][sutun] satır sırasındadır: aynı satırın elemanları bitişiktir. Satırlar boyunca gezen iç döngü uzamsal yerelliğe uyar; sütunlar boyunca gezen iç döngü her adımda bir satır boyu atlar. Bu ayrımı aşağıda geçiş sayımıyla gösteriyoruz.

Yapı Dizisi ve Dizi Yapısı

Bir nokta kümesi üç alanla x, y ve z tutulur. İlk düzen yapı dizisidir (AoS): her nokta bir yapıdır ve bütün noktalar bir dizide durur. Bellekte sıra x0 y0 z0 x1 y1 z1 ... olur. İkinci düzen dizi yapısıdır (SoA): üç alanın her biri kendi dizisinde durur. Bellekte sıra x0 x1 x2 ... y0 y1 y2 ... z0 z1 z2 ... olur.

Yalnız x alanını dolaşan bir döngü, yapı dizisinde her adımda diğer iki alanı da atlar; bitişik olan x değerleri değil, aralarında y ve z olan değerlerdir. Dizi yapısında x değerleri yan yanadır. Aşağıdaki başlık iki düzeni ve ölçümü kurar. Ölçü, bir döngünün dokunduğu adresleri sırayla kaydeder ve art arda iki dokunuşun arasındaki mesafenin tam bir int kadar olup olmadığına bakar. Adres basılmaz; yalnızca sayı çıkar.

// dizilim.hpp — iki veri duzeni ve dokunuslari kaydeden olcum
#pragma once
#include <array>
#include <cstddef>
#include <cstdint>
#include <vector>

constexpr int NOKTA_SAYISI = 4;

struct Nokta {
    int x, y, z;
};

struct NoktaDizisi {
    std::array<Nokta, NOKTA_SAYISI> noktalar;
};

struct AlanDizileri {
    std::array<int, NOKTA_SAYISI> x, y, z;
};

inline NoktaDizisi yapi_dizisi_kur() {
    NoktaDizisi d;
    for (int i = 0; i < NOKTA_SAYISI; ++i) d.noktalar[i] = Nokta{i, 10 + i, 20 + i};
    return d;
}

inline AlanDizileri dizi_yapisi_kur() {
    AlanDizileri d;
    for (int i = 0; i < NOKTA_SAYISI; ++i) {
        d.x[i] = i;
        d.y[i] = 10 + i;
        d.z[i] = 20 + i;
    }
    return d;
}

inline bool bitisik(const int* once, const int* sonra) {
    auto a = reinterpret_cast<std::uintptr_t>(once);
    auto b = reinterpret_cast<std::uintptr_t>(sonra);
    return b - a == sizeof(int);
}

struct Gecisler {
    int atlanan = 0;
    int toplam = 0;
};

inline Gecisler say(const std::vector<const int*>& dokunuslar) {
    Gecisler g;
    for (std::size_t i = 0; i + 1 < dokunuslar.size(); ++i) {
        ++g.toplam;
        if (!bitisik(dokunuslar[i], dokunuslar[i + 1])) ++g.atlanan;
    }
    return g;
}

Bitişiklik testi işaretçileri tam sayıya çevirip farkı sizeof(int) ile karşılaştırır. İki ayrı dizinin işaretçilerini çıkarmak tanımsız olurdu; tam sayıya çevirmek bu yüzden gereklidir. atlanan bitişik olmayan geçişleri, toplam bütün geçişleri sayar.

Satır Sırası ve Sütun Sırası: Geçiş Sayımı

Aynı fikri tek bir düz dizi üzerinde sayıya dökelim. Dört satır ve dört sütunluk bir tablo, on altı elemanlı tek bir dizide satır sırasıyla durur: m[r * 4 + c] ifadesi r. satırın c. elemanıdır. İki iç içe döngüyü ele alalım. Birincisinde dış döngü satırlar, iç döngü sütunlar üzerinde döner; ardışık dokunuşlar dizide yan yanadır. İkincisinde dış döngü sütunlar, iç döngü satırlar üzerinde döner; ardışık dokunuşlar her adımda bir satır boyu, yani dört int atlar, sütun değişirken de geriye döner.

Dikkat edilecek nokta, on altı dokunuşun on beş geçiş ürettiğidir: geçiş, art arda iki dokunuş arasındaki adımdır. Satır sırasında on beş geçişin hiçbiri atlamaz. Sütun sırasında on beşinin hepsi atlar, çünkü ardışık iki dokunuş ya dört int ileridedir ya da geridedir. Geriye atlayan geçiş de bitişik sayılmaz: bitişiklik testi farkın tam bir int olmasını ister.

// matris.hpp — dort satir dort sutunluk duz dizide iki dolasma sirasi
#pragma once
#include <array>

#include "dizilim.hpp"

constexpr int SATIR = 4;
constexpr int SUTUN = 4;

inline Gecisler satir_sirasi_say(const std::array<int, SATIR * SUTUN>& m) {
    std::vector<const int*> dokunuslar;
    for (int r = 0; r < SATIR; ++r)
        for (int c = 0; c < SUTUN; ++c) dokunuslar.push_back(&m[r * SUTUN + c]);
    return say(dokunuslar);
}

inline Gecisler sutun_sirasi_say(const std::array<int, SATIR * SUTUN>& m) {
    std::vector<const int*> dokunuslar;
    for (int c = 0; c < SUTUN; ++c)
        for (int r = 0; r < SATIR; ++r) dokunuslar.push_back(&m[r * SUTUN + c]);
    return say(dokunuslar);
}

Bu, bir önceki bölümdeki aynı say işlevidir; yeni bir ölçü yok, yalnızca iki yeni erişim örüntüsü var. Gerçek bir tabloda bu fark, her atlayan geçişin başka bir önbellek satırını getirme ihtimaline dönüşür. Tablonun bir satırı önbellek satırından uzunsa atlayan her geçiş başka bir önbellek satırına düşer, bu yüzden büyük tablolarda döngü sırasını verinin dizilişine uydurmak ilk bakılacak yerdir.

Sahte Paylaşım ve alignas

Veri düzeni yalnızca tek iş parçacığını ilgilendirmez. İki iş parçacığı birbirinden bağımsız iki değişkene yazıyorsa ama bu iki değişken aynı önbellek satırına düşmüşse, bir iş parçacığının yazısı öbürünün satırını geçersiz kılar ve iki iş parçacığı birbirinin önbelleğini sürekli boşaltır. Buna sahte paylaşım denir: değişkenler paylaşılmıyor, ama satır paylaşılıyor. Kod doğrudur, veri yarışı yoktur; yalnızca her yazı satırın sahipliğini el değiştirmeye zorlar. Bu, kilitlerin ya da atomiklerin dersindeki bekleme noktalarından farklı bir bedeldir: kodda hiçbir eşgüdüm görünmez, bedel düzenden gelir.

Çözüm, iş parçacıklarının yazdığı alanları farklı satırlara ayırmaktır. C++’ta bunu alignas belirteci yapar: bir tipe alignas(N) verilirse o tipin nesnelerinin adresi N’in katı olur ve tipin boyutu da N’in katına yuvarlanır. İki ardışık Hizali elemanı bu yüzden en az N bayt arayla durur.

Burada 64 sayısı bir varsayımdır: yaygın işlemcilerde önbellek satırı bu boydadır, ama dilin söylediği bir sabit değildir ve her donanımda doğru olmayabilir. Bu yüzden sayıyı adlandırıp tek yerde tutuyoruz ve ölçüm, gerçek satırı değil, o varsayımı kullanıyor. Ayrıca aşağıdaki static_assert, hizalamanın gerçekten istenen değerde olduğunu derleme sırasında doğrular. Sayım, ardışık iki elemanın adresleri arasındaki farkın varsayılan satır boyundan küçük olup olmadığına bakar; küçükse ikisi aynı satıra düşme adayıdır.

// paylasim.hpp — paketli ve hizali sayaclar, ayni satira dusme adayi sayimi
#pragma once
#include <array>
#include <cstddef>
#include <cstdint>
#include <thread>
#include <vector>

constexpr std::size_t SATIR_VARSAYIM = 64;  // varsayim: yaygin islemci onbellek satiri

struct Paketli {
    long deger = 0;
};

struct alignas(SATIR_VARSAYIM) Hizali {
    long deger = 0;
};

static_assert(alignof(Hizali) == SATIR_VARSAYIM, "hizalama istenen degerde degil");
static_assert(sizeof(Hizali) % SATIR_VARSAYIM == 0, "boyut satira yuvarlanmadi");

template <typename T>
int ayni_satir_adayi(const std::array<T, 4>& dizi) {
    int aday = 0;
    for (std::size_t i = 0; i + 1 < dizi.size(); ++i) {
        auto a = reinterpret_cast<std::uintptr_t>(&dizi[i]);
        auto b = reinterpret_cast<std::uintptr_t>(&dizi[i + 1]);
        if (b - a < SATIR_VARSAYIM) ++aday;
    }
    return aday;
}

template <typename T>
long dort_yazici(std::array<T, 4>& dizi) {
    std::vector<std::thread> isler;
    for (int t = 0; t < 4; ++t) {
        isler.emplace_back([&dizi, t] {
            for (int k = 0; k < 10000; ++k) ++dizi[t].deger;
        });
    }
    for (auto& is : isler) is.join();
    long toplam = 0;
    for (const auto& e : dizi) toplam += e.deger;
    return toplam;
}

Her iş parçacığı yalnızca kendi elemanına yazar; bu yüzden iki sürüm de doğrudur ve aynı toplamı verir. ayni_satir_adayi bu platformda sekiz baytlık olan long elemanlar için üç çiftin üçünü, altmış dört baytlık hizalı elemanlar için üçünün hiçbirini aday sayar. Burada sayılan şey gerçek bir taşıma değil, düzenin yol açabileceği durumdur.

Ölçüm: Yalnız x Alanı, Tablo ve Sayaçlar

Aşağıdaki program üç ölçümü birlikte koşturur ve her birinin sayacını basar.

// dizilim_olcumu.cpp — yalniz x alani ve uc alan birlikte
#include <array>
#include <iostream>
#include <vector>

#include "dizilim.hpp"
#include "matris.hpp"
#include "paylasim.hpp"

int main() {
    NoktaDizisi aos = yapi_dizisi_kur();
    AlanDizileri soa = dizi_yapisi_kur();

    std::vector<const int*> aos_x;
    std::vector<const int*> soa_x;
    int aos_toplam = 0;
    int soa_toplam = 0;
    for (int i = 0; i < NOKTA_SAYISI; ++i) {
        aos_x.push_back(&aos.noktalar[i].x);
        aos_toplam += aos.noktalar[i].x;
        soa_x.push_back(&soa.x[i]);
        soa_toplam += soa.x[i];
    }
    Gecisler a = say(aos_x);
    Gecisler s = say(soa_x);
    std::cout << "yalniz x alani bellek aos=" << a.atlanan << "/" << a.toplam
              << " soa=" << s.atlanan << "/" << s.toplam << "\n";
    std::cout << "toplam x aos=" << aos_toplam << " soa=" << soa_toplam << "\n";

    std::array<int, SATIR * SUTUN> tablo{};
    for (int i = 0; i < SATIR * SUTUN; ++i) tablo[i] = i;
    Gecisler satir = satir_sirasi_say(tablo);
    Gecisler sutun = sutun_sirasi_say(tablo);
    std::cout << "satir ve sutun sirasi bellek satir=" << satir.atlanan << "/"
              << satir.toplam << " sutun=" << sutun.atlanan << "/" << sutun.toplam << "\n";

    std::array<Paketli, 4> paketli{};
    std::array<Hizali, 4> hizali{};
    std::cout << "sahte paylasim bellek paketli=" << ayni_satir_adayi(paketli) << "/3"
              << " hizali=" << ayni_satir_adayi(hizali) << "/3\n";
    long paketli_toplam = dort_yazici(paketli);
    long hizali_toplam = dort_yazici(hizali);
    std::cout << "sahte paylasim sonuc paketli=" << paketli_toplam
              << " hizali=" << hizali_toplam << "\n";

    std::vector<const int*> aos_uc;
    std::vector<const int*> soa_uc;
    for (int i = 0; i < NOKTA_SAYISI; ++i) {
        aos_uc.push_back(&aos.noktalar[i].x);
        aos_uc.push_back(&aos.noktalar[i].y);
        aos_uc.push_back(&aos.noktalar[i].z);
        soa_uc.push_back(&soa.x[i]);
        soa_uc.push_back(&soa.y[i]);
        soa_uc.push_back(&soa.z[i]);
    }
    Gecisler au = say(aos_uc);
    Gecisler su = say(soa_uc);
    std::cout << "uc alan birlikte bellek aos=" << au.atlanan << "/" << au.toplam
              << " soa=" << su.atlanan << "/" << su.toplam << "\n";
    return 0;
}

yalniz x alani bellek aos=3/3 soa=0/3
toplam x aos=6 soa=6
satir ve sutun sirasi bellek satir=0/15 sutun=15/15
sahte paylasim bellek paketli=3/3 hizali=0/3
sahte paylasim sonuc paketli=40000 hizali=40000
uc alan birlikte bellek aos=0/11 soa=11/11

EB13. İlk satır yalnız x alanını dolaşan döngünün iki düzende dört elemanda üç geçiş yaptığını, yapı dizisinde üçünün de bitişik olmadığını, dizi yapısında hiçbirinin atlamadığını gösterir: aos=3/3, soa=0/3. İkinci satır iki düzenin aynı toplamı verdiğini doğrular, yani fark sonuçta değil dokunuşların bellekteki konumundadır.

EB14. Sayım yalnızca bitişik olmayan geçişleri veriyor, satır boyunu vermiyor: dört noktalık küçük bir küme tek bir önbellek satırına sığabilir ve atlanan her geçiş yeni bir satır taşımasına yol açmayabilir. Bu yüzden 3/3 bir taşıma sayısı değil, düzenin bitişikliği bozma yönüdür; gerçek taşıma sayısı küme büyüdükçe anlam kazanır ve makineye bağlıdır.

EB15. Üçüncü satır, dört satır dört sütunluk tabloda satır sırasıyla dolaşmanın on beş geçişin hiçbirini atlatmadığını (satir=0/15), sütun sırasıyla dolaşmanın ise hepsini atlattığını (sutun=15/15) gösterir. İki döngü aynı on altı elemana dokundu, yalnızca sıra farklıydı. Sütun sırasında geriye dönen geçişler de sayıya girdi, çünkü bitişiklik testi yalnızca ileri doğru tam bir int adımı kabul eder.

EB16. Dördüncü satırda bu platformda sekiz baytlık olan long elemanlardan oluşan paketli dizi, üç ardışık çiftin üçünü de aynı satıra düşme adayı yaptı (paketli=3/3); alignas verilen dizi hiçbirini yapmadı (hizali=0/3). Bu sayı gerçek bir önbellek satırı ölçümü değildir, SATIR_VARSAYIM varsayımına dayanır. Varsayım yanlışsa sayım da yanlış olur; bu yüzden değeri adlandırdık ve static_assert ile hizalamanın istenen değerde olduğunu doğruladık.

EB17. Beşinci satırda iki sürüm de 40000 verdi. Her iş parçacığı yalnızca kendi elemanına yazdığı için veri yarışı yoktu ve yerleşim sonucu değiştirmedi. alignas doğruluğu değiştirmez, bedelin nerede ödendiğini değiştirir; bu değişiklik çıktıda görünmez ve bu derste bilinçli olarak ölçülmeyen kısımdır.

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

Bu dersin ölçtüğü düzen, yalnız bir alana dokunan döngüde dizi yapısının üstünlüğüdür. Son satır aynı iki düzeni bu kez üç alanı birlikte okuyan bir döngüyle ölçer: her nokta için x, y, z sırayla okunur. Burada tablo tersine döner: yapı dizisinde bir noktanın üç alanı yan yanadır ve bir sonraki noktanın alanları da öyle, yani on bir geçişin hiçbiri atlanmaz: aos=0/11. Dizi yapısında her okuma farklı bir diziye atlar: soa=11/11.

Düzenin bitişikliğini veri belirlemiyor, erişim örüntüsü belirliyor. Aynı veri bir örüntüde en iyi, bir başkasında en kötü düzende durabilir. Bu yüzden “dizi yapısı daha hızlıdır” ya da “yapı dizisi daha doğaldır” diye bir kural yoktur. Soru, döngünün hangi alanlara birlikte dokunduğudur; alanlar birlikte okunuyorsa yapı dizisi, ayrı ayrı okunuyorsa dizi yapısı bitişikliği korur.

Özet

• Bu dersin ölçtüğü düzenek bedeli bellek sınıfına taşır: bir veri düzeni, bir döngünün art arda dokunduğu değerlerin ne kadarını bitişik bıraktığını belirler; ölçü süre değil, bitişik olmayan geçiş sayısıdır.
• Önbellek satırı belleği bloklar halinde taşır; uzamsal yerellik komşuya, zamansal yerellik aynı değere yeniden dokunmayı ödüllendirir.
• Yapı dizisi alanları birlikte, dizi yapısı alanları ayrı ayrı bitişik tutar; hangisinin uygun olduğunu erişim örüntüsü belirler.
• yalniz x alani yapı dizisinde aos=3/3, dizi yapısında soa=0/3 bıraktı; uc alan birlikte aynı iki düzende aos=0/11 ve soa=11/11 bıraktı.
• Satır sırasıyla dolaşmak satir=0/15, sütun sırasıyla dolaşmak sutun=15/15 atlama bıraktı; sıra, verinin dizilişine uymalıdır.
• Sahte paylaşım, bağımsız değişkenlerin aynı satıra düşmesidir; çözümü iş parçacığı başına satır ayırmaktır, alignas ile; satır boyu burada bir varsayımdır.

Sonraki Adım

Bu derste hangi düzenin hangi örüntüye uyduğunu bildiğimizi varsaydık, ama gerçek bir programda hangi döngünün sıcak olduğunu bilmeden hangi düzene dokunacağımızı bilemeyiz. Bir sonraki ders profillemeyi açıyor: bir sayaç sıcak noktayı nerede buluyor sorusuyla araçlı bir profilleyici kuracağız.