- 1BRC의 병목은 CSV 온도값 10억 개를 극단적으로 빠르게 파싱하는 일이었고, Quân Anh Mai의 merykitty SWAR 코드는
if 없이 고정 ALU 연산으로 온도를 정수화해 주목받음
- 이 코드는
long 하나에 담긴 8바이트를 한꺼번에 다루는 SWAR(SIMD Within A Register) 방식으로, 일반 CPU 레지스터에서 여러 문자를 병렬처럼 처리함
- 처리 흐름은 마이너스 부호 감지, 부호 제거, 소수점 위치 탐지,
XY.Z 정렬, ASCII 숫자 변환, 매직 곱셈, 부호 적용으로 이어짐
- 입력 형식은
-XX.X, -X.X, X.X, XX.X 네 가지이며, 소수점 위치를 기준으로 바이트를 이동해 서로 다른 길이를 같은 비트 배치로 맞춤
- 분기와 반복을 줄이는 대신 ASCII 코드 특성, 2의 보수, 비트 마스크, 곱셈의 시프트-덧셈 성질을 촘촘히 이용해 고성능 파싱을 구현함
1BRC에서 병목이 된 온도 파싱
- One Billion Row Challenge(1BRC)에서는 CSV 파일의 온도값을 매우 빠르게 파싱하는 일이 핵심 병목으로 떠오름
- 이전 최적화만으로도 관용적인 병렬 Java 코드는 71초에서 1.7초까지 빨라짐
- 온도 형식은 단순하지만, 10억 개를 1초 미만에 파싱하려면 작은 비용도 크게 누적됨
- 가능한 형식은
-XX.X, -X.X, X.X, XX.X
- 초기 참가자들은
Double.parseDouble()을 사용했지만, 이후 루프 없는 커스텀 파서들이 등장함
- Quân Anh Mai의 @merykitty 솔루션 일부는
if 없이 단일 파일 읽기로 처리해 1BRC 상위 솔루션의 표준 요소처럼 퍼짐
- 우승자인 Thomas Wuerthinger는 자신의 솔루션에 기여한 팀 일부로 Quân Anh을 명시함
merykitty 코드가 하는 일
- 코드는 8바이트 CSV 입력이 담긴
long을 받아 실제 온도의 10배인 정수 온도값을 반환함
- 입력은
mmap된 CSV 파일에서 직접 네이티브 메모리 읽기로 들어오며, 해당 부분은 별도 관심사로 분리됨
- 연산은 고정된 순서의 18개 ALU 작업으로 구성됨
- 비트 시프트, AND, NOT, XOR
- 덧셈, 뺄셈, 곱셈
Long.numberOfTrailingZeros()
numberOfTrailingZeros()는 JDK 컴파일러 intrinsic을 통해 특수 CPU 명령을 사용함- 일반 SIMD 전용 명령이 아니라 일반 CPU 레지스터와 명령으로 여러 바이트를 다루기 때문에 SWAR 방식에 해당함
- 예시 코드는 원본을 읽기 쉽게 약간 변형한 것이며, 원본은 CalculateAverage_merykitty.java에 있음
전체 처리 단계
- 코드는 다음 순서로 온도를 파싱함
- 첫 문자가
-인지 확인해 음수 여부를 감지함
- 부호 문자가 있으면 해당 바이트를 0으로 만듦
- 소수점
.의 위치를 찾음
- 숫자들이
XY.Z 템플릿에 맞도록 long 내부 비트를 이동함
- ASCII 문자를 실제 숫자값으로 바꿈
- 각 자리 숫자에
1x, 10x, 100x 가중치를 곱해 합산함
- 마지막에 부호를 적용함
- 겉보기에는 고수준 파싱 문제지만, 각 단계는 ALU 연산만으로 구현됨
1단계: 마이너스 부호 감지
long negatedInput = ~inputData;
long broadcastSign = (negatedInput << 59) >> 63;
- 설명상 순서를 바꾸면
( ~(inputData << 59) ) >> 63처럼 볼 수 있음
- ASCII에서 마이너스
-는 비트 4가 0이고, 숫자 문자는 해당 비트가 1이라는 성질을 이용함
- 입력을 왼쪽으로 59비트 이동하면 첫 문자의 구분 비트가 최상위 비트로 이동함
- NOT으로 비트를 뒤집은 뒤 산술 오른쪽 시프트를 63비트 수행하면 최상위 비트가 전체
long에 퍼짐
- 결과인
broadcastSign은 마이너스가 있으면 모든 비트가 1, 없으면 모든 비트가 0이 됨
2단계: 부호 문자 제거
- 음수 여부는
broadcastSign에 저장됐으므로, 입력 데이터에서는 부호 문자를 제거함
long maskToRemoveSign = ~(broadcastSign & 0xFF);
long withSignRemoved = inputData & maskToRemoveSign;
broadcastSign이 모두 1이면 broadcastSign & 0xFF는 최하위 8비트만 1이 됨- 이를 NOT하면 최하위 8비트만 0인 마스크가 만들어짐
inputData와 AND하면 최하위 바이트의 -가 제거됨- 마이너스가 없으면
broadcastSign이 0이므로 마스크는 모든 비트가 1이 되어 숫자 바이트가 유지됨
3단계: 소수점 위치 찾기
int dotPos = Long.numberOfTrailingZeros(negatedInput & DOT_DETECTOR);
. 문자도 마이너스와 마찬가지로 비트 4가 0이라는 특성을 가짐- 가능한 소수점 위치의 비트 4만 확인하기 위해
DOT_DETECTOR = 0x10101000 마스크를 사용함
- 원본 입력을 반전한
negatedInput에서는 소수점 위치의 해당 비트가 1이 됨
Long.numberOfTrailingZeros()는 이 1비트의 위치를 반환함- 예시
-10.8에서는 소수점이 비트 위치 28에 있어 dotPos = 28이 됨
4단계: 고정 템플릿으로 정렬
- 소수점 위치를 기준으로 입력을 왼쪽으로 이동해 항상 같은 템플릿에 맞춤
long alignedToTemplate = withSignRemoved << (28 - dotPos);
0 0 0 Z . Y X 0
- 여기서
X는 십의 자리, Y는 일의 자리, Z는 소수 첫째 자리임
0은 ASCII "0"이 아니라 값이 0인 바이트를 뜻함- 부호 제거 후 입력은 네 가지 배치 중 하나일 수 있음
0 0 0 Z . Y X 00 0 0 0 Z . Y 00 0 0 0 Z . Y X0 0 0 0 0 Z . Y
-10.8은 이미 dotPos = 28이므로 이동량이 0임-7.7은 소수점 위치가 비트 20이라 8비트, 즉 한 바이트 왼쪽으로 이동해 X 자리에 0이 놓임
5단계: ASCII 숫자를 값으로 바꾸기
- 정렬 후에는 ASCII 문자에서 숫자값만 남김
long digits = alignedToTemplate & ASCII_TO_DIGIT_MASK;
- ASCII 숫자
0부터 9는 16진수로 0x30부터 0x39임
- 하위 4비트만 남기면 문자 코드가 실제 숫자값이 됨
- 템플릿의 숫자 위치에만
F가 있는 마스크를 적용함
0 0 0 Z . Y X 0
000000F000F0F00
- 예시
-10.8은 마스크 적용 후 Z=8, Y=0, X=1을 나타내는 값만 남음
6단계: 매직 곱셈으로 자리값 합산
- 최종 절댓값은
100 * X + 10 * Y + Z로 계산해야 함
- 곱셈이 시프트와 덧셈의 조합이라는 성질을 이용해 여러 자리의 가중치 계산을 한 번의 곱셈으로 처리함
- 먼저
X + Y + Z를 생각하면, digits를 0, 16, 24비트 위치로 시프트한 값을 더해 특정 비트 구간에 합을 모을 수 있음
- 이 시프트-덧셈 조합은 다음과 같은 곱셈으로 표현됨
0x1 + 0x10000 + 0x1000000
- 실제로는 각 자리의 가중치가 다르므로
MAGIC_MULTIPLIER는 다음처럼 구성됨
MAGIC_MULTIPLIER = 0x1 + 10 * 0x10000 + 100 * 0x1000000;
absValue = ((digits * MAGIC_MULTIPLIER) >>> 32) & 0x3FF;
0x3FF는 10비트 폭 결과만 분리하는 마스크임100 * X가 10비트까지 커져 인접 비트와 겹칠 수 있지만, Y * 100의 오른쪽 두 비트가 0이 되는 성질 때문에 필요한 비트 공간이 확보됨- merykitty는 이 부분에
// That was close :)라는 주석을 남김
7단계: 분기 없이 부호 적용
- 이 시점에는 절댓값
absValue와 부호 정보 broadcastSign이 있음
broadcastSign은 양수면 0, 음수면 -1로 동작함- 2의 보수에서 음수는 다음 식으로 표현됨
-n = NOT(n) + 1
- XOR는 조건부 NOT처럼 사용할 수 있음
n XOR -1은 NOT(n)n XOR 0은 n
- 선택적인
+1은 -broadcastSign으로 처리함
temperature = (absValue ^ broadcastSign) - broadcastSign;
- 결과적으로
if 없이 양수는 그대로, 음수는 2의 보수 음수값으로 변환됨
보너스: 다음 CSV 행 시작 위치 계산
- 전체 1BRC 솔루션에서는 다음 CSV 라인의 시작 위치도 저렴하게 계산해야 함
- 소수점 뒤에는 항상 소수 한 자리와 개행 문자가 이어지므로, 소수점 위치를 기준으로 다음 행 시작 위치를 구함
dotPos는 비트 단위 위치이므로 8로 나누기 위해 3비트 오른쪽 시프트를 사용함
nextLineStart = (dotPos >>> 3) + 3;
+3은 소수점, 소수 한 자리, 개행 이후의 첫 바이트를 가리키기 위한 값임
결론
- merykitty의 SWAR 코드는 고정된 비트 연산만으로 네 가지 온도 문자열 형식을 통일해 파싱함
- 핵심은 ASCII 코드의 비트 특성, 소수점 위치 기반 정렬, 마스크를 통한 숫자 추출, 곱셈을 이용한 자리값 합산, 2의 보수 기반 부호 적용임
- 단계별로 나누면 동작을 따라갈 수 있지만, 이를 온라인 챌린지 며칠 안에 조합한 점이 인상적인 부분으로 남음