Geliştirici Günlüğü #7: Oyun matematiği nasıl hızlandı?
Kısaca: MKA Engine'in sayı hesabını (bölme, karekök, üs, logaritma ve kuvvet alma) aynı ölçüm düzeneğinde ölçüp hızlandırdık. Bölme, karekök, üs, logaritma ve kuvvet işlemleri tek tek 3 ila 4 kat hızlandı; geç oyundaki bir oyun günü yaklaşık yüzde 23–30 kısaldı. Bölme ve karekökün sonuçları bit bit aynı kaldı; üs, logaritma ve kuvvetin sonuçları ise biraz değişti ve eskisinden daha doğru çıktı.
Bir strateji oyununda her gün binlerce eyaletin vergisi, nüfus artışı ve fiyatı hesaplanır. Bu hesapların hepsi sonunda birkaç basit işleme iner: toplamak, çarpmak, bölmek, karekök almak. Motorun her bilgisayarda aynı sonucu vermesi için Günlük #1'de anlattığımız sabit noktalı sayıları kullanıyoruz. Orada bir ölçüm de vermiştik: bölme ve karekök ondalıklı sayıya göre çok pahalıydı. Bu günlükte o pahalı işlemleri nasıl ucuzlattığımızı anlatıyoruz.
Hazır tablo mu, elle hesap mı?
Hazinenin iki kâtibini düşünün. Biri her vergi hesabını uzun bir tomara elle yazıyor. Öteki ise sık sorulan cevapların hazır olduğu büyük bir tabloya bakıyor, bulduğu yaklaşık cevabı küçük bir düzeltmeyle kesinleştiriyor. İkisi de aynı doğru sonuca varıyor; ikincisi çok daha çabuk. Bu günlük, motorun matematiğini birinci kâtipten ikinciye çevirmenin hikâyesi.
Neden bu işe girdik?
Önce nereye bakacağımızı bilmemiz gerekiyordu. Ekransız koşucuyla geç oyun dünyasını profilledik: işlemcinin zamanını hangi işlevler yiyor? Çıkan sonuç net: 128 bitlik bölme, işlemci zamanının yaklaşık yüzde 11'ini alıyordu. Bu sayıyla hedeflerimizi şöyle koyduk:
| İşlem | Hedef | Neden bu hedef |
|---|---|---|
| Bölme | en çok 6 ns | Gün profilinde işlemci zamanının yaklaşık %11'i bölmeye gidiyordu; ölçülen 13 ns'nin yarısından aşağı |
| Üs | en çok 45 ns | Ölçülen yaklaşık 128 ns'nin üçte birine yakın |
| Karekök | en çok 10 ns | Ölçülen 20 ns'nin yarısı |
| Logaritma ve kuvvet | en az 2 kat hızlanma | Başlangıç süreleri çok yüksekti (yaklaşık 90 ve 208 ns) |
| Bölmenin gün süresindeki payı | en çok yüzde 4 | Profildeki yüzde 7,6'nın yarısından az |
Bu hedefler tahminden doğdu, kural değil. Tuttuklarını aşağıda göreceksiniz. Ölçümü basit tuttuk: ekransız koşucu, milyon rastgele sayı, her işlem için beş koşunun en iyisi.
Ne değişti?
Çarpma. Sonucu en yakın sayıya yuvarlarken işarete göre dallanıyorduk. İşlemci dalın hangi yöne gideceğini tahmin ederken şaşırınca zaman kaybediyor. Yuvarlamayı dalsız yazdık.
Bölme. Eskiden bölme iki ayrı bölmeyle yapılıyordu (bölüm ve kalan için). Şimdi tek bölme yapıyor, kalanı bölümden çıkarıyoruz. Sayılar yeterince küçükse, ki oyunun tipik sayılarında öyledir, işlemcinin hızlı 64 bitlik bölmesini kullanıyoruz. Sayılar çok büyükse eski 128 bitlik yol kalıyor.
Karekök. Hazır tablo benzetmesinin en açık hali burada. 769 noktalı bir tablo, her noktada karekökün yaklaşık değerini tutuyor. Verilen sayıya en yakın noktayı buluyoruz ve tek bir düzeltme adımı atıyoruz. Bu yöntemin adı Newton yöntemi; yaklaşık bir cevabı her adımda iyileştirir. Sonuç, kütüphanenin kendi tam karekökünden bit bit farksız. Tablo yalnız 6 kilobayt.
Üs ve logaritma. İkisi de bir polinomu hesaplamaya iniyor; polinomu çarpma ve toplama dizisi olarak sıralı yazdık (Horner yöntemi). Logaritmada ayrıca 128 girişli bir tablo var, bölme hiç yok. Tabloları elle yazmıyoruz: 80 basamaklı hassasiyetle bir betik üretiyor ve ayrı bir denetim, tabloların betikle güncel olup olmadığını sınıyor.
Paylaştırma. Bir hazineyi ülkeler arasında paylaştırırken kesirli kalanlar oluşur; kalanlar en büyük kalandan başlayarak dağıtılır. Burada iş, çok sayıda bölmeyi tek bir ters sayıyla çarpmaya çevirmek ve en büyük kalanları sıralamak yerine seçmekti. Dağıtım sırası ve sonuç eskisiyle aynı.
Mod formülleri. Modların formülleri WebAssembly olarak çalışıyor ve orada bölme 64 adımlı bir döngüyle yapılıyordu. Sayı yeterince küçükse tek bölmeye indirdik.
Sonuçlar
İşlem başına hızlanma (tipik işlenenler) (kat)
| Etiket | Hızlanma |
|---|---|
| Çarpma | 3,0 |
| Bölme | 3,6 |
| Karekök | 4,1 |
| Üs | 3,5 |
| Logaritma | 4,1 |
| Kuvvet | 3,5 |
| İşlem | Önce | Sonra | Hedef | Durum |
|---|---|---|---|---|
| Çarpma | 5,90 | 1,94 | — | — |
| Bölme | 13,49 | 3,76 | en çok 6 | Tuttu |
| Karekök (0–65.536) | 20,48 | 4,95 | en çok 10 | Tuttu |
| Karekök (0–1 milyon) | 21,90 | 8,49 | en çok 10 | Tuttu |
| Üs | 127,11 | 36,67 | en çok 45 | Tuttu |
| Logaritma | 89,62 | 21,86 | en az 2 kat | Tuttu (4,1 kat) |
| Kuvvet | 207,23 | 59,75 | en az 2 kat | Tuttu (3,5 kat) |
Bu tablo "tipik" işlenenlerle: değeri yaklaşık 2⁻¹⁶ ile 2²⁰ arasında olan sayılar; fiyat, oran ve nüfus gibi. Çok büyük sayılarla (en kötü durum) kazanç daha küçük: bölme 13,25 ns'den 7,25 ns'ye iniyor, yani 1,8 kat.
Aynı koşuda ölçülen oranlar daha güvenilirdir; makine ölçüm sırasında başka işlerle meşguldü. Bu yüzden #1'deki sayılarla birebir karşılaştırmıyoruz. Orada işlenen aralığı ve makine yükü farklıydı. Bu günlükteki "önce" değerleri de aynı düzenekte, yeniden ölçüldü.
- %7,6 → %0,24 128 bitlik bölmenin gün süresindeki payı
- %23–30 geç oyunda bir oyun gününün kısalması (8 iş parçacığı)
- 13,5 → 3,8 ns tipik işlenenlerle bir bölme
Gün süresini geç oyunda, 300 gün boyunca, sekiz iş parçacığında, art arda beş koşuda ölçtük:
| Koşu | Önce | Sonra |
|---|---|---|
| 1 | 2,21 | 1,74 |
| 2 | 2,15 | 1,60 |
| 3 | 2,88 | 1,93 |
| 4 | 2,76 | 2,16 |
| 5 | 2,85 | 2,12 |
Her koşuda gün kısaldı; yaklaşık yüzde 23 ile 30 arasında. En önemlisi: bölme, karekök ve paylaştırma bit bit aynı çıktığı için oyunun parmak izi önce ve sonra aynı. Yani aynı oyunu daha hızlı oynuyoruz.
Bu hızlanma bir oyun gününün neresinde işe yarıyor? Çoğunlukla sistemlerin içinde: vergi, nüfus, fiyat hesapları. Günün sıralamasını değiştirmedik, yalnız her adımı ucuzlattık.
Mod formüllerinde
Modların formüllerinde bölmenin hızı da arttı. Küçük sayılarda tek bölmeye inen yol, iki ayrı arka uçta ölçüldü:
| Arka uç | Önce | Sonra | Kazanç |
|---|---|---|---|
| Yerel kod (Cranelift) | 303 | 133 | 2,3 kat |
| Yorumlayıcı (Pulley) | 1.852 | 504 | 3,7 kat |
Kontrol olarak aynı koşuda ölçtüğümüz çarpma değişmedi. Üç yolun, yani yerel kodun, yorumlayıcının ve motorun kendi sayı türünün sonucu bit bit aynı.
Sınırlar
- Ondalıklı sayı hâlâ daha hızlı: Tipik işlenenlerde çarpma ondalıklıdan yaklaşık 2,4 kat, bölme 3,2 kat, karekök 2,4 ile 4,2 kat yavaş; üs 9,3, logaritma 5,8, kuvvet 5,4 kat. Bunun karşılığında her makinede aynı sonuç var.
- Büyük sayılarda kazanç daha az: Çok büyük işlenenlerde bölme 1,8 kat, bölme ile çarpmanın birleşik hali (
mul_div) yalnız 1,3–1,4 kat hızlandı. - Üs, logaritma ve kuvvetin bitleri değişti: Eski sürümle üretilmiş bir oyunda bu işlevler kullanılıyorsa, kayıt ve komut günlüğü tekrar oynatıldığında düşük bitlerde ayrışma görülür. Şu an dağıtılmış bir kayıt yok ve repodaki hiçbir kayıt örneği bu işlevlere bağlı değil; bu yüzden kayıt sürümünü artırmadık. Dışarıda bu işlevleri kullanan bir oyun çıkarsa, kayıtlar yeni sürümle yeniden üretilmeli.
- Doğruluk arttı: Sayıların en küçük adımı (1/16.777.216) cinsinden en büyük hata, üste 9,5'ten 4,1'e, kuvvette 35,5'ten 6,4'e indi; logaritmada 0,5 kaldı.
- Ölçüm: Basit, ekransız, paylaşımlı ve yüklü bir makinede. Mutlak süreler değil, aynı koşudaki oranlar anlamlıdır. Tek iş parçacığında gün süresi yük yüzünden dalgalı çıktı ve iyileşme kesin söylenemeyecek kadar belirsiz.
- Gerçek oyun değil: Ölçek dünyası bir deneme dünyası. Gerçek bir oyunun sayı karışımı farklı olabilir.
Sık sorulanlar
Oyun motorunda matematik neden hızlandırılır?
Büyük strateji oyunları her gün binlerce konum için aynı işlemleri tekrarlar. Bölme ve karekök gibi pahalı işlemler çok sık çağrıldığında oyun gününün önemli bir kısmını yer. MKA Engine'de profilde 128 bitlik bölme işlemci zamanının yaklaşık yüzde 11'ini alıyordu.
Karekök tablodan alınırsa sonuç yaklaşık mı olur?
Hayır. Tablo yalnız başlangıç tahminini verir; ardından bir düzeltme adımı sonucu kesinleştirir. Sonuç, kütüphanenin kendi tam karekökü ile bit bit aynıdır.
Hızlandırma oyunun sonucunu değiştirir mi?
Bölme, karekök ve paylaştırmada hayır; ölçek dünyasında oyunun parmak izi önce ve sonra aynıdır. Üs, logaritma ve kuvvetin son bitleri değişti, ama sonuçlar eskisinden daha doğru.
Ondalıklı sayı daha hızlıysa neden sabit noktalı sayı kullanılıyor?
Ondalıklı sayı her işlemcide aynı sonucu garanti etmez. Çok oyunculu oyunda herkesin aynı sonucu görmesi gerekir; bu yüzden sabit noktalı sayı kullanıyoruz ve hız farkını bu günlükteki gibi kapatmaya çalışıyoruz.
Kaynaklar ve kayıtlar
Dış kaynaklar:
- Vikipedi, Fixed-point arithmetic (sabit noktalı sayı) (yeni sekmede açılır)
- Vikipedi, Newton's method (Newton yöntemi) (yeni sekmede açılır)
- Vikipedi, Horner's method (Horner yöntemi) (yeni sekmede açılır)
- Vikipedi, Lookup table (hazır sonuç tablosu) (yeni sekmede açılır)
İç kayıtlarımız (motorun deposu kapalı olduğu için bağlantı veremiyoruz):
- Sayı modeli kararı: sabit noktalı sayı, en yakına yuvarlama, taşmada panik.
- Hız hedefi kararı: ölçek dünyasında günlük hedefler.
- Sayı matematiği ölçümü: 16 Ekim 2026; önce ve sonra aynı düzenekte, art arda; gün profili ve gün süresi ölçümü ayrı.
Bu konuda daha fazlası gelecek
MKA Engine hâlâ geliştirme aşamasında. Sayı matematiği ve hız çalışmalarımızı yeni günlüklerle paylaşmaya devam edeceğiz; bu günlük bunların ilkidir.
Bu günlük hakkında sorularınız ya da önerileriniz varsa bize iletişim sayfasından yazabilirsiniz. Motorun genel tanıtımı için MKA Engine sayfasına, bütün günlükler için Geliştirici Günlükleri listesine bakabilirsiniz.