KAL
Menu

Iterasi Tanpa Biaya

Kebiasaan performa iterator dibanding loop manual.

Daftar isi

Topik ini membahas klaim zero-cost abstraction pada iterator Rust, yaitu janji bahwa rantai adapter dikompilasi menjadi kode mesin yang setara dengan perulangan manual yang ditulis tangan. Pembahasan mencakup mekanisme di balik klaim itu, mulai dari monomorphization hingga inlining, cara membandingkan pekerjaan kedua bentuk melalui penghitungan yang deterministik, serta pola yang benar-benar menambah biaya tersembunyi seperti koleksi perantara dan dynamic dispatch. Setelah membaca topik ini, pilihan antara rantai iterator dan perulangan manual dapat diambil sebagai perkara kejelasan kode, bukan spekulasi kecepatan, karena kondisi ketika biaya benar-benar muncul sudah terpetakan.

Dari mana klaim tanpa biaya berasal#

Setiap adapter adalah fungsi generik atas tipe iterator konkret, misalnya Filter<I, P> yang membungkus I. Kompilator menjalankan monomorphization, yaitu pembuatan salinan kode untuk setiap kombinasi tipe konkret dalam rantai, sehingga tidak ada kode generik yang tersisa saat program berjalan. Pada setiap salinan, tubuh next yang pendek kemudian di-inline ke pemanggilnya, dan lapisan Filter yang memanggil Map yang memanggil Iter pun runtuh menjadi urutan instruksi yang sama dengan perulangan yang ditulis tangan. Pemeriksa batas indeks juga dapat dibuang ketika pola aksesnya terbukti sehat, sehingga tidak ada ongkos penjaga keamanan yang tersisa.

Program berikut menjumlahkan seribu bilangan dengan kedua bentuk tersebut. Fungsi black_box dari std::hint dipakai untuk menghalangi kompilator melipat masukan menjadi konstanta waktu kompilasi, sehingga penjumlahan benar-benar dikerjakan saat program berjalan, sebagaimana layaknya saat pengukuran performa.

rust jumlah-sama.rs 
use std::hint::black_box;

fn jumlah_loop(data: &[i32]) -> i32 {
    let mut total = 0;
    for &n in data {
        total += black_box(n);
    }
    total
}

fn jumlah_iterator(data: &[i32]) -> i32 {
    data.iter().copied().map(black_box).sum()
}

fn main() {
    let data: Vec<i32> = (1..=1000).collect();

    let a = jumlah_loop(black_box(&data));
    let b = jumlah_iterator(black_box(&data));

    println!("loop     : {}", black_box(a));
    println!("iterator : {}", black_box(b));
    println!("selisih  : {}", a - b);
}
text Keluaran 
loop     : 500500
iterator : 500500
selisih  : 0

Kedua fungsi menghasilkan 500500 dengan selisih nol, dan strukturnya pun setara, yaitu satu lintasan atas seribu elemen dengan satu penjumlahan per elemen serta satu penampung akumulator. Kesetaraan hasil memang dijamin semantik bahasa, sedangkan kesetaraan biaya adalah hasil kerja kompilator pada rantai pendek semacam ini. Verifikasi yang meyakinkan untuk biaya memerlukan pengamatan bahasa rakitan atau pengukuran waktu, dan keduanya bergantung versi kompilator serta mesin, sehingga topik ini memakai perbandingan struktural pada bagian berikutnya.

Membandingkan pekerjaan lewat penghitungan#

Waktu eksekusi bergantung pada mesin dan beban sistem saat pengukuran, sehingga tidak stabil untuk ditampilkan sebagai keluaran contoh. Ukuran yang stabil adalah jumlah pekerjaan, yaitu berapa kali sebuah closure benar-benar berjalan, dan jumlah itu dapat dihitung langsung dari dalam program. Closure pada map menangkap lingkungannya lewat referensi mutable, sehingga closure tersebut dapat menambah pencacah setiap kali dipanggil. Perbandingan jumlah pemanggilan pada dua bentuk kode dengan demikian menjadi proksi yang sah untuk perbandingan biaya, dan nilainya tidak berubah antar-jalankan maupun antar-mesin.

rust jumlah-kerja.rs 
fn main() {
    let data: Vec<i32> = (1..=1000).collect();

    // perulangan manual dengan break setelah tiga hasil terkumpul
    let mut hasil_manual: Vec<i32> = Vec::new();
    for &n in &data {
        if n > 500 {
            hasil_manual.push(n * 2);
            if hasil_manual.len() == 3 {
                break;
            }
        }
    }

    // rantai iterator: closure pada map menghitung pemakaiannya sendiri
    let mut pemakaian = 0;
    let hasil_iterator: Vec<i32> = data
        .iter()
        .filter(|&&n| n > 500)
        .map(|&n| {
            pemakaian += 1;
            n * 2
        })
        .take(3)
        .collect();

    println!("manual   : {:?}", hasil_manual);
    println!("iterator : {:?}", hasil_iterator);
    println!("map jalan: {} kali dari 1000 elemen", pemakaian);
    println!("sama     : {}", hasil_manual == hasil_iterator);
}
text Keluaran 
manual   : [1002, 1004, 1006]
iterator : [1002, 1004, 1006]
map jalan: 3 kali dari 1000 elemen
sama     : true

Kedua bentuk menghasilkan tiga nilai yang sama, dan closure pengali pada rantai iterator berjalan tepat tiga kali meskipun sumbernya memuat seribu elemen. Adapter take(3) memutus aliran begitu hasil ketiga terkumpul, dan karena seluruh rantai lazy, elemen ke-504 sampai ke-1000 tidak pernah disentuh. Perulangan manual mencapai efisiensi yang sama lewat break, sehingga keduanya membaca prefiks yang dibutuhkan saja, tanpa koleksi perantara. Penghitungan semacam ini menjadi bukti struktural bahwa perpindahan antara kedua bentuk tidak menambah langkah kerja.

Pola yang benar-benar menambah biaya#

Sifat tanpa biaya tidak berlaku otomatis pada semua bentuk pemakaian. Pola yang paling lazim menambah biaya adalah collect di tengah rantai, karena hasil antara menjadi koleksi utuh yang harus dialokasikan, diisi, lalu diiterasi ulang pada tahap berikutnya. Rantai yang dipertahankan sampai akhir hanya melakukan satu lintasan tanpa penampungan antara.

rust dua-tahap.rs 
fn main() {
    let data: Vec<i32> = (1..=1000).collect();

    // dua tahap: hasil saringan ditampung vektor, lalu diiterasi lagi
    let saringan: Vec<i32> = data.iter().copied().filter(|&n| n % 3 == 0).collect();
    let total_dua: i32 = saringan.iter().copied().map(|n| n * 2).sum();

    // satu tahap: satu rantai, satu lintasan
    let total_satu: i32 = data
        .iter()
        .copied()
        .filter(|&n| n % 3 == 0)
        .map(|n| n * 2)
        .sum();

    println!("dua tahap              : {}", total_dua);
    println!("satu tahap             : {}", total_satu);
    println!("elemen vektor sementara: {}", saringan.len());
}
text Keluaran 
dua tahap              : 333666
satu tahap             : 333666
elemen vektor sementara: 333

Kedua bentuk menghasilkan 333666, tetapi bentuk dua tahap mengalokasikan vektor sementara berisi 333 elemen, mengisinya lewat satu lintasan saringan, lalu membacanya lagi pada lintasan kedua. Bentuk satu tahap menyelesaikan pekerjaan yang sama dalam satu lintasan tanpa alokasi perantara, dan itulah makna praktis dari menjaga rantai tetap utuh. Biaya serupa muncul pada iterator yang disimpan sebagai Box<dyn Iterator>, karena setiap pemanggilan next dilakukan lewat dynamic dispatch alih-alih pemanggilan langsung yang dapat di-inline. Sifat tanpa biaya melekat pada rantai generik yang tipe konkretnya diketahui kompilator, bukan pada iterator yang tipe disembunyikan di balik trait object.

Kesalahan umum#

Menyisipkan collect demi memecah rantai panjang. Setiap collect perantara mengalokasikan koleksi baru dan memaksa lintasan tambahan saat koleksi itu dibaca lagi. Pecah rantai panjang dengan pemformatan baris atau variabel bernama untuk iterator yang belum dikonsumsi, bukan dengan koleksi jadi.

Menyembunyikan iterator di balik Box tanpa alasan. Trait object menghapus tipe konkret dari pandangan kompilator, sehingga setiap next membayar pemanggilan tidak langsung dan lapisan adaptornya tidak dapat di-inline. Gunakan parameter generik dengan batasan Iterator atau impl Iterator pada tanda tangan, dan gunakan Box<dyn Iterator> hanya ketika satu nilai memang harus menghem banyak tipe iterator berbeda.

Menerjemahkan rantai ke perulangan indeks karena “pasti lebih cepat”. Perulangan indeks manual membawa risiko off-by-one dan pemeriksaan batas yang tidak selalu dapat dihilangkan kompilator, sementara rantai iterator menjaga pola akses yang sehat secara terbukti. Simpan penerjemahan manual untuk saat pengukuran sungguhan menunjukkan rantai sebagai penghambat.

Ringkasan#

  • Rantai adapter menjadi tanpa biaya melalui monomorphization dan inlining yang meruntuhkan lapisan next menjadi kode setara perulangan manual.
  • Perbandingan pekerjaan yang stabil memakai penghitungan closure atau jumlah lintasan, bukan waktu eksekusi yang bergantung mesin dan beban sistem.
  • black_box menghalangi pelipatan konstanta sehingga komputasi contoh benar-benar dikerjakan saat runtime.
  • collect perantara menambah alokasi dan lintasan, sedangkan Box<dyn Iterator> menambah dynamic dispatch pada setiap langkah.

Referensi#