Thuật toán tìm kiếm chuỗi con phù hợp với SIMD (2018)

• Các API như strstr, std::string::find giả định tìm kiếm chuỗi con một lần, nhưng trên CPU hiện đại chi phí so sánh chuỗi ngắn và vector thấp nên cách làm dùng SIMD có thể có lợi hơn
• Ý tưởng cốt lõi là thay điều kiện băm yếu của Karp-Rabin bằng một vị từ vector, rồi chỉ thực hiện so sánh chuỗi con chính xác tại các vị trí ứng viên
• Thuật toán SIMD tổng quát giảm số ứng viên bằng cách so sánh song song ký tự đầu và ký tự cuối của needle, rồi chỉ xác minh các vị trí có khả năng khớp bằng memcmp
• Bài viết cũng so sánh cách dùng SSE4.1 MPSADBW và SSE4.2 PCMPESTRM, nhưng kết quả đo cho thấy SIMD tổng quát nhanh hơn một cách ổn định hơn, còn PCMPESTRM lại chậm hơn cả MPSADBW
• SIMD tổng quát nhanh hơn C strstr trên mọi nền tảng, nhưng không an toàn vì có thể đọc ra ngoài chuỗi đầu vào, đồng thời cũng không hoàn toàn cùng điều kiện so sánh vì nhận trước thông tin độ dài

---

Giả định chi phí đã thay đổi trong tìm kiếm chuỗi

• Các API như strstr của C, std::string::find của C++, hay pos, index của chuỗi Python đều được thiết kế cho tìm kiếm một lần trong một chuỗi cho trước
• Các thuật toán truyền thống chủ yếu chia làm hai nhóm
  • Cách làm dựa trên ô tô mát hữu hạn tất định như Knuth-Morris-Pratt, Boyer Moore
  • Cách làm dựa trên so sánh đơn giản như Karp-Rabin
• Các thuật toán chuẩn giả định rằng so sánh một cặp ký tự, tra bảng phụ trợ, và rẽ nhánh điều kiện là rẻ, còn so sánh hai chuỗi con là đắt
• Trên CPU desktop hiện đại, giả định này có thể không còn đúng
  • Trên CPU 64-bit, chi phí so sánh 1, 2, 4, hay 8 byte là như nhau
  • Nếu hỗ trợ lệnh SIMD, so sánh vector 16, 32, 64 byte cũng có thể rẻ ngang so sánh một byte đơn lẻ
  • Tra bảng tốn chi phí truy cập bộ nhớ cỡ một vòng L1 cache, và việc đọc theo từng ký tự cũng có chi phí tương tự
  • Một lần dự đoán nhánh sai có thể gây ra hình phạt khoảng 10~20 chu kỳ
  • Chuỗi phụ thuộc ngắn gồm đọc ký tự, so sánh, rồi rẽ nhánh điều kiện khiến CPU khó tận dụng thực thi out-of-order

Cách tiếp cận: dùng vị từ vector thay cho băm yếu

• Karp-Rabin chỉ thực hiện so sánh chính xác khi băm yếu của chuỗi con cần tìm trùng với băm của đoạn chuỗi hiện tại
• Cách làm với SIMD thay điều kiện băm này bằng một vị từ vector
  • Vị từ được tính song song
  • Chỉ với các vị trí có giá trị đúng trong vector vị từ mới thực hiện so sánh chuỗi con chính xác
• Chuyên biệt hóa theo độ dài cũng được dùng để cải thiện hiệu năng
  • Bản cài đặt tổng quát gọi các hàm như memcmp để so sánh chuỗi con
  • Nếu biết trước độ dài chuỗi con cần tìm, lời gọi hàm có thể được thay bằng vài lệnh CPU, đôi khi chỉ một lệnh, dành riêng cho độ dài đó
  • Cách này giảm chi phí gọi hàm và cả chi phí nội bộ của memcmp

Thuật toán 1: SIMD tổng quát

• Thuật toán SIMD tổng quát có thể áp dụng cho nhiều tập lệnh SIMD và cả cách làm SWAR
• Vị từ cơ bản là kiểm tra xem ký tự đầu và ký tự cuối của needle có cùng khớp hay không
  • Nạp ký tự đầu vào thanh ghi F
  • Nạp ký tự cuối vào thanh ghi L
  • Ở mỗi vòng lặp, đọc chunk A của haystack tại offset hiện tại i, và đọc chunk B tại i + k - 1
  • Tính F == A và B == L, rồi kết hợp hai kết quả để tạo mask vị trí ứng viên
  • Chỉ tại các vị trí có giá trị đúng trong mask mới thực hiện so sánh chuỗi con chính xác
• Trong ví dụ tìm "cat" trong "a_cat_tries", chỉ có vị trí chỉ số 2 là nơi ký tự đầu c và ký tự cuối t cùng khớp, nên chỉ cần một lần so sánh chính xác
• Tuy nhiên, việc chọn ký tự đầu và ký tự cuối không phải lúc nào cũng tốt nhất
  • Nếu chuỗi đầu vào phần lớn là 'A' và needle là "AjohndoeA", số vị trí ứng viên có thể tăng mạnh
  • Bản cài đặt có thể chọn ký tự xa nhất khác ký tự đầu thay cho ký tự cuối
  • Nếu mọi ký tự trong needle đều giống nhau, có thể dùng thủ tục đặc biệt cho mẫu như "AAAAA"

Khác biệt giữa các bản cài đặt

• Các bản SSE và AVX2 gần như giống hệt nhau về cấu trúc và dùng số lệnh tối thiểu
  • Vì đã biết ký tự đầu và ký tự cuối khớp, memcmp không cần so sánh lại các ký tự đó
• Cách làm SWAR tận dụng việc kết quả XOR bằng 0 nghĩa là các byte bằng nhau
  • Thay vì AND các kết quả trung gian như SSE/AVX2, nó dùng OR
  • Quá trình tìm vị trí byte 0 đòi hỏi nhiều thao tác hơn
  • Bản cài đặt C++ cho vector 64-bit tính ra mask byte chính xác
• AVX512F không có phép toán trên byte và phần tử vector nhỏ nhất là word 32-bit, nên cần dùng kỹ thuật SWAR
  • Tính hai phép XOR và một phép OR bằng lệnh AVX512F
  • Tìm các phần tử 32-bit có chứa byte 0
  • Với mỗi phần tử 32-bit như vậy, kiểm tra 4 chuỗi con ứng viên
• Bản cài đặt ARM Neon 32-bit dùng thanh ghi SIMD 128-bit
  • Nút thắt là độ trễ lớn khi quay từ Neon unit về CPU
  • Kết quả so sánh được ghi ra bộ nhớ dưới dạng word 64-bit để xử lý
  • Nếu unroll hai vòng lặp trong vòng lặp trong cùng thì nhanh hơn khoảng 1.2 lần
• Bản cài đặt AArch64 gần như giống hệt quy trình của ARM Neon, nhưng việc đọc trực tiếp lane trong thanh ghi SIMD nhanh hơn

Thuật toán 2: SSE4.1 MPSADBW

• MPSADBW trong SSE4.1 và AVX2 tính khoảng cách Manhattan giữa một subvector 4 byte trong một thanh ghi và 8 subvectors 4 byte liên tiếp trong thanh ghi kia
• Nếu hai subvector bằng nhau thì khoảng cách L1 bằng 0, nên có thể dùng điều này để tìm vị trí ứng viên
  • Cách này dùng điều kiện 4 ký tự đầu giống nhau làm vị từ
• So sánh 4 ký tự đầu nghe có vẻ mạnh hơn so với so sánh ký tự đầu và cuối, nhưng trong trường hợp xấu nhất vẫn không tránh được độ phức tạp bậc hai
  • Nếu haystack toàn là "a" và needle là "aaaabcde", vị từ sẽ đúng ở mọi ký tự đầu vào
• Cách dùng MPSADBW có một số ràng buộc
  • Về cơ bản không phù hợp với chuỗi con có độ dài dưới 4
  • Có thể xử lý độ dài 3 nhưng cần thêm mã bổ sung
  • MPSADBW của SSE mỗi lần chỉ xử lý được 8 byte
  • MPSADBW của AVX2 hoạt động theo từng lane 128-bit chứ không trên toàn bộ 256-bit, nên cần thêm mã nạp dữ liệu
  • Độ trễ lệnh khá cao, 5~7 chu kỳ tùy CPU, nhưng throughput là 1~2 chu kỳ nên có thể che giấu độ trễ bằng unroll vòng lặp
• AVX512F không có MPSADBW, nhưng do hỗ trợ tự nhiên phần tử 32-bit nên có thể mô phỏng vị từ so khớp tiền tố 4 byte
  • Mỗi vòng lặp tạo ra 4 vector AVX512 chứa các tiền tố 4 byte khả dĩ
  • Việc dựng từng vector cần 2 phép shift và 1 phép OR
  • Vòng lặp so sánh trở nên phức tạp hơn, và để điền phần tử cuối cần thêm 4 byte vượt ra ngoài vector

Thuật toán 3: SSE4.2 PCMPESTRM

• SSE4.2 đưa vào tập lệnh STNI với mục tiêu làm khối xây dựng cho các phép toán chuỗi
• Intel về sau gần như bỏ dở STNI trên các bộ xử lý mới, không đưa ra bản AVX2, và các lệnh này rất chậm
  • Độ trễ 11 chu kỳ bị đánh giá là khó chấp nhận
• Các lệnh PCMPxSTRx có bốn biến thể tùy theo cách xác định độ dài chuỗi và cách lưu kết quả
  • Độ dài có thể được truyền tường minh, hoặc xác định theo byte 0 đầu tiên như chuỗi C truyền thống
  • Kết quả có thể được lưu dưới dạng mask bit/byte hoặc số thứ tự bit được đặt đầu tiên/cuối cùng trong mask
• Ở đây dùng chế độ so sánh range ordered
  • Trái với tên gọi, khi chuỗi con hoặc dữ liệu vượt quá bề rộng thanh ghi, nó sẽ tìm prefix tương ứng
  • Trong ví dụ tìm "ABCD" trong "ABCD_ABC_ABCD_AB", hậu tố "AB" cũng có thể bị coi là khớp
  • Vì vậy điều duy nhất có thể giả định an toàn là ký tự đầu khớp, còn lại phải xác minh bằng memcmp

Môi trường đo hiệu năng

• Hiệu năng của nhiều bản cài đặt SIMD đã được đo, bao gồm cả chuyên biệt hóa runtime cho chuỗi con ngắn
• C strstr được đưa vào làm đối tượng so sánh, nhưng do lỗi hiệu năng của std::string::find trong GNU libc nên nó bị loại khỏi bảng x64
• Mỗi chương trình thử nghiệm được chạy ba lần
• Môi trường thử nghiệm x64
  • Westmere i5 M540, GCC 6.2.0
  • Bulldozer FX-8150, GCC 4.8.4
  • Haswell i7 4470, GCC 5.4.1
  • Skylake i7 6700, GCC 5.4.1
  • Knights Landing 7210, GCC 5.3.0
• Môi trường thử nghiệm ARM
  • ARMv7 Raspberry Pi 3, mã 32-bit, GCC 4.9.2
  • ARMv8 ARM Cortex A57 / AMD Opteron A1100, mã 64-bit, Clang 3.8.0

Kết quả x64

• Bản cài đặt SIMD tổng quát cho mức tăng tốc lớn nhất so với strstr trên x64
  • Trên Westmere, SSE2 generic đạt 0.74589 giây, còn strstr là 0.82246 giây
  • Trên Haswell, AVX2 generic đạt 0.38653 giây, còn strstr là 0.52786 giây
  • Trên Skylake, AVX2 generic đạt 0.36309 giây, còn strstr là 0.66148 giây
  • Trên KNL, AVX512F generic đạt 1.14057 giây, còn strstr là 4.94606 giây
• Mức tăng tốc tối đa là Westmere 1.10 lần, Haswell 1.37 lần, Skylake 1.82 lần, và KNL 4.33 lần
• Hiệu năng strstr trên Bulldozer rất tệ, ở mức 9.37792 giây, nên khó dùng làm mốc chuẩn
• Cách dùng MPSADBW nhìn chung không tốt ngoại trừ trên Skylake, và đặc biệt tệ trên KNL
• Cách dùng PCMPESTRM còn chậm hơn MPSADBW

Kết quả ARM

• Trên ARMv7, std::strstr là 7.30405 giây, còn std::string::find là 4.17131 giây
• Trên ARMv7, ARM Neon 32-bit generic đạt 1.29861 giây, nhanh tối đa 3.1 lần so với std::string::find
• Trên ARMv8, std::strstr là 3.37546 giây, còn std::string::find là 1.81368 giây
• Trên ARMv8, AArch64 64-bit generic đạt 0.27897 giây, nhanh tối đa 6.5 lần so với std::string::find
• Trên ARMv8, SWAR 64-bit generic đạt 0.46269 giây, cho hiệu năng gần với quy trình SIMD 32-bit

Kết luận và giới hạn

• Thuật toán SIMD tổng quát nhanh hơn C strstr trên mọi nền tảng
• Với từng CPU, nên chọn phiên bản SIMD cao nhất mà CPU đó hỗ trợ
• MPSADBW cho hiệu năng không tốt ngoại trừ trường hợp Skylake, và rất kém trên Knights Landing
• PCMPESTRM cho hiệu năng thấp hơn MPSADBW
• Hiệu năng của ARM Neon là tốt, kể cả khi tính cả bản cài đặt SWAR
  • Bản SWAR nhanh hơn string::find 1.7 lần
  • Bản SIMD nhanh hơn string::find 3.1 lần
• So sánh với strstr có thể không hoàn toàn công bằng
  • strstr xử lý chuỗi không biết trước độ dài
  • Các bản cài đặt này nhận độ dài làm đối số và tận dụng nó
• Bản cài đặt không an toàn
  • Nó có thể đọc dữ liệu vượt ra ngoài chuỗi đầu vào
  • Nếu chuỗi nằm ngay trước vùng nhớ chưa được ánh xạ, có thể xảy ra lỗi truy cập
  • AddressSanitizer cũng có thể báo lỗi
  • Có thể làm cho nó an toàn hơn, nhưng đó không phải mục tiêu của bài viết
• Toàn bộ bản cài đặt và chương trình kiểm thử đều có trên GitHub