Khi nhiều luồng cùng cập nhật một dữ liệu chung, cách quen thuộc là dùng mutex (khóa): luồng nào muốn sửa thì khóa lại, sửa, rồi mở khóa; luồng khác chờ. Nhưng có một hướng khác nghe rất hấp dẫn: lock-free — đồng bộ không cần khóa, dùng các lệnh nguyên tử (atomic) của CPU, chủ yếu là CAS (compare-and-swap: "nếu giá trị vẫn là X thì đặt thành Y"). Nhiều người tin "lock-free không khóa nên luôn nhanh hơn mutex". Tôi đo một biến đếm bị nhiều luồng cùng tăng, so mutex với atomic và CAS-loop trong container gcc:13, và con số cho thấy câu chuyện phụ thuộc mức tranh chấp — không có bên nào luôn thắng.

Cấu trúc dữ liệu lock-free

Khóa và chờ, so với thử-lại không khóa

Hai cách đồng bộ khác nhau ở chỗ xử lý xung đột thế nào:

  • Mutex (khóa): một luồng khóa, sửa, mở khóa; các luồng khác chờ. Đơn giản, dễ viết đúng. Nhược điểm: nếu luồng đang giữ khóa bị treo/chậm, cả hệ chờ theo (không đảm bảo tiến độ). Khóa không tranh chấp thì rẻ, nhưng tranh chấp cao thì tốn (chờ, đánh thức, chuyển ngữ cảnh).

  • Lock-free (atomic/CAS): không khóa. Luồng đọc giá trị, tính giá trị mới, rồi CAS ghi lại — nếu trong lúc đó ai đó chen vào (giá trị đã đổi), CAS thất bại và luồng thử lại. Ưu điểm lớn: một luồng chết/treo không kẹt luồng khác (đảm bảo tiến độ toàn hệ). std::atomic::fetch_add là một lệnh atomic sẵn của phần cứng; còn CAS-loop là bạn tự viết vòng lặp thử-lại.

Điểm mấu chốt đo lường: khi nhiều luồng cùng đụng một biến, cache line chứa biến đó phải nhảy qua lại giữa các lõi (phần 13) — và cả mutex lẫn atomic đều chịu chi phí này. Lock-free không xóa được chi phí đó; nó chỉ đổi cách trả.

Đo: atomic thắng khi ít luồng, ngang hoặc thua khi tranh gay gắt

Tôi cho nhiều luồng cùng tăng một biến đếm chung (tổng 40 triệu lần), đo ns mỗi thao tác theo số luồng, cho ba cách: mutex, atomic::fetch_add, và CAS-loop tự viết:

Biến đếm dùng chung, tổng 40 triệu lần tăng, g++ -O2 -pthread:

   luồng | mutex (khóa) | atomic fetch_add | CAS loop
   ------|--------------|------------------|----------
     1   |   4,1 ns     |    1,6 ns        |   1,6 ns
     2   |  31,2 ns     |    3,2 ns        |   2,5 ns
     4   |  18,9 ns     |    6,5 ns        |   8,0 ns
     8   |  22,1 ns     |   20,8 ns        | 141,5 ns

Nhìn dòng 1 luồng (không tranh chấp): mutex 4,1 ns, atomic 1,6 ns. Atomic nhanh hơn, nhưng mutex không đắt — một khóa không tranh chỉ tốn vài nano-giây. Điều này đã bác "mutex luôn chậm".

Nhìn 2–4 luồng (tranh vừa): atomic thắng rõ — 3,2 và 6,5 ns so với mutex 31,2 và 18,9 ns. Ở mức tranh chấp vừa, fetch_add không phải vào nhân, không chờ, nên nhanh hơn hẳn mutex. Đây là sân của lock-free.

Nhìn dòng 8 luồng (tranh gay gắt) — chỗ phá vỡ "lock-free luôn nhanh hơn": atomic fetch_add tụt xuống 20,8 ns, gần bằng mutex 22,1 ns. Vì cache line của biến đếm phải ping-pong liên tục giữa 8 lõi, throughput không còn scale — ns/op tăng theo số luồng thay vì giảm. Và CAS-loop tự viết thì tệ hẳn: 141,5 ns, chậm hơn mutex 6,8 lần. Vì mỗi lần một luồng CAS thất bại (giá trị đã đổi), nó phải thử lại từ đầu — càng đông luồng, càng nhiều lần thử lại phí công. fetch_add (một lệnh phần cứng) tránh vòng lặp thử-lại nên tốt hơn CAS-loop khi đông.

Chú ý dáng chung: không cách nào scale — ns/op ở 8 luồng đều tệ hơn ở 1 luồng, vì tất cả tranh một cache line. Lock-free không phải phép màu chống tranh chấp.

Một lần tôi đo hớ: "lock-free luôn nhanh hơn mutex" và "mutex luôn chậm nên tránh"

Tôi vào đo với niềm tin phổ biến: "lock-free không dùng khóa, không chờ, nên chắc chắn nhanh hơn mutex — cứ dùng atomic/CAS thay khóa là được". Đo phá tan: ở tranh chấp gay gắt (8 luồng, một biến), atomic fetch_add chỉ ngang mutex (20,8 vs 22,1 ns), và CAS-loop tự viết còn tệ hơn mutex 6,8 lần (141,5 ns) vì thử-lại liên tục cộng cache line nhảy giữa các lõi. "Không khóa" không có nghĩa "không tranh chấp" — dữ liệu chung vẫn phải đồng bộ qua cache, và lock-free trả chi phí đó dưới dạng retry. Chưa kể lock-free cực khó viết đúng: các bẫy ABA, thứ tự bộ nhớ (memory ordering), khiến một cấu trúc lock-free tự viết dễ sai một cách tinh vi.

Nhưng đo cũng phá luôn niềm tin ngược: "mutex là khóa, khóa thì chậm, nên tránh mutex bằng mọi giá". Sai: mutex không tranh chấp chỉ tốn 4,1 ns (một luồng) — rất rẻ; và ngay ở 8 luồng, mutex (22,1 ns) còn tốt hơn CAS-loop tự viết (141,5 ns). Mutex đơn giản, dễ viết đúng, và ở phần lớn workload (tranh chấp thấp-vừa, hoặc vùng khóa ngắn) nó đủ nhanh. Né mutex để tự viết lock-free thường là đánh đổi đúng đắn và đơn giản lấy phức tạp và dễ sai mà không có lợi tốc độ tương xứng.

Bài học đo lường: lock-free (atomic/CAS) vs mutex phụ thuộc TRANH CHẤP: ít luồng — atomic nhanh hơn mutex (1 luồng 1,6 vs 4,1 ns; 2-4 luồng atomic thắng rõ); tranh GAY GẮT (8 luồng, một biến) — atomic fetch_add ~ngang mutex (20,8 vs 22,1 ns), CAS-loop tự viết TỆ HƠN mutex 6,8x (141,5 ns) do retry + cache line ping-pong (phần 13). Không cách nào scale khi tranh một biến. Mutex không-tranh rẻ (4 ns), đơn giản, dễ đúng; lock-free cực khó viết đúng (ABA, ordering). Nếu tôi tin "lock-free luôn nhanh" tôi tự viết CAS-loop rồi thua mutex; nếu tin "mutex luôn chậm" tôi né một công cụ đơn giản và đủ tốt.

Vì sao điều này quan trọng khi lập trình

Hệ quả đầu tiên: mặc định dùng mutex (hoặc atomic sẵn như fetch_add) — chỉ tự viết lock-free khi đo cho thấy thật sự cần. Với tranh chấp thấp-vừa và vùng khóa ngắn, mutex đủ nhanh và đúng. Nếu cần một biến đếm/cờ chia sẻ, dùng std::atomic với thao tác sẵn (fetch_add, exchange) — chúng là lock-free phần cứng, nhanh, và đúng mà không phải tự lo ordering. Đừng nhảy vào tự cài lock-free stack/queue trừ khi hồ sơ hiệu năng chỉ đúng chỗ đó.

Hệ quả thứ hai: giảm tranh chấp quan trọng hơn chọn cơ chế đồng bộ. Cả mutex lẫn atomic đều tệ khi nhiều luồng đụng một điểm nóng. Cách thắng thật là đừng chia sẻ điểm nóng: đếm cục bộ mỗi luồng rồi cộng cuối (sharding), chia dữ liệu theo luồng, dùng cấu trúc per-thread. Một biến đếm sharded scale tuyến tính, trong khi một biến chung không cách nào scale dù mutex hay lock-free. Kiến trúc giảm chia sẻ đánh bại mọi tối ưu vi mô về khóa.

Hệ quả thứ ba là tinh thần đo lường: "không khóa" nghe như "không chi phí", nhưng chi phí đồng bộ nằm ở cache, không ở khóa — và nó không biến mất. Con số mang theo: lock-free thắng mutex khi ít tranh chấp (atomic fetch_add 1,6-6,5 ns vs mutex 4-31 ns ở 1-4 luồng), nhưng tranh gay gắt thì ngang (fetch_add ~mutex ở 8 luồng) hoặc thua (CAS-loop 141,5 ns = 6,8x mutex) do retry + cache ping-pong; không cách nào scale khi tranh một biến. Mutex không-tranh rẻ (4 ns) và đơn giản; lock-free cực khó đúng. Ưu tiên giảm tranh chấp (sharding) hơn đổi cơ chế. Đo throughput theo số luồng mới thấy sự thật — một phép đo đơn luồng sẽ nói dối.

Thử ba mươi giây

Viết một biến đếm bị nhiều luồng cùng tăng, theo ba cách: một dùng std::mutex bảo vệ một int, một dùng std::atomic<long>::fetch_add, một dùng vòng lặp compare_exchange_weak (CAS tự viết). Chạy tổng cùng số lần tăng, chia cho 1, 2, 4, 8 luồng, và bấm giờ thời gian thực (dùng steady_clock, không phải clock() — nó cộng CPU của mọi luồng). Bạn sẽ thấy ở một luồng atomic nhanh hơn mutex nhưng mutex vẫn rẻ; ở vài luồng atomic thắng rõ; ở tám luồng cả ba đều chậm lại (ns/op tăng theo số luồng), atomic gần bằng mutex, và CAS-loop tệ hẳn vì thử lại liên tục. Cuối cùng, thử phiên bản mỗi luồng đếm riêng rồi cộng cuối — nó scale, vì không tranh một cache line. Ba mươi giây đó cho bạn thấy điều mà "lock-free không khóa nên nhanh hơn" giấu đi: chi phí đồng bộ nằm ở cache line chia sẻ, không ở bản thân cái khóa — và cách nhanh nhất thường là đừng chia sẻ, chứ không phải đổi khóa lấy CAS.