Parsing SIMD CSV : classification de nibbles

Analyse Vectorisée de CSV avec SIMD et Masques Binaires

L'analyse de CSV selon la norme RFC4180 nécessite l'identification des caractères structurels : les virgules pour les colonnes, \r\n pour les lignes, et les guillemets pour l'échappement. SIMD permet de classifier 16 octets par cycle sans branchement, en utilisant des tables de recherche pour les nibbles.

L'algorithme fonctionne avec ARM NEON (similaire à x86 AVX2). Chaque octet est divisé en nibble haut et bas. Deux tables de 16 éléments renvoient des bits de classe : VIRGULE=1, GUILLEMET=2, NOUVELLE_LIGNE=3.

Pour une virgule (0x2C) : nibble haut 0x2 → VIRGULE|GUILLEMET, nibble bas 0xC → VIRGULE. L'opération AND laisse VIRGULE.

Vérification des faux positifs : le nombre d'octets dans une classe doit être égal au produit des nibbles uniques.

Implémentation du Classificateur Vectorisé

La boucle scalaire est remplacée par un traitement par blocs de 16 octets :

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

const LO_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x2] = GUILLEMET;
    t[0xA] = NOUVELLE_LIGNE;
    t[0xC] = VIRGULE;
    t[0xD] = NOUVELLE_LIGNE;
    t
};

const HI_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x0] = NOUVELLE_LIGNE;
    t[0x2] = VIRGULE | GUILLEMET;
    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);
    }
}

Les intrinsèques vqtbl1q_u8 effectuent la recherche, vandq_u8 — l'opération AND. Le reste est géré avec du remplissage.

Compression en Masques Binaires

Les octets classifiés sont convertis en trois Vec<u64>, où chaque bit du masque correspond à une position de classe de caractère. u64 décrit 64 octets du flux.

Exemple pour alice,30,Irvine\n :

• Masque VIRGULE : positions 5, 8
• Masque GUILLEMET : vide
• Masque NOUVELLE_LIGNE : position 15

Filtrage des Champs Entre Guillemets

Le classificateur marque tous les caractères, y compris ceux internes. Pour le filtrage, un XOR préfixe du masque GUILLEMET est utilisé.

La parité des guillemets détermine l'état :

• Nombre impair après la position → à l'intérieur du champ
• Nombre pair → à l'extérieur du champ

L'échappement "" s'auto-équilibre. Dans l'exemple "où elle a dit, ""bonjour"\nà moi" :

• Position 0 (") : 1 guillemet → à l'intérieur
• Position 17 (") : 2 → à l'extérieur
• Position 29 (") : 6 → à l'extérieur

Les virgules et \n internes sont ignorés.

XOR Préfixe pour les États

Pour les blocs de 16 octets, un XOR cumulatif du masque GUILLEMET est calculé. Le bit i est égal à la parité des guillemets de la position i à la fin.

// Pseudocode
let prefix_xor = 0;
for (i, &bit) in quote_mask.iter().enumerate() {
    prefix_xor ^= bit;
    if prefix_xor == 0 {
        // à l'extérieur du champ
    }
}

La version SIMD utilise un XOR horizontal à travers les blocs avec un masque pour le popcount ou le bitscan.

Collecte des Positions des Délimiteurs

Les masques filtrés sont scannés pour extraire les positions des vrais délimiteurs :

• Virgules à l'extérieur → limites de colonnes
• \n à l'extérieur → limites de lignes

Les positions sont enregistrées dans des tableaux d'offsets. Cela permet de diviser le flux sans copier les données.

Avantages de l'approche :

• Aucun branchement dans le cœur
• Parallélisme 16x par bloc
• Représentations binaires compactes
• Facilement extensible à 32/64 octets (AVX512)

Points Clés

• Deux tables de nibbles de 16 octets remplacent une LUT de 256 octets pour SIMD.
• L'opération AND des deux recherches élimine les fausses classes sans conditions.
• Le XOR préfixe détermine les limites des champs entre guillemets en O(n).
• Les masques binaires compressent les données à 3/8 de la taille originale.
• L'algorithme est portable : NEON → SSE4/AVX2 avec pshufb/_mm_shuffle_epi8.

— Editorial Team