- Một tối ưu hóa trong assembly AArch64 nhằm giảm bớt một nhánh trong vòng lặp lại khiến mã chậm hơn 4 lần, và nguyên nhân là do dùng cặp gọi-trả về
bl/ret một cách bất đối xứng, làm bộ dự đoán nhánh bị rối loạn
- Mã gốc mỗi vòng lặp thực hiện hai lần rẽ nhánh là
bl foo và b loop, còn mã sửa đổi cố gắng giảm số nhánh bằng cách dùng một lần bl loop để cố định x30, rồi để nhiều ret quay về cùng một địa chỉ
- Trên M1 Max, khi cộng một mảng 1024 phần tử
float, mã bl/ret bình thường mất 969ns, nhưng cấu trúc một lần bl và nhiều ret chậm xuống 3.85µs; nếu đổi ret thành br x30 thì phục hồi về 913ns
- Bộ đếm hiệu năng của Instruments cho thấy khi cộng 1 tỷ phần tử, cấu trúc
bl/ret bất đối xứng có tỷ lệ dự đoán sai nhánh trả về khoảng 93%, đồng thời FETCH_RESTART, MAP_DISPATCH_BUBBLE, và MAP_REWIND cũng tăng mạnh
- Các cách cài đặt nhanh hơn tiếp tục đi từ inline
foo, Rust iter().sum(), cho đến NEON SIMD và unroll vòng lặp thủ công; phiên bản SIMD cuối cùng giảm xuống còn 94ns, nhưng vì thứ tự cộng số thực dấu phẩy động thay đổi nên kết quả có thể khác
Tác dụng ngược phát sinh trong một vòng lặp AArch64
- Hàm ví dụ duyệt qua một mảng
float, truyền từng giá trị vào foo, và foo sẽ cập nhật giá trị tích lũy g
- Bản chuyển đổi AArch64 đơn giản có luồng như sau
- Kiểm tra
n == 0 ở đầu vòng lặp
- Đọc giá trị bằng
ldr s1, [x0], #4
- Gọi chương trình con bằng
bl foo
ret của foo quay về lệnh ngay sau bl- Dùng
b loop để quay lại đầu vòng lặp
foo có dạng gần giống một naked function, dùng cùng stack frame và thanh ghi với hàm cha, đọc s1 và cộng dồn vào s0
Vai trò của bl và ret
bl là lệnh branch and link, nhảy đến nhãn chỉ định và lưu địa chỉ lệnh kế tiếp vào thanh ghi liên kết lr hay x30ret nhảy tới địa chỉ đang nằm trong thanh ghi liên kết- Trong cấu trúc ban đầu,
bl foo và ret khớp cặp với nhau, và ret luôn quay về lệnh ngay sau bl
Tối ưu hóa “giảm một nhánh” đã thất bại
- Cấu trúc sửa đổi cố giảm đi một nhánh trong vòng lặp mà không thay đổi
foo
- Ở đầu hàm, gọi
bl loop để ghi địa chỉ bắt đầu của loop vào x30
- Kiểm tra điều kiện kết thúc vòng lặp rồi rơi thẳng vào mã
foo mà không cần nhánh riêng
ret của foo quay lại loop đang nằm trong x30
- Trong cấu trúc này,
x30 không thay đổi bên trong thân vòng lặp, nên các ret lặp lại luôn quay về cùng một địa chỉ
foo đơn giản chỉ là đoạn mã một dòng cộng float như sau
foo:
fadd s0, s0, s1
ret
- Trong trường hợp này, toàn bộ hàm sẽ tính tổng của mảng
float đầu vào
Kết quả benchmark và vấn đề dự đoán nhánh
- Benchmark mảng 1024 phần tử trên CPU M1 Max bằng
criterion
bl/ret bình thường: 969ns- Một lần
bl, nhiều ret: 3.85µs
- Đoạn mã giảm được một nhánh lại chậm hơn khoảng 4 lần so với mã gốc dùng hai nhánh
- Cliff và Dan cho rằng bộ dự đoán nhánh đã bị làm rối vì các cặp
bl/ret không còn khớp nhau
- Theo tài liệu ARM,
RET giúp bộ xử lý nhận ra đây là một lần trả về hàm để dự đoán nhánh chính xác hơn
BR LR về mặt chức năng cũng có thể làm điều tương tự- Nhưng
RET là một lệnh riêng mà bộ xử lý có thể nhận diện là trả về hàm
- Nếu dự đoán nhánh đúng, pipeline sẽ nhận được đúng lệnh và tránh phải chờ lệnh từ bộ nhớ
Ngăn xếp địa chỉ trả về và thí nghiệm với br x30
- Bộ dự đoán nhánh có thể nội bộ duy trì một ngăn xếp địa chỉ trả về của hàm
- Khi chạy
bl, nó push địa chỉ trả về lên ngăn xếp
- Khi thấy
ret, nó giả định sẽ quay về địa chỉ trả về của bl gần nhất
- Từ địa chỉ đó, nó bắt đầu prefetch và speculative execution, rồi pop ngăn xếp
- Cách này hoạt động tốt khi
bl/ret là những cặp khớp nhau
- Nếu nhiều
ret lặp đi lặp lại cùng dùng một địa chỉ, dự đoán có thể thất bại và dẫn tới prefetch vô ích, speculative execution sai, cùng các lần dừng hoặc flush pipeline
- Theo gợi ý của Dan, khi đổi
ret thành br x30, hiện tượng tụt hiệu năng biến mất
bl/ret bình thường: 969ns- Một lần
bl, nhiều ret: 3.85µs
- Một lần
bl, nhiều br x30: 913ns
- Phiên bản
br x30 chỉ thực hiện một nhánh mỗi vòng lặp nên nhanh hơn bản gốc một chút
Bộ đếm hiệu năng của Instruments
- Tác giả dùng Instruments để xem bộ đếm hiệu năng của hai chương trình đầu tiên
- Việc đo được thực hiện khi cộng mảng 1 tỷ phần tử
- Trong trường hợp
bl/ret bất đối xứng, tỷ lệ dự đoán sai nhánh trả về là khoảng 93%
| Bộ đếm |
bl/ret bình thường |
Một lần bl, nhiều ret |
BRANCH_RET_INDIR_MISPRED_NONSPECIFIC |
92 |
928,644,975 |
FETCH_RESTART |
61,121 |
987,765,276 |
MAP_DISPATCH_BUBBLE |
1,155,632 |
7,350,085,139 |
MAP_REWIND |
6,412,734 |
2,789,499,545 |
- Apple không tài liệu hóa đầy đủ các bộ đếm này
- Các bộ đếm khác nhiều khả năng là hiệu ứng downstream của dự đoán nhánh tệ
FETCH_RESTART: có thể là do prefetch saiMAP_DISPATCH_BUBBLE: có thể liên quan đến pipeline stallMAP_REWIND: có thể là speculative execution sai cần phải tua ngược
Cách làm nhanh hơn nữa
- Ví dụ này là mã phục vụ mục đích giáo dục, và lý do
foo là một chương trình con cũng gần với cấu trúc minh họa hơn là “mã nhanh nhất có thể”
- Nếu nội dung của
foo đã biết tại thời điểm build và nằm trong khoảng nhảy tối đa, có thể loại bỏ hoàn toàn bl và ret bằng cách inline
- Tăng tốc từ 969ns xuống 911ns, tức khoảng 6%
- Nếu chỉ viết đơn giản bằng Rust là
f.iter().sum() thì thời gian giảm còn 833ns
pub fn sum_slice(f: &[f32]) -> f32 {
f.iter().sum()
}
SIMD và unroll vòng lặp thủ công
- Bản cài đặt SIMD AArch64 thủ công gồm ba vòng lặp
loop: cộng từng giá trị riêng lẻ vào s0 cho đến khi số phần tử còn lại là bội số của 4simd: cộng 4 giá trị một lần vào thanh ghi vector v1, lặp cho đến khi số phần tử còn lại là bội số của 8simd2: unroll simd gấp đôi để mỗi lần lặp xử lý 8 giá trị và cộng dồn vào v1 và v2
- Khi kết thúc hàm, giá trị trong
v1 và v2 được cộng dồn vào s0 rồi trả về
- Type punning ở đây là coi
x0, vốn là float*, như thể double* để đọc 128 bit tức 4 giá trị float vào d3 và d4
mov v3.d[1], v4.d[0] chuyển 64 bit của d4 vào 64 bit cao của v3fadd v1.4s, v1.4s, v3.4s dùng hậu tố .4s để xử lý như bốn giá trị float
- Bản SIMD này chạy trong 94ns, nhanh hơn khoảng 8.8 lần so với phiên bản Rust tốt nhất trước đó là 833ns
Tổng kết hiệu năng và điểm cần lưu ý
| Cách cài đặt |
Thời gian |
bl/ret bình thường |
969ns |
Một lần bl, nhiều ret |
3.85µs |
Một lần bl, nhiều br x30 |
913ns |
Vòng lặp thông thường dùng b |
911ns |
| Viết lại bằng Rust |
833ns |
| SIMD + unroll vòng lặp thủ công |
94ns |
- Mã SIMD thay đổi thứ tự cộng số thực dấu phẩy động
- Phép cộng số thực dấu phẩy động không có tính kết hợp, nên phiên bản SIMD có thể không cho ra cùng kết quả với mã tuyến tính
- Đây cũng có thể là lý do trình biên dịch không tạo lệnh SIMD cho phép cộng tổng
- Toàn bộ mã nguồn được công bố trên GitHub
- Có thể tái hiện benchmark bằng cách chạy
cargo bench trên máy ARM64
1 bình luận
Các ý kiến trên Hacker News
Đoạn mã tối ưu cuối cùng hoàn thành việc tính tổng một mảng 1024 số dấu phẩy động 32-bit trong 94ns
Trong 94ns đó, người bạn cũ 1MHz 6502 có lẽ mới bắt đầu cân nhắc xem có nên phát tín hiệu cho chip nhớ để lấy byte đầu tiên của lệnh đầu tiên trong chương trình hay không
Tuy nhiên, đoạn mã này hoàn toàn dựa trên giả định rằng nó chạy trong cache. Nếu không, ngay cả chiếc M1 Max mạnh mẽ trong bài viết cũng đã phải đứng chờ lần lấy dữ liệu bộ nhớ đầu tiên. DRAM chậm
Raymond Chen đã nói về nội dung tương tự gần 20 năm trước: https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...
Ngoại trừ hiểu biết cơ bản về tính chất bán dẫn của silicon và doping, gần như chẳng có gì trực giác ở đây cả. Nếu chưa nhìn thấy sơ đồ mạch die, dây nối và đường đi, thì gần như không có lý do gì để kỳ vọng A sẽ nhanh hơn B trừ khi kỹ sư và datasheet nói rõ như vậy. Tôi nghĩ điều này đặc biệt đúng với ARM
Điểm mà bài này bổ sung là một chỉnh sửa đơn giản: thay
retbằng một lệnhbrkhác. Nhờ đó cặp này lại “đối xứng”, và có thể có mã nhanh hơn một chút mà không làm hỏng bộ dự đoán nhánhTất nhiên điều gì cũng có thể xảy ra, và một vòng lặp bình thường để tính tổng mảng thực sự là dạng chỉ thị máy tính cộng dồn từng phần tử một
Nhưng chẳng hạn, dùng SIMD để tạo bốn giá trị tích lũy song song rồi cộng lại ở cuối thì khó có thể nói là sai hơn so với cộng từng phần tử một
Về cơ bản, phép cộng số dấu phẩy động nên được xem là có một khoảng sai số, và các đáp án nằm trong khoảng đó phải được coi là hợp lệ. Nếu bạn biết điều gì đặc biệt về các số dấu phẩy động đầu vào, ngôn ngữ nên cung cấp cách biểu đạt rõ ý định đó. Vì vòng lặp cơ bản nhất là mặc định, tôi nghĩ mặc định cũng nên cho hiệu năng tốt nhất
Cách ngây thơ cộng từng số trong vòng lặp là hiển nhiên, nhưng có những phương pháp tinh vi hơn đưa ra giới hạn tốt hơn cho tổng sai số tích lũy, và phép cộng Kahan là một ví dụ nổi tiếng: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
Nếu là dữ liệu streaming thì có thể bạn chỉ có thể cộng từng số một, nhưng nếu có thể dùng N bộ đệm kích thước cố định, sẽ nảy sinh các vấn đề như khi một số mới đi vào thì chọn tập con nào để tạo tổng con, cộng nó vào tổng tích lũy ra sao, và liệu lựa chọn đó có cải thiện sai số theo cách chứng minh được hay không
Ví dụ, tính
[1e50, -1e50, 1e3, 1e3]theo(((1e50 + -1e50) + 1e3) + 1e3)sẽ được2e3, nhưng tính theo((1e50 + 1e3) + (-1e50 + 1e3))thì sẽ thành0Khi cộng nhiều giá trị nhỏ vào một giá trị rất lớn cũng tương tự,
(((1e3 + 1e3) + 1e3) ... + 1e50)và(((1e50 + 1e3) + 1e3) ... + 1e3)khác nhau khá nhiềuNếu kết quả số học không ổn định giữa các lần build thì sẽ là cơn ác mộng thật sự. Không thể để việc build lại phần mềm với cùng đầu vào rồi chạy lại cho ra kết quả khác
Tôi cũng từng gặp một trường hợp đặc thù của Intel ngày xưa: FPU dùng thanh ghi 80-bit bên trong nhưng dùng 64-bit trong bộ nhớ, nên khi thời điểm nạp/xả thanh ghi thay đổi thì thời điểm làm tròn cũng thay đổi và kết quả cũng khác. Có thể đặt cờ FPU toàn cục khi chương trình khởi động để buộc làm tròn sau mỗi phép toán
Luôn có một đáp án đúng, và tôi nghĩ compiler ít nhất không nên thực hiện thay đổi sai ở chế độ mặc định. Tuy nhiên, cách để lập trình viên biểu đạt ý định rõ ràng hơn thì luôn đáng hoan nghênh
Việc áp dụng SIMD cho vòng lặp dấu phẩy động lẽ ra có thể trở thành mặc định, nhưng vì nó sẽ làm hỏng nhiều mã hiện có và thường khiến đầu ra thay đổi không quyết định, nên nó trở thành một tính năng mà lập trình viên phải chọn rõ ràng
Hơn nữa, nhiều lập trình viên có thể không biết điều này, nên nếu
float Sum(float[] values)bắt đầu trả về giá trị khác, họ có thể không có cách nào biết nguyên nhân là do vector hóa. Vì vậy, chẳng hạn thư viện chuẩn .NET dùng SIMD chointegers.Sum()nhưng không dùng chofloats.Sum()Chỉ đọc dòng “sau khi kiểm tra kết thúc vòng lặp, nó rơi thẳng vào trong hàm
foomà không có nhánh” là tôi đã nghĩ “à, vấn đề là ở đó rồi”Tôi tưởng đây sẽ là một câu chuyện sâu về các heuristic của bộ dự đoán nhánh hào nhoáng, nhưng cuối cùng lại là vi phạm heuristic cơ bản
Không nên nghĩ rằng có thể đạt được mức tăng tốc khổng lồ bằng cách dùng các lệnh
call/retkhông khớp nhau. Việc bộ dự đoán nhánh duy trì một shadow stack các địa chỉ trả về đã là cách làm có từ hàng chục năm trướcVì vậy những rủi ro như thế này nên được ghi trong tài liệu, nhưng nhà thiết kế có quyền giả định rằng người viết assembly trực tiếp đã đọc tài liệu
Mặt khác nữa, Sophie Wilson đã viết bản hiện thực BBC BASIC ban đầu cho ARM, nhưng khi đó chưa có bộ dự đoán nhánh. Dù vì là 32-bit nên quy tắc khác nhau, tôi vẫn tò mò AArch64 làm mã chậm đi như thế nào khi các giả định kiến trúc thay đổi
Đây là tham chiếu SNL kinh điển “Do not taunt happy fun ball”: https://www.youtube.com/watch?v=GmqeZl8OI2M
Đừng bỏ qua việc đây là bài viết năm 2023. Hiện giờ nó đã hơi cũ, và từ Rust 1.78 trở đi trình biên dịch dùng unroll vòng lặp mạnh tay hơn và một chút SIMD: https://godbolt.org/z/zhbobW7rr
Bài gốc nói “nhìn assembly thì thấy đang unroll vòng lặp” và liên kết tới https://godbolt.org/z/Kv77abW6c, nhưng nó đang dùng “Rust Nightly” vốn thay đổi liên tục. Hiện giờ việc unroll vòng lặp nhiều hơn
Unroll vòng lặp bắt đầu từ Rust 1.59: https://godbolt.org/z/5PTnWrWf7
Theo mã trên GitHub thì họ đã dùng Rust
1.67.0-nightly, bản 2022-11-27Tôi đã tự chạy benchmark trên cùng phần cứng với nightly Rust 1.81 mới nhất, có unroll vòng lặp mạnh tay, nhưng không có khác biệt, tốc độ vẫn như 1,5 năm trước
Đây là bài viết năm 2023. Thảo luận khi đó: https://news.ycombinator.com/item?id=34520498
Việc đăng lại sau khoảng một năm thì không sao, và liên kết tới luồng cũ là dành cho độc giả muốn tìm hiểu thêm
Vì không quá quen với assembly ARM/ARM64 nên tôi đã bối rối không rõ
x0tăng lên thế nàoconst float f = *data++;trở thànhldr s1, [x0], #4, và lệnh này có vẻ vừa đọc giá trị vừa tăngx0thêm 4Có thể dùng cả số âm nên có lẽ cũng duyệt ngược được. Khá hay. Có vẻ x86_64 không có một lệnh đơn lẻ vừa đọc vừa tăng
lodsvàstoslần lượt thực hiện đọc/ghi đồng thời tăngrsihoặcrdi. Cũng cómovsđể sao chép giữa hai địa chỉ bộ nhớ đồng thời tăng chúngThường dùng cùng
rep, lặprcxlần. Ví dụ,memset10 byte có thể ở dạngmov rcx, 10,mov rdi, dest,mov rax, 0,rep stosbDùng hậu tố
w,d,qthì lần lượt tiến thêm 2, 4, 8 byteBài viết hay, nhưng hơi tiếc là trong bảng cứ chuyển qua lại giữa đơn vị µs và ns, khiến việc lướt qua để so sánh trở nên khó khăn
Tôi ngạc nhiên là trước khi tối ưu mã, họ không thử cách kém thông minh hơn trước
Nếu viết lại assembly thì ở cuối vòng lặp chỉ cần một nhánh, và với
X1cũng có thể xử lý bằng một phép toán ALU duy nhất thay vì tách riêng phép trừ để so sánh và phép giảmĐi xa hơn nữa thì cứ inline
foo, và có thể bỏ luôn lệnhRETmà không cần thủ thuậtBL/RETkhông khớp. Tôi chưa tự benchmark nên không biết thực tế sẽ nhanh hơn bao nhiêucbnzphải làcbz. CBZ rẽ nhánh tới nhãn nếu thanh ghi bằng 0, còn CBNZ rẽ nhánh nếu khác 0