serde_json 문자열 처리 20% 속도 향상

 (purplesyringa.moe)
2P by GN⁺ | ★ favorite | 댓글 1개
  • Rust 생태계의 기본 JSON 파서처럼 쓰이는 serde_json은 문자열이 많은 벤치마크에서 작은 내부 최적화만으로도 10%, 23%, 32% 성능 개선을 얻음
  • 오류 위치 계산은 문자열 앞부분을 직접 훑는 대신 memchr로 줄 수와 마지막 개행을 찾도록 바뀌어, 성공 경로보다 2배 이상 느리던 오류 경로 격차가 줄어듦
  • 문자열 파싱 핵심 루프는 \, ", 제어 문자를 따로 찾지 않고 SWAR로 한 번에 검사해, 실제 SIMD 없이도 짧은 문자열에서 낮은 지연 시간을 확보함
  • \u escape 디코딩은 LUT, 부호 있는 정수, 사전 시프트 테이블로 분기와 shift 비용을 줄였고, 러시아어 War and Peace JSON 파싱은 284 MB/s에서 344 MB/s로 빨라짐
  • 이후 병목이 된 UTF-8 인코딩은 char::encode_utf8와 Vec::extend_from_slice의 초기화·복사 비용을 피하는 수동 UTF-8 생성으로 처리해 같은 벤치마크가 374 MB/s까지 올라감

왜 serde_json 최적화가 큰 효과를 내는가

  • serde는 Rust의 대표적인 직렬화·역직렬화 프레임워크이고, serde_json은 JSON 처리를 위한 공식 조합으로 널리 사용됨
  • 게시 시점 기준 serde_json의 역의존성은 26,916개였고, simd-json은 66개였음
  • 이 정도 사용량에서는 serde_json 내부의 작은 개선도 Rust 생태계 전반에 누적 효과를 낼 수 있음
  • 많은 사용자가 다른 JSON 파서로 쉽게 바꾸지 않는 상황에서는, 기존 라이브러리 안의 저위험 최적화가 실용적임

오류 위치 계산: 단순 루프에서 memchr로

  • 오류 경로 벤치마크에서 serde_json은 같은 데이터의 성공 경로보다 2배 이상 느렸음
    • canada, citm_catalog, twitter 데이터셋에서 오류 경로는 성공 경로 대비 -48%~-77% 느렸음
  • 병목은 오류 메시지 포맷을 위해 인덱스를 line/column으로 바꾸는 position_of_index() 함수였음
    • 기존 구현은 self.slice[..i]를 바이트 단위로 순회하며 \n을 만날 때마다 line과 column을 갱신함
  • 계산을 두 단계로 나누면 memchr를 적용할 수 있음
    • self.slice[..i] 안의 \n 개수를 세어 0 기반 line 번호를 구함
    • 마지막 \n 위치를 찾아 i에서 빼 column 번호를 구함
  • memchr는 단일 문자 검색과 개수 세기에 최적화된 구현을 제공하며, 내부적으로 SIMD를 사용함
  • PR #1160이 병합된 뒤 오류 경로 성능이 크게 개선됨
    • canada DOM 기준 오류 경로가 122 MB/s에서 216 MB/s로 상승
    • citm_catalog struct 기준 195 MB/s에서 736 MB/s로 상승
    • 오류 경로는 여전히 성공 경로보다 느렸지만 격차가 줄어듦

문자열 이스케이프 탐색: 세 조건을 한 번에 찾기

  • 문자열 파싱의 기존 핵심 루프는 ESCAPE 테이블을 보며 escape가 아닌 바이트를 지나감
    • JSON 문자열에서 처리해야 하는 escape 대상은 \, ", 그리고 0x1F 이하의 ASCII 제어 문자임
    • JSON 명세상 문자열 안의 제어 코드는 허용되지 않음
  • 첫 시도는 memchr2로 \ 또는 "를 먼저 찾고, 이후 제어 문자를 별도로 확인하는 방식이었음
    • 문자열을 빠르게 한 번, 느리게 한 번 두 번 순회하게 되어 기존보다 느렸음
    • 단순한 절반만 벡터화하고 나머지를 스칼라로 남기면 전체 개선으로 이어지지 않았음
  • 두 번째 시도는 memchr2와 수동 SIMD로 제어 문자가 없는지 확인하는 구조였음
    • 짧은 문자열에서는 런타임 선택 함수 호출 비용이 부담이 됨
    • 긴 문자열에서는 메모리를 두 번 읽는 문제가 남아 있음
  • 최종 구현은 \, ", 제어 문자를 한 번의 패스에서 찾는 방향으로 정리됨

SWAR로 SIMD에 가까운 처리 구현

  • 플랫폼별 SIMD 코드를 따로 넣지 않기 위해 SWAR(SIMD Within A Register) 기법을 사용함
    • 128비트 SIMD 대신 64비트 워드를 8개 바이트처럼 다룸
    • 비트 연산으로 각 바이트가 조건을 만족하는지 동시에 검사함
  • 제어 문자 검사는 c >= 0 && c < 0x20 조건을 비트 연산 형태로 바꿔 처리함
    • 8바이트 묶음에서는 !c & (c - 0x2020202020202020) & 0x8080808080808080 형태의 마스크로 확인함
    • 64비트 뺄셈의 borrow가 상위 바이트로 전파될 수 있지만, 가장 낮은 위치의 제어 문자를 찾는 목적에는 문제가 되지 않음
  • \와 "도 유사한 방식으로 검사해 하나의 식으로 합침
    • 전체 식은 9개의 비트 연산으로 구성됨
    • x86 SIMD라면 7개 연산이 필요하므로 처리량은 낮지만, 짧은 문자열에서는 지연 시간이 더 중요함
  • json-benchmark에서는 이 SWAR 코드가 실제 SIMD 코드보다 효율적이었음
  • 너무 짧은 문자열에서는 SWAR가 스칼라 코드보다 느려질 수 있음
    • 약 5자 문자열에서 회귀가 나타남
    • 빈 문자열 ""과 연속 escape \r\n, \uD801\uDC37 같은 흔한 패턴을 보호하기 위해 SWAR 루프 진입 전 첫 문자가 escape인지 확인함
  • 문자열 탐색 최적화 결과는 데이터셋별로 달랐음
    • twitter struct는 638 MB/s에서 785 MB/s로 +23%
    • twitter DOM은 305 MB/s에서 335 MB/s로 +10%
    • citm_catalog struct는 865 MB/s에서 905 MB/s로 +5%
    • 빈 문자열은 특정 마이크로벤치마크에서 여전히 2% 이내로 느려짐

Unicode escape 디코딩 최적화

  • serde_json은 원시 Unicode 문자열과 \u escape를 모두 처리함
    • 예: "🥺"와 "\ud83e\udd7a"
  • 기존 hex 디코딩은 256개 항목 LUT를 사용해 각 문자를 0~15 값으로 매핑함
    • '0'..='9', 'A'..='F', 'a'..='f'를 처리함
    • 잘못된 문자는 센티널 값으로 표시함
  • \u escape는 4개의 hex digit을 읽으므로, 기존 방식에는 반복마다 shift, add, 비교, 조건 분기가 들어감
  • 개선 구현은 반복 중 매번 오류를 반환하지 않고, 4자리를 모두 처리한 뒤 유효성을 확인함
  • 최종 구현은 [i8; 256] LUT에서 잘못된 digit을 -1로 두고, 32비트 정수로 계산함
    • 성공 시 결과가 음수가 아니고, 실패 시 음수가 됨
    • x86에서는 메모리 로드와 sign extension이 movsx로 결합될 수 있음
  • shift 지연을 줄이기 위해 두 개의 테이블을 사용함
    • HEX0: 원래 값
    • HEX1: 값을 미리 4비트 왼쪽 shift한 테이블
  • 루프를 명확히 unroll한 decode_four_hex_digits() 구현으로 정리됨
  • 이 최적화로 러시아어 War and Peace를 JSON-encoded 형태로 파싱하는 성능이 284 MB/s에서 344 MB/s로 올라 21% 개선됨

UTF-8 인코딩 병목과 수동 생성

  • Unicode escape 디코딩 이후 병목은 UTF-8 인코딩으로 이동함
  • UTF-8은 codepoint를 길이에 따라 1~4바이트로 인코딩함
    • 1바이트: 0xxxxxxx
    • 2바이트: 110xxxxx 10xxxxxx
    • 3바이트: 1110xxxx 10xxxxxx 10xxxxxx
    • 4바이트: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
  • Rust 표준 라이브러리의 char::encode_utf8는 &mut [u8] 버퍼에 쓰므로, 버퍼가 이미 유효한 u8 값을 담고 있어야 함
    • 초기화되지 않은 버퍼에 바로 쓸 수 없음
    • UTF-8은 가변 길이 인코딩이라 LLVM이 불필요한 zeroization을 제거하기 어려움
  • serde_json은 scratch.extend_from_slice(c.encode_utf8(&mut [0u8; 4]).as_bytes()) 방식으로 처리했음
    • 로컬 [0u8; 4] 버퍼를 사용하면 이론상 alias 분석이 도움을 줄 수 있음
    • 실제로는 1~4바이트 가변 길이 복사 때문에 LLVM이 memcpy 호출을 생성함
  • memset과 memcpy 호출을 피하기 위해 UTF-8을 직접 생성함
    • 알고리듬 자체는 단순하지만 unsafe가 필요했음
    • 몇 가지 작은 변경과 함께 War and Peace 벤치마크가 344 MB/s에서 374 MB/s로 추가 +9% 개선됨

최종 결과

  • 문자열이 많은 JSON 벤치마크에서 serde_json 성능은 각각 10%, 23%, 32% 개선됨
  • 많은 JSON 데이터가 문자열을 많이 포함하므로, 이 최적화는 serde_json을 쓰는 Rust 코드 전반에 영향을 줄 수 있음
  • 개선은 오류 위치 계산, 문자열 escape 탐색, Unicode escape 디코딩, UTF-8 인코딩처럼 서로 다른 병목을 순차적으로 제거하는 방식으로 이뤄짐

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • UTF-8 트릭은 파서 혼동 공격을 너무 많이 봐서 꽤 불안함
    serde는 속도보다 정확성 때문에 쓰는 쪽이라, 잘못된 UTF-8 문자열을 잔뜩 넣어 끝까지 퍼징했기를 바람

    • 다행히 UTF-8 구조는 평균적인 파서에 비해 아주 단순함
      버그가 없다는 뜻은 아니지만, 파서의 내부 상태가 크지 않아야 하고 exhaustive test도 가능해 보임
    • 이런 영역이야말로 퍼저를 돌린 결과를 보고 싶음
    • 이 부류의 버그 중 바로 떠오르는 사례가 있으면 알려줄 수 있음?

  • serde가 이렇게 빠르게 움직이는 건 멋짐
    방금 simdutf8을 보다가, SIMD 지원 UTF-8 파싱 PR이 거의 5년째라는 걸 알게 됨
    https://github.com/rust-lang/rust/issues/68455

  • 이 사람 블로그에서 강한 jart 느낌이 나서 재미있게 읽었음
    “바퀴를 다시 발명해야 하겠지만, 생각해보면 꽤 근사하다”는 대목은 진심인지 아이러니인지 모르겠음
    읽고 작성자를 비웃으며 웃기 시작했는데, 나머지 페이지는 자기비하가 꽤 강해 보임

    • 그 말은 바퀴를 다시 발명해야 한다는 사실이 아니라, 접근 방식이 꽤 근사하다는 뜻 같음
    • jart가 무슨 뜻임?

  • “생각하는 법을 가르치는 것은 코딩을 가르치는 것만큼 중요하지만, 거의 이루어지지 않는다”라니
    상대가 생각하지 않는다고 여기는 오만함이 느껴짐

    • 그 문장에 오만함은 없다고 봄
      다른 사람들이 생각하지 않는다고 가정하는 게 아니라, 대부분의 블로그 글과 사용법 글이 최종 결과만 보여주고 거기까지 가는 단계는 꼭 보여주지 않는다는 관찰에 가까움
    • 저자는 그런 주장을 하는 게 아님
      생각하는 법을 가르친다는 건 조사해야 하고 그 단계를 건너뛸 수 없으며, 조사를 했다고 해서 스스로 결론을 내릴 책임이 사라지는 것도 아니라는 뜻임
      둘 중 하나를 건너뛰기는 쉽지만 잘못된 방식임

  • serde_json은 디버그 빌드와 릴리스 빌드를 한 번씩 하면 의존성이 3GB나 됨
    활발한 프로젝트 몇 개에서 serde를 쓰면 디스크 공간이 바닥남
    JSON 파싱에 왜 3GB 의존성이 필요한지 모르겠고, 코드 재사용은 찬성하지만 serde의 JSON 쪽 의존성은 꽤 난잡해 보임
    그 의존성 중 하나에서 익스플로잇만 나와도 Rust 생태계 절반이 취약해짐
    Rust에는 JSON이 내장돼야 함

    • 의존성은 5개뿐이고, 그중 하나는 선택 사항이며 다른 하나는 serde 자체임: https://github.com/serde-rs/json/blob/master/Cargo.toml
      indexmap = { version = "2.2.3", optional = true }
      itoa = "1.0"
      memchr = { version = "2", default-features = false }
      ryu = "1.0"
      serde = { version = "1.0.194", default-features = false }
      3GB 의존성이라고 할 때 실제로 측정한 게 그게 아닐 가능성이 큼
      증거 없이 사실처럼 말하고 있어서 확신은 못 하겠지만, 추측하자면 #[derive(Serialize, Deserialize)]를 많이 써서 코드가 대량 생성됐고, 그 뒤 target 디렉터리 전체 크기를 재고 있는 듯함
      단순 빌드는 다른 댓글들이 보여준 것처럼 수십 MB 규모로 나옴
    • Rust에 JSON을 내장하는 건 합리적인 접근이 아니라고 봄
      그건 비대화를 끌어들이는 방식일 뿐이고, 표준 라이브러리는 안정성 보장 외에는 다른 크레이트와 다르지 않아서 장점이 없음
      결국 라이브러리 릴리스 주기를 컴파일러 릴리스 주기에 묶는 효과만 생김
      실제로 예전에는 rustc-serialize가 내장에 가까웠고, Rust는 이미 그 방향을 시도한 적이 있음
      그리고 기본 상태의 serde_json은 크지 않음
      serde_json도 serde도 크지 않고, 둘 다 다른 크레이트들이 잘 지원하지 않는 매우 낮은 MSRV를 유지해서 사실상 의존성을 많이 가질 수도 없음
    • 의존성 비대화는 Rust 전반의 문제임
      어느 정도 규모 있는 Rust 프로젝트의 의존성 트리는 금방 꽤 끔찍해지고, 이 모든 의존성을 감사하는 건 현실적으로 불가능하며 상당수에 대한 신뢰도도 낮음
      몇 년간 Rust로 일해본 뒤로는, 생태계가 훨씬 성숙해지기 전까지는 Rust를 다시 만지지 않을 것 같음
      그 성숙은 대규모 기업 채택이 있어야 올 것이고, 아니면 no-std, no-deps, 순수 C 대체용 프로젝트에서나 쓸 듯함
      다만 Zig가 안정화되면 이 용도에서도 Rust를 밀어낼 수 있음
    • Rust는 디버그 정보를 비정상적으로 많이 뱉어냄
      너무 기괴하게 커서 그냥 버그일 거라고 예상함
      뭘 컴파일하든 target 폴더에 기가바이트 단위로 쌓이지만, 디버그 정보를 제거하거나 적어도 덜 자세한 설정을 쓰고 난 최종 산출물을 대표하지는 않음
    • 어느 정도 규모가 있는 프로젝트라면 target 폴더가 말 그대로 항상 최소 몇 GB는 되는 것 같음
답변달기