Làm thế nào để memchr() làm việc dưới mui xe?

Question

Bối cảnh: Tôi đang cố gắng tạo một ngôn ngữ D thực hiện thuần túy chức năng tương đương với C's memchr nhưng sử dụng mảng và chỉ mục thay vì con trỏ. Lý do là std.string sẽ làm việc với việc đánh giá hàm thời gian biên dịch. Đối với những người không quen thuộc với W/D, các chức năng có thể được đánh giá vào thời gian biên dịch nếu các hạn chế nhất định được đáp ứng. Một hạn chế là họ không thể sử dụng con trỏ. Khác là họ không thể gọi hàm C hoặc sử dụng ngôn ngữ lắp ráp nội tuyến. Việc chuỗi thư viện hoạt động vào thời gian biên dịch rất hữu ích đối với một số đoạn mã thời gian biên dịch gen.

Câu hỏi: Memchr hoạt động như thế nào dưới mui xe để hoạt động nhanh như vậy? Trên Win32, bất cứ thứ gì mà tôi có thể tạo ra trong D thuần túy bằng cách sử dụng các vòng lặp đơn giản ít nhất là 2x kỹ thuật tối ưu hóa rõ ràng như tắt kiểm tra giới hạn, bỏ vòng lặp, v.v. một cái gì đó đơn giản như việc tìm kiếm một ký tự trong một chuỗi?

Answer 1

Tôi khuyên bạn nên xem nguồn của GNU libc. Đối với hầu hết các chức năng, nó sẽ chứa cả một phiên bản C tối ưu hóa chung của hàm và các phiên bản ngôn ngữ lắp ráp được tối ưu hóa cho càng nhiều kiến ​​trúc được hỗ trợ càng tốt, tận dụng các thủ thuật cụ thể của máy.

Các x86-64 SSE2 version kết hợp các kết quả từ pcmpeqb trên một bộ nhớ cache-line toàn bộ dữ liệu cùng một lúc (bốn 16B vectơ), để trừ dần nguyên overhead của sớm thoát pmovmskb/test/jcc.

gcc và clang hiện không có khả năng tự động vectơ vòng lặp với if() break điều kiện xuất cảnh sớm, do đó, chúng tạo ra các byte vô tận tại thời điểm triển khai C rõ ràng.

Answer 2

This implementation of memchr from newlib là một ví dụ về bản ghi tối ưu hóa của ai đó: nó đọc và kiểm tra 4 byte cùng một lúc (ngoài memchr, các chức năng khác trong thư viện newlib là here).

Ngẫu nhiên, hầu hết mã nguồn cho thư viện thời gian chạy MSVC đều có sẵn, như một phần tùy chọn của bản cài đặt MSVC (vì vậy, bạn có thể xem nó).

Answer 3

Đây là bản ghi nhớ của FreeBSD (BSD được cấp phép)() từ memchr.c. Trình duyệt mã nguồn trực tuyến của FreeBSD là một tài liệu tham khảo tốt cho các ví dụ mã được cấp phép BSD được kiểm tra thời gian.

void * 
memchr(s, c, n) 
    const void *s; 
    unsigned char c; 
    size_t n; 
{ 
    if (n != 0) { 
     const unsigned char *p = s; 

     do { 
      if (*p++ == c) 
       return ((void *)(p - 1)); 
     } while (--n != 0); 
    } 
    return (NULL); 
} 

Answer 4

memchr như memset và memcpy thường giảm xuống một lượng khá nhỏ mã máy. Bạn không thể tái tạo loại tốc độ đó mà không cần inlining similar assembly code. Một vấn đề chính cần xem xét trong quá trình triển khai là data alignment.

Một generic technique you may be able to use để chèn sentinel vào cuối chuỗi đang được tìm kiếm, đảm bảo rằng bạn sẽ tìm thấy nó. Nó cho phép bạn di chuyển thử nghiệm cho kết thúc chuỗi từ bên trong vòng lặp, đến sau vòng lặp.