Nhanh hơn C {n} lần

 (owen.cafe)
1 điểm bởi GN⁺ 2023-07-07 | 1 bình luận | Chia sẻ qua WhatsApp
  • Ngay cả với một vòng lặp C nhỏ, đầu ra của trình biên dịch không phải lúc nào cũng là tốt nhất; sau khi tự tay tinh chỉnh assembly x86_64, phiên bản loại bỏ nhánh điều kiện đã nhanh hơn 6,73 lần so với đầu ra của clang
  • Hàm được thử nghiệm xử lý chuỗi với 's' là +1, 'p' là -1, và '\0' là kết thúc; đầu ra của clang 16 chia luồng này thành 3 nhánh điều kiện
  • Sau khi đổi thứ tự nhánh, bố trí lại basic block và thay nhảy bằng số học, thời gian chạy giảm từ 3,23 giây xuống 2,87 giây, và ở bước này đạt tốc độ ngang với GCC 12
  • Phiên bản nhanh nhất dùng cmove để chọn giá trị cộng theo từng ký tự giữa 0, 1 và -1, rồi luôn thực hiện add, ghi nhận 0,48 giây và thông lượng 1,94GiB/s
  • Benchmark được chạy trên AMD Ryzen 5 5625U và Linux 6.1.33, xử lý danh sách 1 triệu ký tự 'p'/'s' ngẫu nhiên 1000 lần, và dùng kết quả tốt nhất trong nhiều lần chạy

Hàm thử nghiệm và đầu ra của trình biên dịch

  • Hàm mục tiêu tăng con trỏ chuỗi từng bước và cập nhật số nguyên res tùy theo ký tự
    • 's': res += 1
    • 'p': res -= 1
    • '\0': trả về res
    • Ký tự khác: không thay đổi
  • Vì hàm nhỏ nên điểm xuất phát là kỳ vọng gcc hoặc clang có thể tối ưu khá tốt, thậm chí có thể là tối ưu hoàn toàn
  • Assembly ban đầu do clang tạo ra chia bốn trường hợp bằng ba nhánh điều kiện (je, je, jne)
    • Bắt đầu với res = 0
    • Đọc ký tự và kiểm tra '\0' trước
    • Sau đó so sánh với 'p' và 's'
  • Kết quả clang ban đầu
    • Thời gian chạy: 3,23 giây
    • Thông lượng: 295,26MiB/s
  • GCC tạo ra nhiều mã hơn một chút nhưng nhanh hơn đôi chút

Kiểm tra ký tự thường gặp trước điều kiện kết thúc hiếm gặp

  • Vòng lặp chỉ kết thúc khi gặp ký tự kết thúc chuỗi rỗng '\0', và trong hàm này ký tự null nhiều nhất chỉ xuất hiện một lần
  • Đầu ra của clang kiểm tra '\0' đầu tiên, nên với mỗi ký tự 'p' và 's' đều phải kiểm tra điều kiện kết thúc trước
  • Thay đổi thủ công đầu tiên là đảo thứ tự so sánh để kiểm tra 'p' và 's' trước
  • Kết quả
    • Thời gian chạy: 3,10 giây
    • Mức tăng tốc: 1,04 lần
    • Thông lượng: 307,64MiB/s

Bố trí lại basic block và giảm số lần nhảy

  • Vì hai trường hợp phổ biến là 'p' và 's' đều nhảy lại về đầu vòng lặp, có thể giảm nhánh bằng cách đặt một block ở phía trên vòng lặp
  • Nếu đặt block 's' ngay trước vòng lặp, sau khi xử lý 's' có thể rơi thẳng vào vòng lặp mà không cần nhảy riêng
  • Đổi lại, khi hàm bắt đầu phải nhảy một lần vào vòng lặp để bỏ qua block 's'
    • Cú nhảy ở đầu hàm chỉ xảy ra một lần
    • Ký tự 's' có thể xuất hiện nhiều lần nên đây được xem là một đánh đổi chấp nhận được
  • Kết quả
    • Thời gian chạy: 2,98 giây
    • Tăng tốc tổng thể: 1,08 lần
    • Thông lượng: 320,02MiB/s

Dùng số học để loại bỏ thêm một lệnh nhảy vô điều kiện

  • Để bỏ jmp vô điều kiện quay lại vòng lặp trong block p:, tác giả dùng số học
  • Vì giảm 1 lần có thể cho cùng hiệu ứng bằng sub eax, 2 rồi inc eax, nên sau khi xử lý 'p' có thể rơi tiếp sang block 's'
  • Cách này loại bỏ thêm một lệnh nhánh
  • Kết quả
    • Thời gian chạy: 2,87 giây
    • Tăng tốc tổng thể: 1,12 lần
    • Thông lượng: 332,29MiB/s
  • Ở thời điểm này hiệu năng ngang với mã do GCC 12 sinh ra
    • Mã GCC 12 cũng chạy trong 2,87 giây
    • Bản viết tay có 13 lệnh
    • Đầu ra GCC có 19 lệnh
    • Có vẻ mã GCC đã unroll vòng lặp và tái sử dụng các block case ở một mức độ nào đó

Thay nhánh điều kiện bằng cmove

  • Nếu nhánh điều kiện là nút thắt cổ chai, có thể bỏ hẳn nhánh thay vì trông chờ vào bộ dự đoán nhánh
  • Phiên bản nhanh nhất dùng cmove, tức conditional move nếu bằng nhau
  • Quy tắc hoạt động rất đơn giản
    • Giá trị mặc định là 0
    • Nếu ký tự hiện tại là 's' thì là 1
    • Nếu ký tự hiện tại là 'p' thì là -1
    • Mỗi vòng lặp luôn cộng giá trị đã chọn vào res
  • Cách này loại bỏ nhiều mũi tên trong đồ thị luồng điều khiển
  • Kết quả
    • Thời gian chạy: 0,48 giây
    • Tăng tốc tổng thể: 6,73 lần
    • Thông lượng: 1,94GiB/s
  • Với assembly của một vòng lặp C gọn do tự viết, có thể đạt mức tăng tốc hơn 6 lần nhờ các tối ưu mà trình biên dịch không tự động thực hiện

Thử tiết kiệm thanh ghi và các thử nghiệm bổ sung không thành công

  • Một phiên bản dùng sete của x86_64 để đặt thanh ghi 1 byte thành 0 hoặc 1 theo điều kiện cũng đã được thử
  • Phiên bản này bỏ được việc dùng r8d, nhưng chậm hơn phiên bản chỉ dùng cmov
  • Kết quả
    • Thời gian chạy: 0,51 giây
    • Tăng tốc tổng thể: 6,33 lần
    • Thông lượng: 1,83GiB/s
  • Dùng ít thanh ghi hơn hoặc dùng phép toán 8 bit thay vì 32 bit không khiến nó nhanh hơn
  • Các thử nghiệm thêm cũng làm giảm hiệu năng
    • Unroll vòng lặp của phiên bản tốt nhất: chậm hơn
    • Căn chỉnh đầu vòng lặp theo biên 16 byte: chậm hơn
    • Trong GNU assembler, chèn .align <bytes> trước nhãn có thể thêm các lệnh nop

Môi trường benchmark và mã nguồn

  • Danh sách mã có trên GitHub
  • Môi trường benchmark
    • OS: Linux 6.1.33
    • CPU: AMD Ryzen 5 5625U with Radeon Graphics
    • CPU family 25, 6 lõi, 2 luồng mỗi lõi, 1 socket
    • clang: 16.0.1
    • gcc: 12.2.0
  • Phiên bản C được biên dịch với -march=native để có thể sinh mã phù hợp với CPU cụ thể
  • Benchmark dùng danh sách 1 triệu ký tự gồm 'p' và 's' ngẫu nhiên
    • Mỗi phiên bản hàm xử lý danh sách này 1000 lần
    • Mỗi phiên bản được chạy nhiều lần và chọn kết quả tốt nhất
  • Bài viết tiếp theo được nối bằng part two

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-07-07
Các ý kiến trên Hacker News

  • Kết luận đúng có lẽ không phải là assembly viết tay nhanh hơn C 6 lần, mà gần hơn với việc nhảy có thể chậm hơn rất nhiều so với phép toán số học có điều kiện
    Ngay cả trong C, nếu không dùng switch mà xử lý bằng một hai câu if thì cũng dễ đạt hiệu quả tương tự. Khi đổi hàm C theo kiểu gặp s thì tăng, p thì giảm, \0 thì kết thúc, nó nhanh hơn 5,5 lần, và trong lần chạy ví dụ giảm từ 3,58 giây xuống 0,65 giây

    • Hay đấy. Ở phần 2, tác giả viết lại C và đạt tăng tốc 12 lần: https://owen.cafe/posts/the-same-speed-as-c/
      Như những người khác đã nói, sau khi điều chỉnh đầu vào cũng có thể vector hóa thuật toán. Tôi xem đây là bài tập mang tính giáo dục, và thật lòng hy vọng sẽ không có chuyện hạ xuống assembly khi không có lý do đủ thuyết phục
    • Nói nhảy chậm hơn phép toán số học có điều kiện là đúng khi lệnh nhảy không thể dự đoán. Nếu lệnh nhảy có thể dự đoán thì nhảy nhanh hơn
      Trước đây Linus cũng từng viết khá dài rằng cmov không hữu ích với các nhánh có thể dự đoán: https://yarchive.net/comp/linux/cmov.html
    • Tôi tò mò đang dùng phiên bản GCC nào. Trên cả Ubuntu và Windows đều cho cùng hiệu năng, và với gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 thì cả lone lẫn ltwo đều khoảng 3,58 giây
    • Tôi thắc mắc liệu đổi switch thành nhiều if có phải lúc nào cũng nhanh hơn không. Cũng tò mò từ khoảng bao nhiêu trường hợp trở lên thì switch nhanh hơn, và nếu nhất quán thì có vẻ nên đưa vào tối ưu hóa trình biên dịch
    • Tôi nghĩ trình biên dịch cũng phải làm được mức biến đổi này chứ nhỉ

  • Theo tôi, mã gốc không được viết theo kiểu thân thiện với trình biên dịch cho lắm. Nếu viết như result += *s == 's'; result -= *s == 'p'; thì trình biên dịch sẽ tạo ra mã sete/cmov không rẽ nhánh phù hợp, và tốc độ gần như tương đương assembly đã tối ưu trong bài
    Tuy nhiên nó không unroll vòng lặp hay vector hóa. Nếu truyền riêng kích thước chuỗi để biết size khi chạy, trình biên dịch có thể biết kích thước vòng lặp nên sẽ unroll, và nếu có thể còn dùng cả lệnh AVX-512. Với đầu vào lớn thì nhanh hơn nhiều, nhưng tôi lười benchmark trực tiếp. Nếu là lập trình viên C mà không theo dõi độ dài chuỗi thì cứ tùy ý, nhưng tôi nghĩ thật sự không nên làm vậy: https://godbolt.org/z/rde51zMd8

    • Phiên bản thân thiện với trình biên dịch có ở phần 2: https://owen.cafe/posts/the-same-speed-as-c/
      Phiên bản đó đạt 3,88GiB/s. Tôi cố ý chưa đi đến mức vector hóa, mà muốn giữ phạm vi bài toán nhỏ và trình bày các mẹo, thủ thuật assembly trong bài. Sau này vẫn có thể viết một bài về việc padding chuỗi đầu vào và vector hóa thuật toán
    • Trong mã thiếu một dòng quan trọng: /* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */
    • Trong Nim hình như cũng có thể kích hoạt theo cách sau: bật {.overflowChecks:off.} rồi duyệt input, gặp 's' == c thì tăng, 'p' == c thì giảm
      Trên Apple M1 có mức tăng tốc khoảng 5 lần, còn khi vẫn bật kiểm tra tràn thì chỉ nhanh hơn khoảng 2 lần so với phiên bản C mặc định. Biết các mẫu tốt để gợi ý tối ưu SIMD luôn là điều hữu ích
    • “Thật sự không nên làm vậy” nghĩa là không nên theo dõi độ dài chuỗi à?

  • Ở góc độ gần như một chuyên gia tối ưu hóa, tôi nghĩ bài toán này sẽ được giải hoàn toàn khác. Trên máy tôi, phiên bản C ban đầu đạt 389MB/giây, và nếu assembly trong bài đạt cùng mức cải thiện 6,2 lần thì sẽ vào khoảng 2,4GB/giây
    Với buffer dài, phiên bản C++ này trên máy tôi vượt 24GB/giây: https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7...
    Không cần assembly, dựa trên AVX2 intrinsic và nhanh hơn 61 lần so với phiên bản gốc

    • Thú vị đấy. Thay vì giữ bộ đếm trong thanh ghi ymm, có vẻ có thể vector hóa phần prologue bằng movemask và popcnt
      Mã này chưa được thử nghiệm nên cần benchmark, nhưng có vẻ có thể tiếp cận bằng cách tạo mask cho s, p, \0, rồi dùng tzcnt, bzhi để đếm các bit trước cuối chuỗi
    • Tôi tò mò không biết việc này có làm được bằng std::experimental::simd không: https://en.cppreference.com/w/cpp/experimental/simd
    • Sẽ hay nếu viết lại cái này theo dạng tương thích với repository của @414owen
    • Tôi muốn biết tài liệu nào tốt để học và luyện AVX

  • Đoạn mã này trông thật sự rất hợp với SIMD. Nếu có thể đổi prototype để nhận độ dài tường minh thì đọc và xử lý 16 byte mỗi lần sẽ dễ hơn
    Chỉ cần cộng và trừ trực tiếp kết quả so sánh, và có lẽ chỉ riêng việc gọi strlen() ở đầu hàm để lấy độ dài tường minh cũng đã đáng làm

  • Tôi đã thử nhanh một triển khai vector hóa RISC-V. Cách làm là dùng rvv để đọc chuỗi và tìm vị trí \0, sau đó đếm số lượng s và p bằng vcpop
    Trên Mangopi MQ Pro(C906, rv64gc + rvv 0.7.1, độ dài vector 128 bit), switch đạt 0,19 Bytes/Cycle, triển khai C dùng bảng đạt 0,17 Bytes/Cycle, còn rvv đạt 1,57 Bytes/Cycle và giảm xuống 1,35 sau khoảng 30KiB. Nếu căn chỉnh con trỏ theo trang và bảo đảm vl không lớn hơn kích thước trang thì có thể đạt 2/1,7 Bytes/Cycle

    • Để hoàn toàn đúng, lệnh load phải là fault-only-first load. rvv có tính năng này; nếu không, nó có thể thất bại khi byte null nằm ngay trước cuối vùng nhớ đã cấp phát

  • Đây có vẻ là đặc tính riêng của kiến trúc x86. Vì chi phí khi không rẽ nhánh vốn rất rẻ, nên rẽ nhánh trông tương đối đắt hơn: https://wordsandbuttons.online/challenge_your_performance_in...
    Nhưng trên các bộ xử lý khác thì có thể không như vậy: https://wordsandbuttons.online/using_logical_operators_for_l...
    Câu hỏi lớn hơn là nói chung vì sao cần C. Nếu định chỉnh tay để chạy tốt nhất trên một phần cứng cụ thể thì C là công cụ sai; thứ cần là assembly và một hệ thống macro tử tế. Mục tiêu ban đầu của C là giúp chuyển mã cấp hệ thống từ nền tảng này sang nền tảng khác dễ hơn, và việc mất hiệu suất trong quá trình đó là điều đã được dự liệu. Nó giống như thay vì dịch thơ Hindi sang Urdu, ta viết bằng Esperanto rồi tự động dịch sang ngôn ngữ mong muốn. Bạn sẽ không có được hai bài thơ xuất sắc, mà nhanh chóng có được hai bản dịch chất lượng thấp; đó chính là vai trò của C

  • Nếu build bằng FDO/PGO, việc tái bố trí nhánh và block chắc chắn có thể diễn ra. Vì nếu không có FDO, compiler không thể biết mỗi nhánh sẽ được chọn thường xuyên đến mức nào. Trong một số trường hợp, FDO cũng có thể kích hoạt cmov
    Tuy nhiên việc cmov có hiệu quả hơn test/jump thông thường hay không phụ thuộc rất nhiều vào mức độ dự đoán được của nhánh, và thường cmov hoạt động tốt hơn khi nhánh rất khó dự đoán. Nếu nhờ cmov mà nhanh hơn 6 lần, tôi đoán input test gần như toàn là chuỗi ngẫu nhiên gồm s và p. Điều đó không sai, nhưng vì đã tận dụng một thuộc tính không được nhắc đến của dữ liệu để chuyên biệt hóa benchmark, nên bài viết có vẻ hơi dễ gây hiểu lầm

    • Mã test ở đây: https://github.com/414owen/blog-code/blob/master/02-the-same...
      Nó chọn ngẫu nhiên 's' hoặc 'p', và ký tự không thể là gì ngoài 's', 'p' và null kết thúc. Nếu biết đặc tính input này thì cũng có thể tối ưu quá khôn như result += (1 | *s++) - 'r';. Mã quá thông minh, nhưng thể hiện hoàn hảo điểm chính là tận dụng thuộc tính dữ liệu
    • Trong chuỗi, '\0' chỉ có thể gặp tối đa một lần vì khi đó hàm trả về, còn các ký tự khác có thể gặp nhiều lần. Thông tin này trông như thứ compiler có thể tiếp cận mà không cần PGO
      Tất nhiên PGO có ích, và trên máy tôi ra 2,80 giây, tốt hơn đoạn mã ở cuối phần Rearranging blocks. Input được mô tả trong Benchmarking setup và cũng có trong repo: https://github.com/414owen/blog-code/blob/master/01-six-time...
      Ở phần 2 được liên kết cuối bài, họ làm cho mã C nhanh nhất có thể và đánh bại toàn bộ assembly trong bài này. Tôi chưa từng nói dùng assembly nhất thiết là ý hay; tôi chỉ xem tối ưu hóa và giải đọc output của compiler là một thử thách thú vị và một cơ hội học tập tốt

  • Có vẻ tôi đã làm nhanh hơn cả bài viết và bài tiếp theo. Tuy nhiên cái giá là nó chuyên biệt cho trường hợp chuỗi chỉ gồm 's' và 'p'
    Benchmark cũng chỉ test các chuỗi gồm 's' và 'p', nên tôi nghĩ là công bằng. Điểm mấu chốt là khi ký tự tiếp theo là s, ta muốn tăng res thêm 1, nhưng res += c - 'r' thì với s là 1 còn với p là -2 nên thất bại. Nhưng nếu xem 'p' - 'r' như số nguyên không dấu thì sẽ bị underflow và cờ carry được bật, còn adc của x64 cộng hai thanh ghi cùng với cờ carry. Vì vậy có thể thay hai lệnh cmp, cmov bằng một sub, adc. Phiên bản này nhanh hơn bản C trong bài tiếp theo 1,08 lần và nhanh hơn x64-7 cũ 1,66 lần. Tất nhiên nếu dùng SWAR/SIMD thì còn có thể cải thiện hơn nữa

    • Cách tiếp cận thú vị. Có lẽ đáng ra tôi nên nói rõ rằng assembly hơi đơn giản trong 02-the-same-speed-as-c/loop-5.x64.s là phiên bản nhanh nhất tôi có
      Trên máy tôi, loop-5.x64.s mất 0,244 giây, còn triển khai trên mất 0,422 giây. Tôi không biết chính xác vì sao có khác biệt này, và nhìn thì triển khai trên có vẻ nhanh hơn. Vì vậy luôn phải benchmark trên phần cứng sẽ chạy thực tế
    • Đơn giản hơn nữa là cộng tất cả phần tử trong mảng, rồi cuối cùng trừ 'p' * len, sau đó chia cho ('s' - 'p') để lấy số lượng s. Số lượng p là len - s_count
      Phần cộng ban đầu cũng dễ vector hóa. Nếu tôi không nhầm thì nó sẽ chạy được, và vấn đề duy nhất là khả năng overflow của tổng tích lũy. Tôi không có động lực tự benchmark. Sửa: tôi đã bỏ sót phần giảm khi thấy s, nên kết quả cuối cùng là p_count - s_count

  • strlen() hẳn được triển khai khá nhanh, và nếu biết kích thước buffer thì compiler có thể tự động vector hóa vòng lặp bên trong
    Thực tế, đoạn mã gọi len = strlen(buf) rồi trong vòng lặp for cộng (buf[i] == 's') - (buf[i] == 'p') được tự động vector hóa: https://gcc.godbolt.org/z/qYfadPYoq

  • Trước đây tôi từng viết một bộ giải mã UTF-8 bằng Common Lisp cho SBCL. Nó đã có decoder tích hợp sẵn nên chỉ là để luyện tập
    Trừ các tối ưu dễ thấy hiển nhiên, gần như toàn bộ cải thiện hiệu năng đến từ việc cấu trúc mã sao cho compiler sinh lệnh cmov* thay vì rẽ nhánh

    • Tôi tò mò muốn biết ví dụ anh đã đổi mã theo kiểu nào. Và cũng tò mò liệu anh có lặp lại việc disassemble hàm để xem có dùng đúng lệnh không, hay xác nhận cải thiện thực tế bằng benchmark
    • Nếu nhánh được dự đoán đúng thì có khả năng nó nhanh hơn conditional move. Vì rẽ nhánh không làm tăng độ dài critical path
      Bộ giải mã UTF-8 thường chạy rất nhiều trên input toàn ASCII. Tôi tò mò anh đã benchmark bằng loại input nào