Tìm ví dụ đầu tiên của một ký tự bằng cách sử dụng simd

Question

Tôi đang cố gắng tìm trường hợp đầu tiên của một ký tự, trong trường hợp này là "" sử dụng simd (AVX2 hoặc cũ hơn) .Tôi muốn sử dụng _mm256_cmpeq_epi8, nhưng sau đó tôi cần một cách nhanh chóng để tìm kiếm xem có bất kỳ byte kết quả nào trong __m256i đã được đặt thành 0xFF hay không. Kế hoạch sau đó sử dụng _mm256_movemask_epi8 để chuyển đổi kết quả từ byte thành bit và sử dụng ffs để có chỉ mục phù hợp. để di chuyển ra khỏi một phần tại một thời gian sử dụng _mm_movemask_epi8 Bất kỳ lời đề nghị khác

Answer 1

Bạn có ý tưởng đúng với _mm256_cmpeq_epi8 -?..>_mm256_movemask_epi8 AFAIK, đó là cách tối ưu để thực hiện điều này cho CPU Intel ít nhất PMOVMSKB r32, ymm là tốc độ tương tự như phiên bản 16-byte XMM, do đó, nó sẽ là một mất mát lớn để giải nén hai l anes của một vector 256b và di chuyển chúng một cách riêng biệt và sau đó kết hợp lại các kết quả số nguyên. (Nguồn:. Agner Fog's instruction table Xem các liên kết Perf khác trong x86 thẻ wiki.)

Tận dụng mã bên trong vòng lặp như hiệu quả càng tốt bằng cách rời khỏi ffs cho đến sau khi bạn đã xác định một tổ chức phi zero kết quả từ _mm256_movemask_epi8.

KIỂM TRA/JCC có thể làm cầu chì vĩ mô thành một uop đơn, nhưng BSF/JCC thì không, do đó, nó có thêm hướng dẫn. (Và bạn sẽ khó có được trình biên dịch C để phát ra BSF/JCC. Khả năng phân nhánh trên kết quả của ffs sẽ cung cấp cho bạn một số loại kiểm tra cho đầu vào là khác 0, sau đó thêm BSF, sau đó thêm 1 Sau đó, lưu ý rằng đối với các vấn đề tương tự, so sánh movemask (ví dụ để kiểm tra xem nó là 0xFFFFFFFF) có hiệu quả như phân nhánh trên nó hay không. không khác.

---

Như Paul R đã đề xuất, xem xét một số triển khai strlen, strchr và memchr có thể mang tính thông tin. Có nhiều triển khai asm viết tay trong triển khai libc nguồn mở và các địa điểm khác. (ví dụ glibc, và Agner Fog's asmlib.)

Nhiều phiên bản của glibc quét lên ranh giới liên kết, sau đó sử dụng vòng lặp không đọc 64B tại một thời điểm (trong 4 vector SSE, vì tôi không nghĩ rằng glibc có AVX2 phiên bản).

Để tối ưu hóa chuỗi dài, hãy giảm chi phí từ việc kiểm tra kết quả so sánh bằng cách HOẶC so sánh kết quả với nhau và kiểm tra điều đó. Nếu bạn tìm thấy một lần truy cập, hãy quay lại và kiểm tra lại vectơ của bạn để xem véc tơ nào có lượt truy cập.

Có thể sẽ hiệu quả hơn khi thực hiện ffs trên một số nguyên 64 bit mà bạn đã tạo ra từ nhiều kết quả di chuyển (với ca và |). Tôi không chắc chắn về việc làm điều này bên trong vòng lặp trước khi thử nghiệm cho số không; Tôi không nhớ nếu một trong những chiến lược strlen của glibc đã làm điều đó hay không.

---

Mọi thứ tôi đã đề xuất ở đây là có thể thấy trong asm trong các chiến lược glibc khác nhau cho strlen, memchr và các chức năng liên quan. Đây là sysdeps/x86_64/strlen.S, nhưng tôi có thể có một tệp nguồn khác ở đâu đó bằng cách sử dụng hơn SSE2 cơ bản. . (Hoặc không, tôi có thể nghĩ đến việc một chức năng khác nhau, có lẽ không có gì để đạt được vượt SSE2, cho đến khi AVX (insns 3 toán hạng) và AVX2 (256b vectơ số nguyên) là

Xem thêm:

• glibc's strchr-avx2.S (Woboq.org có một trình duyệt nguồn tốt với tìm kiếm hữu ích cho tên tập tin/biểu tượng).
• glibc của memchr-avx2.S

---

glibc's memchr sử dụng PMAXUB thay vì POR. Tôi không chắc chắn nếu đó là hữu ích cho một số lý do vi kiến ​​trúc phức tạp, nhưng nó chạy trên cổng ít hơn trên hầu hết các CPU. Có lẽ đó là mong muốn, để tránh xung đột tài nguyên với cái gì khác? IDK, có vẻ lạ, vì nó cạnh tranh với PCMPEQB.