SIMD CSV-Parsing: Nibble-Klassifikation

Vektorisierte CSV-Verarbeitung mit SIMD und Bitmasken

Das Parsen von CSV-Dateien gemäß RFC4180 erfordert die Identifizierung struktureller Zeichen: Kommas für Spalten, \r\n für Zeilen und Anführungszeichen für Escaping. SIMD ermöglicht die Klassifizierung von 16 Bytes pro Zyklus ohne Verzweigungen, wobei Lookup-Tabellen für Nibbles verwendet werden.

Der Algorithmus funktioniert mit ARM NEON (ähnlich zu x86 AVX2). Jedes Byte wird in hohes und niedriges Nibble aufgeteilt. Zwei 16-Elemente-Tabellen liefern Klassenbits: KOMMA=1, ANFÜHRUNGSZEICHEN=2, ZEILENUMBRUCH=3.

Für ein Komma (0x2C): hohes Nibble 0x2 → KOMMA|ANFÜHRUNGSZEICHEN, niedriges Nibble 0xC → KOMMA. UND lässt KOMMA übrig.

Falsch-Positiv-Prüfung: Die Anzahl der Bytes in einer Klasse muss dem Produkt der eindeutigen Nibbles entsprechen.

Implementierung des vektorisierten Klassifizierers

Die skalare Schleife wird durch die Verarbeitung von 16-Byte-Blöcken ersetzt:

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 führen die Lookup-Operation durch, vandq_u8 — UND. Der Rest wird mit Padding behandelt.

Komprimierung in Bitmasken

Klassifizierte Bytes werden in drei Vec<u64> umgewandelt, wobei jedes Bit in der Maske einer Zeichenklassenposition entspricht. u64 beschreibt 64 Bytes des Datenstroms.

Beispiel für alice,30,Irvine\n:

• KOMMA-Maske: Positionen 5, 8
• ANFÜHRUNGSZEICHEN-Maske: leer
• ZEILENUMBRUCH-Maske: Position 15

Filtern von Anführungszeichen-Feldern

Der Klassifizierer markiert alle Zeichen, einschließlich interner. Zum Filtern wird ein Präfix-XOR der ANFÜHRUNGSZEICHEN-Maske verwendet.

Die Parität der Anführungszeichen bestimmt den Zustand:

• Ungerade Anzahl nach Position → innerhalb des Feldes
• Gerade Anzahl → außerhalb des Feldes

Escaped "" gleicht sich selbst aus. Im Beispiel "where she said, ""hi"\nto me":

• Position 0 ("): 1 Anführungszeichen → innerhalb
• Position 17 ("): 2 → außerhalb
• Position 29 ("): 6 → außerhalb

Interne Kommas und \n werden ignoriert.

Präfix-XOR für Zustände

Für 16-Byte-Blöcke wird ein kumulatives XOR der ANFÜHRUNGSZEICHEN-Maske berechnet. Bit i entspricht der Parität der Anführungszeichen von Position i bis zum Ende.

// Pseudocode
let prefix_xor = 0;
for (i, &bit) in quote_mask.iter().enumerate() {
    prefix_xor ^= bit;
    if prefix_xor == 0 {
        // außerhalb des Feldes
    }
}

Die SIMD-Version verwendet horizontales XOR über Blöcke mit einer Maske für Popcount oder Bitscan.

Sammeln von Trennzeichenpositionen

Gefilterte Masken werden gescannt, um Positionen echter Trennzeichen zu extrahieren:

• Kommas außerhalb → Spaltengrenzen
• \n außerhalb → Zeilengrenzen

Positionen werden in Offset-Arrays gespeichert. Dies ermöglicht das Aufteilen des Datenstroms ohne Datenkopie.

Vorteile des Ansatzes:

• Keine Verzweigungen im Kern
• 16-fache Parallelität pro Block
• Kompakte Bitdarstellungen
• Leicht erweiterbar auf 32/64 Bytes (AVX512)

Wichtige Punkte

• Zwei 16-Byte-Nibble-Tabellen ersetzen eine 256-Byte-LUT für SIMD.
• UND von zwei Lookups eliminiert falsche Klassen ohne Bedingungen.
• Präfix-XOR bestimmt Grenzen von Anführungszeichen-Feldern in O(n).
• Bitmasken komprimieren Daten auf 3/8 der ursprünglichen Größe.
• Der Algorithmus ist portabel: NEON → SSE4/AVX2 mit pshufb/_mm_shuffle_epi8.

— Editorial Team