simdjson - Phân tích cú pháp JSON ở mức GB/giây

 (github.com)
19 điểm bởi xguru 2020-08-12 | 4 bình luận | Chia sẻ qua WhatsApp

  • Phân tích cú pháp nhanh hơn 2,5 lần so với các parser hiện có nhờ sử dụng bộ lệnh SIMD

  • Tự động chọn parser được tối ưu theo từng CPU khi chạy: Haswell (AVX2)/Westmere (SSE4.2)/ARM64/các kiến trúc 64-bit khác

  • Hỗ trợ xác thực đầy đủ JSON & UTF-8

  • Một file .h + .cpp duy nhất

  • Chỉ sử dụng 25% số lệnh so với RapidJSON, 50% so với sajson

Bài viết liên quan

4 bình luận

 
novemberoscar 2020-08-12

Có khá nhiều binding / port nhỉ

  • 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: phiên bản C# cho .NET Core (bindings và port đầy đủ).

  • 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 sử dụng assembly của Golang.

rcppsimdjson: R bindings.
 
xguru 2020-08-12

Phiên bản Rust - https://github.com/simd-lite/simd-json

Nội dung bài phát biểu của nhà phát triển tại QCon "Parsing JSON Really Quickly: Lessons Learned"

https://www.youtube.com/watch?v=wlvKAT7SZIQ
 
kunggom 2020-08-13

Bản ghi chép của video bài thuyết trình được liên kết:

https://www.infoq.com/presentations/simdjson-parser/

Tôi đọc thử vì tò mò không biết họ làm thế nào để đạt được tốc độ như vậy, và có thể nói đây đúng là kết tinh của đủ loại “hắc ma thuật”. Tóm tắt ý chính đại khái như sau.

[Phần mở đầu]

Phần lớn thư viện phân tích JSON chậm hơn tốc độ đọc tuần tự của ổ đĩa

  • Trên ổ hệ thống của tôi (diễn giả Daniel Lemire), tốc độ đọc tuần tự một tệp văn bản lớn là 2.2 GB/s, nhưng tốc độ phân tích của các thư viện JSON chủ chốt lại không theo kịp mức đó.

  • Vì hiếm có thư viện nào vượt được 1 GB/s, chúng tôi quyết định tự làm một cái.

  • Kết quả là chúng tôi đạt được tốc độ xử lý có thể tận dụng toàn bộ băng thông của ổ đĩa. Tính ra, CPU chỉ dùng 1.5 chu kỳ cho mỗi byte đầu vào. Vậy đã đạt được điều đó bằng cách nào?

[Các nguyên tắc khác nhau]

Tránh câu lệnh rẽ nhánh tối đa có thể

  • Ví dụ, với một đoạn mã đơn giản đưa số ngẫu nhiên vào mảng, chỉ cần thêm một câu if để kiểm tra số đó có lẻ hay không là đã chậm đi 5 lần. Đó là vì chi phí khi CPU dự đoán nhánh sai rất lớn.

  • Nếu loại bỏ câu if trong đoạn mã nêu trên bằng phép toán bit thì tốc độ gần như trở lại như cũ.

  • Khi chạy lặp lại cùng một đoạn mã, độ chính xác của branch prediction có thể tăng lên nên mức suy giảm hiệu năng có thể giảm bớt, nhưng rốt cuộc đây vẫn là hành vi không mang tính quyết định, nên khi branch prediction can thiệp thì hiệu năng trở nên khó dự đoán và khó đo đạc hơn.

Tích cực dùng SIMD để tận dụng word rộng hơn

  • Dùng lệnh SIMD sẽ cho phép sử dụng các thanh ghi word rộng hơn 64 bit, nhờ đó xử lý được nhiều dữ liệu hơn trong mỗi chu kỳ. (Ví dụ SSE hay NEON là 128 bit, AVX là 256 bit.) Vì vậy, chúng tôi dùng SIMD tối đa ở nơi có thể. Đây chính là bí quyết giúp chỉ tiêu tốn 1.5 chu kỳ cho mỗi byte dữ liệu đầu vào.

  • Để dùng SIMD, họ sử dụng các intrinsic function phụ thuộc vào từng bộ xử lý cụ thể. Không khuyến nghị viết trực tiếp bằng assembly.

Tránh cấp phát bộ nhớ/đối tượng

  • Trong simdjson, dữ liệu JSON được xem như một dải băng dài duy nhất và dữ liệu được tái sử dụng. Nói cách khác, không cấp phát bộ nhớ riêng cho chuỗi hay số, mà xử lý mọi thứ theo một hàng liên tục. Đây là một mẹo khá phổ biến.

Liên tục đo hiệu năng

  • Họ phát triển theo kiểu benchmark-driven. Trong CI của họ có bao gồm benchmark hiệu năng.

  • Nhân tiện, khi làm việc gì đó nặng về CPU thì cần ghi nhớ rằng tần số hoạt động của CPU sẽ liên tục thay đổi.

[Các ví dụ thực tế]

Ví dụ 1: Kiểm tra có phải UTF-8 hợp lệ hay không

  • Việc kiểm tra dữ liệu đầu vào tùy ý có phải là code point UTF-8 hợp lệ hay không thông thường là một công việc có nhiều câu lệnh rẽ nhánh.

  • Họ đã tạo ra một cách dùng SIMD để kiểm tra 32 byte dữ liệu có phải UTF-8 hợp lệ hay không trong tối đa 20 chu kỳ mà không cần rẽ nhánh.

  • Vì byte trong UTF-8 không thể có giá trị số nguyên vượt quá 244, nên chỉ cần nạp dữ liệu vào thanh ghi 256 bit bằng lệnh SIMD, trừ đi số nguyên 244 cho từng byte bằng saturation arithmetic (phép toán giới hạn phạm vi kết quả), rồi kiểm tra xem có giá trị nào khác 0 hay không.

  • Cách này nhanh hơn hơn 20 lần so với phương pháp dùng câu lệnh rẽ nhánh!

Ví dụ 2: Phân loại ký tự

  • Để phân tích JSON, cần phân loại các ký tự như dấu phẩy, dấu hai chấm, ngoặc, khoảng trắng v.v. theo từng loại.

  • Trên x86-64 và ARM NEON có lệnh tra cứu bảng kích thước 16 byte chỉ trong một lần.

  • Chia 1 byte thành 4 bit cao và 4 bit thấp, áp dụng lần lượt 2 bảng tra cứu đã chuẩn bị sẵn, rồi thực hiện phép AND trên kết quả.

  • Mã trông có vẻ khá bẩn, nhưng chỉ với 5 lệnh là có thể phân loại 16 ký tự mà không cần rẽ nhánh.

Ví dụ 3: Phát hiện ký tự escape

  • Có thể phát hiện các ký tự escape, tức các ký tự được biểu diễn bằng cách thêm dấu gạch chéo ngược (\) ở trước, mà không cần rẽ nhánh hay không? Đặc biệt còn phải xử lý cả trường hợp chính dấu gạch chéo ngược đó được escape nên xuất hiện liên tiếp nhiều cái.

  • Trong trường hợp này có một mẹo là chỉ cần nhìn vào các dấu gạch chéo ngược ở vị trí lẻ.

  • Dùng một bitmask hằng số để biểu diễn các vị trí chẵn và lẻ, rồi qua các phép toán bit phức tạp là có thể lọc ký tự escape mà không cần rẽ nhánh.

  • Sau khi loại bỏ các dấu ngoặc kép đã bị escape, thứ còn lại là các dấu ngoặc kép dùng để biểu diễn chuỗi.

  • Dùng vị trí của các dấu ngoặc kép tìm được theo dạng bitmask rồi lặp lại phép xor bit sẽ thu được bitmask biểu diễn vị trí của chuỗi. Phần này trên phần lớn bộ xử lý có thể xử lý chỉ bằng một lệnh.

  • Cũng có mẹo để đối ứng giữa tập bit và vị trí chuỗi, nhưng do thời gian có hạn nên xin bỏ qua.

Ví dụ 4: Phân tích số

  • Phân tích số là một công việc cực kỳ tốn kém. Khi benchmark việc phân tích số thực dấu chấm động bằng một hàm C được tối ưu khá tốt, tốc độ chỉ đạt 0.09 GB/s, mức tốc độ khiến người ta phát điên. Đây rõ ràng là một nút thắt cổ chai.

  • Phần lớn mã phân tích số thường xử lý theo đơn vị từng byte một. Cách đó tuyệt đối không nhanh.

  • Nếu lấy 8 ký tự, ghép chúng thành một số nguyên 64 bit rồi đưa vào một công thức đặc biệt mà diễn giả nghĩ ra vào tối muộn thứ Bảy, thì có thể biết được 8 ký tự đó có phải là 8 chữ số liên tiếp hay không. Điều này đặc biệt quan trọng vì số càng nhiều chữ số thì càng mất nhiều thời gian để phân tích.

  • Trên Stack Overflow cũng có một đoạn mã ví dụ để phân tích nhanh số nguyên 8 chữ số. Dùng SIMD thì còn có thể cải thiện thêm, nhưng điều quan trọng là rút ra ý tưởng về chiến lược xử lý thật nhiều dữ liệu trong một lần như thế này.

[Khác]

Runtime dispatch

  • Vì có nhiều mã phụ thuộc phần cứng nên sinh ra các hàm tối ưu hóa riêng cho từng bộ xử lý, và việc khiến chương trình khi chạy sẽ gọi đúng hàm phù hợp với loại bộ xử lý là một việc khá khó.

  • Có thể bạn không hiểu điều gì khó ở đây, nhưng vấn đề là phải hiện thực chuyện này bằng mã có tính di động, không phụ thuộc vào loại compiler. Một số compiler còn có bug, và ở cấp độ ngôn ngữ thì đây cũng không phải thứ được hỗ trợ sẵn.

  • Điểm này rất quan trọng vì simdjson là một thư viện mã nguồn mở dạng single header file có thể dễ dàng tích hợp vào các dự án khác.

Khác

  • Có các wrapper để dùng trong nhiều ngôn ngữ khác nhau.

  • Có bản port sang Rust, các bản port cho Go và C# cũng đang được chuẩn bị, nhưng không có bản port cho Java.

  • Nhiều công thức toán học được dùng trong dự án này do đồng tác giả Geoff Langdale cùng nghĩ ra, và họ đã công bố một bài báo liên quan trên VLDB Journal. ( https://doi.org/10.1007/s00778-019-00578-5 )
 
xguru 2020-08-13

Ồ, tôi đã đọc rất thú vị. Cảm ơn bạn!