Olimpiada üçün C++-da Performans Mühəndisliyi, Dərs 1

Published:

TED Super Finalçılar Sinfi, Qonaq Dərs (Barış Namazov)

Mündəricat

Motivasiya

Sürətli kod yazmağı niyə bilək:

Müasir CPU-lar çoxsaylı nüvələr, keş yaddaşlarının qat-qat hissələri, pipelining və vektor təlimat dəstləri (SIMD) kimi mürəkkəb xüsusiyyətlərlə təchiz olunub. Əvvəllər alqoritmlərin sürətini təxmin etmək üçün yalnız əməliyyat sayını hesablamaq kifayət edirdi, amma indi fərqli prosessorlar, kompilyator optimizasiyaları və keşdən yaxşı istifadə bu yanaşmanı natamam edir. Sadəcə “hərfi əməliyyat sayma” ilə real icra vaxtını dəqiq proqnozlaşdırmaq mümkün deyil. Aşağıda isə bu yeni imkanlardan faydalanaraq kodu necə sürətləndirə biləcəyimizi göstərəcəyik.

Giriş/Çıxış

C++-da standart giriş-çıxış axınları (cin və cout) rahatlıq üçün nəzərdə tutulub, amma performans baxımından yavaşdırlar. Aşağıdakı üsullarla sürətini artıra bilərsiniz.

ios_base::sync_with_stdio(false);

Bu funksiya C və C++ axınlarının (stdio və iostream) sinxronizasiyasını söndürür. Normalda onlar sinxron işləyir ki, qarışıqlıq olmasın, amma bu cin və cout-un sürətini azaldır.

ios_base::sync_with_stdio(false);

Bu sətri əlavə etməklə cin və cout daha sürətli işləyir, amma scanf/printf ilə qarışıq istifadə edərkən ehtiyatlı olun.

Ətraflı cppreference

cin.tie(nullptr);

Standartda cin axını cout-a bağlıdır (tied), yəni cin əməliyyatından əvvəl cout avtomatik flush olunur. Bu, interaktiv proqramlarda faydalıdır, amma əlavə gecikmə yaradır.

cin.tie(nullptr);

Bu sətri yazmaqla cin və cout-un bu bağını aradan qaldırıb performansı artırırsınız.

Ətraflı cppreference

#define endl '\n'

endl sadəcə sətir sonu simvolu əlavə etmir, həm də axını flush edir. Flush əməliyyatı çıxışı gecikdirə bilər.

#define endl '\n'

Bu definisiya endl əvəzinə sadəcə '\n' istifadə etməyə imkan verir, çıxışı sürətləndirir. Əgər interaktiv proqramdırsa və çıxış dərhal göstərilməlidirsə, flush edilməlidir.

İnteraktiv məsələlərdə flush

İnteraktiv proqramlarda çıxışın dərhal göstərilməsi vacibdir. Bu halda:

Nümunə

#include <iostream>

using namespace std;

#define endl '\n'

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cout << i << endl;
    }

    // İnteraktiv məsələlərdə lazım ola bilər, hər dəfə giriş oxunandan əvvəl:
    // cout << flush;

    return 0;
}

Ümumi tövsiyə

Kompilyatorlar

Kompilyator növləri

C++ kompilyatorları

Maraqlı alətlər

GCC optimallaşdırma səviyyələri

GCC-də optimallaşdırma səviyyəsi -O flag-i ilə idarə olunur. Bu səviyyələr kodun sürətini və ölçüsünü dəyişir, tərtib vaxtına da təsir göstərir. Aşağıda əsas optimallaşdırma səviyyələri və onların istifadə məqsədləri göstərilmişdir:

SəviyyəTəsviri
-O0Heç bir optimallaşdırma tətbiq olunmur. Dəyişənlər və funksiyalar olduğu kimi saxlanılır, debug üçün əlverişlidir.
-O1Əsas optimallaşdırmalar həyata keçirilir: ölü kodun silinməsi, dövrlərin sadələşdirilməsi və s.
-O2Daha geniş optimallaşdırma dəsti aktivləşir: dövr transformasiyaları, avtomatik vektorizasiya və funksiyaların daha effektiv yerləşdirilməsi. Olimpiadalar və online judge-lərdə standart olaraq bu istifadə olunur.
-O3Hesablama intensiv kodlar üçün əlavə aqressiv optimallaşdırmalar (loop unrolling, daha geniş inlining və s.). Bəzən faydalıdır, bəzən faydasız və ya hətta zərərli ola bilər.
-Ofast-O3 səviyyəsinə əlavə olaraq -ffast-math aktivləşdirilir. Bu isə bəzi standartlara zidd transformasiyalarla nəticənin dəqiqliyini riskə ata bilər, amma performans daha yüksək ola bilər.

Kompilyasiya əmrləri

# Balanslı və təhlükəsiz optimallaşdırma
g++ -std=c++20 -O2 main.cpp -o main

# Aqressiv optimallaşdırma
g++ -std=c++20 -O3 main.cpp -o main

# Maksimum performans, daha riskli optimallaşdırmalarla
g++ -std=c++20 -Ofast main.cpp -o main

Yarışlarda #pragma istifadəsi

Yarışlarda faylın əvvəlində #pragma direktivləri ilə optimallaşdırmanı kompilyator səviyyəsində göstərə bilərsiniz. GCC bu direktivləri dəstəkləyir və optimallaşdırmanı uyğun şəkildə tətbiq edir.

#pragma GCC optimize("O3")

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // ...
}

Kompilyasiya əmrinə optimizasiya flag-i əlavə etmək (-O2, -O3) ilə #pragma GCC optimize arasındakı fərq nədir? Birbaşa əmrə əlavə etmək bütün kod fayllarına va daxili funksiyalara (məsələn, std::sort) da tətbiq olunur, amma pragma yalnızca yazılan kod faylına. Amma yarışlarda əmri biz idarə etmirik deyə pragma yazmağa məcbur qalırıq.

Nümunə kod

Aşağıdakı kodu Godbolt saytında fərqli flag-lar ilə yoxlayın:

#include <bits/stdc++.h>
using namespace std;

int main() {
    constexpr size_t N = 1'000'000;
    vector<double> a(N), b(N);

    for (size_t i = 0; i < N; ++i) {
        a[i] = static_cast<double>(i);
        b[i] = static_cast<double>(N - i);
    }

    auto t0 = chrono::high_resolution_clock::now();
    double sum = 0.0;

    for (size_t i = 0; i < N; ++i) {
        sum += a[i] * b[i];
    }

    auto t1 = chrono::high_resolution_clock::now();
    chrono::duration<double> dt = t1 - t0;

    cout << "sum = " << sum
         << "    time = " << dt.count() << " s\n";
    return 0;
}

Vektorizasiya (SIMD)

Vektorizasiya (Single Instruction Multiple Data) eyni əməliyyatı “paralel” şəkildə bir neçə məlumat elementi üzərində icra etməyə imkan verir. Burada paralel dedikdə, 1 instruksiyada nəzərdə tuturuq (bir neçə nüvə yox). Məsələn, AVX təlimat dəsti 256-bit registrindən istifadə edir; bu registr 8 × 32-bit tam ədədi eyni vaxtda saxlayır. Beləliklə, vektorizasiya olunmuş kodda tək bir vaddps (və ya vpaddd) təlimatı 8 tam ədədi toplamağa qadirdir, halbuki vektorizasiya olunmamış (scalar) kodda eyni işi görmək üçün 8 ayrı add təlimatı lazım olardı.

Avto-vektorizasiya

Xoşbəxtlikdən, kompilyator bizə vektorizasiya ilə kömək edə bilər.

C++-da olimpiadaçılar arasında məşhur olan bitset tipi də avtomatik vektorizasiya olunan tipdir.

Manual vektorizasiya

Yarışda etmək tövsiyə olunmur!

Bu, C++ kodunda assembly instruksiyaları yazmağa bənzəyir.

Məsələlər

Dərs 2-də nələr olacaq?

Dərs 2-də yaddaşı daha yaxşı başa düşəcəyik (stack və heap), keş haqqında öyrənəcəyik, C++-ın standart tiplərindən daha sürətli olan data strukturları görəcəyik.