simdjson - JSON을 GB/초 단위로 파싱하기
(github.com)- SIMD 명령어셋을 이용해서 기존 파서들보다 2.5배 빠르게 파싱
- 런타임에 CPU별 최적화된 파서 자동 선택 : 하스웰(AVX2)/웨스트미어(SSE4.2)/ARM64/기타64
- Full JSON & UTF-8 validation 지원
- 한개의 .h + .cpp 파일
- RapidJSON 대비 25%, sajson 대비 50%의 명령어 셋만 사용
다양한 바인딩 / 포트가 있네요
- ZippyJSON: Swift bindings for the simdjson project.
- libpy_simdjson: high-speed Python bindings for simdjson using libpy.
- pysimdjson: Python bindings for the simdjson project.
- simdjson-rs: Rust port.
- simdjson-rust: Rust wrapper (bindings).
- SimdJsonSharp: C# version for .NET Core (bindings and full port).
- simdjson_nodejs: Node.js bindings for the simdjson project.
- simdjson_php: PHP bindings for the simdjson project.
- simdjson_ruby: Ruby bindings for the simdjson project.
- fast_jsonparser: Ruby bindings for the simdjson project.
- simdjson-go: Go port using Golang assembly.
rcppsimdjson: R bindings.
Rust 버전 - https://github.com/simd-lite/simd-json
QCon 에서 개발자의 발표 내용 "Parsing JSON Really Quickly: Lessons Learned"
https://www.youtube.com/watch?v=wlvKAT7SZIQ
링크된 강연 동영상의 녹취록:
https://www.infoq.com/presentations/simdjson-parser/
어떻게 이렇게 빠른 속도를 낼 수 있는지 궁금해서 읽어봤는데, 가히 온갖 흑마술의 결정체라 할 수 있을 것 같습니다. 요점을 대강 정리하면 다음과 같습니다.
----
[서론]
# 대부분의 JSON 파싱 라이브러리는 드라이브의 순차 읽기 속도보다 느리다
- 나(강연자 Daniel Lemire)의 시스템 드라이브에서 큰 텍스트 파일을 순차적으로 읽어들이는 속도는 2.2 GB/s인데, 주요 JSON 라이브러리의 파싱 속도는 이를 못 따라가더라.
- 파싱 속도가 1 GB/s를 넘기는 라이브러리가 드물길래, 우리가 작접 만들어보기로 했다.
- 그 결과, 드라이브 대역폭을 전부 쓸 수 있는 처리 속도를 달성했다. 계산해보면 입력 1바이트당 CPU를 1.5사이클밖에 쓰지 않았다. 어떻게 이를 달성했는가?
[각종 원칙들]
# 분기문을 최대한 피한다
- 예를 들어 랜덤 숫자를 배열에 집어넣는 간단한 코드에 숫자가 홀수인지 판별하는 if문 하나만 넣어도 5배로 느려진다. 이는 CPU 분기 예측이 실패할 때의 비용이 크기 때문이다.
- 위에서 제시된 코드에서 비트 연산으로 if문을 제거하면 속도가 거의 원상복구된다.
- 코드를 반복 실행하면 분기 예측의 정확도가 올라가서 성능 저하가 감소할 수 있긴 하지만, 이건 결국 비결정론적인 동작이므로 분기 예측이 작용할 때면 성능을 예측하거나 측정하기가 어려워진다.
# 더 넓은 워드를 쓰기 위해 SIMD를 적극 사용한다
- SIMD 명령을 쓰면 64비트보다 더 넓은 워드의 레지스터를 사용할 수 있어, 1사이클에 더 많은 데이터를 처리할 수 있다. (예를 들면 SSE나 NEON은 128비트, AVX는 256비트) 따라서 가능하면 SIMD를 적극적으로 사용했다. 이는 입력 데이터 1바이트에 불과 1.5사이클만 사용할 수 있었던 비결이다.
- SIMD를 쓰기 위해 특정 프로세서에 의존적인 내장 함수(Intrinsic function)를 사용했다. 어셈블리어를 직접 사용하는 것은 권장하지 않는다.
# 메모리/객체의 할당을 피한다
- simdjson에서는 JSON 데이터를 하나의 긴 테이프처럼 취급하고, 데이터를 재활용한다. 다시 말해, 문자열이나 숫자에 메모리를 따로 할당하지 않고 모든 것을 일렬로 처리한다. 이는 흔한 트릭이다.
# 성능을 계속 측정한다
- 벤치마크 주도적으로(Benchmark-driven) 개발하였다. 우리 CI에는 성능 벤치마크가 포함되어 있다.
- 참고로 뭔가 CPU 집중적인 작업을 할 때는 CPU의 작동 주파수가 계속 변한다는 점을 명심해야 한다.
[실제 사례들]
# 예시 1: 올바른 UTF-8인지 검증하기
- 입력된 임의의 데이터가 올바른 UTF-8 코드포인트인지 검증하는 작업은 일반적으로 여러 분기문이 들어가는 작업이다.
- 우리는 SIMD로 32바이트 데이터를 최대 20번의 사이클만에 분기문 없이 올바른 UTF-8인지 검증하는 방법을 만들었다.
- UTF-8의 바이트는 정수값으로 최대 244를 넘을 수 없으므로, SIMD 명령으로 데이터를 256비트 레지스터에 넣고 각 바이트마다 정수 244를 포화 연산(Saturation arithmetic: 결과값의 범위를 제한하는 연산)으로 뺀 다음 0이 아닌 값이 없는지만 확인하면 된다.
- 이 방법은 분기문을 사용하는 방법보다 20배 이상 빠르다!
# 예시 2: 글자 종류 분류하기
- JSON을 파싱하려면 콤마, 콜론, 괄호, 공백 등 각종 문자를 종류별로 분류해야 한다.
- x86-64 및 ARM NEON에는 16바이트 크기의 룩업 테이블을 단번에 찾는 명령어가 있다.
- 1바이트를 상위 4비트와 하위 4비트로 나누어, 미리 준비한 2개의 룩업 테이블을 각각 적용한 다음 그 결과를 AND 연산한다.
- 코드가 더러워 보이긴 하지만, 5개의 명령만으로 분기문 없이 16개의 글자를 분류할 수 있다.
# 예시 3: 이스케이프 문자 감지하기
- 백스페이스(\) 문자를 앞에 붙여서 표현하는 이스케이프 문자를 분기문 없이 감지할 수 있을까? 특히 백스페이스 자체를 이스케이프 처리하기 위해 백스페이스가 연달아 나오는 경우도 처리해야 한다.
- 이런 경우, 홀수번째 백스페이스만 보면 된다는 트릭이 있다.
- 짝수번째 위치와 홀수번째 위치를 나타내는 비트마스크를 상수로 두고, 복잡한 비트 연산을 거치면 분기 없이 이스케이프 문자를 걸러낼 수 있다.
- 이스케이프된 따옴표를 걸러내고 나면 남는 것은 문자열을 나타내기 위한 따옴표이다.
- 이렇게 구한 따옴표의 위치를 비트마스크로 두고 xor 비트 연산을 거듭하면 문자열의 위치를 나타내는 비트마스크를 구할 수 있다. 이 부분은 대부분의 프로세서에서 명령어 하나로 처리할 수 있다.
- 비트 집합과 문자열 위치를 대응하는 방법에도 트릭이 있지만, 시간 관계상 넘어가겠다.
# 예시 4: 숫자 파싱하기
- 숫자를 파싱하는 것은 대단히 비싼 작업이다. 잘 최적화한 C 함수로 부동소수점을 파싱하는 벤치마크를 했더니 0.09 GB/s라는 환장하는 속도가 나왔다. 명백한 병목 지점이었다.
- 숫자를 파싱하는 대부분의 코드는 한번에 바이트 단위로 작업하는 것이 보통이다. 이는 결코 빠르지 않다.
- 문자 8개를 가져와서 64비트 정수 하나로 만들고 강연자가 토요일 밤늦게 고안해낸 특정 공식에 대입하면 이 8개의 문자가 연속된 8자리 숫자인지 알 수 있다. 이는 특히 자릿수가 많은 숫자일수록 파싱하는 데 시간이 오래 걸리기 때문에 중요하다.
- 스택 오버플로우에 보니까 8자리 정수를 빠르게 파싱하는 코드 스니펫도 있더라. SIMD를 쓰면 좀 더 개선할 수 있긴 한데, 중요한 것은 이렇게 한 번에 데이터를 많이 처리하는 전략에 관한 아이디어를 얻는 것이다.
[그 외]
# 런타임 디스패치
- 하드웨어 의존적인 코드가 많이 들어가다 보니 각 프로세서별로 최적화된 함수가 나오는데, 실행할 때 프로세서 종류에 맞는 함수를 실행하게끔 하는 것이 상당히 어려웠다.
- 그게 뭐가 어려운지 이해를 못할 수도 있겠는데, 문제는 컴파일러 종류를 가리지 않는 이식성 있는 코드로 이런 것을 구현하는 것이었다. 어떤 컴파일러에는 버그가 있기도 했고, 또 언어 차원에서 이런 것을 지원하는 것도 아니다.
- 이 점은 simdjson이 다른 프로젝트에 쉽게 통합할 수 있는 단일 헤더파일 오픈소스 라이브러리라서 중요했다.
# 기타
- 여러 언어에서 쓸 수 있도록 각각 wrapper가 있다.
- Rust 포팅 버전이 있고 Go와 C# 포팅도 준비중이지만, Java 포팅은 없다.
- 이 프로젝트에서 사용된 여러 수학 공식들은 공동 저자인 Geoff Langdale과 고안한 것으로, VLDB Journal에 관련 논문을 출판하였다. ( https://doi.org/10.1007/s00778-019-00578-5 )