Họ đề xuất đưa vào nhân Linux một bản triển khai nhanh hơn tới 4 lần memchr

Gần đây một đề xuất cho nhân Linux đã được phát hành, trong đó nó được đề xuất bao gồm một tập hợp các bản vá với triển khai tối ưu hóa hàm memchr () được sử dụng để tìm kiếm một ký tự trong một mảng.

Hàm memchr () quét n byte hàng đầu của vùng nhớ được trỏ tới bởi s đối với trường hợp đầu tiên của c. Cả c và các byte trong vùng nhớ được trỏ tới bởi s được hiểu là các ký tự không dấu.

Đề xuất promete Nhanh hơn để định vị một ký tự trong một khối bộ nhớ. Trong các thử nghiệm dành cho nhà phát triển, việc triển khai mới có thể nhanh hơn gần bốn lần trên các tìm kiếm lớn

Không giống như phiên bản trước, sử dụng phép so sánh từng byte, việc triển khai đề xuất được tạo có tính đến việc sử dụng đầy đủ các thanh ghi CPU 64 bit và 32 bit. Thay vì byte, so sánh được thực hiện bằng cách sử dụng các từ máy, cho phép ít nhất 4 byte được so sánh cùng một lúc.

Loạt bản vá lỗi này đã tối ưu hóa "memchr ()" và thêm một macro cho
"memchr_inv ()" để cả hai hàm đều có thể sử dụng nó để tạo mặt nạ bit.

Việc triển khai ban đầu của "memchr ()" dựa trên so sánh byte,
mà không sử dụng đầy đủ thanh ghi 64 hoặc 32 bit trong CPU. Chúng tôi thực hiện một
so sánh bằng từ để ít nhất 4 byte có thể được so sánh với
thời tiết. Memchr () được tối ưu hóa nhanh hơn gần 4 lần so với bản gốc
cho chuỗi dài. Trong Linux Kernel, chúng tôi thấy rằng độ dài của chuỗi
được tìm kiếm bởi "memchr ()" có tối đa 512 byte trong trình điều khiển / misc / lkdtm / heap.c.

Khi tìm kiếm trên các chuỗi lớn, phiên bản mới hóa ra nhanh hơn 4 lần so với phiên bản cũ (ví dụ: đối với chuỗi 1000 ký tự). Đối với các chuỗi nhỏ, hiệu quả của việc triển khai mới không đáng kể nhưng vẫn cao hơn so với phiên bản gốc.

Điều thú vị về đề xuất mới là cải tiến cho các chuỗi lớn, giúp cải thiện thời gian đáng kể. Điều đáng nói là trong nhân Linux, kích thước của chuỗi được xử lý trong memchr () đạt tới 512 byte. Trong các thử nghiệm của chúng tôi, hiệu suất đạt được đối với các chuỗi 512 byte, trong tình huống ký tự tìm kiếm ở cuối chuỗi, nó là 20%.

Điều đáng nói là phiên bản gốc của memchr () được thực hiện với kỹ thuật so sánh byte-khôn ngoan, không sử dụng đầy đủ các thanh ghi trên CPU 64-bit hoặc 32-bit.

Chúng tôi sử dụng so sánh toàn bộ từ để 8 ký tự có thể được so sánh cùng một lúc trên CPU. Mã này dựa trên việc triển khai của David Light.

Chúng tôi tạo hai tệp để đo hiệu suất của tệp đầu tiên chứa trung bình 10 ký tự trước ký tự đích. Tệp thứ hai chứa ít nhất 1000 ký tự trước nhân vật mục tiêu.

Việc triển khai "memchr ()" của chúng tôi hơi tốt hơn trong lần thử nghiệm đầu tiên và nhanh hơn gần 4 lần so với bản gốc thực hiện trong thử nghiệm thứ hai.

Kiểm tra hạt nhân 5.18 với biến thể "memchr ()" mới cho kiến ​​trúc 32 bit và 64 bit không tiết lộ bất kỳ vấn đề.

Điều gì xảy ra nếu p không phải là byte 8 (hoặc 4 trên mục tiêu 32 bit) được căn chỉnh? Không phải tất cả các mục tiêu đều hỗ trợ tải không thẳng hàng (hiệu quả), phải không?
 Tôi nghĩ rằng nó hoạt động nếu p không được căn chỉnh 8 hoặc 4 byte. Giả sử chuỗi là 10 byte. Vòng lặp for ở đây sẽ tìm kiếm 8 byte đầu tiên. Nếu ký tự đích nằm trong 2 byte cuối cùng, thì vòng lặp for thứ hai sẽ tìm thấy nó. Nó cũng hoạt động như vậy trên máy 32-bit.

Mức tăng hiệu suất tổng thể chưa được đánh giá của hệ thống con hạt nhân khi sử dụng biến thể "memchr ()" được tối ưu hóa, cũng như chưa được thảo luận về việc có ghi đè việc triển khai hay không (lệnh gọi hàm memchr () xảy ra 129 lần trong mã hạt nhân, bao gồm trình điều khiển và hệ thống tệp).

Cuối cùng Nếu bạn muốn biết thêm về nó, bạn có thể kiểm tra các chi tiết Trong liên kết sau.


Hãy là người đầu tiên nhận xét

Để lại bình luận của bạn

địa chỉ email của bạn sẽ không được công bố. Các trường bắt buộc được đánh dấu bằng *

*

*

  1. Chịu trách nhiệm về dữ liệu: Miguel Ángel Gatón
  2. Mục đích của dữ liệu: Kiểm soát SPAM, quản lý bình luận.
  3. Hợp pháp: Sự đồng ý của bạn
  4. Truyền thông dữ liệu: Dữ liệu sẽ không được thông báo cho các bên thứ ba trừ khi có nghĩa vụ pháp lý.
  5. Lưu trữ dữ liệu: Cơ sở dữ liệu do Occentus Networks (EU) lưu trữ
  6. Quyền: Bất cứ lúc nào bạn có thể giới hạn, khôi phục và xóa thông tin của mình.