Benchmark terhadap C

Benchmark yang adil adalah syarat sebelum satu pun klaim kecepatan boleh dibuat. Topik ini menetapkan metodologi membandingkan program assembly tulisan tangan dengan C yang dioptimalkan, mulai dari persamaan beban kerja, alat ukur, pengulangan, hingga cara melaporkan hasilnya termasuk ketika C ternyata lebih cepat. Dua program peraga digunakan sepanjang topik, yaitu perbandingan hashing FNV-1a yang berakhir setara dan transformasi buffer yang justru dimenangkan oleh compiler C.

Prinsip benchmark yang adil#

Benchmark adalah pengukuran waktu berjalan yang dilakukan dengan mengubah satu variabel saja, yaitu implementasinya, sementara semua variabel lain dipertahankan sama. Prinsip tunggal itu menurunkan lima langkah yang digunakan di seluruh topik ini. Langkahnya berurutan karena setiap langkah hanya bermakna apabila langkah sebelumnya sudah terpenuhi, misalnya angka waktu dari dua versi yang checksumnya berbeda tidak membandingkan pekerjaan yang sama.

Kebalikan prinsip ini adalah perbandingan yang tampak meyakinkan tetapi tidak sah. Contohnya adalah mengukur versi C tanpa optimasi, mengganti ukuran data di tengah perbandingan, atau mengutip satu eksekusi terbaik dari banyak percobaan. Ketiganya mengubah lebih dari satu variabel sekaligus, sehingga perbedaan yang terukur tidak lagi dapat disandarkan pada implementasinya. Diagram berikut merangkum kelima langkah tersebut sebagai satu alur kerja.

Program benchmark yang identik#

Program peraga pertama menghitung hash FNV-1a 32-bit secara berantai sebanyak lima juta putaran atas string tetap “konfirmasi”. Rantai berarti hash akhir satu putaran menjadi hash awal putaran berikutnya, sehingga hasil tiap putaran selalu dibutuhkan oleh putaran berikutnya dan compiler tidak dapat memangkas perulangannya sebagai perhitungan yang sia-sia. Keluarannya adalah satu baris checksum lebar sepuluh digit dengan angka nol di depan bila perlu, sehingga dua versi mudah dibandingkan hingga tanda terakhirnya.

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

/* Benchmark FNV-1a 32-bit: hash dirantai sebanyak PUTARAN kali atas
   string tetap, lalu dicetak sebagai satu baris checksum deterministik. */
#define PUTARAN 5000000
#define PRIME 16777619u

int main(void) {
    const char *pesan = "konfirmasi";
    uint32_t hash = 2166136261u;               /* offset basis FNV-1a */
    for (int k = 0; k < PUTARAN; k++) {
        for (int i = 0; pesan[i] != '\0'; i++) {
            hash ^= (uint32_t)(unsigned char)pesan[i];
            hash *= PRIME;                     /* prime FNV-1a */
        }
    }
    printf("checksum: %010u\n", hash);
    return 0;
}

checksum: 2969014853

Versi assembly berikut menjalankan algoritma yang sama dengan bentuk perulangan yang sama, yaitu xor lalu kali prime untuk setiap byte di dalam setiap putaran.

default rel

; Benchmark FNV-1a 32-bit: hash dirantai sebanyak PUTARAN kali atas
; string tetap, lalu dicetak sebagai satu baris checksum deterministik.
; Format keluaran sama dengan bench.c, yaitu sepuluh digit desimal
; dengan angka nol di depan bila perlu.

section .data
pesan:  db "konfirmasi"
PANJANG equ $ - pesan
baris:  db "checksum: 0000000000", 10
PANJANG_BARIS equ $ - baris

section .text
global _start

PUTARAN equ 5000000

_start:
    mov ebx, 2166136261        ; hash awal = offset basis FNV-1a
    mov r13d, PUTARAN
putaran:
    lea rsi, [pesan]
    mov ecx, PANJANG
per_byte:
    movzx edx, byte [rsi]      ; byte pesan, diperluas tanpa tanda
    xor ebx, edx               ; hash ^= byte
    imul ebx, ebx, 16777619    ; hash *= prime (mod 2^32)
    inc rsi
    dec ecx
    jnz per_byte
    dec r13d
    jnz putaran

    ; format checksum sebagai sepuluh digit desimal, dari kanan
    mov eax, ebx
    mov ebx, 10                ; pembagi
    lea rdi, [baris + 20]      ; satu posisi di kanan digit terakhir
    mov ecx, 10
isi_digit:
    xor edx, edx
    div ebx                    ; eax = hasil bagi, edx = satu digit
    add edx, '0'
    dec rdi
    mov [rdi], dl
    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

Kedua berkas dibangun dan dijalankan dalam satu blok berikut, dengan opsi -O2 pada sisi C sebagai acuan yang sah. -O2 dipilih karena itulah tingkat optimasi yang wajar digunakan dalam kode produksi, sehingga versi assembly diukur terhadap lawan yang sebenarnya. Baris checksum keduanya identik, sehingga langkah kebenaran dan persamaan beban kerja terpenuhi.

# bangun kedua versi dengan beban kerja yang sama persis
gcc -O2 bench.c -o bench-c
nasm -f elf64 bench.asm -o bench.o
ld bench.o -o bench-asm

# jalankan keduanya dan bandingkan baris checksumnya
./bench-c
./bench-asm

checksum: 2969014853
checksum: 2969014853

Mengukur waktu dengan time#

Kata kunci time milik shell mengukur satu perintah dan melaporkan tiga durasinya, yaitu waktu nyata (real) sejak perintah dimulai hingga selesai, waktu pemroses (user) yang dihabiskan kode program, dan waktu sistem (sys) yang dihabiskan di dalam kernel. Laporan time ditulis ke stderr dan isinya berubah dari satu eksekusi ke eksekusi lain, sehingga tidak pernah dimasukkan ke dalam blok keluaran yang dibandingkan secara ketat. Sebagai ilustrasi bentuknya, satu eksekusi ./bench-c pada lingkungan penulisan topik ini melaporkan real 0m0.057s, dengan penekanan bahwa nilai itu berbeda antar mesin dan antar eksekusi.

Cara yang digunakan di sini adalah menggabungkan stderr ke dalam saluran keluaran lalu menyaring baris checksum dengan grep, sehingga blok berikut tetap deterministik dan angka waktunya dibahas terpisah dalam prosa.

# ukur kedua versi dengan time, tampilkan hanya baris checksumnya
{ time ./bench-c ; } 2>&1 | grep checksum
{ time ./bench-asm ; } 2>&1 | grep checksum

checksum: 2969014853
checksum: 2969014853

Pengukuran lima eksekusi per versi pada mesin penulisan topik ini memberi rentang sekitar 0,057 sampai 0,058 detik untuk kedua versi, tanpa pemenang yang konsisten. Kesimpulan yang jujur dari data tersebut adalah keduanya setara. Hasil ini masuk akal secara teknis, karena rantai perkalian FNV-1a bersifat serial, sedangkan compiler C juga menghasilkan perulangan serial yang sama padatnya untuk pola tersebut, sehingga versi assembly tidak memiliki celah untuk menang maupun kalah jauh.

Ketika C lebih cepat#

Perbandingan kedua menunjukkan sisi yang jarang ditampilkan pada contoh assembly, yaitu kekalahan versi tulisan tangan. Program berikut meng-xor setiap byte buffer 4 MiB dengan 0x5A sebanyak 100 putaran, lalu menjumlahkan seluruh byte sebagai checksum. Beban kerjanya identik di kedua versi, dan versi assembly-nya sengaja ditulis skalar, yaitu satu byte per iterasi, sebagaimana implementasi pertama yang wajar.

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

/* Transformasi buffer: setiap byte di-xor dengan 0x5A sebanyak PUTARAN
   kali, lalu jumlah seluruh byte dicetak sebagai checksum. Buffer diisi
   dengan pola tetap agar hasilnya deterministik. */
#define UKURAN (4 * 1024 * 1024)
#define PUTARAN 100

static unsigned char data[UKURAN];

int main(void) {
    for (unsigned long i = 0; i < UKURAN; i++) {
        data[i] = (unsigned char)(i * 31 + 7);
    }
    for (int k = 0; k < PUTARAN; k++) {
        for (unsigned long i = 0; i < UKURAN; i++) {
            data[i] ^= 0x5A;
        }
    }
    unsigned long checksum = 0;
    for (unsigned long i = 0; i < UKURAN; i++) {
        checksum += data[i];
    }
    printf("checksum: %010lu\n", checksum);
    return 0;
}

checksum: 0534773760

Versi assembly berikut memproses buffer yang sama dengan perulangan skalar byte-per-byte.

default rel

; Versi skalar byte-per-byte dari transformasi yang sama dengan
; transform.c: isi buffer dengan pola tetap, xor 0x5A sebanyak PUTARAN
; kali, jumlahkan seluruh byte, lalu cetak checksum lebar sepuluh digit.

section .bss
data:   resb 4194304

section .data
baris:  db "checksum: 0000000000", 10
PANJANG_BARIS equ $ - baris

section .text
global _start

UKURAN  equ 4194304
PUTARAN equ 100

_start:
    ; isi data[i] = (i * 31 + 7) mod 256
    lea rdi, [data]
    xor rsi, rsi
isi_buffer:
    mov rax, rsi
    imul eax, eax, 31
    add eax, 7
    mov [rdi + rsi], al
    inc rsi
    cmp rsi, UKURAN
    jne isi_buffer

    ; PUTARAN kali transformasi xor byte-per-byte
    mov r13d, PUTARAN
putaran:
    lea rdi, [data]
    mov ecx, UKURAN
xor_byte:
    xor byte [rdi], 0x5A
    inc rdi
    dec ecx
    jnz xor_byte
    dec r13d
    jnz putaran

    ; jumlahkan seluruh byte
    lea rdi, [data]
    mov ecx, UKURAN
    xor r10, r10
jumlah:
    movzx edx, byte [rdi]
    add r10, rdx
    inc rdi
    dec ecx
    jnz jumlah

    ; format checksum sebagai sepuluh digit desimal, dari kanan
    mov eax, r10d
    mov ebx, 10
    lea rdi, [baris + 20]
    mov ecx, 10
isi_digit:
    xor edx, edx
    div ebx
    add edx, '0'
    dec rdi
    mov [rdi], dl
    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

# bangun kedua versi transformasi dengan beban kerja yang sama
gcc -O2 transform.c -o transform-c
nasm -f elf64 transform.asm -o transform.o
ld transform.o -o transform-asm

# checksum keduanya harus identik sebelum waktu dibandingkan
./transform-c
./transform-asm

checksum: 0534773760
checksum: 0534773760

Checksum keduanya identik, tetapi waktunya tidak. Pada lima eksekusi per versi di mesin penulisan topik ini, versi C berada di sekitar 0,025 detik sedangkan versi assembly berada di sekitar 0,13 detik, yaitu sekitar lima kali lebih lambat, dengan catatan bahwa angka pasti berubah antar mesin. Penyebabnya terlihat pada hasil disasembli versi C, yang perulangan xor-nya diganti oleh compiler menjadi instruksi pxor 128-bit, sehingga enam belas byte diproses dalam satu instruksi. Perulangan xor yang seragam memang termasuk yang pertama diubah menjadi kode vectorized oleh compiler, sedangkan versi skalar menyerahkan keunggulan itu kepada compiler. Pelajarannya sesuai metodologi di atas, yaitu hasil dilaporkan apa adanya, dan jalan untuk menang bukan mengabaikan hasilnya, melainkan memanfaatkan SIMD secara eksplisit di dalam assembly.

Kesalahan umum#

Empat kekeliruan berikut paling sering muncul ketika benchmark pertama kali dilakukan.

• Mengukur sebelum checksum identik. Waktu dari versi yang menghitung hasil berbeda bukan perbandingan, sehingga pastikan baris checksum sama persis sebelum time pertama dijalankan.
• Menggunakan beban kerja yang berbeda diam-diam, misalnya jumlah putaran atau ukuran data yang tidak sama. Perbedaan itu mengubah pekerjaan yang diukur, sehingga samakan konstantanya di kedua kode sumber dan periksa ulang sebelum mengeksekusi.
• Mengutip satu eksekusi terbaik. Eksekusi tercepat dari lima percobaan adalah keberuntungan, bukan kinerja, sehingga laporkan rentang beberapa eksekusi dan nyatakan pula apabila tidak ada pemenang yang konsisten.
• Mengukur biner yang lama setelah kode disunting. Kesimpulan tertuju pada program yang tidak sesuai kode sumber terkininya, sehingga bangun ulang kedua versi sebelum setiap sesi pengukuran.

Ringkasan#

• Benchmark yang sah mengubah satu variabel saja, yaitu implementasinya, dengan checksum identik, beban kerja sama, alat ukur sama, dan opsi compiler -O2 di kedua sisi.
• Hash dirantai antar putaran agar compiler tidak dapat memangkas perulangan, dan baris checksum yang identik menjadi bukti kebenaran sebelum waktu dibandingkan.
• Angka waktu bersifat variabel, sehingga diukur dengan time beberapa kali dan dilaporkan sebagai rentang dalam prosa, bukan sebagai blok keluaran.
• Compiler C dapat memenangkan perbandingan dengan mengubah perulangan menjadi kode vectorized secara otomatis, sehingga hasil yang jujur mencakup kekalahan versi assembly dan penyebab teknisnya.

Referensi#

• GCC 14.2 manual: Optimize Options — Free Software Foundation — Dokumentasi opsi -O2 yang dipakai sebagai tingkat optimasi acuan pada kedua sisi perbandingan.
• time(1) — Linux man-pages project — Dokumentasi pengukur waktu beserta makna durasi real, user, dan sys yang dirujuk topik ini.
• FNV hash — Landon Curt Noll — Halaman resmi konstanta FNV-1a yang dipakai program benchmark pada topik ini.