Ở bài mutex ta thấy khóa không tranh chấp rất rẻ. Nhưng có một cách khác để cập nhật dữ liệu chia sẻ mà không cần khóa chút nào: các biến atomic. Chúng cho phép đọc-sửa-ghi nguyên tử — không thể bị xen giữa — bằng chỉ thị phần cứng, nên được ca ngợi là "lock-free" và nhanh. Câu hỏi: atomic thật sự rẻ đến đâu, và "lock-free" có nghĩa là thoát khỏi cái giá của tranh chấp không? Tôi đo, và cả ba niềm tin phổ biến về atomic đều lệch.
Hai kiểu atomic: fetch_add và CAS
Có hai thao tác atomic hay dùng. atomic_fetch_add cộng một giá trị vào biến một cách nguyên tử — trên ARM hiện đại (LSE) đây là một lệnh phần cứng (ldadd) thực hiện đọc-cộng-ghi không thể bị chia cắt, và không thử lại. CAS (compare_exchange — so sánh và đổi) đổi giá trị chỉ khi nó vẫn đúng như bạn kỳ vọng; nếu một luồng khác đã chen vào và đổi nó, CAS thất bại và bạn phải thử lại trong một vòng lặp. CAS mạnh hơn (cập nhật có điều kiện, nền tảng của mọi cấu trúc lock-free) nhưng mang theo chi phí thử lại.
Tôi đo trong container gcc:13 (AArch64, 10 lõi), so với mutex ở bài trước.
Không tranh chấp: rẻ, nhưng không miễn phí
atomic_fetch_add KHÔNG tranh chấp (1 luồng) : 1,59 ns/thao tác
(so với mutex không tranh chấp : 3,3 ns)
atomic không tranh chấp là 1,59 ns — rẻ hơn mutex khoảng 2 lần. Đây là niềm tin thứ nhất bị điều chỉnh: atomic không miễn phí (nó vẫn là một phép đọc-sửa-ghi trên bộ nhớ, có rào ngầm), và nó chỉ nhanh hơn mutex khoảng 2 lần, cùng bậc độ lớn — không phải "trăm lần" như đồn. Với một biến không bị giành, cả hai đều là thao tác vài nano giây.
Có tranh chấp: lock-free không phải contention-free
Đây là chỗ niềm tin thứ hai sụp. Cho nhiều luồng cùng fetch_add vào một biến chung:
T=1 : 1,6 ns T=2 : 5,3 ns T=4 : 9,1 ns T=8 : 16,6 ns
Chi phí mỗi thao tác tăng ~10 lần từ 1 lên 8 luồng. atomic "lock-free" vẫn chậm đi khi tranh chấp — vì dù không có khóa, biến vẫn nằm trên một dòng cache, và khi nhiều lõi cùng ghi vào nó, dòng cache đó phải nảy qua lại giữa các lõi (cache-line bouncing). Mỗi lõi muốn ghi phải giành quyền sở hữu độc quyền dòng cache, đẩy nó ra khỏi cache của lõi khác. Lock-free không phải contention-free. Cái đắt của việc chia sẻ không đến từ cơ chế khóa, mà từ vật lý của cache coherence — và atomic không thoát khỏi nó.
Còn vòng CAS thì tệ hơn hẳn khi đông:
T=1 : 1,6 ns (0 thử lại) T=4 : 8,0 ns (0,25 thử lại/op)
T=8 : 128,9 ns (3,76 thử lại/op)
Ở 8 luồng, mỗi thao tác CAS tốn 128,9 ns — và trung bình 3,76 lần thử lại cho mỗi lần thành công. Vì nhiều luồng cùng đọc giá trị cũ rồi cùng thử đổi; chỉ một thắng, những luồng còn lại thấy giá trị đã đổi, thất bại, phải đọc lại (dòng cache đang nảy) và thử lại. So với mutex ở bài trước — 27 ns ở 8 luồng cho vùng tới hạn ngắn — vòng CAS chậm hơn cả mutex.
Một lần tôi đo hớ: ba niềm tin cùng lệch
Tôi vào đo với ba niềm tin phổ biến về atomic, và cả ba đều bị đo phá. Một: "atomic miễn phí" — không, 1,6 ns, rẻ nhưng thật. Hai: "atomic lock-free nên không bị tranh chấp" — sai hẳn, fetch_add vẫn chậm 10 lần khi tranh chấp vì cache nảy; lock-free chỉ nghĩa là không có khóa/không thể deadlock, không nghĩa là không tốn khi giành. Ba: "atomic luôn nhanh hơn mutex nhiều lần" — fetch_add nhanh hơn mutex chút ít (cùng bậc), nhưng một vòng CAS dưới tranh chấp cao lại chậm hơn cả mutex (128,9 so 27 ns), vì công thử-lại bị phí.
Sự thật chung, và là bài học đo lường của bài: cái đắt không nằm ở việc bạn dùng mutex hay atomic, mà ở chỗ nhiều lõi cùng GHI vào một ô nhớ. Chia sẻ một biến ghi giữa các lõi luôn tốn — vì dòng cache phải nảy — dù bạn bọc nó bằng khóa hay bằng lệnh atomic. Đổi mutex sang atomic không giải quyết được contention; nó chỉ đổi hình dạng của cái giá.
Vì sao fetch_add thắng vòng CAS
Chênh lệch giữa fetch_add (16,6 ns) và vòng CAS (128,9 ns) ở 8 luồng đáng để hiểu, vì nó dạy một điều tinh tế về phần cứng. fetch_add trên ARMv8.1+ là một lệnh atomic duy nhất (ldadd) mà con chip thực hiện không bao giờ thất bại: nó giành dòng cache, cộng, xong — mỗi lõi được phục vụ lần lượt, không ai phải "làm lại". Vòng CAS thì ngược lại: nó là mẫu "đọc giá trị cũ → tính giá trị mới → thử đổi, nếu ai chen vào thì lặp". Dưới tranh chấp cao, nhiều luồng cùng đọc một giá trị cũ, cùng tính, rồi chỉ một luồng đổi thành công; phần còn lại phí toàn bộ công vừa làm và phải đọc lại dòng cache đang nảy. Đó là lý do CAS đo ra 3,76 lần thử lại mỗi op và chậm gấp 8 lần fetch_add. Bài học đo lường, đúng như đo lường vi mô đúng cách nhấn mạnh: hai thao tác "cùng là atomic" có thể có hành vi tranh chấp khác hẳn — nên khi chọn giữa fetch_add và một vòng CAS, hãy đo ở đúng mức tranh chấp bạn sẽ gặp, đừng giả định "atomic là atomic".
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng đổi mutex sang atomic với kỳ vọng "lock-free nên nhanh". Nếu điểm nóng là một biến bị nhiều luồng cùng ghi, atomic hóa nó vẫn để lại cache-line bouncing — và nếu bạn dùng vòng CAS, có thể còn chậm hơn. Cách đúng để tăng tốc là giảm chia sẻ, không phải đổi cơ chế đồng bộ.
Hệ quả thứ hai: cho mỗi luồng một ô riêng, gộp cuối cùng. Thay vì tất cả cùng fetch_add vào một bộ đếm chung, cho mỗi luồng một bộ đếm cục bộ (không chia sẻ, không nảy cache), rồi cộng tất cả lại một lần khi xong. Đây là mẫu "reduction" mà ta sẽ đo kỹ ở phần sau; nó biến một điểm nóng tranh chấp thành các phép cộng cục bộ rẻ. Với fetch_add một biến chung ở 8 luồng là 16,6 ns/op; với bộ đếm cục bộ thì mỗi op quay về ~1 ns không tranh chấp.
Hệ quả thứ ba là tinh thần đo lường: hiểu một công cụ giải quyết gì và không giải quyết gì. Con số mang theo: atomic không tranh chấp ~1,6 ns (rẻ hơn mutex ~2 lần, cùng bậc); nhưng khi nhiều luồng cùng ghi một biến, fetch_add VẪN chậm 10 lần (16,6 ns ở 8 luồng) vì dòng cache nảy — lock-free KHÔNG phải contention-free — và một vòng CAS ở 8 luồng còn chậm hơn cả mutex (128,9 so 27 ns) vì phải thử lại ~3,76 lần/op; chia sẻ một ô nhớ ghi giữa nhiều lõi luôn tốn, dù mutex hay atomic. Muốn nhanh, giảm chia sẻ — đừng chỉ đổi khóa.
Thử ba mươi giây
Cho 8 luồng cùng atomic_fetch_add vào một biến chung 10 triệu lần mỗi luồng, đo thời gian mỗi thao tác — bạn sẽ thấy nó chậm hơn nhiều so với một luồng, dù "không có khóa". Rồi đổi thành: mỗi luồng cộng vào một biến long cục bộ của riêng nó, rồi cộng 8 kết quả lại ở cuối — đo lại, mỗi phép cộng giờ quay về ~1 ns và tổng thời gian giảm mạnh. Ba mươi giây đó dạy bạn điều cốt lõi về đồng thời hiệu năng: nút thắt không phải "khóa hay không khóa", mà là "có chia sẻ ô nhớ ghi hay không" — và cách nhanh nhất luôn là đừng chia sẻ khi không cần.
