SIMD parsowanie CSV: klasyfikacja nibblami

Wektorowy parsowanie CSV z wykorzystaniem SIMD i masek bitowych

Parsowanie CSV zgodnie z RFC4180 wymaga identyfikacji znaków strukturalnych: przecinki dla kolumn, \r\n dla wierszy, cudzysłowy dla ekranowania. SIMD umożliwia klasyfikację 16 bajtów na cykl bez rozgałęzień, wykorzystując tablice wyszukiwania dla półbajtów.

Algorytm działa z ARM NEON (odpowiedniki w x86 AVX2). Każdy bajt dzielony jest na starszy i młodszy półbajt. Dwie tablice po 16 elementów zwracają bity klas: PRZECINEK=1, CUDZYSŁÓW=2, NOWA_LINIA=3.

Dla przecinka (0x2C): starszy półbajt 0x2 → PRZECINEK|CUDZYSŁÓW, młodszy 0xC → PRZECINEK. AND pozostawia PRZECINEK.

Weryfikacja fałszywych trafień: liczba bajtów w klasie musi równać się iloczynowi unikalnych półbajtów.

Wektorowa implementacja klasyfikatora

Skalarna pętla zastępowana jest przetwarzaniem fragmentów po 16 bajtów:

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

const LO_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x2] = CUDZYSŁÓW;
    t[0xA] = NOWA_LINIA;
    t[0xC] = PRZECINEK;
    t[0xD] = NOWA_LINIA;
    t
};

const HI_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x0] = NOWA_LINIA;
    t[0x2] = PRZECINEK | CUDZYSŁÓW;
    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 wykonują wyszukiwanie, vandq_u8 — AND. Reszta przetwarzana jest z dopełnieniem.

Kompresja do masek bitowych

Sklasyfikowane bajty przekształcane są w trzy Vec<u64>, gdzie każdy bit maski odpowiada pozycji znaku klasy. u64 opisuje 64 bajty strumienia.

Przykład dla alice,30,Irvine\n:

• Maska PRZECINEK: pozycje 5, 8
• Maska CUDZYSŁÓW: pusta
• Maska NOWA_LINIA: pozycja 15

Filtrowanie pól w cudzysłowach

Klasyfikator oznacza wszystkie znaki, w tym wewnętrzne. Do filtrowania używany jest prefiksowy XOR maski CUDZYSŁÓW.

Parzystość cudzysłowów określa stan:

• Nieparzysta liczba po pozycji → wewnątrz pola
• Parzysta → na zewnątrz

Ekranowane "" samobalansują się. W przykładzie "where she said, ""hi"\nto me":

• Pozycja 0 ("): 1 cudzysłów → wewnątrz
• Pozycja 17 ("): 2 → na zewnątrz
• Pozycja 29 ("): 6 → na zewnątrz

Wewnętrzne przecinki i \n są ignorowane.

Prefiksowy XOR dla stanów

Dla fragmentów 16-bajtowych obliczany jest kumulacyjny XOR maski CUDZYSŁÓW. Bit i równa się parzystości cudzysłowów od pozycji i do końca.

// Pseudokod
let prefix_xor = 0;
for (i, &bit) in quote_mask.iter().enumerate() {
    prefix_xor ^= bit;
    if prefix_xor == 0 {
        // na zewnątrz pola
    }
}

Wersja SIMD wykorzystuje poziomy XOR po fragmentach z maską dla popcount lub bitscan.

Zbieranie pozycji separatorów

Przefiltrowane maski są skanowane w celu wyodrębnienia pozycji prawdziwych separatorów:

• Przecinki na zewnątrz → granice kolumn
• \n na zewnątrz → granice wierszy

Pozycje zapisywane są w tablicach offsets. Pozwala to podzielić strumień bez kopiowania danych.

Zalety podejścia:

• Brak rozgałęzień w jądrze
• 16x równoległość na fragment
• Kompaktowe reprezentacje bitowe
• Łatwo rozszerzalne na 32/64 bajty (AVX512)

Co jest ważne

• Dwie 16-bajtowe tablice półbajtów zastępują 256-bajtową LUT dla SIMD.
• AND dwóch wyszukiwań eliminuje fałszywe klasy bez warunków.
• Prefiksowy XOR określa granice pól w cudzysłowach w O(n).
• Maski bitowe kompresują dane do 3/8 oryginału.
• Algorytm przenośny: NEON → SSE4/AVX2 z pshufb/_mm_shuffle_epi8.

— Editorial Team