Tăng hiệu năng code lên 4 lần với một `if` vô dụng

 (purplesyringa.moe)
1 điểm bởi GN⁺ 3 giờ trước | 1 bình luận | Chia sẻ qua WhatsApp
  • Bằng cách thêm đúng một câu lệnh điều kiện vào vòng lặp duyệt đường mã hóa tối ưu của một bộ nén chuyên biệt theo miền, thời gian chạy benchmark tổng hợp đã giảm từ 320µs xuống 80µs
  • Vì ở mỗi lần lặp, địa chỉ bộ nhớ phụ thuộc vào j của lần lặp trước, nên ngay cả một lệnh mov đơn lẻ cũng không thể tận dụng instruction-level parallelism mà bị trói vào độ trễ truy cập bộ nhớ
  • Nếu phản ánh vào dự đoán nhánh đặc tính next_j[i][j] phần lớn giữ nguyên như j hiện tại, CPU có thể lách qua sự phụ thuộc giữa các lần lặp để thực thi suy đoán nhiều lần lặp cùng lúc
  • Tác giả dùng ép kiểu volatile để trình biên dịch không loại bỏ câu lệnh if vốn không cần thiết về mặt ngữ nghĩa. Trên LLVM, [[unlikely]] hay __builtin_expect(..., 0) cũng có tác dụng, nhưng volatile sinh mã tốt hơn và còn được GCC hỗ trợ
  • Trong thử nghiệm thực tế hơn, tác giả thu được mức cải thiện hiệu năng khoảng 2 lần, có thể do LLVM sinh mã chưa tối ưu; nếu j khó dự đoán, có thể dùng pshufb với độ trễ 1 chu kỳ làm phương án thay thế

Duyệt đường đi tối ưu trong bộ nén

  • Chuỗi đầu vào được chia thành nhiều khối, và ở mỗi khối cần chọn cách mã hóa nhỏ nhất
    • Mỗi cách mã hóa nén tốt với các ký tự khác nhau, nên khó xác định ngay ranh giới khối
    • Thuật toán trong bài viết trước biến bài toán này thành việc tìm đường đi ngắn nhất trên một lưới
  • Mỗi ô lưu lại ô tối ưu cần đi tiếp theo
    • Theo lần lượt các tham chiếu từ ô đầu đến ô cuối sẽ thu được thứ tự mã hóa tối ưu
  • Vòng lặp đầu tiên điền next_j đã được tối ưu bằng SIMD
    • Nút thắt thực sự là vòng lặp duyệt đường đi đơn giản như sau
uint8_t encoding[n_symbols];
uint8_t j = 0;

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}
  • Phép toán cốt lõi ngoài phần ghi dữ liệu là j = next_j[i][j], được biên dịch thành đúng một lệnh mov

Sự phụ thuộc khiến cả một lệnh đơn cũng chậm

  • CPU hiện đại tận dụng instruction-level parallelism để thực thi đồng thời nhiều lệnh và công việc từ các lần lặp khác nhau
    • Đây là lý do trong các vòng lặp thông thường, chi phí của phép kiểm tra i < n_symbols và i++ không chặn các công việc khác
  • Nhưng các lệnh phụ thuộc lẫn nhau thì không thể chạy đồng thời
    • Muốn tính địa chỉ bộ nhớ next_j[i][j] của lần lặp hiện tại thì cần j lấy được từ lần lặp trước
    • Lần lặp tiếp theo không thể bắt đầu cho đến khi có kết quả của lần lặp trước, nên ngay cả khi dữ liệu nằm trong cache vẫn bị ảnh hưởng bởi độ trễ truy cập bộ nhớ

Tận dụng dự đoán nhánh như một dạng suy đoán giá trị

  • Bộ nén này dự kiến không có quá nhiều khối, nên trong đa số trường hợp next_j[i][j] sẽ giống với j hiện tại
  • Không thể trực tiếp yêu cầu CPU dự đoán địa chỉ dựa trên việc j giữ nguyên, nhưng có thể tạo ra hiệu ứng tương tự bằng dự đoán nhánh
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}
  • Nếu CPU dự đoán phần thân if sẽ không chạy, nó sẽ xem như không có phụ thuộc giữa các lần lặp trong việc cập nhật j và thực thi suy đoán nhiều lần lặp cùng lúc
  • Khi điều kiện thực sự đúng, sẽ xảy ra khôi phục sau dự đoán nhánh sai
    • Các thao tác ghi đã thực hiện do suy đoán sai sẽ bị loại bỏ
    • Việc thực thi sẽ bắt đầu lại với j đúng
  • Khi j gần như không đổi, nút thắt của vòng lặp chuyển từ độ trễ sang thông lượng

Ngăn trình biên dịch xóa if

  • Xét từ góc nhìn của trình biên dịch, đoạn có thêm điều kiện và đoạn gốc có cùng ngữ nghĩa
    • Nếu j nằm trong bộ nhớ thì có thể tránh ghi thừa hoặc tránh ghi vào bộ nhớ chỉ đọc, nhưng ở đây nó là giá trị trong thanh ghi
    • Các tối ưu hóa như common subexpression elimination (CSE) có thể loại bỏ điều kiện và truy cập lặp lại
  • Thông thường các gợi ý cho trình biên dịch được dùng để loại bỏ nhánh, nhưng ở đây lại cần giữ đoạn code không nhánh thành code có nhánh
  • Tác giả áp dụng ép kiểu volatile ở phía phép gán để truy cập bộ nhớ của phép kiểm tra điều kiện và phép gán trông như độc lập với nhau
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}
  • Trong phần bổ sung ngày 13/7, tác giả xác nhận rằng giống như cách ibookstein tìm ra, dùng [[unlikely]] hoặc __builtin_expect(..., 0) cũng cho cùng hiệu quả trên LLVM
  • Cách dùng volatile tạo ra mã tốt hơn và cũng hoạt động trên GCC

Thay đổi hiệu năng được xác nhận qua benchmark

  • Trong benchmark tổng hợp, thời gian chạy của vòng lặp giảm từ 320µs xuống 80µs, tức nhanh hơn 4 lần
    • Chênh lệch thời gian của một lần chạy là nhỏ, nhưng vì vòng lặp này được gọi nhiều lần trong quá trình nén nên chi phí cộng dồn thành đáng kể
  • Trong các thử nghiệm thực tế hơn, tác giả ghi nhận mức cải thiện hiệu năng khoảng 2 lần
    • Có thể một phần do LLVM sinh mã chưa tối ưu, nhưng vẫn đủ đáng để áp dụng

Một phương án khác: biểu diễn bằng bitmask

  • Trong thuật toán này, next_j[i][j] chỉ có thể nhận một trong hai giá trị
    • Phần lớn thời gian là j hiện tại
    • Giá trị còn lại không phụ thuộc vào j mà chỉ phụ thuộc vào i
  • Có thể thay mảng 8 phần tử next_j[i] bằng một cặp gồm giá trị thay thế và bitmask
    • Với cách biểu diễn này, if là cần thiết về mặt ngữ nghĩa nên không cần lách qua bằng volatile
    • Tuy nhiên trên x86, phép kiểm tra một bit ở vị trí biến đổi có thể chậm hơn so với so sánh, nên tổng hiệu năng có thể còn thấp hơn

Khi j không thể dự đoán

  • Bài viết về tăng tốc duyệt linked list bằng suy đoán giá trị cũng đề cập cách tăng hiệu năng theo hướng tương tự
  • Nếu j khó dự đoán, có thể dùng phép đánh chỉ số vector pshufb
    • pshufb có độ trễ 1 chu kỳ nên rất khó giảm thêm nếu không dùng thực thi suy đoán
    • Có thể tính song song bằng vector các đường đi tương ứng với từng j khởi đầu khả dĩ
    • Cũng có thể chia công việc ra nhiều luồng rồi hợp nhất kết quả

Bài viết liên quan

1 bình luận

 
GN⁺ 3 giờ trước
Các ý kiến trên Lobste.rs

  • Có vẻ việc gắn thuộc tính [[unlikely]] của C++20 vào câu lệnh if là đủ để ngăn clang loại bỏ đoạn mã đó: https://clang.godbolt.org/z/r4xYWfPfe
    Chưa kiểm tra trên các trình biên dịch khác

    • Kiểm tra lại thì thấy nó thực sự hoạt động trên LLVM; có lẽ ban đầu tôi đã thử nhầm với GCC, nơi nó không có tác dụng
      Tuy nhiên, vì [[unlikely]] di chuyển mã ra khỏi hot path, LLVM tạo ra đoạn mã hơi kém hiệu quả như sau 
              cmp     r8b, dl  
        jne     not_equal  
continue:  
        ...  
not_equal:  
        mov     ecx, edx  
        jmp     continue
      Dạng sau có vẻ hợp lý hơn 
              cmp     r8b, dl  
        je      skip  
        mov     ecx, edx  
skip:  
        ...
      Ngoài ra, khi tối ưu để không đọc giá trị từ bộ nhớ nhiều lần, nó cũng thêm một lệnh vào hot loop. Vì vậy, kỹ thuật dùng volatile vẫn hữu ích, nhưng cũng đáng mừng là mã gốc vẫn có thể hoạt động nguyên như vậy

  • Ở nơi khác, kỹ thuật này được gọi là suy đoán giá trị (value speculation): https://mazzo.li/posts/value-speculation.html

    • Sau khi tự nghĩ lại cách này, điều đầu tiên tôi nghĩ là nó cũng có thể áp dụng cho danh sách liên kết được lưu trong arena; bài viết được liên kết nói đúng về nội dung đó nên tôi đã thêm liên kết vào bài của mình

  • Tôi tự hỏi liệu trong 2–3 năm tới, khi các lập trình viên ngày càng thờ ơ với đầu ra của LLM, họ có còn quan tâm đến những bài blog kiểu này không

    • Ngay cả bây giờ cũng rất ít người quan tâm, và nếu nhìn trên toàn bộ lĩnh vực lập trình thì đây là kiến thức ngách
      Dù vậy, với những ai quan tâm, đây vẫn là một bài viết rất hữu ích và hay
    • Godbolt rất phổ biến. Khi bị phê bình về thói quen không đọc mã, các lập trình viên say mê LLM thường đưa ra câu “anh còn xem cả assembly à?” như thể đó là một phản bác ghê gớm, nhưng thực tế là chúng tôi kiểm tra assembly và sẽ tiếp tục làm vậy
      Một lập trình viên cho rằng chi tiết không quan trọng thì khó trở thành lập trình viên giỏi. Cũng như một kỹ sư xây dựng giỏi phải để ý cả bu-lông và đai ốc trong các dự án lớn, một lập trình viên giỏi cũng phải đào sâu đến những chi tiết nhỏ. Tổng thể được tạo nên từ các chi tiết, nên nếu bạn coi trọng thứ mình tạo ra thì không thể né tránh điều đó
    • Tôi cho rằng về cơ bản sẽ không khác hiện tại. Ngay bây giờ, đa số cũng không quan tâm đến đầu ra của trình biên dịch đối với mã do con người viết
      Số người xem đầu ra trình biên dịch của mã do AI viết có thể còn ít hơn, nhưng tôi không nghĩ cấu trúc cơ bản sẽ thay đổi
    • Điều thay đổi có lẽ không phải là có quan tâm hay không, mà là sắp xếp lại thứ tự ưu tiên tối ưu hóa
      10 năm trước, chỉ vì một script Bash hơi chậm, hẳn bạn cũng sẽ không bắt đầu bằng việc nghĩ đến song song hóa ở mức lệnh hay dự đoán nhánh của CPU. Có thể có một phần lõi hiệu năng được viết bằng ngôn ngữ có thể biên dịch và tối ưu hóa; trong đó có các hot path đáng xem xét chi tiết; rồi sâu hơn nữa có thể có một, hai hot loop đáng kiểm tra về vector hóa hoặc khác biệt trong cách CPU hiện đại vận hành
      Ngay cả khi dùng LLM, những điểm nóng nhất về hiệu năng vẫn là ngoại lệ đáng để tự mình xem xét. Dù có chủ động chấp nhận chất lượng đầu ra thấp, hoặc làm 70% bằng LLM rồi sửa tay 30% còn lại và tỷ lệ đó có thể cải thiện lên 85:15, bài viết này vẫn đang bàn về một vùng chi tiết thuộc top 1%
    • Vì tôi không viết C++, theo nghĩa đó thì ngay cả bây giờ nó cũng không phải mối quan tâm trực tiếp của tôi, nhưng tôi vẫn đọc thấy thú vị và nghĩ rằng 2–3 năm nữa những nội dung như thế này vẫn sẽ tiếp tục hấp dẫn