Hàm `tolower()` sử dụng AVX-512

 (dotat.at)
1 điểm bởi GN⁺ 2024-07-30 | 1 bình luận | Chia sẻ qua WhatsApp

  • Vài năm trước, tác giả đã viết về cách tăng tốc tolower() bằng mẹo SWAR. Vài ngày trước, khi đọc bài của Olivier Giniaux, tác giả thấy hứng thú với cách tối ưu xử lý chuỗi ngắn bằng lệnh SIMD. Cách này được dùng trong một hàm băm nhanh viết bằng Rust.

  • Lệnh SIMD có thể xử lý chuỗi ngắn rất dễ dàng, nhưng việc truyền dữ liệu giữa bộ nhớ và thanh ghi vector luôn là điểm gây khó chịu. Bài viết của Olivier đã đưa ra một cách thú vị để giải quyết vấn đề này.

Dấu hiệu đáng hy vọng

  • Một số tập lệnh SIMD cung cấp các tính năng load và store có mặt nạ rất hữu ích cho xử lý chuỗi. Chúng hoạt động ở mức byte.

    • ARM SVE: có trên các lõi ARM Neoverse lớn gần đây, chẳng hạn Amazon Graviton. Tuy nhiên không có trên Apple Silicon.
    • AVX-512-BW: có trên các bộ xử lý AMD Zen gần đây. AVX-512 là một tập mở rộng phức tạp, và mức hỗ trợ trên Intel khá ngẫu nhiên.

  • Vì có một máy dùng AMD Zen 4, tác giả quyết định thử AVX-512-BW.

tolower64()

  • Tác giả dùng hướng dẫn intrinsics của Intel để viết một hàm tolower() cơ bản có thể xử lý 64 byte cùng lúc.
    • Dùng * làm wildcard để tìm mm512*epi8, qua đó tìm các hàm AVX-512 xử lý theo byte.
    • Điền vài thanh ghi bằng 64 byte hữu ích.
    • Thiết lập các giá trị cần thiết để chuyển chữ in hoa thành chữ thường.
    • So sánh ký tự đầu vào với A và Z để kiểm tra xem có phải chữ in hoa hay không.
    • Dùng mặt nạ để chuyển thành chữ thường nếu là chữ in hoa.

Load và store hàng loạt

  • Cần bọc kernel tolower64() trong một hàm tiện dụng hơn, ví dụ một hàm vừa sao chép chuỗi vừa chuyển thành chữ thường.
    • Với chuỗi dài, dùng lệnh vector load và store không căn chỉnh.

Load và store có mặt nạ

  • Với chuỗi nhỏ và phần cuối của chuỗi dài, dùng load và store không căn chỉnh có mặt nạ.
    • Mặt nạ sẽ bật len bit đầu tiên.
    • Load và store tương tự phiên bản toàn độ rộng nhưng có thêm mặt nạ.

Benchmark

  • Tác giả benchmark hiệu năng của nhiều hàm tương tự.

    • Biên dịch bằng Clang 16 và chạy trên AMD Ryzen 9 7950X.
    • Mỗi hàm được biên dịch riêng để tránh nhiễu từ inline và di chuyển mã.

  • Kết quả:

    • tolower64 là nhanh nhất trong tất cả các hàm được thử nghiệm.
    • copybytes64 cũng dùng AVX-512 theo cách tương tự tolower64, nhưng không nhanh hơn đáng kể.
    • copybytes1 thực hiện memcpy theo từng byte, cho thấy khả năng tự động vector hóa của Clang 11 tương đối kém.
    • tolower() chuẩn là chậm nhất.
    • tolower1 là phiên bản tolower() theo từng byte được biên dịch bằng Clang 16; tự động vector hóa đã được cải thiện nhưng vẫn chậm.
    • tolower8 là tolower() SWAR từng được giới thiệu trong bài blog trước; Clang cố tự động vector hóa nhưng kết quả không tốt.
    • memcpy ban đầu nhanh nhưng sau đó giảm xuống còn một nửa tốc độ của copybytes64.

Kết luận

  • AVX-512-BW đặc biệt hữu ích khi xử lý chuỗi ngắn.

  • Nó rất nhanh trên Zen 4, và các hàm nội tại cũng dễ sử dụng.

  • Hiệu năng của AVX-512-BW rất mượt.

  • Tác giả không có máy hỗ trợ ARM SVE để khảo sát chi tiết, nhưng rất tò mò SVE hoạt động tốt đến mức nào với chuỗi ngắn.

  • Tác giả hy vọng các mở rộng tập lệnh như vậy sẽ được dùng rộng rãi hơn. Chúng sẽ cải thiện đáng kể hiệu năng xử lý chuỗi.

  • Có thể xem mã của bài blog này trên website của tác giả.

Tóm tắt của GN⁺

  • Bài viết giải thích cách xử lý chuỗi ngắn hiệu quả bằng lệnh SIMD.
  • Bài viết cho thấy các tập lệnh AVX-512-BW và ARM SVE hữu ích cho xử lý chuỗi.
  • Kết quả benchmark cho thấy AVX-512-BW đạt hiệu năng nổi bật, đặc biệt với chuỗi ngắn.
  • Bài viết sẽ hữu ích cho các lập trình viên quan tâm đến tối ưu hiệu năng.

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-07-30
Ý kiến trên Hacker News

  • Trong mô hình bộ nhớ của Rust và LLVM, mẹo "unsafe read beyond of death" được xem là hành vi không xác định

    • Trình biên dịch có thể giả định rằng hành vi như vậy không xảy ra để phục vụ tối ưu hóa
    • Để tránh điều này, cần dùng inline assembly

  • Có sự tò mò về cách triển khai AVX512 của AMD và cuộc cạnh tranh với AVX10 của Intel

    • AVX10 là để giải quyết vấn đề P core và E core của Intel
    • AMD tùy tình huống mà dùng full width của Zen5 hoặc 256-bit double pump trên Zen4 và Zen5 mobile
    • Mức tăng hiệu năng lớn đạt được trên các nhân Zen4

  • Tối ưu hóa SWAR chỉ hữu ích với chuỗi được căn chỉnh theo địa chỉ 8 byte

    • Nếu áp dụng cho chuỗi không căn chỉnh thì còn chậm hơn thuật toán gốc
    • Nếu chia thuật toán thành ba phần thì sẽ cần nhiều lệnh hơn

  • Việc thêm mask trông khá gọn gàng

    • Ước gì trong các intrinsic của .NET có cách thao tác trực tiếp với thanh ghi mask của AVX512

  • Dùng Clang có thể cho kết quả tốt hơn

    • Nó đưa ra lựa chọn lệnh tốt hơn và kết quả được tối ưu hóa tốt hơn

  • Vòng lặp lõi cho chuỗi ngắn có ít hơn một lệnh

    • Xử lý nhanh chuỗi ngắn là điều quan trọng

  • Có người đã viết một cách triển khai tương tự bằng C# để chuyển chữ hoa/chữ thường từ ASCII sang UTF-8

    • Vì chuỗi ngắn chiếm phần lớn trong đa số codebase, nên xử lý nhanh chúng là rất quan trọng

  • Có một ví dụ dùng SIMD với AVX512 để biến đổi văn bản thành uwu

  • Sẽ còn ấn tượng hơn nếu tính đến việc chuyển đổi ký tự Unicode

    • Đa số lập trình viên chỉ quan tâm đến ASCII, nhưng ngoài bộ ký tự tiêu chuẩn vẫn còn cả một thế giới rộng lớn

  • Trước đây từng có kinh nghiệm thêm viền đen quanh ảnh để tránh các vấn đề SIMD của buffer

    • Không phải lúc nào cũng có thể kiểm soát hoàn toàn dữ liệu đầu vào