SIMD CSV 파싱: nibble 분류

SIMD와 비트마스크를 활용한 벡터화 CSV 파싱

RFC4180에 따른 CSV 파싱은 구조적 문자를 식별해야 합니다: 열 구분을 위한 쉼표, 행 구분을 위한 \r\n, 이스케이프를 위한 따옴표. SIMD를 사용하면 분기 없이 사이클당 16바이트를 분류할 수 있으며, 니블을 위한 룩업 테이블을 활용합니다.

이 알고리즘은 ARM NEON(x86 AVX2와 유사)에서 작동합니다. 각 바이트는 상위 니블과 하위 니블로 분리됩니다. 두 개의 16요소 테이블이 클래스 비트를 반환합니다: COMMA=1, QUOTE=2, NEWLINE=3.

쉼표(0x2C)의 경우: 상위 니블 0x2 → COMMA|QUOTE, 하위 니블 0xC → COMMA. AND 연산으로 COMMA만 남습니다.

거짓 긍정 확인: 클래스 내 바이트 수는 고유 니블의 곱과 같아야 합니다.

벡터화 분류기 구현

스칼라 루프는 16바이트 청크 처리로 대체됩니다:

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);
    }
}

내장 함수 vqtbl1q_u8은 룩업을 수행하고, vandq_u8은 AND 연산을 합니다. 나머지는 패딩으로 처리됩니다.

비트마스크로 압축

분류된 바이트는 세 개의 Vec<u64>로 변환되며, 마스크의 각 비트는 문자 클래스 위치에 대응합니다. u64는 스트림의 64바이트를 설명합니다.

alice,30,Irvine\n의 예:

• COMMA 마스크: 위치 5, 8
• QUOTE 마스크: 비어 있음
• NEWLINE 마스크: 위치 15

따옴표 필드 필터링

분류기는 내부 문자를 포함한 모든 문자를 표시합니다. 필터링을 위해 QUOTE 마스크의 접두사 XOR이 사용됩니다.

따옴표 패리티가 상태를 결정합니다:

• 위치 이후 홀수 개 → 필드 내부
• 짝수 개 → 필드 외부

이스케이프된 ""는 자체 균형을 이룹니다. 예시 "where she said, ""hi"\nto me":

• 위치 0("): 따옴표 1개 → 내부
• 위치 17("): 2개 → 외부
• 위치 29("): 6개 → 외부

내부 쉼표와 \n은 무시됩니다.

상태를 위한 접두사 XOR

16바이트 청크의 경우, QUOTE 마스크의 누적 XOR이 계산됩니다. 비트 i는 위치 i부터 끝까지의 따옴표 패리티와 같습니다.

// 의사 코드
let prefix_xor = 0;
for (i, &bit) in quote_mask.iter().enumerate() {
    prefix_xor ^= bit;
    if prefix_xor == 0 {
        // 필드 외부
    }
}

SIMD 버전은 팝카운트나 비트스캔을 위한 마스크와 함께 청크 간 수평 XOR을 사용합니다.

구분자 위치 수집

필터링된 마스크는 진정한 구분자의 위치를 추출하기 위해 스캔됩니다:

• 외부 쉼표 → 열 경계
• 외부 \n → 행 경계

위치는 오프셋 배열에 저장됩니다. 이렇게 하면 데이터를 복사하지 않고 스트림을 분할할 수 있습니다.

이 접근법의 장점:

• 핵심 부분에 분기 없음
• 청크당 16배 병렬 처리
• 간결한 비트 표현
• 32/64바이트(AVX512)로 쉽게 확장 가능

핵심 포인트

• 두 개의 16바이트 니블 테이블이 SIMD용 256바이트 LUT를 대체합니다.
• 두 룩업의 AND 연산으로 조건 없이 거짓 클래스를 제거합니다.
• 접두사 XOR이 O(n)으로 따옴표 필드 경계를 결정합니다.
• 비트마스크가 데이터를 원본 크기의 3/8로 압축합니다.
• 이 알고리즘은 이식 가능합니다: NEON → SSE4/AVX2 with pshufb/_mm_shuffle_epi8.

— Editorial Team