Optimasi Performa

Kode DSA yang benar belum tentu cepat. Pada kompetisi dan interview, perbedaan 10× antara solusi yang “lengkap” vs “cepat” menentukan AC atau TLE (Time Limit Exceeded). Ada tiga lapisan optimasi yang sering kali lebih penting daripada pemilihan algoritma: I/O (baca/tulis data efisien), cache locality (akses memori berurutan), dan compiler flags (-O2, -O3). Pada Chapter ini kita membedah teknik-teknik ini dengan kode C++ yang dapat diuji, mendemonstrasikan efek cache pada vector vs list, dan menutup dengan checklist optimasi untuk kompetisi.

Aturan: Tiga Lapisan Optimasi #

Algoritma adalah lapisan paling penting (10× atau lebih), tetapi setelah algoritma optimal, tiga lapisan berikutnya sering kali menjadi penentu AC vs TLE.

Mekanisme: I/O Optimization #

Stream C++ (cin, cout) secara default sinkron dengan C stdio (scanf, printf) — setiap operasi memanggil lock dan flush, menjadi bottleneck untuk input besar. Tiga teknik cepat:

#include <iostream>
using namespace std;

int main() {
    // Tiga baris ini di awal main() memberi speedup 5-10x untuk cin/cout
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;  // sekarang secepat scanf
    // ...
    cout << "hasil\n";  // '\n' bukan endl — endl flush buffer tiap kali
    return 0;
}

Mekanisme: Cache Locality #

CPU modern punya cache L1/L2/L3 yang berukuran kecil tetapi sangat cepat (L1 ~1 ns, RAM ~100 ns). Akses memori berurutan (sequential scan vector) memanfaatkan cache line 64 byte (16 int) — satu miss cache membawa 16 elemen ke cache. Sebaliknya, list dengan node tersebar di heap menghasilkan cache miss per elemen.

Konsekuensi praktis:

1. std::vector hampir selalu lebih cepat dari std::list untuk traversing, bahkan untuk operasi O(1) linked list (insert/delete middle) — kecuali bila benar-benar sering insert/delete di tengah.
2. Loop 2D row-major (mat[i][j], j berubah paling cepat) jauh lebih cepat dari col-major (mat[j][i]).
3. reserve() sebelum banyak push_back menghindari realokasi dan copy.

Kode: Demo Cache Locality #

#include <iostream>
#include <vector>
#include <list>
#include <chrono>
#include <algorithm>
#include <random>
#include <cstdio>

using namespace std;
using namespace std::chrono;

int main() {
    // === Demo 1: cache locality (vector vs list) ===
    const int N1 = 1'000'000;
    vector<int> v(N1);
    list<int> l;
    for (int i = 0; i < N1; ++i) { v[i] = i; l.push_back(i); }

    auto t0 = steady_clock::now();
    long long sum_v = 0;
    for (int x : v) sum_v += x;
    auto t1 = steady_clock::now();

    auto t2 = steady_clock::now();
    long long sum_l = 0;
    for (int x : l) sum_l += x;
    auto t3 = steady_clock::now();

    double ms_v = duration<double, milli>(t1 - t0).count();
    double ms_l = duration<double, milli>(t3 - t2).count();

    cout << "Demo 1: cache locality (sum N=1,000,000 integers)\n";
    cout << "  vector (contiguous):  " << ms_v << " ms, sum=" << sum_v << " (waktu bervariasi)\n";
    cout << "  list (scattered):     " << ms_l << " ms, sum=" << sum_l << " (waktu bervariasi)\n";
    cout << "  ratio list/vector:   " << ms_l / ms_v << "x\n";

    // === Demo 2: cache locality 2D (row-major vs col-major) ===
    const int N2 = 1500;
    vector<vector<int>> mat(N2, vector<int>(N2));
    for (int i = 0; i < N2; ++i)
        for (int j = 0; j < N2; ++j)
            mat[i][j] = i * N2 + j;

    auto t4 = steady_clock::now();
    long long sum_row = 0;
    for (int i = 0; i < N2; ++i)
        for (int j = 0; j < N2; ++j)
            sum_row += mat[i][j];  // row-major: akses berurutan
    auto t5 = steady_clock::now();

    auto t6 = steady_clock::now();
    long long sum_col = 0;
    for (int j = 0; j < N2; ++j)
        for (int i = 0; i < N2; ++i)
            sum_col += mat[i][j];  // col-major: akses melompat per row
    auto t7 = steady_clock::now();

    double ms_row = duration<double, milli>(t5 - t4).count();
    double ms_col = duration<double, milli>(t7 - t6).count();

    cout << "\nDemo 2: cache 2D (sum " << N2 << "x" << N2 << " matrix)\n";
    cout << "  row-major: " << ms_row << " ms, sum=" << sum_row << " (waktu bervariasi)\n";
    cout << "  col-major: " << ms_col << " ms, sum=" << sum_col << " (waktu bervariasi)\n";
    cout << "  ratio col/row: " << ms_col / ms_row << "x\n";

    // === Demo 3: reserve() untuk hindari realokasi ===
    const int N3 = 1'000'000;
    auto t10 = steady_clock::now();
    string small_str;
    for (int i = 0; i < N3; ++i) {
        small_str += to_string(i);
        small_str += '\n';
    }
    auto t11 = steady_clock::now();

    auto t12 = steady_clock::now();
    string big_str;
    big_str.reserve(N3 * 7);  // pre-allocate
    for (int i = 0; i < N3; ++i) {
        big_str += to_string(i);
        big_str += '\n';
    }
    auto t13 = steady_clock::now();

    double ms_naive = duration<double, milli>(t11 - t10).count();
    double ms_buf = duration<double, milli>(t13 - t12).count();

    cout << "\nDemo 3: build string N=" << N3 << " baris\n";
    cout << "  naive (tanpa reserve):  " << ms_naive << " ms, size=" << small_str.size() << " (waktu bervariasi)\n";
    cout << "  reserve(N*7) + append:  " << ms_buf << " ms, size=" << big_str.size() << " (waktu bervariasi)\n";
    cout << "  ratio naive/reserve:    " << ms_naive / ms_buf << "x\n";
    cout << "  ukuran sama? " << (big_str.size() == small_str.size() ? "YA" : "TIDAK") << '\n';

    return 0;
}

Output yang Dihasilkan (dengan g++ -std=c++17 -O2, waktu bervariasi antar mesin):

Demo 1: cache locality (sum N=1,000,000 integers)
  vector (contiguous):  0.21 ms, sum=499999500000 (waktu bervariasi)
  list (scattered):     4.40 ms, sum=499999500000 (waktu bervariasi)
  ratio list/vector:   21.06x

Demo 2: cache 2D (sum 1500x1500 matrix)
  row-major: 0.46 ms, sum=2531248875000 (waktu bervariasi)
  col-major: 2.18 ms, sum=2531248875000 (waktu bervariasi)
  ratio col/row: 4.72x

Demo 3: build string N=1000000 baris
  naive (tanpa reserve):  18.66 ms, size=6888890 (waktu bervariasi)
  reserve(N*7) + append:  15.99 ms, size=6888890 (waktu bervariasi)
  ratio naive/reserve:    1.17x
  ukuran sama? YA

Bedah Kode Baris-per-Baris #

1. vector<int> v(N1); list<int> l; — vector mengalokasikan satu blok kontigu N1 * 4 byte = 4 MB; list mengalokasikan N1 node terpisah dengan masing-masing 2 pointer overhead. List memakan lebih banyak memori dan tersebar.
2. for (int x : v) sum_v += x; — iterator vector adalah pointer ke array kontigu; prefetcher CPU mendeteksi pola akses dan menarik cache line berikutnya sebelum dibutuhkan. Iterator list adalah pointer ke node berbeda — setiap dereference menyebabkan cache miss.
3. vector<vector<int>> mat — matriks 2D sebagai vector of vectors. Setiap baris mat[i] adalah vector terpisah — cache-friendly untuk row-major traversal, tetapi tetap memerlukan indirection per baris.
4. Row-major mat[i][j] dengan j di loop dalam: akses mat[i][0], mat[i][1], ..., mat[i][N-1] berurutan dalam satu blok memori. Cache line 64 byte = 16 int dibawa per miss.
5. Col-major mat[i][j] dengan i di loop dalam: akses mat[0][j], mat[1][j], ..., mat[N-1][j] melompat N * 4 byte setiap iterasi. Setiap akses adalah cache miss (kecuali N kecil). Hasilnya 4-5× lebih lambat.
6. string small_str tanpa reserve(): saat += melebihi capacity, string mengalokasikan ulang (biasanya 2× capacity sebelumnya), copy seluruh konten. Untuk N3 = 1jt iterasi, ~20 realokasi terjadi (capacity tumbuh 1→2→4→…→2M). Total copy = O(N) tetapi konstanta besar.
7. big_str.reserve(N3 * 7): pre-allocate satu blok 7 MB. Tidak ada realokasi selama loop. Konstanta copy turun ke 0, hanya penulisan langsung.
8. Verifikasi: sum_v == sum_l == 499999500000 (jumlah 0..999999). sum_row == sum_col == 2531248875000 (jumlah 0..(N²-1)). small_str.size() == big_str.size() == 6888890 byte. Semua operasi menghasilkan nilai yang sama, hanya waktu yang berbeda — bukti bahwa optimasi tidak mengubah hasil.

Mekanisme: Branch Prediction #

CPU modern menjalankan instruksi secara speculative — ketika branch if (cond) ditemui, CPU menebak arah (taken/not-taken) berdasarkan riwayat (branch history). Bila tebakan benar, eksekusi berlanjut tanpa jeda. Bila salah (misprediction), pipeline di-flush dan 10-20 cycle terbuang.

Untuk data terurut dengan branch yang polarnya konsisten (mis. semua elemen di awal tidak memenuhi kondisi, semua di akhir memenuhi), branch predictor akurasi ~99%. Untuk data random dengan branch 50/50, akurasi ~50% — setiap iterasi berpotensi misprediction.

// Branch yang predictable (data terurut, threshold di tengah):
//   predictor akurasi ~99% → eksekusi cepat
sort(data.begin(), data.end());
long long sum = 0;
for (int x : data) if (x > threshold) sum += x;

// Branch yang unpredictable (data random):
//   predictor akurasi ~50% → eksekusi lambat
shuffle(data.begin(), data.end(), rng);
for (int x : data) if (x > threshold) sum += x;

Solusi alternatif tanpa branch:

// Branchless: compiler dapat vectorize dengan SIMD
long long sum = 0;
for (int x : data) sum += (x > threshold) ? x : 0;  // CMOV

Mekanisme: Compiler Flags #

Benchmark tipikal (sorting 1 juta integer):

-O0: ~200 ms
-O1: ~80 ms
-O2: ~50 ms (rekomendasi default)
-O3: ~45 ms (marginal vs -O2)
-O3 -march=native: ~35 ms

Checklist Optimasi untuk Kompetisi #

Sebelum submit solusi DSA ke kontes, jalankan checklist berikut:

1. Algoritma: kompleksitas sesuai constraint? Mis. n = 10^5 → O(n log n) OK, O(n²) TLE.
2. I/O: tambah ios::sync_with_stdio(false); cin.tie(nullptr); di awal main(). Gunakan '\n' bukan endl.
3. Data structure: vector > list untuk traversing; unordered_map > map bila tidak perlu urut.
4. Pre-allocation: reserve() untuk vector/string yang akan banyak di-push_back/append.
5. Loop order 2D: pastikan inner loop遍遍-index kedua (mat[i][j] dengan j di dalam) untuk cache locality.
6. Compiler: kompilasi dengan -O2 -std=c++17. Tambah -march=native bila mesin mendukung.
7. Avoid copies: pass parameter besar via const& (mis. void f(const vector<int>& v) bukan void f(vector<int> v)).
8. Move semantics: gunakan std::move untuk mentransfer kepemilikan resource (lihat Chapter move-semantics).
9. Benchmark: uji solusi pada input maksimum sebelum submit. Bila mendekati TLE, optimasi paling bottleneck.

Aplikasi: Pola Umum di DSA #

Fast Input/Output Template #

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

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;

    // ... solve ...

    for (int i = 0; i < n; ++i) {
        cout << a[i] << (i + 1 == n ? '\n' : ' ');
    }
    return 0;
}

Vector sebagai Pool untuk Node-Based Structure #

// Alih-alih new/delete node, simpan di vector
struct Node { int val, next; };
vector<Node> pool;
int alloc_node(int v, int next) {
    pool.push_back({v, next});
    return (int)pool.size() - 1;
}
// Index digunakan sebagai "pointer" — cache-friendly, no leak

Buffer Output untuk Banyak Line #

// Untuk output 10^6+ baris, build ke string buffer lalu write sekali
string out;
out.reserve(8 * 1'000'000);
for (int i = 0; i < N; ++i) {
    out += to_string(result[i]);
    out += '\n';
}
cout << out;  // satu write call, jauh lebih cepat dari endl per line

Ringkasan #

• I/O optimization: sync_with_stdio(false), cin.tie(nullptr), '\n' bukan endl — speedup 5-10×.
• Cache locality: vector 20× lebih cepat dari list untuk traversing; row-major 5× lebih cepat dari col-major untuk 2D.
• reserve(): pre-alokasi menghindari realokasi dan copy — speedup 1.2-2× untuk build string/vector besar.
• Branch prediction: sorted data predictable; bila compiler gunakan CMOV (di -O2), efek menghilang. Untuk amati, gunakan -O0 atau branchless code.
• Compiler flags: -O2 default; -O3 -march=native untuk benchmark; -O0 -g -fsanitize=address untuk development.
• Checklist kompetisi: algoritma tepat → I/O cepat → vector > list → reserve → loop order → -O2 → benchmark.
• Optimasi terbesar datang dari algoritma (10× atau lebih); tiga lapisan lainnya penting setelah algoritma optimal.