Giới thiệu về cuộc thi 1BRC
- Trong cuộc thi 1BRC, đã có dự đoán rằng sau khi xử lý "những nghi phạm thông thường", việc phân tích nhiệt độ từ tệp CSV sẽ trở thành nút thắt cổ chai.
- Nhiệt độ có thể xuất hiện ở bốn dạng:
-XX.X, -X.X, X.X, XX.X, và ban đầu người ta dùng lệnh gọi thư viện Double.parseDouble().
- Tuy nhiên, các giải pháp tùy biến nhanh chóng xuất hiện, và một trong số đó trông như một phương pháp tối ưu chỉ với hai nhánh mà không cần vòng lặp.
- Sau đó, giải pháp do Quân Anh Mai (@merykitty) đưa ra đã khiến hashtag #1BRC trên Twitter bùng nổ. Giải pháp này không dùng câu lệnh
if và chỉ thực hiện một lần đọc tệp duy nhất.
Phân tích SWAR kỳ diệu của merykitty
- Mã của merykitty chỉ gồm 18 phép toán ALU và có một lời gọi hàm mức thấp duy nhất là
numberOfTrailingZeros().
- Số
long đầu vào chứa 8 byte từ CSV, và đầu ra là nhiệt độ ở dạng số nguyên (gấp 10 lần nhiệt độ thực tế).
- Kỹ thuật này được gọi là "SIMD Within A Register" (SWAR), sử dụng các thanh ghi và lệnh CPU tiêu chuẩn.
- Mã thực hiện các bước như phát hiện số có âm hay không, loại bỏ ký tự dấu, tìm vị trí dấu thập phân, căn chỉnh nội dung theo mẫu, chuyển ký tự ASCII thành giá trị số, nhân từng chữ số với trọng số rồi cộng lại, sau đó áp dụng dấu.
- Tất cả các bước này đều được thực hiện chỉ bằng các phép toán ALU.
Kết luận
- Việc merykitty một mình có thể làm ra tất cả điều này chỉ trong vài ngày là một bí ẩn thực sự mà một bài blog không thể giải thích hết.
- QuestDB là mã nguồn mở và cung cấp khả năng chèn dữ liệu nhanh cùng phân tích SQL theo giấy phép Apache 2.0.
Ý kiến của GN⁺
- Bài viết này cho thấy sự phức tạp và sáng tạo của kỹ thuật SWAR được thiết kế để giải quyết một bài toán tưởng như đơn giản là phân tích nhiệt độ. Điều này nhấn mạnh sức mạnh của các phép toán bit và tầm quan trọng của tối ưu hóa trong lập trình.
- Cách tiếp cận này có thể là một ví dụ thú vị, đặc biệt với các kỹ sư phần mềm mới vào nghề quan tâm đến lập trình hệ thống hoặc phát triển ứng dụng nhạy cảm về hiệu năng.
- Để nâng cao hiểu biết về phép toán bit và tối ưu hóa, sẽ hữu ích nếu tìm các cuộc thi lập trình trực tuyến hoặc hướng dẫn liên quan đến những chủ đề hay bài toán tương tự.
- Cần nghiên cứu thêm về cách kỹ thuật này có thể được áp dụng trong môi trường công nghiệp thực tế, cũng như liệu có cơ sở dữ liệu hoặc hệ thống nào khác sử dụng các kỹ thuật tối ưu hóa tương tự hay không.
- Khi đưa vào sử dụng các hệ thống như QuestDB, cần cân nhắc không chỉ cải thiện hiệu năng mà còn các yếu tố khác như khả năng bảo trì, độ dễ đọc của mã và hỗ trợ kỹ thuật dài hạn.
1 bình luận
Ý kiến trên Hacker News
Tóm tắt các bình luận trên Hacker News liên quan đến bài báo simdjson:
Diễn giải về ngữ cảnh của đoạn mã: Lời giải được đưa ra rất xuất sắc, nhưng cần giả định rằng dữ liệu được định dạng tốt. Khả năng kiểm tra lỗi và phục hồi hiệu quả mang lại giá trị lớn trong các parser giàu kinh nghiệm.
Kỹ thuật phân tích số: Việc nhân từng bitfield của số với các lũy thừa tương ứng của 10 rồi dùng MUL để shift/cộng là một kỹ thuật đã được biết đến. Tham khảo blog của Lemire.
Giải thích về SWAR (SIMD Within A Register): Có nhiều ví dụ triển khai các routine SWAR hiệu quả trong Java/Scala bằng cách dùng var handle cho byte array view.
Định nghĩa ngắn gọn về SWAR: "SIMD Within A Register" là thực hiện các phép toán SIMD bên trong một thanh ghi.
Câu hỏi về nút thắt I/O của BRC (Branchless Ray Casting): Không hiểu vì sao CPU lại là nút thắt cổ chai.
Kinh nghiệm dùng SWAR trên 68000: Có thể xử lý song song 4 byte cùng lúc, nhưng việc xử lý tràn khá khó. Rất thích bài viết này.
Không gian trạng thái và superoptimizer: Đặt câu hỏi liệu có superoptimizer nào tạo ra kết quả tương tự hay không, vì không gian trạng thái nhỏ.
Lệnh AVX và hỗ trợ SIMD của Java: Thuật toán này có thể chạy song song gấp 32 lần bằng lệnh AVX, nhưng thật tiếc là Java không hỗ trợ tốt việc sử dụng CPU SIMD ngoài một số trường hợp nhất định.
Hiểu biết về thao tác bit: Bài viết này đã giúp hiểu rõ thao tác bit hơn bất kỳ bài nào trước đó, và cảm ơn tác giả đã đưa ra lời giải Java cho thử thách 1BRC.