Đừng chế giễu bộ dự đoán nhánh vui vẻ thú vị (2023)

Đừng chế giễu bộ dự đoán nhánh vui vẻ

• Gần đây đang viết khá nhiều assembly AArch64
• Một ý tưởng "thông minh" nhằm loại bỏ một lệnh nhảy trong vòng lặp lại làm hiệu năng giảm đi
• Giải thích sai lầm này để người khác không lặp lại cùng một lỗi

Ví dụ mã

float run(const float* data, size_t n) {
  float g = 0.0;
  while (n) {
    n--;
    const float f = *data++;
    foo(f, &g);
  }
  return g;
}

static void foo(float f, float* g) {
  // g를 수정하는 작업
}

Dịch sang assembly AArch64

// x0: const float* data
// x1: size_t n
// s0: float trả về
stp  x29, x30, [sp, #-16]!
mov s0, #0.0
loop:
  cmp x1, #0
  b.eq exit
  sub x1, x1, #1
  ldr s1, [x0], #4
  bl foo
  b loop
foo:
  // đọc từ s1 và cộng dồn vào s0
  // ...
  ret
exit:
  ldp  x29, x30, [sp], #16
  ret

Thử tối ưu hóa

• Muốn cải thiện hiệu năng bằng cách giảm lệnh bl
• Nhưng hiệu năng lại giảm đi

So sánh hiệu năng

• Mã gốc: 969 ns
• Mã tối ưu hóa: 3.85 µs

Phân tích nguyên nhân

• Bộ dự đoán nhánh bị rối vì cặp bl và ret không khớp nhau
• Theo tài liệu ARM, lệnh ret giúp dự đoán việc trả về hàm

Cách giải quyết

• Dùng br x30 thay cho ret
• Hiệu năng phục hồi: 913 ns

Tối ưu hóa bổ sung

• Inline foo để cải thiện hiệu năng
• Unroll vòng lặp và dùng lệnh SIMD

Hiệu năng cuối cùng

• SIMD + unroll vòng lặp thủ công: 94 ns

Kết luận

• Đừng làm bộ dự đoán nhánh bị rối
• Mã SIMD nhanh hơn, nhưng vì phép cộng số thực dấu chấm động không tuân theo tính kết hợp nên kết quả có thể khác

Ý kiến của GN⁺

• Bài viết này cho thấy rõ tầm quan trọng của tối ưu hóa assembly AArch64
• Hiểu nguyên lý hoạt động của bộ dự đoán nhánh là điều thiết yếu để tối ưu hiệu năng
• Tối ưu hóa bằng lệnh SIMD rất hiệu quả, nhưng cần cân nhắc vấn đề độ chính xác
• Nếu dùng ngôn ngữ bậc cao như Rust, có thể dễ dàng cải thiện hiệu năng nhờ tối ưu hóa của compiler
• Một dự án có chức năng tương tự là hướng dẫn tối ưu hóa assembly của Agner Fog

[GN⁺]

Ý kiến trên Hacker News

• Đã tóm tắt bài viết cùng với những người bạn từ thời Apple II

  • Mã đã tối ưu mất 94 nano giây để cộng 1024 số dấu phẩy động 32-bit
  • Con 6502 1 MHz trong 94 nano giây đó có lẽ còn đang cố lấy byte đầu tiên của lệnh đầu tiên từ bộ nhớ
  • Đoạn mã này chỉ đạt hiệu năng tối ưu khi chạy từ cache. DRAM thì chậm

• Raymond Chen đã bàn về cùng chủ đề này từ gần 20 năm trước

  • Sau khi kiểm tra điều kiện kết thúc vòng lặp thì chuyển sang hàm foo mà không cần nhánh
  • Điều này vi phạm heuristic dự đoán cơ bản
  • Việc bộ dự đoán nhánh duy trì shadow stack của địa chỉ trả về đã tồn tại hàng chục năm

• Mã SIMD có thể thực hiện phép cộng theo thứ tự khác vì phép cộng dấu phẩy động không tuân theo tính kết hợp

  • Đây có thể là lý do trình biên dịch không tạo ra lệnh SIMD
  • Phép cộng dấu phẩy động về bản chất có một biên độ sai số, và mọi đáp án nằm trong phạm vi đó đều hợp lệ
  • Nếu có đầu vào dấu phẩy động đặc biệt thì ngôn ngữ cần cung cấp cách để mã hóa điều đó một cách tường minh

• Từ Rust 1.78 trở đi, trình biên dịch dùng loop unrolling quyết liệt hơn và một chút SIMD

  • Loop unrolling đã bắt đầu từ Rust 1.59
  • Trong mã trên GitHub, tác giả đang dùng bản Rust 1.67.0-nightly

• Có người thấy khó hiểu về cách x0 tăng lên trong assembly ARM/ARM64

  • Lệnh ldr s1, [x0], #4 sẽ load rồi tăng x0 thêm 4
  • x86_64 không có một lệnh đơn nào vừa load vừa tăng như vậy

• Ngạc nhiên là tác giả không thử cách ít phức tạp hơn để tối ưu mã assembly

  • Có thể viết lại mã assembly để chỉ cần một nhánh ở cuối vòng lặp
  • Có thể inline foo và bỏ lệnh RET

• Có ý kiến mong tác giả đừng liên tục đổi đơn vị