SIMD parsování CSV: klasifikace nibbly

Vektorizované parsování CSV pomocí SIMD a bitových masek

Parsování CSV podle RFC4180 vyžaduje identifikaci strukturních znaků: čárky pro sloupce, \r\n pro řádky a uvozovky pro escapování. SIMD umožňuje klasifikovat 16 bajtů za cyklus bez větvení pomocí vyhledávacích tabulek pro nibblů.

Algoritmus pracuje s ARM NEON (analogie v x86 AVX2). Každý bajt je rozdělen na horní a dolní nibbl. Dvě tabulky po 16 prvků vracejí bity tříd: COMMA=1, QUOTE=2, NEWLINE=3.

Pro čárku (0x2C): horní nibbl 0x2 → COMMA|QUOTE, dolní 0xC → COMMA. AND ponechá COMMA.

Kontrola falešných poplachů: počet bajtů ve třídě se musí rovnat součinu unikátních nibblů.

Vektorizovaná implementace klasifikátoru

Skalární cyklus je nahrazen zpracováním chunků po 16 bajtech:

use std::arch::aarch64::*;


const LO_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x2] = QUOTE;
    t[0xA] = NEWLINE;
    t[0xC] = COMMA;
    t[0xD] = NEWLINE;
    t
};

const HI_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x0] = NEWLINE;
    t[0x2] = COMMA | QUOTE;
    t
};

unsafe {
    let lo_lut = vld1q_u8(LO_LOOKUP.as_ptr());
    let hi_lut = vld1q_u8(HI_LOOKUP.as_ptr());
    let mask = vdupq_n_u8(0x0F);

    for chunk in bytes.chunks_exact(16) {
        let input = vld1q_u8(chunk.as_ptr());
        let lo_nibbles = vandq_u8(input, mask);
        let hi_nibbles = vandq_u8(vshrq_n_u8::<4>(input), mask);
        
        let lo_result = vqtbl1q_u8(lo_lut, lo_nibbles);
        let hi_result = vqtbl1q_u8(hi_lut, hi_nibbles);
        let classified = vandq_u8(lo_result, hi_result);
        
        let mut out = [0u8; 16];
        vst1q_u8(out.as_mut_ptr(), classified);
        classified_bytes.extend_from_slice(&out);
    }
}

Intrinsics vqtbl1q_u8 provádějí vyhledávání, vandq_u8 — AND. Zbytek je zpracován s paddingem.

Komprese do bitových masek

Klasifikované bajty jsou převedeny na tři Vec<u64>, kde každý bit masky odpovídá pozici znaku třídy. u64 popisuje 64 bajtů proudu.

Příklad pro alice,30,Irvine\n:

• Maska COMMA: pozice 5, 8
• Maska QUOTE: prázdná
• Maska NEWLINE: pozice 15

Filtrace uvozovaných polí

Klasifikátor označí všechny znaky, včetně vnitřních. Pro filtraci se používá prefixový XOR masky QUOTE.

Parita uvozovek určuje stav:

• Lichý počet po pozici → uvnitř pole
• Sudý → vně

Escapované "" se samovyvažují. V příkladu "where she said, ""hi"\nto me:

• Pozice 0 ("): 1 uvozovka → uvnitř
• Pozice 17 ("): 2 → vně
• Pozice 29 ("): 6 → vně

Vnitřní čárky a \n jsou ignorovány.

Prefixový XOR pro stavy

Pro 16-bajtové chunky se vypočítá kumulativní XOR masky QUOTE. Bit i se rovná paritě uvozovek od pozice i do konce.

// Pseudokód
let prefix_xor = 0;
for (i, &bit) in quote_mask.iter().enumerate() {
    prefix_xor ^= bit;
    if prefix_xor == 0 {
        // vně pole
    }
}

SIMD verze používá horizontální XOR po chunkách s maskou pro popcount nebo bitscan.

Sběr pozic oddělovačů

Filtrované masky jsou skenovány pro extrakci pozic skutečných oddělovačů:

• Čárky vně → hranice sloupců
• \n vně → hranice řádků

Pozice jsou uloženy v polích offsets. To umožňuje rozdělit proud bez kopírování dat.

Výhody přístupu:

• Žádné větvení v jádru
• 16x paralelismus na chunk
• Kompaktní bitová reprezentace
• Snadno rozšiřitelné na 32/64 bajtů (AVX512)

Co je důležité

• Dvě 16-bajtové tabulky nibblů nahrazují 256-bajtovou LUT pro SIMD.
• AND dvou vyhledání eliminuje falešné třídy bez podmínek.
• Prefixový XOR určuje hranice uvozovaných polí v O(n).
• Bitové masky komprimují data na 3/8 původní velikosti.
• Algoritmus je přenositelný: NEON → SSE4/AVX2 s pshufb/_mm_shuffle_epi8.

— Editorial Team