Ở bài về tranh chấp mutex tôi hứa sẽ đo thao tác nguyên tử (atomic) so với khóa. Đây là bài đó. Câu hỏi: một bộ đếm chung tăng bằng atomic_fetch_add (không khóa, "lock-free") so với tăng trong một mutex — cái nào nhanh hơn, và có scale không? Tôi đo trong container, và con số ở một luồng suýt khiến tôi khái quát một điều sai cho mọi luồng.
Nguyên tử là gì, khác khóa thế nào
Một thao tác nguyên tử thực hiện đọc-sửa-ghi như một bước không thể chia cắt của phần cứng. atomic_fetch_add(&x, 1) đọc x, cộng 1, ghi lại — và CPU đảm bảo không luồng nào chen được vào giữa. Trên ARM đời mới, nó biên dịch thành một lệnh phần cứng duy nhất ldadd (nhìn assembly xác nhận). Không mutex, không lời gọi hệ thống, không ngủ — nên gọi là lock-free.
Khác với mutex: mutex bảo vệ cả một vùng găng (đoạn code) và có thể khiến luồng ngủ khi tranh chấp (như bài futex đo); atomic chỉ làm nguyên tử một thao tác đơn trên một biến, không bao giờ ngủ. Nghe như atomic phải luôn nhanh hơn. Tôi đo thông lượng (triệu lần tăng mỗi giây) của một bộ đếm chung, tăng dần số luồng.
Đo: atomic thắng ở một luồng, thua ở tám luồng
Bộ đếm CHUNG, triệu ops/giây:
luồng | mutex | atomic
1 | 239 | 626
2 | 42 | 311
4 | 53 | 154
8 | 40 | 25 <-- atomic THUA mutex
Ở một luồng, atomic (626) nhanh hơn mutex (239) khoảng 2,6 lần — đúng như kỳ vọng, vì nó bỏ được toàn bộ chi phí khóa/mở khóa. Ở 2 và 4 luồng, atomic vẫn thắng rõ (311 so với 42, 154 so với 53). Nhìn ba dòng đầu, tôi đã định viết "atomic lock-free thì luôn nhanh hơn và scale tốt hơn khóa, cứ dùng nó".
Nhưng dòng cuối chặn tôi lại: ở tám luồng, atomic tụt xuống 25 triệu ops/giây — chậm hơn cả mutex (40). Con số này phá vỡ khái quát vội vàng của tôi.
Một lần tôi đo hớ: lock-free không phải contention-free
Lý do atomic sụp ở tám luồng nối thẳng với bài trước: dù không có khóa, tất cả tám lõi vẫn đập vào cùng một biến, tức cùng một dòng cache. Phần cứng chỉ cho một lõi sở hữu một dòng cache ở trạng thái ghi tại một thời điểm, nên dòng cache đó phải nảy qua nảy lại giữa các lõi mỗi lần một lõi muốn tăng — đúng cái trần cache-line đã đo ở bài tranh chấp mutex. Atomic bỏ được lời gọi khóa và nguy cơ ngủ, nhưng không bỏ được cái giá vật lý của nhiều lõi giành một dòng cache. Càng đông, càng nảy, càng chậm.
Và tôi đo một biến thể tệ hơn: vòng CAS tự viết. Thay vì fetch_add, ta đọc giá trị cũ rồi dùng compare-and-swap (so-sánh-và-đổi) để ghi giá trị mới, lặp lại nếu có ai chen vào giữa:
CAS loop, bộ đếm chung:
1 luồng: 600 M ops/s | 0 lần thử lại
2 luồng: 297 M ops/s | 13.392.590 lần CAS PHẢI thử lại
4 luồng: 107 M ops/s | 14.454.761 lần thử lại
8 luồng: 7,5 M ops/s | ~9.500.000 lần thử lại <-- chậm nhất mọi cách
Ở một luồng, không ai chen nên 0 lần thử lại, siêu nhanh. Nhưng ở nhiều luồng, mỗi lần một luồng đọc giá trị rồi định CAS, một luồng khác đã kịp thay đổi giá trị đó → CAS thất bại, luồng phải đọc lại và làm lại từ đầu. Ở tám luồng, có mười triệu lần thử lại — hầu hết công sức đổ vào việc đọc-tính-rồi-vứt-bỏ. Thông lượng rơi xuống 7,5 triệu ops/giây, chậm nhất trong mọi cách, kể cả mutex.
Bài học đo lường: "lock-free" không có nghĩa "contention-free" cũng không có nghĩa "scalable". Con số "atomic nhanh gấp 2,6 lần mutex" là thật — ở một luồng. Nhưng nó dụ tôi khái quát cho mọi mức luồng, và sai. Atomic thắng khi tranh chấp thấp; khi tranh chấp cao, nó sụp ngang hoặc tệ hơn khóa, còn CAS tự viết thì thảm họa. Cái bẫy là đo ở một điểm (một luồng) rồi ngoại suy cho cả đường cong. "Nhanh" vô nghĩa nếu chưa hỏi "ở mức tranh chấp nào".
Một cái bẫy nữa của CAS: bài toán ABA
Ngoài chuyện thử lại, CAS còn một cạm bẫy tinh vi mà đo tốc độ không thấy: bài toán ABA. CAS chỉ hỏi "giá trị hiện tại có bằng cái tôi đọc lúc nãy không?" — nó không biết giá trị đó có bị đổi rồi đổi lại trong lúc đó. Hình dung: luồng A đọc con trỏ đầu danh sách là X. Trong lúc A tạm dừng, luồng B lấy X ra, dùng, trả X về (địa chỉ tái sử dụng), rồi đầu danh sách lại là X. Khi A tỉnh dậy, CAS của nó thấy đầu vẫn là X nên thành công — dù cấu trúc bên dưới đã đổi hoàn toàn, dẫn tới hỏng dữ liệu. Với một bộ đếm long tăng đơn thuần thì ABA vô hại (giá trị cứ tăng, không quay lại), nhưng với con trỏ trong cấu trúc lock-free thì đây là lỗi kinh điển, phải chống bằng thẻ phiên bản (tagged pointer) hay con trỏ nguy hiểm (hazard pointer). Đây là lý do viết cấu trúc lock-free đúng khó hơn nhiều so với chỉ "dùng atomic cho nhanh".
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: dùng atomic cho bộ đếm/cờ tranh chấp thấp, không phải cho mọi thứ đồng thời. Một biến atomic thay cho mutex là lựa chọn tốt khi thao tác đơn giản (tăng một bộ đếm, đặt một cờ) và tranh chấp không quá gắt — nó nhanh và gọn. Nhưng đừng tưởng "lock-free" là phép màu cho khả năng mở rộng; dưới tranh chấp cao trên một biến, nó không cứu được bạn khỏi trần cache-line. Giải pháp scale thật vẫn là giảm chia sẻ: mỗi luồng một bộ đếm riêng (đệm ra dòng cache riêng), cộng lại khi cần — đúng cái đã đo ở bài trước.
Hệ quả thứ hai: cẩn thận với vòng CAS tự viết. CAS là nền của mọi cấu trúc lock-free, nhưng một vòng CAS ngây thơ dưới tranh chấp cao biến thành một cơn bão thử-lại đốt CPU mà không tiến triển — chính là 7,5 triệu ops/giây với mười triệu lần thử lại. Nếu bạn thấy mình viết while (!compare_exchange(...)), hãy đo nó dưới tải thật; thường một fetch_add sẵn có (nếu đủ) hoặc giảm chia sẻ sẽ tốt hơn nhiều.
Hệ quả thứ ba là về thứ tự bộ nhớ (memory ordering). Ở phép đo này, relaxed và seq_cst tốn gần bằng nhau (phần cứng ARM đời mới có lệnh atomic riêng cho từng mức), nhưng trên nhiều kiến trúc seq_cst (mặc định) chèn thêm rào chắn bộ nhớ đắt hơn relaxed. Với một bộ đếm thuần túy — nơi bạn không dùng nó để đồng bộ dữ liệu khác — relaxed là đủ và rẻ hơn. Con số mang theo: atomic nhanh hơn mutex khi tranh chấp thấp (626 so với 239 ở một luồng) nhưng cùng sụp vì trần cache-line khi tranh chấp cao (25 so với 40 ở tám luồng), và vòng CAS tự viết còn tệ nhất (7,5 triệu ops/giây, mười triệu lần thử lại); lock-free không phải scalable, và cách scale thật là giảm chia sẻ. Chọn công cụ đồng bộ theo mức tranh chấp thật, đo được, không theo nhãn "lock-free".
Thử ba mươi giây
Trong ngôn ngữ của bạn, tìm kiểu atomic: C11 _Atomic/stdatomic.h, C++ std::atomic, Java AtomicLong, Rust AtomicU64, Go sync/atomic. Thử viết một bộ đếm chung tăng bằng atomic từ 1, 2, 4, 8 luồng và đo ops/giây — bạn sẽ thấy đường cong đi lên rồi chững hoặc đi xuống, không phải tăng mãi. Rồi thử phiên bản "mỗi luồng một bộ đếm riêng, cộng ở cuối" và so: nó sẽ scale gần tuyến tính. Khác biệt giữa hai đường cong đó chính là bài học của cả hai bài (tranh chấp mutex và bài này): trên phần cứng nhiều lõi, thứ quyết định khả năng mở rộng không phải bạn dùng khóa hay atomic, mà là có bao nhiêu lõi cùng giành một dòng cache.
