Meningkatkan Performa Kode 4 Kali dengan `if` yang Tidak Berguna

• Dengan menambahkan satu conditional statement ke loop yang menelusuri jalur encoding optimal pada kompresor khusus domain, waktu eksekusi benchmark sintetis turun dari 320µs menjadi 80µs
• Karena pada setiap iterasi alamat memori bergantung pada j dari iterasi sebelumnya, bahkan satu instruksi mov pun tidak dapat memanfaatkan instruction-level parallelism dan terikat oleh latensi akses memori
• Jika karakteristik bahwa next_j[i][j] sebagian besar sama dengan j yang lama direfleksikan ke branch prediction, CPU dapat melewati dependensi antar-iterasi dan mengeksekusi secara spekulatif beberapa iterasi
• Menggunakan cast volatile agar compiler tidak menghapus if yang secara semantik tidak perlu. Di LLVM, [[unlikely]] atau __builtin_expect(..., 0) juga bekerja, tetapi volatile menghasilkan kode yang lebih baik dan juga didukung GCC
• Dalam eksperimen realistis, diperoleh peningkatan performa sekitar 2 kali yang mungkin disebabkan oleh code generation LLVM yang tidak optimal; jika j sulit diprediksi, pshufb dengan latensi 1 siklus dapat digunakan sebagai alternatif

---

Menelusuri Jalur Optimal Kompresor

• String input harus dibagi menjadi beberapa chunk, dan encoding terkecil harus dipilih untuk tiap chunk
  • Karena setiap encoding berbeda dalam karakter yang dapat dikompresi dengan baik, batas chunk sulit ditentukan langsung
  • Algoritme dari artikel sebelumnya mengubah masalah ini menjadi pencarian jalur terpendek di atas grid
• Setiap sel mencatat sel optimal yang harus dituju berikutnya
  • Dengan mengikuti referensi dari sel pertama hingga sel terakhir, urutan encoding optimal dapat diperoleh
• Loop pertama yang mengisi next_j sudah dioptimalkan dengan SIMD
  • Bottleneck sebenarnya adalah loop penelusuran jalur sederhana seperti berikut

uint8_t encoding[n_symbols];
uint8_t j = 0;

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}

• Operasi inti selain penulisan, yaitu j = next_j[i][j], dikompilasi menjadi satu instruksi mov

Dependensi yang Membuat Satu Instruksi pun Lambat

• CPU modern menjalankan beberapa instruksi dan pekerjaan dari iterasi yang berbeda secara bersamaan menggunakan instruction-level parallelism
  • Inilah alasan mengapa dalam loop umum biaya pemeriksaan i < n_symbols dan i++ tidak menghambat pekerjaan lain
• Namun, instruksi yang saling bergantung tidak dapat dijalankan bersamaan
  • Untuk menghitung alamat memori next_j[i][j] pada iterasi saat ini, diperlukan j yang diperoleh dari iterasi sebelumnya
  • Iterasi berikutnya tidak dapat dimulai sampai hasil iterasi sebelumnya keluar, sehingga tetap terpengaruh latensi akses memori meskipun datanya ada di cache

Memanfaatkan Branch Prediction sebagai Value Speculation

• Kompresor ini diperkirakan tidak memiliki banyak chunk, sehingga next_j[i][j] hampir selalu sama dengan j yang sudah ada
• Kita tidak bisa secara langsung memberi tahu CPU untuk memprediksi alamat bahwa j akan tetap sama, tetapi efek yang sama bisa dibuat dengan memanfaatkan branch prediction

for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}

• Jika CPU memprediksi bahwa body if tidak akan dijalankan, CPU menganggap tidak ada dependensi antar-iterasi untuk memperbarui j dan mengeksekusi beberapa iterasi secara spekulatif
• Jika kondisi ternyata benar, terjadi pemulihan dari branch misprediction
  • Penulisan yang dilakukan berdasarkan spekulasi yang salah dibatalkan
  • Eksekusi dimulai ulang dengan j yang benar
• Selama j hampir tidak berubah, bottleneck loop bergeser dari latensi ke throughput

Mencegah Compiler Menghapus if

• Dari sudut pandang compiler, kode yang menambahkan conditional statement dan kode awal memiliki makna yang sama
  • Jika j berada di memori, penulisan yang tidak perlu atau penulisan ke memori read-only dapat dihindari, tetapi di sini ia adalah nilai register
  • Optimisasi seperti common subexpression elimination (CSE) dapat menghapus kondisi dan akses duplikat
• Hint compiler umumnya dipakai untuk menghilangkan branch, tetapi di sini sebaliknya: kode tanpa branch harus dipertahankan sebagai kode bercabang
• Terapkan cast volatile pada sisi assignment agar akses memori untuk pemeriksaan kondisi dan assignment terlihat seolah-olah independen

for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}

• Dalam konfirmasi tambahan pada 13 Juli, seperti metode yang ditemukan ibookstein, penggunaan [[unlikely]] atau __builtin_expect(..., 0) juga bisa mendapatkan efek yang sama di LLVM
• Metode volatile menghasilkan kode yang lebih baik dan juga bekerja di GCC

Perubahan Performa yang Dikonfirmasi di Benchmark

• Dalam benchmark sintetis, waktu eksekusi loop turun dari 320µs menjadi 80µs, sehingga 4 kali lebih cepat
  • Perbedaan waktu dalam satu eksekusi memang kecil, tetapi karena loop dijalankan berkali-kali selama proses kompresi, biayanya terakumulasi pada keseluruhan proses
• Dalam eksperimen yang lebih realistis, tercatat peningkatan performa sekitar 2 kali
  • Kemungkinan ada pengaruh dari LLVM yang menghasilkan kode tidak optimal, tetapi level peningkatannya tetap layak diterapkan

Alternatif Berupa Representasi Berbasis Bitmask

• Dalam algoritme ini, next_j[i][j] hanya dapat memiliki salah satu dari dua nilai
  • Sebagian besar adalah j saat ini
  • Sisanya adalah nilai yang tidak bergantung pada j dan hanya bergantung pada i
• Array next_j[i] berisi 8 elemen dapat diganti dengan pasangan nilai pengganti dan bitmask
  • Dalam representasi ini, if memang diperlukan secara semantik, sehingga tidak perlu memakai bypass volatile
  • Namun di x86, operasi untuk memeriksa bit pada posisi variabel bisa lebih lambat daripada perbandingan, sehingga performa keseluruhan justru berpotensi lebih rendah

Saat j Tidak Dapat Diprediksi

• Artikel tentang mempercepat penelusuran linked list dengan value speculation juga membahas cara meningkatkan performa dengan metode yang sama
• Jika j sulit diprediksi, operasi indeks vektor pshufb dapat digunakan
  • Latensi pshufb adalah 1 siklus, sehingga sulit dipangkas lebih jauh tanpa eksekusi spekulatif
  • Dengan operasi vektor, jalur untuk setiap kemungkinan j awal dapat dihitung secara paralel
  • Pekerjaan juga bisa dibagi ke beberapa thread lalu hasilnya digabungkan

[GN⁺]

Pendapat di Lobste.rs

• Menambahkan atribut [[unlikely]] C++20 ke pernyataan if tampaknya cukup untuk mencegah clang menghapus kode tersebut: https://clang.godbolt.org/z/r4xYWfPfe
  Belum dicek di compiler lain

  • Setelah dicek lagi, ini memang bekerja di LLVM, dan kemungkinan awalnya saya keliru mencobanya di GCC yang tidak memberi efek
    Namun [[unlikely]] memindahkan kode keluar dari jalur cepat, sehingga LLVM menghasilkan kode yang agak kurang efisien seperti di bawah ini

            cmp     r8b, dl  
            jne     not_equal  
    continue:  
            ...  
    not_equal:  
            mov     ecx, edx  
            jmp     continue  
    

    Bentuk berikut tampak lebih masuk akal

            cmp     r8b, dl  
            je      skip  
            mov     ecx, edx  
    skip:  
            ...  
    

    Selain itu, sembari mengoptimalkan agar nilai tidak dibaca berkali-kali dari memori, ia juga menambahkan satu instruksi ke loop yang panas. Jadi teknik menggunakan volatile masih berguna, tetapi menyenangkan bahwa kode aslinya juga bisa tetap bekerja apa adanya

• Teknik ini di tempat lain disebut value speculation: https://mazzo.li/posts/value-speculation.html

  • Setelah menemukan kembali metode ini, saya awalnya berpikir metode ini juga bisa diterapkan pada linked list yang disimpan di arena, dan tulisan yang ditautkan itu ternyata membahas persis hal tersebut, jadi saya menambahkan tautannya ke tulisan saya

• Dalam 2–3 tahun ke depan, developer akan makin tidak peduli pada output LLM; saya penasaran apakah mereka masih akan tertarik pada artikel blog semacam ini

  • Bahkan sekarang pun sangat sedikit orang yang tertarik, dan dalam keseluruhan bidang pemrograman ini adalah pengetahuan niche
    Namun bagi orang yang tertarik, ini tetap tulisan yang sangat berguna dan bagus
  • Godbolt sangat populer. Ketika dikritik karena kebiasaan tidak membaca kode, para developer yang mabuk LLM menjawab “sampai lihat assembly juga?” seolah itu bantahan hebat, tetapi kenyataannya orang memang memeriksa assembly dan akan terus begitu
    Developer yang menganggap detail tidak penting sulit menjadi developer yang baik. Seperti insinyur sipil hebat yang memperhatikan sampai baut dan mur dalam proyek besar, developer hebat juga harus menggali sampai detail kecil. Keseluruhan tersusun dari detail, jadi jika Anda peduli pada hasil yang Anda buat, hal ini tidak bisa dihindari
  • Menurut saya secara mendasar tidak berbeda dari sekarang. Saat ini pun kebanyakan orang tidak tertarik pada output compiler dari kode yang ditulis manusia
    Jumlah orang yang melihat output compiler dari kode yang ditulis AI mungkin bisa lebih sedikit, tetapi susunan dasarnya sepertinya tidak akan berubah
  • Yang berubah lebih dekat ke penyusunan ulang prioritas optimasi daripada ada tidaknya minat
    Sepuluh tahun lalu, hanya karena script Bash sedikit lambat, orang tidak akan langsung memikirkan parallelism tingkat instruksi atau branch prediction CPU. Bisa saja ada bagian inti performa yang ditulis dalam bahasa yang dapat dikompilasi dan dioptimalkan, di dalamnya ada jalur panas yang perlu ditelaah detail, dan lebih jauh lagi ada satu atau dua loop panas yang layak dicek dari sisi vektorisasi atau perbedaan perilaku CPU modern
    Meski menggunakan LLM, titik paling panas dari sisi performa tetap layak ditinjau langsung sebagai pengecualian. Entah secara sadar menerima kualitas output yang rendah, atau membuat 70% dengan LLM lalu memperbaiki 30% sisanya secara manual hingga rasio itu bisa membaik menjadi 85:15, tulisan ini tetap membahas ranah detail level 1% teratas
  • Karena saya tidak menulis C++, dalam arti itu ini bahkan sekarang bukan minat langsung saya, tetapi saya tetap membacanya dengan menarik, dan saya rasa konten seperti ini akan tetap menarik 2–3 tahun lagi