Parseo SIMD de CSV: clasificación de nibbles

Análisis Vectorizado de CSV con SIMD y Máscaras de Bits

Analizar CSV según RFC4180 requiere identificar caracteres estructurales: comas para columnas, \r\n para filas y comillas para escape. SIMD permite clasificar 16 bytes por ciclo sin bifurcaciones, utilizando tablas de búsqueda para nibbles.

El algoritmo funciona con ARM NEON (similar a x86 AVX2). Cada byte se divide en nibbles alto y bajo. Dos tablas de 16 elementos devuelven bits de clase: COMA=1, COMILLA=2, NUEVA_LÍNEA=3.

Para una coma (0x2C): nibble alto 0x2 → COMA|COMILLA, nibble bajo 0xC → COMA. AND deja COMA.

Verificación de falsos positivos: el número de bytes en una clase debe igualar el producto de nibbles únicos.

Implementación del Clasificador Vectorizado

El bucle escalar se reemplaza con procesamiento por fragmentos de 16 bytes:

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

const LO_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x2] = COMILLA;
    t[0xA] = NUEVA_LÍNEA;
    t[0xC] = COMA;
    t[0xD] = NUEVA_LÍNEA;
    t
};

const HI_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x0] = NUEVA_LÍNEA;
    t[0x2] = COMA | COMILLA;
    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);
    }
}

Las intrínsecas vqtbl1q_u8 realizan la búsqueda, vandq_u8 — AND. El resto se maneja con relleno.

Compresión en Máscaras de Bits

Los bytes clasificados se convierten en tres Vec<u64>, donde cada bit en la máscara corresponde a una posición de clase de carácter. u64 describe 64 bytes del flujo.

Ejemplo para alice,30,Irvine\n:

• Máscara COMA: posiciones 5, 8
• Máscara COMILLA: vacía
• Máscara NUEVA_LÍNEA: posición 15

Filtrado de Campos entre Comillas

El clasificador marca todos los caracteres, incluidos los internos. Para filtrar, se usa un XOR de prefijo de la máscara COMILLA.

La paridad de comillas determina el estado:

• Conteo impar después de la posición → dentro del campo
• Conteo par → fuera del campo

El escape "" se auto-equilibra. En el ejemplo "where she said, ""hi"\nto me":

• Posición 0 ("): 1 comilla → dentro
• Posición 17 ("): 2 → fuera
• Posición 29 ("): 6 → fuera

Se ignoran comas y \n internos.

XOR de Prefijo para Estados

Para fragmentos de 16 bytes, se calcula un XOR acumulativo de la máscara COMILLA. El bit i iguala la paridad de comillas desde la posición i hasta el final.

// Pseudocódigo
let prefix_xor = 0;
for (i, &bit) in quote_mask.iter().enumerate() {
    prefix_xor ^= bit;
    if prefix_xor == 0 {
        // fuera del campo
    }
}

La versión SIMD usa XOR horizontal entre fragmentos con una máscara para popcount o bitscan.

Recolección de Posiciones de Delimitadores

Las máscaras filtradas se escanean para extraer posiciones de delimitadores verdaderos:

• Comas fuera → límites de columna
• \n fuera → límites de fila

Las posiciones se guardan en arreglos de desplazamiento. Esto permite dividir el flujo sin copiar datos.

Ventajas del enfoque:

• Sin bifurcaciones en el núcleo
• Paralelismo 16x por fragmento
• Representaciones de bits compactas
• Fácilmente extensible a 32/64 bytes (AVX512)

Puntos Clave

• Dos tablas de nibbles de 16 bytes reemplazan una LUT de 256 bytes para SIMD.
• AND de dos búsquedas elimina clases falsas sin condiciones.
• XOR de prefijo determina límites de campos entre comillas en O(n).
• Las máscaras de bits comprimen datos a 3/8 del tamaño original.
• El algoritmo es portable: NEON → SSE4/AVX2 con pshufb/_mm_shuffle_epi8.

— Editorial Team