Səmərəli C++ kodu: həlledici olan verilənlərin yaddaşda yerləşməsidir

Sürətli proqram üçün təkcə C++ seçmək kifayət etmir. “Writing Efficient C++ Code” məqaləsində proqramçı Adam Sawicki kodun aparatı həqiqətən istifadə edib-etmədiyini nəyin müəyyən etdiyini izah edir: verilənlərin yaddaşda necə yerləşməsi və prosessorun keşi nə qədər tez-tez gözləməsi. Məqalə ilk dəfə 2013-cü ildə Programista jurnalında çap olunub.

Təkcə C++ sürət gətirmir

C++ obyekt yönümlü dizayn və hazır konteynerlər üçün kifayət qədər yüksək səviyyəli, amma kodla əməliyyat sistemi arasında nə virtual maşın, nə də zibil toplayıcı dayanacaq qədər aşağı səviyyəli dildir: yaddaşı proqramçı azad edir.

Verilənlərə yönəlmiş dizayn

Oyun developerləri arasında yayılmış Data-Oriented Design əvvəlcə verilənlərdən başlayır: onların yaddaşda yerləşməsi və saxlayan strukturlar, alqoritmlər isə sonra seçilir. Yanaşma sinifləri qadağan etmir, amma yaddaşda səpələnmiş və göstəricilərlə bağlanmış çoxlu kiçik obyektlərə qarşı xəbərdarlıq edir: belə yerləşmə tez-tez keş buraxmasına səbəb olur və paralelləşdirməni çətinləşdirir. Adi massiv isə element-element emal olunur və onun aralığını axınlar arasında bölmək olar.

Yaddaş iyerarxiyası qiyməti müəyyən edir

3 GHz tezlikli prosessorda bir arifmetik əməliyyat təxminən 0,33 nanosaniyə, yəni bir tsikl çəkir. L1 keşindəki dəyər təqribən 1 nanosaniyə, L2-də 4,7, RAM-da isə 83 nanosaniyə, yəni 250 tsiklə bərabərdir. Verilənlər 64 baytlıq keş sətirləri ilə ötürülür, ona görə birlikdə istifadə olunan dəyərlər yaddaşda yan-yana durmalıdır.

Buna görə adi massiv və ya std::vector kimi kəsintisiz strukturlar bağlı siyahıları və ağacları üstələyir. Məqalə “məhsuldarlıq piramidası”nı təsvir edir: ən sürətlisi arifmetikadır, sinus və ya bölmə kimi transsendent əməliyyatlar daha yavaşdır, keş buraxmasından sonra RAM-a müraciət yüzlərlə tsiklə başa gəlir, dinamik yaddaş ayırma bahadır, ən yavaşı isə giriş-çıxışdır.

AOS, SOA və kompilyatorun hüdudları

Hissəcik sistemi bu seçimi aydın göstərir. Array of Structures hər hissəciyin mövqeyini, sürətini və rəngini birlikdə saxlayır; Structure of Arrays hər xassə üçün ayrı massiv saxlayır, beləcə bir dövrədə lazım olan dəyərlər yaxın qalır və istifadə olunmayan sahələr keşə düşmür.

Kompilyator hər şeyi düzəldə bilmir. Göstərici massivin elementlərinə işarə edə biləndə dəyər hər təkarda yenidən oxunmalı olur, buna yerli dəyişənə köçürmə və ya __restrict kömək edir. std::string-in dövrədən çıxarılması və hər dəfə təmizlənməsi testi 0,36 saniyədən 0,27 saniyəyə, yəni 25% azaltdı, çünki sətir ayrılmış buferi saxlayır.