Tăng tốc xử lý chuỗi của serde_json thêm 20%

 (purplesyringa.moe)
2 điểm bởi GN⁺ 2024-08-25 | 1 bình luận | Chia sẻ qua WhatsApp
  • serde_json, vốn được dùng như trình phân tích JSON mặc định trong hệ sinh thái Rust, đã đạt cải thiện hiệu năng 10%, 23%, 32% trên các benchmark nhiều chuỗi chỉ nhờ những tối ưu hóa nội bộ nhỏ
  • Việc tính vị trí lỗi được đổi từ quét trực tiếp phần đầu chuỗi sang dùng memchr để tìm số dòng và ký tự xuống dòng cuối cùng, giúp thu hẹp khoảng cách của đường đi lỗi vốn chậm hơn đường đi thành công hơn 2 lần
  • Vòng lặp cốt lõi của việc phân tích chuỗi không còn tìm riêng \\, \", ký tự điều khiển mà kiểm tra tất cả cùng lúc bằng SWAR, nhờ đó đạt độ trễ thấp trên chuỗi ngắn mà không cần SIMD thực sự
  • Giải mã escape \u giảm chi phí nhánh và shift bằng LUT, số nguyên có dấu và bảng shift tính sẵn, giúp tốc độ phân tích JSON War and Peace tiếng Nga tăng từ 284 MB/s lên 344 MB/s
  • Sau đó, nút thắt cổ chai chuyển sang mã hóa UTF-8 và được xử lý bằng tạo UTF-8 thủ công để tránh chi phí khởi tạo và sao chép của char::encode_utf8 cùng Vec::extend_from_slice, đưa cùng benchmark lên 374 MB/s

Vì sao tối ưu hóa serde_json lại có tác động lớn

  • serde là framework tuần tự hóa/giải tuần tự hóa tiêu biểu của Rust, còn serde_json là bộ kết hợp chính thức cho xử lý JSON và được dùng rất rộng rãi
  • Tại thời điểm bài viết được đăng, serde_json có 26.916 reverse dependency, còn simd-json có 66
  • Với mức độ sử dụng như vậy, ngay cả những cải tiến nhỏ bên trong serde_json cũng có thể tạo hiệu ứng cộng dồn trên toàn bộ hệ sinh thái Rust
  • Trong bối cảnh nhiều người dùng không dễ dàng chuyển sang parser JSON khác, tối ưu hóa ít rủi ro ngay trong thư viện hiện có là cách tiếp cận thực tế

Tính vị trí lỗi: từ vòng lặp đơn giản sang memchr

  • Trong benchmark đường đi lỗi, serde_json chậm hơn hơn 2 lần so với đường đi thành công trên cùng dữ liệu
    • Trên các bộ dữ liệu canada, citm_catalog, twitter, đường đi lỗi chậm hơn -48%~-77% so với đường đi thành công
  • Nút thắt nằm ở hàm position_of_index() chuyển chỉ số thành line/column để định dạng thông báo lỗi
    • Cách cũ duyệt self.slice[..i] theo từng byte và cập nhật line, column mỗi khi gặp \n
  • Khi tách phép tính thành hai bước, có thể áp dụng memchr
    • Đếm số \n trong self.slice[..i] để lấy số dòng theo chỉ số bắt đầu từ 0
    • Tìm vị trí \n cuối cùng rồi lấy i trừ đi để ra số cột
  • memchr cung cấp triển khai tối ưu cho việc tìm một ký tự và đếm số lần xuất hiện, bên trong có dùng SIMD
  • Sau khi PR #1160 được merge, hiệu năng đường đi lỗi cải thiện đáng kể
    • Theo chuẩn DOM của canada, đường đi lỗi tăng từ 122 MB/s lên 216 MB/s
    • Theo chuẩn struct của citm_catalog, tăng từ 195 MB/s lên 736 MB/s
    • Đường đi lỗi vẫn chậm hơn đường đi thành công, nhưng khoảng cách đã được thu hẹp

Tìm escape trong chuỗi: gom ba điều kiện trong một lần tìm

  • Vòng lặp cốt lõi cũ của phân tích chuỗi dùng bảng ESCAPE để bỏ qua các byte không cần escape
    • Trong chuỗi JSON, các đối tượng cần xử lý escape là \\, \", và các ký tự điều khiển ASCII từ 0x1F trở xuống
    • Theo đặc tả JSON, mã điều khiển không được phép xuất hiện trong chuỗi
  • Lần thử đầu tiên dùng memchr2 để tìm \\ hoặc \" trước, rồi mới kiểm tra riêng ký tự điều khiển
    • Cách này khiến chuỗi bị duyệt hai lần: một lần nhanh, một lần chậm, nên còn chậm hơn trước
    • Chỉ vector hóa một nửa đơn giản rồi để phần còn lại chạy scalar không dẫn tới cải thiện tổng thể
  • Lần thử thứ hai kết hợp memchr2 với SIMD thủ công để kiểm tra không có ký tự điều khiển
    • Trên chuỗi ngắn, chi phí gọi hàm chọn thực thi lúc chạy trở thành gánh nặng
    • Trên chuỗi dài, vấn đề phải đọc bộ nhớ hai lần vẫn còn
  • Triển khai cuối cùng được chốt theo hướng tìm \\, \" và ký tự điều khiển trong một lượt duy nhất

Dùng SWAR để đạt xử lý gần SIMD

  • Để không phải viết mã SIMD riêng cho từng nền tảng, tác giả dùng kỹ thuật SWAR (SIMD Within A Register)
    • Thay vì SIMD 128-bit, nó xử lý một word 64-bit như 8 byte song song
    • Dùng phép toán bit để kiểm tra đồng thời từng byte có thỏa điều kiện hay không
  • Việc kiểm tra ký tự điều khiển chuyển điều kiện c >= 0 && c < 0x20 sang dạng phép toán bit
    • Với cụm 8 byte, dùng mask dạng !c & (c - 0x2020202020202020) & 0x8080808080808080
    • Dù borrow của phép trừ 64-bit có thể lan sang byte cao hơn, điều đó không gây vấn đề cho mục tiêu tìm ký tự điều khiển ở vị trí thấp nhất
  • \\ và \" cũng được kiểm tra theo cách tương tự rồi gộp vào một biểu thức
    • Toàn bộ biểu thức gồm 9 phép toán bit
    • Nếu dùng SIMD trên x86 thì cần 7 phép toán, nên throughput thấp hơn, nhưng với chuỗi ngắn thì độ trễ quan trọng hơn
  • Trong json-benchmark, mã SWAR này còn hiệu quả hơn cả mã SIMD thực sự
  • Với chuỗi quá ngắn, SWAR có thể còn chậm hơn mã scalar
    • Có hiện tượng hồi quy ở chuỗi dài khoảng 5 ký tự
    • Để bảo vệ các mẫu phổ biến như chuỗi rỗng "" và escape liên tiếp \r\n, \uD801\uDC37, trước khi vào vòng lặp SWAR sẽ kiểm tra xem ký tự đầu tiên có phải escape hay không
  • Kết quả tối ưu hóa việc dò chuỗi khác nhau tùy bộ dữ liệu
    • twitter struct tăng từ 638 MB/s lên 785 MB/s, tương đương +23%
    • twitter DOM tăng từ 305 MB/s lên 335 MB/s, tương đương +10%
    • citm_catalog struct tăng từ 865 MB/s lên 905 MB/s, tương đương +5%
    • Chuỗi rỗng vẫn chậm hơn dưới 2% trong một số microbenchmark cụ thể

Tối ưu hóa giải mã Unicode escape

  • serde_json xử lý cả chuỗi Unicode thô lẫn escape \u
    • Ví dụ: "🥺" và "\ud83e\udd7a"
  • Cách giải mã hex cũ dùng LUT 256 phần tử để ánh xạ mỗi ký tự sang giá trị từ 0 đến 15
    • Xử lý '0'..='9', 'A'..='F', 'a'..='f'
    • Ký tự không hợp lệ được đánh dấu bằng giá trị sentinel
  • Vì escape \u đọc 4 chữ số hex, cách cũ phải thực hiện shift, cộng, so sánh và nhánh điều kiện trong mỗi vòng lặp
  • Bản cải tiến không trả lỗi ở từng vòng lặp nữa mà xử lý đủ cả 4 ký tự rồi mới kiểm tra tính hợp lệ
  • Triển khai cuối cùng dùng LUT [i8; 256] với chữ số không hợp lệ là -1, và tính toán bằng số nguyên 32-bit
    • Khi thành công, kết quả không âm; khi thất bại, kết quả sẽ âm
    • Trên x86, tải bộ nhớ và sign extension có thể được gộp thành movsx
  • Để giảm độ trễ của shift, tác giả dùng hai bảng
    • HEX0: giá trị gốc
    • HEX1: bảng đã được shift trái sẵn 4 bit
  • Mã được sắp lại thành triển khai decode_four_hex_digits() unroll rõ ràng
  • Nhờ tối ưu này, hiệu năng phân tích War and Peace tiếng Nga ở dạng JSON-encoded tăng từ 284 MB/s lên 344 MB/s, tức cải thiện 21%

Nút thắt mã hóa UTF-8 và cách tạo thủ công

  • Sau khi tối ưu giải mã Unicode escape, nút thắt cổ chai chuyển sang mã hóa UTF-8
  • UTF-8 mã hóa codepoint thành 1 đến 4 byte tùy độ dài
    • 1 byte: 0xxxxxxx
    • 2 byte: 110xxxxx 10xxxxxx
    • 3 byte: 1110xxxx 10xxxxxx 10xxxxxx
    • 4 byte: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
  • char::encode_utf8 trong thư viện chuẩn Rust ghi vào bộ đệm &mut [u8], nên bộ đệm phải sẵn chứa các giá trị u8 hợp lệ
    • Không thể ghi trực tiếp vào bộ đệm chưa được khởi tạo
    • Vì UTF-8 là mã hóa có độ dài biến thiên, LLVM khó loại bỏ phần zeroization không cần thiết
  • serde_json trước đó xử lý theo kiểu scratch.extend_from_slice(c.encode_utf8(&mut [0u8; 4]).as_bytes())
    • Việc dùng bộ đệm cục bộ [0u8; 4] về lý thuyết có thể giúp alias analysis
    • Nhưng trên thực tế, do phải sao chép số byte biến thiên từ 1 đến 4, LLVM sinh ra lời gọi memcpy
  • Để tránh các lời gọi memset và memcpy, tác giả tạo UTF-8 trực tiếp
    • Bản thân thuật toán khá đơn giản, nhưng cần dùng unsafe
    • Cùng với vài thay đổi nhỏ khác, benchmark War and Peace tăng thêm từ 344 MB/s lên 374 MB/s, tức thêm +9%

Kết quả cuối cùng

  • Trên các benchmark JSON nhiều chuỗi, hiệu năng của serde_json lần lượt được cải thiện 10%, 23%, 32%
  • Vì nhiều dữ liệu JSON chứa rất nhiều chuỗi, các tối ưu này có thể ảnh hưởng đến diện rộng mã Rust đang dùng serde_json
  • Các cải thiện đạt được bằng cách loại bỏ tuần tự những nút thắt khác nhau như tính vị trí lỗi, dò escape trong chuỗi, giải mã Unicode escape và mã hóa UTF-8

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-08-25
Ý kiến trên Hacker News

  • Mẹo UTF-8 khiến tôi khá bất an vì đã thấy quá nhiều kiểu tấn công làm parser nhầm lẫn
    người ta dùng serde vì độ chính xác hơn là tốc độ, nên mong là họ đã fuzz đến cùng với hàng đống chuỗi UTF-8 lỗi

    • May là cấu trúc UTF-8 rất đơn giản so với parser trung bình
      không có nghĩa là không thể có bug, nhưng trạng thái nội bộ của parser hẳn không nên quá lớn, và có vẻ cũng có thể kiểm thử exhaustive
    • Đây đúng là kiểu chỗ mà tôi muốn xem kết quả chạy fuzzer
    • Có ai nhớ ngay được ví dụ nào thuộc nhóm bug này không?

  • Thật ấn tượng khi serde di chuyển nhanh đến vậy
    Tôi vừa xem simdutf8 và mới biết PR về phân tích UTF-8 có hỗ trợ SIMD đã gần 5 năm rồi
    https://github.com/rust-lang/rust/issues/68455

  • Blog của người này đọc lên thấy rất có vibe jart, nên khá thú vị
    Đoạn “chắc là phải phát minh lại bánh xe, nhưng nghĩ kỹ thì cũng khá ngầu” tôi không rõ là nghiêm túc hay mỉa mai
    Tôi bắt đầu cười nhạo tác giả sau khi đọc câu đó, nhưng phần còn lại của trang lại có vẻ tự giễu khá mạnh

    • Tôi nghĩ ý đó không phải là việc phải phát minh lại bánh xe, mà là cách tiếp cận khá ngầu
    • jart nghĩa là gì?

  • Câu “Dạy cách tư duy cũng quan trọng như dạy code, nhưng hầu như không xảy ra” ư
    Nghe có vẻ kiêu ngạo, như thể cho rằng đối phương không biết nghĩ

    • Tôi không thấy câu đó có gì là kiêu ngạo
      nó không giả định rằng người khác không biết nghĩ, mà gần hơn với nhận xét rằng phần lớn bài blog và bài hướng dẫn chỉ cho thấy kết quả cuối cùng chứ không nhất thiết cho thấy các bước để đi tới đó
    • Tác giả không hề đưa ra kiểu khẳng định đó
      dạy cách tư duy nghĩa là phải điều tra và không thể bỏ qua các bước ấy, còn việc đã điều tra cũng không làm biến mất trách nhiệm tự rút ra kết luận của mỗi người
      bỏ qua một trong hai thì dễ, nhưng là cách làm sai

  • serde_json mà build debug một lần và release một lần thì phần phụ thuộc lên tới 3GB
    Chỉ cần dùng serde trong vài dự án đang hoạt động là hết sạch dung lượng đĩa
    Tôi không hiểu vì sao parse JSON lại cần tới 3GB phụ thuộc, và dù tôi ủng hộ tái sử dụng mã, phần phụ thuộc phía JSON của serde trông khá lộn xộn
    Chỉ cần một phụ thuộc trong số đó có exploit là nửa hệ sinh thái Rust sẽ dính lỗ hổng
    Rust nên có JSON tích hợp sẵn

    • Chỉ có 5 phụ thuộc, một trong số đó là tùy chọn và một cái khác là chính 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 }
      Khi nói 3GB phụ thuộc thì có lẽ thứ được đo thực ra không phải vậy
      tôi không chắc vì họ nói như thể đó là sự thật mà không có bằng chứng, nhưng nếu đoán thì có lẽ họ dùng #[derive(Serialize, Deserialize)] rất nhiều nên sinh ra lượng lớn mã, rồi sau đó đo luôn toàn bộ thư mục target
      build đơn giản thì như các bình luận khác đã chỉ ra, chỉ ở mức vài chục MB
    • Tôi không nghĩ tích hợp JSON vào Rust là cách tiếp cận hợp lý
      đó chỉ là một cách kéo theo phình to, và thư viện chuẩn ngoài cam kết ổn định ra thì không khác các crate khác nên không có lợi thế gì
      cuối cùng chỉ tạo ra hiệu ứng buộc chu kỳ phát hành thư viện phải gắn với chu kỳ phát hành compiler
      thực tế trước đây rustc-serialize từng gần như là đồ tích hợp sẵn, nên Rust đã thử hướng đó rồi
      và bản serde_json mặc định thì không lớn
      cả serde_json lẫn serde đều không lớn, và cả hai còn giữ MSRV rất thấp mà các crate khác thường không hỗ trợ tốt, nên trên thực tế cũng không thể có quá nhiều phụ thuộc
    • Phình to phụ thuộc là vấn đề chung của Rust
      cây phụ thuộc của một dự án Rust có chút quy mô sẽ nhanh chóng trở nên khá kinh khủng, việc audit toàn bộ chúng là không thực tế, và mức độ tin tưởng dành cho khá nhiều cái cũng thấp
      sau vài năm làm việc với Rust, tôi có lẽ sẽ không đụng lại nó cho đến khi hệ sinh thái trưởng thành hơn nhiều
      sự trưởng thành đó có lẽ phải đến từ việc được các doanh nghiệp lớn chấp nhận rộng rãi, nếu không thì tôi chỉ dùng nó cho các dự án no-std, no-deps, hoặc để thay thế C thuần
      dù vậy, nếu Zig ổn định thì có thể nó sẽ đẩy Rust ra cả ở mảng này
    • Rust tạo ra thông tin debug nhiều một cách bất thường
      nó to kỳ quặc đến mức tôi đoán đơn giản là lỗi
      compile gì đi nữa thì thư mục target cũng chất lên hàng GB, nhưng điều đó không đại diện cho sản phẩm cuối cùng sau khi đã bỏ thông tin debug hoặc ít nhất dùng cấu hình bớt chi tiết hơn
    • Với các dự án có chút quy mô thì thư mục target dường như lúc nào cũng tối thiểu vài GB theo đúng nghĩa đen