Pemilihan target

Menulis assembly hanya layak dilakukan pada rutin yang pengaruhnya terukur bagi program secara keseluruhan. Topik ini menetapkan kriteria pemilihan target optimasi di antara hashing, parsing byte, dan rutin penyalinan, kemudian membuktikannya dengan satu program FNV-1a 32-bit dalam NASM yang dibandingkan dengan implementasi C yang identik. Setelah topik ini dibaca, pilihan target dapat diputuskan dengan alasan teknis yang jelas, dan keberhasilannya memiliki definisi yang dapat diperiksa lewat checksum, yakni nilai ringkas hasil perhitungan yang digunakan untuk membandingkan keluaran dua implementasi.

Kriteria target yang layak ditulis assembly#

Target yang layak ditulis assembly adalah perhitungan yang berulang sangat sering, berukuran kecil, dan kontribusi waktunya terukur. Perhitungan semacam ini biasanya disebut hot spot, yaitu bagian program yang menyerap sebagian besar waktu berjalan meskipun jumlah kodenya sedikit. Pemilihan tanpa pengukuran berisiko besar, karena usaha menulis assembly pada rutin yang jarang dipanggil tidak pernah terlihat pada waktu berjalan keseluruhan, sedangkan biaya perawatannya tetap dibayar penuh.

Tiga sifat berikut membuat sebuah target realistis untuk ditulis ulang dalam assembly.

• Perulangan intinya kecil dan berjalan jutaan kali, sehingga penghematan beberapa siklus per iterasi terakumulasi menjadi penghematan yang terlihat.
• Datanya besar dan diproses berulang, sehingga waktu berjalan ditentukan oleh throughput, yakni jumlah byte yang selesai diproses per satuan waktu, dan bukan oleh persiapan awal.
• Pola perhitungannya sederhana dan seragam, misalnya operasi yang sama diterapkan pada setiap byte, sehingga tidak banyak percabangan yang menyulitkan penulisan manual.

Kebalikan sifat-sifat itu juga perlu diakui sejak awal. Kode assembly lebih rumit dibaca, terikat pada satu arsitektur dan satu ABI, serta mahal dirawat karena tidak ada compiler yang menata ulang instruksinya secara otomatis. Isi register harus dijaga secara manual, penyelarasan stack harus dihitung sendiri, dan setiap perbaikan algoritma harus ditulis ulang dua kali, sekali dalam C dan sekali dalam assembly. Karena itu, aturan praktisnya adalah menulis assembly hanya pada rutin yang sudah diukur, bukan pada rutin yang diperkirakan lambat.

Tiga kandidat klasik#

Tiga jenis perhitungan paling sering menjadi target yang berhasil, yaitu hashing, parsing byte, dan transformasi buffer. Ketiganya memenuhi kriteria di atas karena memproses deret byte dengan operasi yang sama dan tanpa percabangan yang rumit. Perbedaannya terletak pada bentuk operasinya, sehingga ketiganya layak dipertimbangkan berdampingan sebelum salah satu dipilih.

Hashing seperti FNV-1a menggabungkan setiap byte ke sebuah akumulator 32-bit dengan xor diikuti perkalian, sehingga isi perulangannya hanya dua instruksi aritmetika. Parsing byte, misalnya konversi digit ASCII menjadi angka, mengulangi pengurangan konstanta dan pemeriksaan rentang yang bentuknya sama untuk setiap karakter. Penyalinan atau transformasi buffer memproses data berukuran besar dengan operasi identik per elemen, sehingga cocok dikerjakan dengan instruksi SIMD (single instruction, multiple data), khususnya apabila compiler gagal menghasilkan kode vectorized secara otomatis. Diagram berikut merangkum alur pemilihan dari profil rutin hingga definisi keberhasilannya.

Uji kebenaran dengan FNV-1a 32-bit#

FNV-1a 32-bit menghasilkan hash, yakni nilai numerik 32-bit yang mewakili deret byte, dengan langkah yang sama untuk setiap byte, yaitu xor ke akumulator lalu mengalikannya dengan konstanta. Konstanta awal disebut offset basis dengan nilai 2166136261, sedangkan konstanta pengalinya disebut prime dengan nilai 16777619. Program NASM berikut menghitung hash string tetap “konfirmasi” dan mencetak hasilnya dalam heksadesimal, sehingga nilai yang benar dapat dikonfirmasi terlebih dahulu sebelum membahas kecepatan.

default rel

; FNV-1a 32-bit atas string tetap "konfirmasi".
; Hash dimulai dari offset basis, lalu per byte: xor lalu kali prime.

section .rodata
digit:  db "0123456789abcdef"

section .data
pesan:  db "konfirmasi"
PANJANG equ $ - pesan
baris:  db "fnv1a: 0x00000000", 10
PANJANG_BARIS equ $ - baris

section .text
global _start

_start:
    mov eax, 2166136261        ; offset basis FNV-1a 32-bit
    lea rsi, [pesan]
    mov ecx, PANJANG

per_byte:
    movzx edx, byte [rsi]      ; byte pesan, diperluas tanpa tanda
    xor eax, edx               ; hash ^= byte
    imul eax, eax, 16777619    ; hash *= prime (mod 2^32)
    inc rsi
    dec ecx
    jnz per_byte

    ; format hash ke baris keluaran, digit paling kanan lebih dahulu
    mov ebx, eax
    lea r8, [digit]
    lea rdi, [baris + 16]      ; posisi digit heksadesimal terakhir
    mov ecx, 8
isi_digit:
    mov eax, ebx
    and eax, 0x0F
    movzx edx, byte [r8 + rax]
    mov [rdi], dl
    shr ebx, 4
    dec rdi
    dec ecx
    jnz isi_digit

    ; tulis(1, baris, PANJANG_BARIS), lalu selesai dengan status 0
    mov eax, 1
    mov edi, 1
    lea rsi, [baris]
    mov edx, PANJANG_BARIS
    syscall

    mov eax, 60
    xor edi, edi
    syscall

# rakit, tautkan, lalu jalankan program hash
nasm -f elf64 fnv1a.asm -o fnv1a.o
ld fnv1a.o -o fnv1a
./fnv1a

fnv1a: 0x8750a4ee

Perulangan per_byte memuat satu byte pesan dengan movzx, meng-xor-nya ke eax, lalu mengalikan eax dengan prime menggunakan imul tiga operan yang hasilnya dipotong menjadi 32 bit. Pemotongan itu bukan kebetulan, melainkan tepat sama dengan aritmetika modulo $2^{32}$ yang diminta definisi FNV-1a. Bagian isi_digit hanya pekerjaan penyajian, yaitu mengambil empat bit rendah hash secara berulang dan menerjemahkannya menjadi karakter heksadesimal mulai dari digit paling kanan agar urutannya benar. Nilai 0x8750a4ee itulah acuan kebenaran untuk seluruh versi lain dari rutin ini.

Bukti yang sama diperoleh dari implementasi C identik berikut, yang algoritmenya baris demi baris sama dengan versi assembly.

#include <stdio.h>
#include <stdint.h>

/* Implementasi acuan FNV-1a 32-bit atas string tetap "konfirmasi". */
int main(void) {
    const char *pesan = "konfirmasi";
    uint32_t hash = 2166136261u;               /* offset basis FNV-1a */
    for (int i = 0; pesan[i] != '\0'; i++) {
        hash ^= (uint32_t)(unsigned char)pesan[i];
        hash *= 16777619u;                     /* prime FNV-1a */
    }
    printf("fnv1a: 0x%08x\n", hash);
    return 0;
}

fnv1a: 0x8750a4ee

Kedua versi mencetak baris yang sama persis, dan itulah definisi keberhasilan pertama. Urutan pengerjaannya sengaja disusun demikian, yaitu kebenaran lebih dahulu dan kecepatan kemudian, karena perbandingan kecepatan terhadap versi yang salah tidak memiliki makna apa pun.

Definisi keberhasilan#

Keberhasilan sebuah penulisan ulang assembly ditetapkan sebelum kode pertama ditulis, dan isinya selalu dua butir. Pertama, checksum keluaran identik dengan versi acuan pada data uji yang sama, yang berarti algoritmanya benar-benar setara. Kedua, waktu berjalan turun secara konsisten pada pengukuran yang adil terhadap C yang dikompilasi dengan -O2, bukan terhadap C tanpa optimasi. Versi assembly tidak perlu dinyatakan tercepat di antara semua kemungkinan, cukup lebih cepat daripada acuannya pada target yang sama.

Pengukuran waktu memiliki metodologinya sendiri, mulai dari persamaan beban kerja hingga pengulangan beberapa kali, dan dibahas tersendiri pada topik benchmark terhadap C. Tanpa metodologi itu, angka kecepatan mudah menyesatkan, misalnya ketika versi assembly dibandingkan dengan C yang belum dioptimalkan atau dengan data yang ukurannya berbeda. Definisi ini berlaku dua arah, sehingga versi assembly yang benar tetapi tidak lebih cepat dilaporkan sebagai setara, bukan diuji ulang sampai menang.

Kesalahan umum#

Empat kekeliruan berikut paling sering muncul ketika target optimasi pertama kali dipilih.

• Memilih target berdasarkan perkiraan tanpa pengukuran. Rutin yang tampak lambat sering kali bukan penyumbang waktu terbesar, sehingga ukur dahulu waktu berjalannya dan pilih rutin dengan porsi terbesar yang bentuk perhitungannya sederhana.
• Membandingkan versi assembly dengan C yang dikompilasi tanpa optimasi. Acuan yang sah adalah C dengan -O2, karena itulah tingkat yang akan dihadapi versi assembly di produksi.
• Mengubah algoritma saat menulis ulang. Penulisan ulang bukan tempat memperbaiki algoritma, karena checksum yang berubah berarti versi baru tidak lagi setara dengan aslinya dan perbandingan waktunya tidak sah.
• Membandingkan versi yang belum dirakit ulang setelah suntingan. Keluaran dari biner lama membuat kesimpulan tertuju pada kode yang tidak sedang diperiksa, sehingga rakit ulang kedua versi dari kode sumber terkini sebelum setiap pengukuran.

Ringkasan#

• Target yang layak ditulis assembly adalah rutin panas yang terukur, memproses data besar secara berulang, dan berbentuk perhitungan seragam per byte.
• Tiga kandidat klasiknya adalah hashing seperti FNV-1a, parsing digit ASCII, serta penyalinan dan transformasi buffer.
• Keberhasilan didefinisikan sebagai checksum identik dengan versi acuan diikuti waktu berjalan yang turun pada pengukuran yang adil, bukan gelar tercepat.
• Kontranya adalah kode yang lebih rumit, tidak portabel, dan mahal dirawat, sehingga pemilihan target selalu didahului pengukuran.

Referensi#

• FNV hash — Landon Curt Noll — Halaman resmi algoritma FNV-1a beserta konstanta offset basis dan prime yang dipakai program pada topik ini.
• NASM Documentation — NASM — Manual assembler untuk direktif section, equ, dan bentuk instruksi imul tiga operan pada kode contoh.