Fast I/O

Pada soal dengan input besar (10^6 elemen atau lebih), I/O bisa menjadi bottleneck utama. Implementasi default std::cin/std::cout sinkron dengan C stdio — aman tetapi lambat. Untuk kompetisi pemrograman, satu baris optimisasi sering mengubah Time Limit Exceeded menjadi Accepted. Pada Chapter ini kita akan membahas tiga tingkat kecepatan I/O di C++: default cin, sync_with_stdio(false) + cin.tie(nullptr), dan custom reader berbasis getchar_unlocked. Kita juga akan benchmark ketiganya pada input 10^6 integer dan melihat perbedaan waktu hingga 10x. Tujuan akhirnya: ketika menulis template solusi CP, I/O cepat menjadi default, bukan optimisasi terakhir.

Aturan: Aktifkan sync_with_stdio(false) di Awal main() #

Dua baris berikut harus ada di awal main() untuk hampir setiap solusi CP:

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

Efeknya:

• sync_with_stdio(false) memutus sinkronisasi antara cin/cout dan scanf/printf. Setelah ini, jangan campur cin dengan scanf atau cout dengan printf — urutan tidak terjamin.
• cin.tie(nullptr) melepaskan tie antara cin dan cout. Tanpa tie, cin otomatis flush cout sebelum membaca — operasi yang mahal. Setelah tie(nullptr), flush tidak terjadi otomatis.

Mekanisme: Mengapa Default cin Lambat #

Tiga sumber overhead pada default cin:

1. Sinkronisasi dengan stdio — setiap cin >> x memeriksa apakah buffer scanf perlu di-flush. Tanpa sync, langkah ini di-skip.
2. Tie dengan cout — setiap cin flush cout terlebih dahulu. Untuk input besar, flush berulang menjadi dominan.
3. Locale parsing — cin menghormati locale (titik vs koma untuk desimal). Untuk angka integer, ini overhead yang tidak perlu.

Benchmark nyata pada 10^6 integer di mesin referensi:

Kode: Tiga Level I/O untuk CP #

#include <iostream>
#include <vector>
#include <cstdio>

// ---------- Level 1: cin + sync off (cukup untuk 99% soal) ----------
void setup_fast_io() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

// ---------- Level 2: Custom reader berbasis getchar_unlocked ----------
// Membaca integer dengan mengakumulasi digit satu per satu dari stdin.
static int read_int_fast() {
    int c = getchar_unlocked();
    while (c != '-' && (c < '0' || c > '9')) {
        if (c == EOF) return 0;
        c = getchar_unlocked();
    }
    bool neg = false;
    if (c == '-') { neg = true; c = getchar_unlocked(); }
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar_unlocked();
    }
    return neg ? -x : x;
}

// ---------- Level 3: Custom writer berbasis putchar_unlocked ----------
static void write_int_fast(long long x) {
    if (x < 0) { putchar_unlocked('-'); x = -x; }
    char buf[24];
    int len = 0;
    if (x == 0) { putchar_unlocked('0'); return; }
    while (x > 0) { buf[len++] = '0' + (x % 10); x /= 10; }
    while (len--) putchar_unlocked(buf[len]);
    putchar_unlocked('\n');
}

int main() {
    setup_fast_io();

    int n;
    std::cin >> n;

    // Baca n elemen dengan cin (level 1)
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) std::cin >> a[i];

    // Hitung sum sebagai contoh operasi
    long long sum = 0;
    for (int x : a) sum += x;

    // Cetak hasil dengan cout (level 1) — untuk sebagian besar soal, ini cukup
    std::cout << sum << '\n';

    // Untuk output besar (> 10^6 elemen), gunakan custom writer:
    // write_int_fast(sum);
    return 0;
}

Output yang Dihasilkan (input: 5\n3 9 2 7 5):

26

Bedah Kode Baris-per-Baris #

1. std::ios::sync_with_stdio(false);: matikan sinkronisasi antara C++ stream (cin/cout) dan C stdio (scanf/printf). Setelah ini, hanya boleh pakai salah satu, jangan campur.
2. std::cin.tie(nullptr);: lepas tie antara cin dan cout. Tanpa ini, setiap cin >> x akan mem-flush cout lebih dulu — bottleneck untuk input besar.
3. int c = getchar_unlocked();: baca satu karakter dari stdin tanpa lock (lebih cepat dari getchar pada single-thread). Tidak tersedia di Windows MSVC — gunakan getchar saja untuk portabilitas.
4. while (c != '-' && (c < '0' || c > '9')): skip karakter non-digit dan non-minus (whitespace, newline). Loop berhenti saat menemukan awal angka.
5. if (c == '-') { neg = true; c = getchar_unlocked(); }: tangani tanda negatif. Bila ada -, set flag dan lanjut ke digit pertama.
6. x = x * 10 + (c - '0');: akumulasi digit. Untuk "123", evaluasi: 0*10+1=1, 1*10+2=12, 12*10+3=123.
7. char buf[24]; int len = 0;: untuk writer, simpan digit terbalik ke buffer (digit paling kanan pertama), kemudian cetak dari belakang. Buffer 24 cukup untuk long long (maks 19 digit + tanda).
8. putchar_unlocked(buf[len]); putchar_unlocked('\n');: cetak karakter tanpa lock. Lebih cepat dari printf untuk output besar.

Bahaya endl vs '\n' #

Banyak pemula menggunakan std::endl untuk newline. endl melakukan dua hal: cetak newline dan flush buffer. Flush setiap baris pada output 10^6 baris menyebabkan slowdown 10-50x dibanding '\n'.

Rekomendasi Per Skala Input #

Benchmark Nyata #

Berikut adalah benchmark pada 10^6 integer di mesin referensi (AMD64, g++ 14.2.0, -O2):

=== cin default (mode 1) ===
mode=1  209.667 ms  sum=61175702

=== cin + sync off (mode 2) ===
mode=2   42.479 ms  sum=61175702

=== custom reader (mode 3) ===
mode=3   22.025 ms  sum=61175702

Speedup:

• Mode 1 → Mode 2: 5x lebih cepat (hanya dengan dua baris setup).
• Mode 2 → Mode 3: 2x lebih cepat lagi (custom reader).
• Mode 1 → Mode 3: 10x lebih cepat total.

Ringkasan #

• Tiga tingkat kecepatan I/O: default cin (paling lambat) → sync_with_stdio(false) + tie (5x lebih cepat) → custom getchar_unlocked reader (10x lebih cepat).
• std::ios::sync_with_stdio(false); std::cin.tie(nullptr); wajib di awal main() untuk hampir setiap solusi CP.
• Setelah sync_with_stdio(false), jangan campur cin/cout dengan scanf/printf.
• Gunakan '\n', bukan std::endl — endl flush buffer setiap kali (10-50x lebih lambat).
• Custom reader berbasis getchar_unlocked untuk input > 10^6 elemen.
• I/O cepat bukan solusi untuk algoritma lambat — optimisasi algoritma dulu, kemudian I/O.