Debug backend SIMD sering terasa menyulitkan karena bug-nya jarang muncul sebagai crash yang jelas. Pada parser data biner berperforma tinggi, kesalahan kecil pada zigzag decode bisa membuat beberapa integer negatif atau positif sesekali salah, lalu merusak data turunan seperti offset, ukuran payload, atau delta timestamp. Yang paling berbahaya: hasil path scalar benar, tetapi path SIMD menghasilkan nilai berbeda hanya pada pola input tertentu.

Artikel ini membahas studi kasus salah decode zigzag pada backend parser yang memakai SIMD/AVX-512 sebagai konteks utama. Tujuannya bukan sekadar menjelaskan rumus zigzag, tetapi menunjukkan cara membedah gejala, membangun reproduksi minimal, menemukan akar masalah yang realistis, lalu memperbaiki implementasi tanpa mengorbankan performa.

Apa itu zigzag decode dan kenapa bug kecil langsung berbahaya

Zigzag encoding umum dipakai untuk menyimpan bilangan bertanda sebagai bilangan tak bertanda agar nilai dengan magnitudo kecil tetap hemat ruang saat digabung dengan varint atau format biner lain. Rumus decode scalar yang lazim untuk 32-bit secara konsep adalah:

decoded = (encoded >> 1) ^ -(encoded & 1)

Untuk 64-bit, ide dasarnya sama. Bit paling rendah menyimpan tanda, sisanya menyimpan magnitudo yang digeser satu bit.

Masalahnya, implementasi SIMD sering tidak sekadar menerjemahkan rumus di atas ke instruksi vektor. Ada detail penting seperti:

  • lebar lane: 16-bit, 32-bit, atau 64-bit,
  • jenis shift: logical vs arithmetic,
  • cara membentuk mask tanda,
  • perilaku sign extension saat berpindah lane width,
  • urutan operasi ketika data masih berada di register vector.

Jika satu detail salah, hasilnya mungkin tampak benar untuk mayoritas data, tetapi salah untuk subset input tertentu. Dalam parser backend, kesalahan ini bisa memicu:

  • delta ID menjadi terlalu besar atau negatif,
  • offset buffer melompat,
  • panjang record salah sehingga field berikutnya ikut bergeser,
  • checksum atau agregasi turunannya ikut korup,
  • repro berbeda antara CPU tanpa SIMD dan CPU dengan path SIMD aktif.

Gejala nyata di produksi

Kasus yang paling sering membingungkan bukan crash, melainkan korupsi data diam-diam. Gejalanya bisa terlihat seperti:

  • hanya sebagian kecil record gagal divalidasi,
  • nilai signed delta kadang berubah tanda, misalnya seharusnya -1 menjadi 2147483647 atau nilai besar lain,
  • path scalar di lingkungan development lulus semua tes, tetapi server produksi dengan fitur SIMD aktif memunculkan anomali,
  • rerun pada data yang sama menghasilkan hasil konsisten per mesin, namun berbeda antar mesin karena jalur eksekusinya berbeda.

Dalam sistem backend, ini sering terlihat lebih dulu sebagai gejala sekunder:

  • jumlah entitas hasil parsing berbeda dari input yang sama,
  • upsert database melonjak karena primary key turunan salah,
  • kompresi atau deduplikasi turun drastis karena delta tidak lagi kecil,
  • pipeline downstream menolak batch karena field length atau monotonicity rusak.

Catatan penting: bug decode zigzag tidak selalu muncul di titik decode. Sering kali gejalanya baru terlihat beberapa tahap setelah parser selesai, misalnya saat membangun array offset, indeks sekunder, atau object graph.

Membangun reproduksi minimal yang benar-benar berguna

Kesalahan umum saat debugging SIMD adalah langsung membaca assembly atau mencoba optimasi balik tanpa terlebih dahulu membuat reproduksi minimal. Padahal target awalnya sederhana: temukan input sekecil mungkin yang menghasilkan output berbeda antara scalar dan SIMD.

1. Isolasi fungsi decode

Pisahkan parser penuh menjadi fungsi kecil yang hanya menerima array nilai encoded dan menghasilkan array decoded. Hindari dulu I/O, varint parser, alokasi kompleks, atau transformasi lanjutan.

// Scalar reference: definisikan sebagai sumber kebenaran yang sederhana dan jelas.
static inline int32_t zigzag_decode32_scalar(uint32_t x) {
    return (int32_t)((x >> 1) ^ (uint32_t)-(int32_t)(x & 1));
}

void decode_scalar(const uint32_t* in, int32_t* out, size_t n) {
    for (size_t i = 0; i < n; ++i) {
        out[i] = zigzag_decode32_scalar(in[i]);
    }
}

Reference scalar sebaiknya mudah dibaca dan tidak terlalu pintar. Fungsi ini akan menjadi oracle untuk membandingkan semua implementasi lain.

2. Pakai fixture input yang memukul edge case

Jangan hanya mengetes angka acak. Sertakan pola yang memang rawan pada zigzag dan SIMD:

  • 0, 1, 2, 3,
  • batas kecil: 0x7f, 0x80, 0xff,
  • batas lane: 0x7fff, 0x8000, 0xffff,
  • batas 32-bit: 0x7ffffffe, 0x7fffffff, 0xfffffffe, 0xffffffff,
  • pola campuran ganjil-genap,
  • jumlah elemen yang tidak kelipatan lebar vektor.

3. Diff output scalar vs SIMD

Saat mismatch muncul, jangan hanya mencetak "failed". Cetak indeks, nilai encoded, hasil scalar, hasil SIMD, dan representasi heksadesimalnya.

for (size_t i = 0; i < n; ++i) {
    if (out_scalar[i] != out_simd[i]) {
        printf("i=%zu enc=0x%08x scalar=%d (0x%08x) simd=%d (0x%08x)\n",
               i,
               in[i],
               out_scalar[i], (uint32_t)out_scalar[i],
               out_simd[i],   (uint32_t)out_simd[i]);
        break;
    }
}

Output seperti ini jauh lebih bernilai daripada log parser besar yang penuh noise. Representasi heksadesimal sering langsung menunjukkan apakah masalahnya ada pada sign bit, shift, atau lane truncation.

4. Simpan input mentah yang gagal

Begitu ada mismatch, simpan fixture tersebut sebagai regresi test. Hindari mengandalkan data produksi utuh yang sulit diputar ulang.

Akar masalah yang masuk akal pada decode zigzag SIMD

Berikut akar masalah yang sering realistis pada implementasi parser backend berbasis SIMD. Tidak semua harus terjadi sekaligus; satu saja sudah cukup membuat hasil salah.

Sign extension yang salah

Formula zigzag decode membutuhkan mask semua-bit-1 ketika bit rendah bernilai 1. Pada scalar, ekspresi -(x & 1) tampak sederhana. Pada SIMD, pembentukan mask sering dilakukan dengan compare, subtract, atau shift. Bug muncul jika mask yang dihasilkan hanya berlaku pada lane 16-bit, lalu dipakai seolah-olah 32-bit atau 64-bit.

Contoh pola bug:

  • mask tanda terbentuk sebagai 0x0001 atau 0xffff per 16-bit lane, bukan 0xffffffff per 32-bit lane,
  • hasil kemudian di-xor dengan nilai 32-bit, sehingga hanya separuh lane yang terpengaruh,
  • angka kecil tampak benar, tapi angka dengan bit tinggi aktif mulai rusak.

Lane width tidak konsisten

Instruksi SIMD bekerja per lane. Jika encoded value diperlakukan sebagai 16-bit pada satu tahap dan 32-bit pada tahap berikutnya, Anda bisa kehilangan bit tinggi atau membuat sign extension yang salah. Ini sering terjadi saat mencoba menggabungkan unpack, shuffle, dan shift demi mengejar throughput.

Gejalanya biasanya:

  • nilai tertentu benar pada lane awal tetapi salah pada lane lain,
  • error muncul setiap kelipatan tertentu, misalnya setiap 8 atau 16 elemen,
  • angka besar lebih sering salah daripada angka kecil.

Logical shift vs arithmetic shift

Zigzag decode umumnya membutuhkan x >> 1 pada bilangan encoded tak bertanda, lalu XOR dengan mask tanda. Jika implementasi SIMD keliru memakai operasi yang menganggap data sudah signed, atau membentuk mask dari shift arithmetic pada lane yang belum benar tipenya, hasilnya bisa meleset.

Kesalahan paling umum adalah berpikir bahwa shift arithmetic bisa menggantikan pembentukan mask tanda dalam semua bentuk transformasi. Padahal urutan operasi dan tipe lane sangat menentukan.

Overflow dan UB pada C/C++

Pada kode scalar, penulisan yang tampak ringkas kadang menyimpan risiko jika melibatkan signed overflow atau konversi implisit yang tidak jelas. Memang formula zigzag dapat ditulis aman, tetapi versi yang terlalu kreatif bisa mengundang perilaku yang sulit dipetakan ke SIMD.

Contoh yang perlu dihindari:

  • menggeser signed negative secara sembarangan,
  • mengandalkan perilaku implementasi untuk cast yang ambigu,
  • mencampur int, long, dan tipe intrinsics tanpa kontrol eksplisit.

Jika scalar reference sendiri tidak tegas tipenya, compiler dapat mengoptimalkan dengan asumsi yang tidak identik dengan path intrinsics.

Alignment dan load/store yang tidak identik

Secara teori, zigzag decode tidak bergantung pada alignment. Namun bug praktis bisa muncul jika path SIMD membaca blok lebih lebar, memakai tail handling berbeda, atau memiliki fallback yang salah pada elemen sisa. Akibatnya, masalah terlihat seolah-olah pada rumus decode, padahal sumbernya ada di cara memuat dan menyimpan lane terakhir.

Fallback scalar tidak identik dengan fast path

Ini salah satu sumber mismatch yang paling sering diabaikan. Implementasi SIMD memproses mayoritas elemen, lalu tail diproses scalar. Jika scalar fallback memakai tipe berbeda, urutan operasi berbeda, atau bahkan helper lama yang tidak sama, hasil bisa berbeda hanya pada batch dengan panjang tertentu.

Dalam parser backend, bug seperti ini sering lolos karena data benchmark memakai jumlah elemen yang kebetulan pas kelipatan lebar vektor.

Langkah investigasi yang efektif

Bandingkan path scalar dan SIMD dengan oracle yang sama

Poin pentingnya adalah semua path harus dibandingkan terhadap satu implementasi referensi yang sederhana. Jangan membandingkan SIMD baru dengan SIMD lama jika keduanya berpotensi punya bug yang sama.

Tambahkan logging heksadesimal per tahap

Jika mismatch belum jelas, log nilai intermediate pada satu batch kecil:

  • encoded asli,
  • hasil shift kanan satu bit,
  • mask tanda per lane,
  • hasil XOR akhir.

Untuk SIMD, Anda tidak perlu mencetak seluruh register setiap saat. Cukup dump lane ke array lokal pada input yang gagal.

alignas(64) uint32_t tmp_shift[16];
alignas(64) uint32_t tmp_mask[16];
alignas(64) uint32_t tmp_out[16];

// Simpan register sementara ke buffer lalu printf dalam hex.
// Teknik ini sering lebih cepat dipahami daripada membaca intrinsics mentah.

Dengan log heksadesimal, pola bug seperti mask 0x0000ffff yang seharusnya 0xffffffff langsung terlihat.

Gunakan property-based test

Property-based test sangat cocok untuk kasus ini karena zigzag memiliki properti matematis yang jelas. Beberapa properti berguna:

  • decode(encode(x)) == x untuk semua domain yang diuji,
  • hasil scalar dan SIMD harus identik untuk input yang sama,
  • output decode harus stabil terhadap pemotongan batch: decode satu blok penuh harus sama dengan decode yang dibagi menjadi beberapa chunk.

Jika Anda belum memakai framework khusus, loop acak sederhana pun sudah sangat membantu, selama mencakup domain edge case secara eksplisit.

for (uint32_t x : corpus) {
    int32_t a = zigzag_decode32_scalar(x);
    int32_t b = zigzag_decode32_simd_single_lane_equivalent(x);
    assert(a == b);
}

Tambahkan fuzzing pada parser biner utuh

Setelah fungsi decode kecil aman, naikkan cakupan ke parser utuh. Fuzzing berguna untuk menemukan kombinasi:

  • varint valid tetapi tidak umum,
  • jumlah field yang menghasilkan tail handling spesifik,
  • layout buffer yang memicu load tidak sejajar,
  • kombinasi nilai yang membuat korupsi baru tampak di tahap turunannya.

Prinsipnya sederhana: satu input biner mentah diparse oleh path scalar dan SIMD, lalu hasil struktur akhirnya dibandingkan byte-per-byte atau field-per-field.

Pastikan benchmark terpisah dari validasi

Jangan menjalankan benchmark sebelum kesetaraan hasil terjamin. Benchmark hanya bermakna jika implementasi benar. Setelah fix selesai, ukur lagi throughput dan latency pada dataset representatif, termasuk dataset yang tidak pas kelipatan lane dan dataset dengan distribusi angka campuran.

Contoh pola bug dan perbaikannya

Misalkan implementasi SIMD mencoba membentuk mask tanda dari bit LSB per lane, tetapi secara tidak sengaja melakukan operasi pada lane 16-bit padahal data sebenarnya 32-bit. Secara konseptual, bug-nya seperti ini:

// PSEUDO-CODE BUGGY: ilustrasi konsep, bukan intrinsics final
shifted = logical_shift_right_32(encoded, 1)
mask16  = sub_16(zero, and_16(encoded, one))
out     = xor_32(shifted, mask16) // SALAH: mask dibentuk per 16-bit, dipakai per 32-bit

Masalahnya bukan pada XOR, melainkan pada lane width mask. Nilai mask yang diinginkan untuk lane 32-bit adalah:

  • 0x00000000 jika bit LSB = 0
  • 0xffffffff jika bit LSB = 1

Perbaikan konseptualnya adalah memastikan semua operasi tanda berlangsung dalam lane yang sama dengan hasil akhir:

// Scalar reference yang aman dan jelas
static inline int32_t zigzag_decode32_scalar(uint32_t x) {
    uint32_t sign = 0u - (x & 1u);
    return (int32_t)((x >> 1) ^ sign);
}

// PSEUDO-CODE SIMD yang benar secara konsep
shifted = logical_shift_right_32(encoded, 1)
lsb     = and_32(encoded, one32)
mask32  = sub_32(zero32, lsb)
out     = xor_32(shifted, mask32)

Pola ini bekerja karena 0 - 0 = 0x00000000 dan 0 - 1 = 0xffffffff dalam aritmetika modulo unsigned 32-bit. Setelah itu, XOR dengan hasil shift memberi kembali bilangan signed hasil zigzag decode.

Jika memakai 64-bit, konsistensi lane harus ikut dinaikkan ke 64-bit. Jangan mencampur helper 32-bit dan 64-bit hanya karena bentuk assembly-nya tampak mirip.

Perhatikan tail handling

Banyak bug tetap bertahan walau rumus inti sudah benar, karena sisa elemen diproses dengan helper berbeda. Solusi yang aman:

  • buat satu scalar reference yang dipakai untuk semua fallback,
  • pakai pembagian kerja yang jelas: SIMD untuk blok penuh, scalar reference untuk sisa,
  • uji semua ukuran input kecil, misalnya 0 sampai beberapa kali lebar vektor.

Kurangi ruang untuk asumsi compiler

Di C/C++, tipe eksplisit lebih aman daripada bergantung pada promosi implisit. Praktik yang membantu:

  • gunakan uint32_t atau uint64_t untuk encoded,
  • gunakan cast akhir ke tipe signed setelah transformasi bitwise selesai,
  • hindari ekspresi padat yang sulit dipastikan perilakunya,
  • simpan scalar reference sesederhana mungkin.

Benchmark sebelum dan sesudah: apa yang perlu diperiksa

Setelah perbaikan, lakukan benchmark ulang, tetapi jangan hanya melihat throughput tertinggi. Periksa juga:

  • apakah dataset acak dan dataset edge case sama-sama benar,
  • apakah batch kecil memburuk drastis karena overhead fallback,
  • apakah performa berbeda pada buffer tidak sejajar,
  • apakah hasil konsisten saat fitur SIMD dimatikan sebagai pembanding.

Anda tidak perlu mengklaim angka spektakuler. Yang lebih penting adalah menunjukkan bahwa:

  1. hasil scalar dan SIMD kini identik,
  2. fix tidak memperkenalkan regresi signifikan,
  3. tail handling dan input aneh tetap aman.

Dalam praktik backend, kecepatan yang sedikit lebih rendah masih layak jika menutup peluang korupsi data diam-diam.

Guardrail code review untuk parser SIMD

Setelah bug ditemukan, nilai terbesar biasanya datang dari guardrail agar pola serupa tidak terulang.

1. Wajib ada scalar reference yang mudah dibaca

Fast path SIMD seharusnya dibaca sebagai optimasi dari reference, bukan sebagai sumber kebenaran tunggal.

2. Satu fungsi, satu kontrak tipe

Jika fungsi menangani 32-bit, semua helper internal harus jelas 32-bit. Hindari utility generik yang diam-diam bekerja per 16-bit lane karena “kebetulan cocok”.

3. Uji ukuran input di sekitar batas lane

Minimal uji ukuran:

  • 0, 1, 2, 3 elemen,
  • satu kurang dari lebar vektor,
  • tepat lebar vektor,
  • satu lebih dari lebar vektor,
  • beberapa kali lebar vektor plus tail.

4. Wajib diff scalar vs SIMD di CI

Idealnya ada test yang membangkitkan input acak dan corpus edge case, lalu memaksa perbandingan hasil dua path tersebut pada setiap build yang menyentuh parser.

5. Pisahkan validasi dari benchmark

Benchmark tanpa oracle kebenaran mudah menutupi bug. Jalur aman adalah: validasi dulu, benchmark kemudian.

Checklist pencegahan untuk parser backend berperforma tinggi

  • Gunakan implementasi scalar referensi yang eksplisit dan mudah diaudit.
  • Pastikan lane width konsisten di seluruh operasi SIMD.
  • Verifikasi pembentukan sign mask dengan dump heksadesimal.
  • Uji semua edge case zigzag, terutama nilai ganjil, batas lane, dan panjang input non-kelipatan vektor.
  • Pastikan fallback scalar identik secara semantik dengan fast path.
  • Tambahkan property-based test untuk decode(encode(x)) == x.
  • Tambahkan fuzzing pada parser utuh, bukan hanya fungsi decode.
  • Jangan mengandalkan promosi tipe implisit atau ekspresi bitwise yang ambigu.
  • Ukur performa sesudah fix pada dataset realistis, termasuk tail dan unaligned input.
  • Simpan fixture input yang pernah gagal sebagai regresi permanen.

Penutup

Debug backend SIMD pada kasus salah decode zigzag hampir selalu menuntut dua hal: disiplin membuat oracle scalar yang benar, dan ketelitian memeriksa semantik lane pada path SIMD. Gejala seperti integer negatif/positif sesekali salah, korupsi data turunan, serta hasil berbeda antara scalar dan SIMD biasanya bukan bug acak; ada akar masalah yang bisa dilokalisasi lewat reproduksi minimal, diff output, logging heksadesimal, property-based test, dan fuzzing.

Perbaikan yang baik tidak berhenti pada satu patch intrinsics. Pastikan review menutup celah sign extension, lane width, overflow, alignment, asumsi compiler, dan fallback yang tidak identik. Pada parser backend berperforma tinggi, kebenaran hasil tetap prioritas utama; optimasi SIMD baru bernilai jika scalar dan SIMD menghasilkan bit yang sama untuk setiap input yang sah.