Verimli C++ kodu: belirleyici olan verinin bellekteki düzeni

Bir programın hızlı olması için C++ seçmek tek başına yeterli değil. “Writing Efficient C++ Code” başlıklı yazıda programcı Adam Sawicki, kodun donanımı gerçekten kullanıp kullanmadığını neyin belirlediğini anlatıyor: verinin bellekte nasıl durduğu ve işlemcinin önbelleği ne sıklıkla beklediği. Yazı ilk kez 2013'te Polonyaca Programista dergisinde yayımlandı.

C++ tek başına hız getirmiyor

C++ nesne yönelimli tasarım ve hazır konteynerler için yeterince yüksek seviyeli, ama kod ile işletim sistemi arasına sanal makine ya da çöp toplayıcı girmeyecek kadar da düşük seviyeli bir dil: belleği programcı serbest bırakıyor.

Veri odaklı tasarım

Oyun geliştiricileri arasında yaygınlaşan Data-Oriented Design önce veriyle başlıyor: verinin bellekteki düzeni ve onu tutan yapılar, algoritmalar ise sonra seçiliyor. Yaklaşım sınıfları yasaklamıyor, ancak bellekte dağınık duran ve işaretçilerle bağlanan çok sayıda küçük nesneye karşı uyarıyor: bu tür düzenler sık önbellek ıskalamasına yol açıyor ve paralelleştirmeyi zorlaştırıyor. Düzgün bir dizi ise öğe öğe işleniyor ve aralığı iş parçacıklarına bölünebiliyor.

Bellek hiyerarşisi bedeli belirliyor

3 GHz hızındaki bir işlemcide basit bir aritmetik işlem yaklaşık 0,33 nanosaniye, yani bir çevrim sürüyor. L1 önbelleğindeki bir değer yaklaşık 1 nanosaniye, L2'de 4,7, RAM'de ise 83 nanosaniye, yani 250 çevrim. Veriler 64 baytlık önbellek satırlarıyla taşınıyor, bu yüzden birlikte kullanılan değerler bellekte yan yana durmalı.

Bu nedenle düz bir dizi ya da std::vector gibi bitişik yapılar bağlı listeleri ve ağaçları geride bırakıyor. Yazı bir “başarım piramidi” çiziyor: en hızlısı aritmetik, sinüs veya bölme gibi aşkın işlemler çok daha yavaş, önbellek ıskalamasından sonra RAM'e erişim yüzlerce çevrim, dinamik bellek ayırma pahalı, giriş ve çıkış ise en yavaşı.

AOS, SOA ve derleyicinin sınırları

Parçacık sistemi bu ödünleşmeyi somutlaştırıyor. Array of Structures her parçacığın konumunu, hızını ve rengini bir arada tutuyor; Structure of Arrays her özellik için ayrı bir dizi saklıyor, böylece bir döngüde gereken değerler yakın kalıyor ve kullanılmayan alanlar önbelleğe girmiyor.

Derleyici her şeyi düzeltemiyor. Bir işaretçi dizinin öğelerine işaret edebiliyorsa değer her yinelemede yeniden okunmak zorunda; yerel bir değişkene kopyalamak veya __restrict bunu çözüyor. std::string bildirimini döngü dışına alıp her turda temizlemek bir testi 0,36 saniyeden 0,27 saniyeye, yani %25 indirdi, çünkü metin ayırdığı tamponu koruyor.