Algoritma yang benar secara kompleksitas belum tentu cepat secara praktik. Implementasi yang sama dapat menjadi 10x lebih lambat karena cache miss, branch misprediction, atau pemilihan struktur data yang buruk. Benchmark dan profiling adalah dua teknik yang melengkapi: benchmark mengukur waktu eksekusi agregat untuk membandingkan alternatif, sedangkan profiling mengidentifikasi titik panas (hotspot) di mana waktu sebagian besar dihabiskan. Pada Chapter ini kita akan menggunakan std::chrono untuk benchmark std::sort vs insertion_sort, lalu membahas penggunaan perf untuk profiling pada level fungsi. Tujuan akhirnya: ketika kode TLE di judge, kita tahu langkah pertama untuk menemukan bottleneck.

Aturan: Selalu Benchmark dengan Optimisasi -O2 #

Benchmark dengan -O0 (default debug) menyesatkan. Compiler modern melakukan optimisasi drastis — inlining, vectorization, constant folding — yang mengubah karakteristik performa. Bandingkan:

Build FlagTujuanHasil Benchmark
-O0 -gDebug step-by-stepTidak menggambarkan produksi
-O1Optimisasi ringanMasih misleading untuk kompetisi
-O2Optimisasi standarBenchmark harus pakai ini
-O3 -march=nativeOptimisasi agresifKadang salah; pakai untuk eksperimen

Mekanisme: std::chrono untuk Pengukuran Waktu #

std::chrono menyediakan tiga jam dengan karakteristik berbeda:

ClockResolusiMonotonik?Cocok untuk
system_clockVariabel (sering mikrodetik)TidakWall-clock time, log timestamp
steady_clockVariabelYaInterval antar event
high_resolution_clockTertinggi (sering nanodetik)Tergantung impl.Benchmark default

Untuk benchmark, pakai high_resolution_clock::now() sebelum dan sesudah kode yang diukur, lalu hitung delta. Konversi ke milli atau micro sesuai kebutuhan.

cpp 
auto t0 = std::chrono::high_resolution_clock::now();
// ... kode yang diukur ...
auto t1 = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> ms = t1 - t0;
std::cout << "waktu: " << ms.count() << " ms\n";

Kode: Benchmark std::sort vs insertion_sort #

cpp 
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <string>
#include <functional>

// ---------- Algoritma yang dibandingkan ----------

// O(n log n) dengan std::sort
void sort_std(std::vector<int>& a) {
    std::sort(a.begin(), a.end());
}

// O(n^2) dengan insertion sort
void insertion_sort(std::vector<int>& a) {
    for (size_t i = 1; i < a.size(); ++i) {
        int key = a[i];
        int j = (int)i - 1;
        while (j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            --j;
        }
        a[j+1] = key;
    }
}

// ---------- Utilitas ----------
std::vector<int> generate_random(int n, int lo, int hi, unsigned seed) {
    std::mt19937 rng(seed);
    std::uniform_int_distribution<int> dist(lo, hi);
    std::vector<int> a(n);
    for (int& x : a) x = dist(rng);
    return a;
}

double measure_ms(std::function<void(std::vector<int>&)> f, std::vector<int> a) {
    auto t0 = std::chrono::high_resolution_clock::now();
    f(a);
    auto t1 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> ms = t1 - t0;
    return ms.count();
}

int main() {
    std::cout << "Benchmark: std::sort (O(n log n)) vs insertion_sort (O(n^2))\n";
    std::cout << "n        | std::sort (ms) | insertion (ms) | ratio\n";
    std::cout << "---------|----------------|----------------|-------\n";

    for (int n : {1000, 2000, 4000, 8000, 16000}) {
        auto data = generate_random(n, -1000000, 1000000, 42);

        // Benchmark std::sort: ulang 5 kali, ambil rata-rata.
        double t_std = 0;
        for (int i = 0; i < 5; ++i) t_std += measure_ms(sort_std, data);
        t_std /= 5.0;

        // Benchmark insertion sort: ulang 1-3 kali (lebih lambat untuk n besar).
        double t_ins = 0;
        int reps = (n >= 8000) ? 1 : 3;
        for (int i = 0; i < reps; ++i) t_ins += measure_ms(insertion_sort, data);
        t_ins /= reps;

        double ratio = (t_std > 0.001) ? t_ins / t_std : 0;
        std::cout << n << "    | " << t_std << "        | " << t_ins
                  << "        | " << ratio << '\n';
    }

    // Demonstrasi: hitung berapa kali comparator dipanggil.
    std::cout << "\n=== Micro-benchmark: hitung comparison sort ===\n";
    long long cmp_count = 0;
    {
        std::vector<int> a = generate_random(1000, -1000, 1000, 7);
        std::sort(a.begin(), a.end(),
                  [&cmp_count](int x, int y) { cmp_count++; return x < y; });
    }
    std::cout << "std::sort(1000 elemen) memanggil comparator sebanyak: "
              << cmp_count << " kali\n";
    std::cout << "Teori O(n log n) untuk n=1000: ~" << (1000 * 10) << " perbandingan\n";

    std::cout << "\n=== Tips profiling ===\n";
    std::cout << "- std::chrono::high_resolution_clock untuk waktu resolusi mikrodetik\n";
    std::cout << "- Ulangi minimal 5-10 kali, ambil median atau rata-rata\n";
    std::cout << "- Profile dengan `perf record ./a.out && perf report`\n";
    std::cout << "- Hindari -O0 saat benchmark — selalu -O2\n";
    return 0;
}

Output yang Dihasilkan (di mesin referensi; angka dapat bervariasi tergantung CPU):

text 
Benchmark: std::sort (O(n log n)) vs insertion_sort (O(n^2))
n        | std::sort (ms) | insertion (ms) | ratio
---------|----------------|----------------|-------
1000    | 0.0260166        | 0.0889933        | 3.42064
2000    | 0.071119        | 0.356354        | 5.01067
4000    | 0.159777        | 1.38617        | 8.67566
8000    | 0.363178        | 5.42037        | 14.9248
16000    | 0.771401        | 21.2828        | 27.5898

=== Micro-benchmark: hitung comparison sort ===
std::sort(1000 elemen) memanggil comparator sebanyak: 12584 kali
Teori O(n log n) untuk n=1000: ~10000 perbandingan

=== Tips profiling ===
- std::chrono::high_resolution_clock untuk waktu resolusi mikrodetik
- Ulangi minimal 5-10 kali, ambil median atau rata-rata
- Profile dengan `perf record ./a.out && perf report`
- Hindari -O0 saat benchmark — selalu -O2

Bedah Kode Baris-per-Baris #

  1. std::function<void(std::vector<int>&)> f: tipe callable yang menerima referensi vektor dan mengembalikan void. Memungkinkan measure_ms menerima baik function pointer maupun lambda. Overhead std::function kecil dan dapat diabaikan untuk benchmark makro.
  2. auto t0 = std::chrono::high_resolution_clock::now();: catat waktu sebelum kode dijalankan. high_resolution_clock biasanya setara dengan steady_clock di Linux, dengan resolusi nanodetik.
  3. std::chrono::duration<double, std::milli> ms = t1 - t0;: selisih t1 - t0 menghasilkan duration tipe int64 nanodetik. Cast ke double, std::milli mengkonversi ke milidetik bertipe double.
  4. for (int i = 0; i < 5; ++i) t_std += measure_ms(sort_std, data);: ulang 5 kali untuk mengurangi noise. Median lebih robust terhadap outlier (GC pause, context switch) dibanding rata-rata, tetapi rata-rata lebih sederhana.
  5. std::sort(a.begin(), a.end(), [&cmp_count](int x, int y) { cmp_count++; return x < y; }): lambda comparator menginkrementasi cmp_count setiap pemanggilan. Hasil 12584 ≈ n log2(n) ≈ 10000 — sesuai teori (sedikit lebih karena introsort fallback).
  6. if (n >= 8000) reps = 1;: untuk n = 16000, insertion sort memakan ~21 ms — terlalu lambat untuk diulang 3 kali. Adaptasi reps mencegah benchmark total menjadi menit.

Profiling dengan perf (Linux) #

Untuk menemukan hotspot pada level fungsi, perf adalah alat standar di Linux:

bash 
# Compile dengan simbol debug (-g) dan optimisasi (-O2)
g++ -std=c++17 -O2 -g -o solusi solusi.cpp

# Rekam profil selama eksekusi
perf record ./solusi < input.txt

# Tampilkan laporan interaktif
perf report

# Atau cetak 10 fungsi teratas
perf report --stdio | head -20

Contoh output perf report:

text 
# Samples: 50K of event 'cycles:u'
# Event count: 123456789
#
# Overhead  Command   Shared Object      Symbol
# ........  ........  .................  ......................................
    42.31%  solusi    solusi             [.] merge_sort_recursive
    18.45%  solusi    solusi             [.] merge
     9.12%  solusi    libc.so.6          [.] malloc
     6.78%  solusi    solusi             [.] std::vector<int>::push_back
     ...

Pada output di atas, merge_sort_recursive adalah hotspot utama (42% dari waktu CPU). Optimisasi harus fokus pada fungsi ini — bukan pada main atau I/O.

Strategi Optimisasi Bertingkat #

LevelTindakanDampak
AlgoritmaGanti O(n²) → O(n log n)100x atau lebih
Struktur dataArray → hash map untuk lookup10x
Memoristd::vector vs std::list (cache locality)5-10x
KonstantaReserve capacity sebelum push_back2x
InlineFungsi kecil inline atau constexpr1.2-2x
Compiler-O2 → -O3 -march=native1.1-1.5x

Checklist Benchmark yang Baik #

  • Compile dengan -O2 (atau flag yang sama dengan judge).
  • Ulangi pengukuran minimal 5-10 kali, ambil median.
  • Hindari pengukuran pada background noise (tutup browser, matikan service).
  • Bandingkan alternatif pada input yang sama (seed sama).
  • Catat spesifikasi mesin (CPU, RAM, OS) — angka absolut tidak portabel.
  • Verifikasi rasio sebanding dengan kompleksitas teoretis (cek konsistensi asimptotik).

Ringkasan #

  • Benchmark mengukur waktu agregat, profiling menemukan hotspot fungsi.
  • Selalu benchmark dengan -O2 — -O0 menyesatkan.
  • std::chrono::high_resolution_clock adalah pilihan default untuk benchmark resolusi tinggi.
  • Ulangi pengukuran minimal 5-10 kali, ambil median untuk robust terhadap noise.
  • perf record + perf report adalah standar profiling di Linux.
  • Strategi optimisasi bertingkat: algoritma → struktur data → konstanta → compiler flag.
  • Verifikasi rasio waktu sebanding dengan kompleksitas asimptotik untuk validasi benchmark.