SIMD와 비트 연산을 사용해 CSV의 구조 문자를 대량으로 분류하고 필터링하는 방법을 설명하는 글.
https://github.com/friendlymatthew
📅 2026-03-20📁 프로그래밍🏷️ rust, simd, csv, 파일 형식⏱️ 12분 읽기👀 — 독자
이 미묘한 니블 추출을 보세요. 그 절제된 lookup table을 보세요. 세상에, vqtbl1q_u8와 vmull_p64까지 있네요.
편집자 주: 일부 독자들이 Paul Allen이 누구인지 헷갈려 하는 것 같습니다. 이것은 영화 American Psycho에 대한 언급입니다. 좋은 설명은 여기에 있습니다. Microsoft 공동 창립자이자 억만장자인 Paul Allen과 그의 SIMD CSV 파서를 가리키는 것이 아닙니다.
1년 전 저는 한 번에 64문자를 파싱할 수 있는 CSV 파서를 작성했습니다. 이것은 순전히 연구 목적이며, validation 같은 프로덕션 파서에 중요한 단계들은 대충 넘어갑니다. 하지만 핵심 알고리즘은 SIMD와 비트 연산을 사용해 구조 문자를 대량으로 분류하고 필터링하며, 오늘 제가 이야기할 내용도 바로 이런 기법들입니다.
SIMD가 처음이라면 여기서 잠시 멈추고 McYoung의 SIMD 입문을 읽어보기를 권합니다. 그래도 SIMD에 대한 아주 짧은 소개를 하자면:
if 문, 루프, 함수 호출을 피하고 입력과 관계없이 같은 연산을 수행한다는 뜻입니다.어떤 주제든 그 문제 영역에서 필독으로 여겨지는 눈에 띄는 논문이 늘 몇 편 있습니다. 예를 들어 Joseph Beryl Koshakow의 표현을 빌리자면, “Amazon DynamoDB와 Google Spanner 논문은 모든 데이터베이스 개발자가 읽어야 할 정전급 데이터베이스 논문들에 속한다”라고 했습니다. [출처]
joekoshakow.com 그는 이어서 “Matthew는 내가 아는 엔지니어 중 가장 똑똑한 사람들 중 하나이고 나보다 훨씬 키가 크다”라고 말했습니다. [출처 필요]
SIMD에 대해서라면 저는 simdjson 논문이 읽어야 할 논문이라고 주장하겠습니다. JSON 파싱은 익숙한 문제지만, simdjson은 한 번에 64바이트를 스캔하고 처리하는 방식으로 이를 해결합니다. 영상이 더 좋다면, 논문의 공동 저자이자 SIMD계의 LeBron James인 Daniel Lemire
Daniel Lemire vs 나머지 우리들, 그가 이에 대해 강연한 영상도 있습니다.
이 글의 나머지 부분에서는 제 CSV 파서에 사용한, 논문에 나온 몇 가지 기법을 설명하겠습니다. 제가 사용하는 SIMD 명령어는 ARM NEON이지만, x86에도 이들 모두에 대한 직접적인 대응물이 있습니다.
다음은 전형적인 CSV입니다:
| name | age | location |
|---|---|---|
| alice | 30 | Irvine |
| bob | 25 | 123 Union Square, New York New York |
| lonely charlie | 28 | where she said, "hi" to me |
그리고 이것을 CSV RFC4180 명세를 따르는 원시 바이트 스트림으로 보면 다음과 같습니다:
name,age,location\r\n
alice,30,Irvine\n
bob,25,"123 Union Square, New York New York"\n
lonely charlie,28,"where she said, ""hi""\nto me"
모든 파일 형식에는 구조 문자가 있습니다. 이는 평평한 바이트 시퀀스에 형태를 부여하는 문자들입니다. CSV에서는 쉼표 (,)가 열을 구분하고, 줄바꿈 (\n 또는 \r\n)이 행을 구분하며, 따옴표 (")는 구조 문자를 자체적으로 포함하는 필드를 감쌉니다. 예를 들어 "123 Union Square, New York New York" 같은 경우입니다. 인용된 필드 안에 리터럴 따옴표를 넣으려면 두 번 써야 합니다. "hi"는 ""hi""가 됩니다.
CSV 파싱은 3단계로 요약됩니다. 먼저 모든 바이트를 분류합니다:
name,age,location\r\n
alice,30,Irvine\n
bob,25,"123 Union Square, New York New York"\n
lonely charlie,28,"where she said, ""hi""\nto me"
하지만 이들 모두가 진짜 구분자는 아닙니다. "where she said, ""hi""\nto me" 안의 쉼표는 그냥 텍스트일 뿐이고, \n은 필드 값의 일부이며, hi를 둘러싼 ""는 경계가 아니라 이스케이프 시퀀스입니다. 그래서 이것들을 걸러냅니다:
name,age,location\r\n alice,30,Irvine\n bob,25,"123 Union Square, New York New York"\n lonely charlie,28,"where she said, ""hi""\nto me" 그러고 나면 실제로 열과 행을 구분하는 문자만 남습니다:
name,age,location\r\n alice,30,Irvine\n bob,25,123 Union Square, New York New York\n lonely charlie,28,where she said, ""hi""\nto me 마지막으로 남아 있는 각 구조 문자의 위치를 기록합니다. 이 오프셋만 있으면 원래의 바이트 스트림을 행과 필드로 잘라낼 수 있습니다.
핵심은 이 단계 각각을 많은 바이트에 대해 한꺼번에 수행할 수 있다는 점입니다.
스칼라 방식은 각 바이트를 모든 구조 문자와 하나씩 비교하면서 분류할 것입니다.
Geoff Langdale
branchfree.org, simdjson의 공동 저자이자 Hyperscan의 창시자는 vectorized classification이라는 기법을 고안했는데, 이를 사용하면 16/32/64바이트를 한 번에 분류할 수 있습니다.
아이디어는 완전 해시처럼 동작하는 lookup table 쌍을 만드는 것입니다. 모든 구조 문자는 자신의 클래스 (COMMA = 1, QUOTE = 2, NEWLINE = 3)에 매핑되고, 나머지는 모두 0에 매핑됩니다. 256엔트리 lookup table을 만들 수도 있겠지만, pshufb나 vqtbl1q_u8 같은 일반적인 SIMD lookup 명령은 16엔트리 테이블(4비트 인덱스)만 지원합니다.
바이트는 8비트이므로, 각 바이트를 반으로 나눕니다. 각 절반을 니블이라고 하며, 16진수에서는 각 자릿수가 정확히 하나의 니블입니다.
| 문자 | Hex | 상위 니블 | 하위 니블 |
|---|---|---|---|
| , | 0x2C | 0x2 | 0xC |
| " | 0x22 | 0x2 | 0x2 |
| \n | 0x0A | 0x0 | 0xA |
| \r | 0x0D | 0x0 | 0xD |
상위 니블로 인덱싱되는 테이블 하나와 하위 니블로 인덱싱되는 테이블 하나를 만듭니다. 각 테이블은 그 니블에 대한 후보 클래스들의 집합을 반환합니다. 그 결과를 AND하면 올바른 클래스만 살아남습니다.
예를 들어 쉼표 (0x2C)가 두 테이블을 통과하는 과정을 따라가 보겠습니다:
상위 니블 테이블
| 인덱스 | 반환값 |
|---|---|
| 0x0 | NEWLINE |
| 0x2 | COMMA |
| ... | 0 |
하위 니블 테이블
| 인덱스 | 반환값 |
|---|---|
| 0x2 | QUOTE |
| 0xA | NEWLINE |
| 0xC | COMMA |
| 0xD | NEWLINE |
| ... | 0 |
0x2C → 상위 니블 0x2는 COMMA | QUOTE를 반환
하위 니블 0xC는 COMMA를 반환
AND 결과: COMMA ✓
상위 니블 0x2는 ,와 "가 공유하므로 둘 다 후보로 반환된다는 점에 주목하세요. 하지만 하위 니블 0xC는 COMMA에만 일치합니다. AND를 하면 QUOTE는 제거되고 COMMA만 남습니다.
이 lookup table을 만드는 데는 약간의 주의가 필요합니다. AND가 서로 독립적인 2개의 조회 결과를 결합하므로, 사실상 격자를 설계하는 셈입니다. 상위 니블이 일치하고 하위 니블이 일치하는 모든 바이트는 분류됩니다.
가령 0xA0, 0xB4, 0xB0을 하나의 클래스로 묶고 싶다고 합시다. 상위 니블은 {0xA, 0xB}이고 하위 니블은 {0x0, 0x4}입니다. 이 격자에는 교차점이 4개 있지만, 나열한 바이트는 3개뿐입니다. 네 번째 바이트인 0xA4는 잘못 분류될 것입니다.
빠른 sanity check 하나: 클래스에 속한 바이트 수가 고유한 상위 니블 개수와 고유한 하위 니블 개수를 곱한 값과 같다면 false positive는 없습니다.
아래에서 스칼라 구현과 벡터화 구현을 둘 다 보겠습니다. 벡터화 구현에서도 여전히 바이트 스트림을 순회하지만, 이제는 16바이트씩 처리합니다. 그리고 내부 본문에는 분기문이 없고, lookup과 AND만 있습니다.
// scalar implementation
enum Class {
Comma = 1,
Quote = 2,
NewLine = 3,
Other = 0,
}
let bytes: &[u8] = &data_stream;
let mut classified_bytes = Vec::with_capacity(bytes.len());
for b in bytes {
let class = match b {
0x2c => Class::Comma,
0x22 => Class::Quote,
0x0A | 0x0D => Class::NewLine,
_ => Class::Other
};
classified_bytes.push(class);
}아래의 v* 함수들은 NEON intrinsics로, Rust에서 어셈블리를 쓰지 않고도 SIMD를 사용할 수 있게 해주는 단일 ARM 명령에 대한 얇은 래퍼입니다.
// vectorized implementation
// i'm on a mac :/
use std::arch::aarch64::*;
const COMMA: u8 = Class::Comma as u8;
const QUOTE: u8 = Class::Quote as u8;
const NEWLINE: u8 = Class::NewLine as u8;
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
};
let bytes: &[u8] = &data_stream;
let mut classified_bytes = Vec::with_capacity(bytes.len());
unsafe {
// load 16 bytes into register
let lo_lut = vld1q_u8(LO_LOOKUP.as_ptr());
let hi_lut = vld1q_u8(HI_LOOKUP.as_ptr());
// broadcast 0x0F to all 16 lanes
let mask = vdupq_n_u8(0x0F);
let chunks = bytes.chunks_exact(16);
let remainder = chunks.remainder();
for chunk in chunks {
let input = vld1q_u8(chunk.as_ptr());
// bitwise AND, isolate low nibble
let lo_nibbles = vandq_u8(input, mask);
// shift right 4, isolate high nibble
let hi_nibbles = vandq_u8(vshrq_n_u8::<4>(input), mask);
// table lookup by low nibble
let lo_result = vqtbl1q_u8(lo_lut, lo_nibbles);
// table lookup by high nibble
let hi_result = vqtbl1q_u8(hi_lut, hi_nibbles);
// AND to get final class
let classified = vandq_u8(lo_result, hi_result);
let mut out = [0u8; 16];
// store 16 bytes from register
vst1q_u8(out.as_mut_ptr(), classified);
classified_bytes.extend_from_slice(&out);
}
// pad remaining bytes with zeros
if !remainder.is_empty() {
let mut padded = [0u8; 16];
padded[..remainder.len()].copy_from_slice(remainder);
let input = vld1q_u8(padded.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[..remainder.len()]);
}
}이제 스트림의 모든 바이트를 분류했으니, 분류된 바이트를 클래스별로 하나씩, 총 3개의 비트마스크로 압축합니다. 비트마스크의 각 비트는 바이트 스트림의 한 위치에 대응합니다. 해당 클래스가 있으면 1, 없으면 0입니다.
alice,30,Irvine\n을 보겠습니다(운 좋게도 16바이트입니다):
원시 바이트: a l i c e , 3 0 , I r v i n e \n
분류 결과: 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 3
COMMA 마스크: 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0
QUOTE 마스크: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
NEWLINE 마스크: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
각 클래스의 비트마스크는 Vec<u64>로 조밀하게 표현되며, 이는 하나의 u64가 스트림의 64바이트를 나타낸다는 뜻입니다.
이 시점에서 분류기는 실제 구분자와 인용된 필드 안에 있는 구분자를 구분하지 못합니다. 예시의 세 번째 행을 보겠습니다:
lonely charlie,28,"where she said, ""hi""\nto me"
분류기는 세 번째 필드 "where she said, ""hi""\nto me" 안의 모든 구조 문자를 표시했습니다. 여기에는 쉼표 하나, 줄바꿈 하나, 따옴표 6개가 포함됩니다. 처음과 마지막 따옴표는 인용된 필드의 안과 밖을 나누는 실제 경계입니다.
어떤 위치가 인용된 필드 안인지 밖인지는 따옴표 위치에 대한 누적 parity를 유지하면 알 수 있습니다. 어떤 위치 앞에 있는 따옴표 개수가 짝수면 바깥이고, 홀수면 안입니다.
이를 예시에 적용하면 첫 번째 따옴표와 마지막 따옴표 사이의 모든 것은 인용된 필드 내부입니다(초록색으로 표시). 이스케이프된 따옴표("")는 그저 연속된 2번의 뒤집기라는 점에 주목하세요. 서로 상쇄되므로, 알고리즘은 이를 실제 경계와 구분할 필요가 없습니다.
"where she said, ""hi""\nto me"
예시를 따라가 봅시다 (각 줄에 마우스를 올려보세요)
byte 0은 "입니다 (따옴표 개수 = 1, 홀수 → 내부)
bytes 1-16 where she said,는 내부입니다
byte 17은 "입니다 (따옴표 개수 = 2, 짝수 → 외부)
byte 18은 "입니다 (따옴표 개수 = 3, 홀수 → 내부)
bytes 19-20 hi는 내부입니다
byte 21은 "입니다 (따옴표 개수 = 4, 짝수 → 외부)
byte 22는 "입니다 (따옴표 개수 = 5, 홀수 → 내부)
byte 23 \n은 내부입니다
bytes 24-28 to me는 내부입니다
byte 29는 "입니다 (따옴표 개수 = 6, 짝수 → 외부)
이를 전체 바이트 스트림에 대해 한 번에 계산하려면, 따옴표 비트마스크의 prefix XOR를 취하면 됩니다.
이 개념을 배웠을 때의 제 기분입니다 각 위치에서 결과는 그 위치까지의 모든 따옴표 비트에 대한 XOR입니다.
"where she said, ""hi""\nto me"
quotes: 100000000000000001100110000001
prefix: 111111111111111110111011111110
이스케이프된 따옴표 쌍("")은 prefix 마스크에서 번갈아 나타나는 01을 만든다는 점을 볼 수 있습니다. 괜찮습니다. 우리는 prefix 마스크를 따옴표 자체가 아니라 쉼표와 줄바꿈을 필터링하는 데만 사용하기 때문입니다. 바깥쪽 마스크를 얻기 위해 prefix를 뒤집고, 그것을 쉼표와 줄바꿈 비트마스크에 AND합니다. 이렇게 하면 인용된 필드 안의 쉼표와 줄바꿈은 0으로 지워지고, 실제 구분자만 남게 됩니다.
"where she said, ""hi""\nto me"
prefix: 111111111111111110111011111110 !prefix: 000000000000000001000100000001
commas: 000000000000000100000000000000 !prefix: 000000000000000001000100000001 & result: 000000000000000000000000000000
newlines: 000000000000000000000001000000
!prefix: 000000000000000001000100000001
& result: 000000000000000000000000000000
64비트에 대한 prefix XOR를 계산하는 것은 6번의 shift 연산 체인으로 할 수도 있고, ARM에서는 단일 vmull_p64 (carryless multiplication) 명령으로도 할 수 있습니다:
// shift-XOR chain: 6 operations
fn prefix_xor(mut x: u64) -> u64 {
x ^= x >> 1;
x ^= x >> 2;
x ^= x >> 4;
x ^= x >> 8;
x ^= x >> 16;
x ^= x >> 32;
x
}// carryless multiplication: 1 instruction
use std::arch::aarch64::vmull_p64;
fn prefix_xor(x: u64) -> u64 {
unsafe { vmull_p64(x, u64::MAX) as u64 }
}이제 쉼표와 줄바꿈 비트마스크에는 실제 구분자만 들어 있으므로, 이를 u64 하나씩 순회합니다.
청크 사이에는 우리가 인용된 필드 안에서 끝났는지를 추적하는 단 하나의 불리언 값을 들고 갑니다. 이전 u64에 따옴표 비트가 홀수 개 있었다면 아직 안쪽에 있는 것이므로, 현재 청크에 대한 prefix XOR는 반전되어야 합니다.
정제된 비트마스크로부터는 leading zero의 개수(clz)를 세어 구분자 위치를 추출합니다. 이는 대부분의 아키텍처에서 단일 사이클 명령입니다. 각 카운트는 다음으로 set된 비트의 오프셋을 주고, 그것이 다음 구분자입니다. 다음 쉼표보다 먼저 줄바꿈이 나타나면, 그것은 현재 필드와 현재 행 둘 다의 끝을 뜻합니다.
type FieldRef = Range<usize>;
type RowRef = Vec<FieldRef>;
let mut rows = Vec::new();
let mut current_row = Vec::new();
let mut start = 0;
let mut end = 0;
let mut carry = false;
for i in 0..quote_bitsets.len() {
let quotes = quote_bitsets[i];
let outside = !prefix_xor(quotes, carry);
// a branchless way of toggling carry
// when the chunk has an odd number of quotes
carry ^= (quotes.count_ones() & 1) != 0;
let mut commas = comma_bitsets[i] & outside;
let mut newlines = newline_bitsets[i] & outside;
loop {
let next_comma = commas.leading_zeros() as usize;
let next_newline = newlines.leading_zeros() as usize;
let advance = next_comma.min(next_newline);
// no delimiters seen in this chunk
if advance == 64 {
end = (i + 1) * 64;
break;
}
end += advance;
if start < end {
current_row.push(start..end);
if next_newline < next_comma {
rows.push(current_row.clone());
current_row.clear();
}
}
// skip the delimiter
end += 1;
// shift out the bits we already processed
commas <<= advance + 1;
newlines <<= advance + 1;
start = end;
}
}공유:[lobste.rs][hacker news][email]
friendlymatthewhttp://chunkofcoal.com/
내 기억력이 나빠지는 게 아니라, 그저 지수 감쇠를 사용할 뿐이다2026-03-15
« 내 기억력이 나빠지는 게 아니라, 그저 지수 감쇠를 사용할 뿐이다
📝 최근 글
🏷️ 태그 클라우드
csv (1)data structures (1)debuggers (1)file formats (1)interpreters (1)rust (2)simd (1)wasm (1)
📅 아카이브
📅 2026년 3월(2) * Paul Allen의 SIMD CSV 파서를 봅시다 * 내 기억력이 나빠지는 게 아니라, 그저 지수 감쇠를 사용할 뿐이다
📊 사이트 통계
이제 농담할 시간입니다! 다음
나는 나 자신을 'steampunk'의 팬이라고 부르지는 않겠지만, punk를 조리하는 가장 건강한 방법이라고는 말하겠다.
— Norm Macdonald Live
friendlymatthewhttp://chunkofcoal.com/https://github.com/friendlymatthew
방문자:——————
페이지 생성: 2026-03-23 19:06:24
© 2026 friendlymatthew