Atomic 'lock-free' vẫn chậm 27 lần khi đông luồng — và không hề nhanh hơn mutex

Hình dung một tấm bảng trắng chung và đúng một cây bút. Một người muốn viết: cầm bút, viết, xong — tức thì. Nhưng tám người cùng cần viết lên cùng tấm bảng bằng cùng cây bút đó: mỗi người phải chờ bút được chuyền tới tay mình, và cây bút cứ nảy vòng quanh phòng — càng đông, càng nhiều lượt chuyền, càng chậm. Trớ trêu là đọc bảng thì miễn phí: ai cũng nhìn cùng lúc được. Một biến atomic mà nhiều luồng cùng ghi chính là cây bút chung đó, và "lock-free" không hề cứu bạn khỏi những lượt chuyền bút.

Ở atomic và CAS ta thấy thao tác nguyên tử là nền của code lock-free — cập nhật không cần khóa. Từ đó dễ hình thành một niềm tin: "atomic là lock-free nên nó rẻ, và nhanh hơn khóa". Nhưng sê-ri này dạy ta nghi ngờ mọi chữ "rẻ" và "nhanh hơn" cho tới khi đo. Tôi đo chi phí của một thao tác atomic khi bị nhiều luồng tranh nhau, và con số cho thấy "lock-free" không hề đồng nghĩa với "miễn phí" — chi phí chỉ chuyển chỗ, và dưới tranh chấp nặng nó lớn không kém một cái khóa.

Atomic rẻ khi cô đơn, đắt khi đông

Một thao tác atomic như fetch_add được phần cứng đảm bảo nguyên tử — không cần khóa, không ngủ/thức. Khi một luồng dùng nó, cực nhanh: chỉ vài chu kỳ, dữ liệu nằm sẵn trong cache của lõi đó (bút trong tay bạn). Nhưng khi nhiều luồng cùng fetch_add vào cùng một biến, biến đó nằm trên một dòng cache, và mỗi lần một lõi muốn ghi, nó phải giành quyền sở hữu độc quyền dòng cache — dòng nảy qua nảy lại giữa các lõi, đúng cây bút chuyền vòng. Mỗi thao tác phải trả một lần chuyển dòng cache-to-cache, và chi phí đó tăng theo số luồng tranh. Tôi đo trong container gcc:13 (10 lõi, dòng cache 64B).

Đo (a): fetch_add đắt dần theo số luồng

số luồng tranh | ns / fetch_add
1              |  1,6 ns
2              |  3,0 ns
4              |  5,2 ns
8              | 44,1 ns

Một luồng: 1,6 ns — gần như miễn phí (dòng cache nằm yên trong lõi đó). Nhưng 8 luồng: 44,1 ns — chậm hơn 27 lần! Không phải vì bản thân phép cộng đắt, mà vì cái dòng cache chứa biến bị 8 lõi giành nhau — mỗi thao tác phải kéo dòng về từ lõi vừa ghi. Chi phí này không cố định: nó là hàm của số luồng tranh. Bài học đầu: một atomic "rẻ" trong microbenchmark một luồng có thể đắt gấp hàng chục lần trong code thật nhiều luồng cùng đập vào nó.

Để so sánh: một mutex bị tranh chấp cho vùng tới hạn ngắn cũng ở khoảng vài chục ns. Nghĩa là một atomic bị tranh chấp nặng không hề nhanh hơn một khóa — cả hai đều bị chặn bởi cùng thứ: dòng cache nảy giữa các lõi.

Đo (b): đọc rẻ, ghi đắt, CAS-loop tệ nhất

Không phải mọi thao tác atomic đắt như nhau khi tranh chấp. Đo bốn loại ở 8 luồng:

load (đọc chung)      :   0,1 ns/op   <- gần MIỄN PHÍ
fetch_add (ghi chung) :  44,6 ns/op
exchange (ghi chung)  :  44,3 ns/op
CAS-loop (ghi chung)  : 119,1 ns/op   <- TỆ NHẤT

Ba kết quả đáng nhớ. Thứ nhất, load chung gần như miễn phí (0,1 ns) ngay cả với 8 luồng — vì đọc không làm dữ liệu cũ đi, mọi lõi giữ một bản "Shared" song song, không ai invalidate ai (đúng đọc-chung rẻ, ghi-chung đắt; ai cũng nhìn bảng được cùng lúc). Thứ hai, fetch_add và exchange (đều là ghi) tốn ~44 ns — mỗi ghi bounce dòng cache. Thứ ba, và tệ nhất: vòng CAS tốn 119 ns, gấp gần ba lần fetch_add. Vì khi CAS thất bại (giá trị đã bị luồng khác đổi giữa lúc đọc và lúc CAS), nó phải thử lại — mỗi retry là một lần đọc lại (bounce) rồi CAS lại (bounce), đúng cầm bút lên thấy bảng đã bị viết khác nên phải xóa làm lại. Dưới tranh chấp cao, một vòng CAS có thể thất bại nhiều lần trước khi thành công. Đây là lý do fetch_add (một thao tác phần cứng không cần retry) thường tốt hơn một vòng CAS tự viết khi chỉ cần tăng.

Đo (c): per-thread nhanh 96 lần

Vậy khi cần đếm/tổng hợp qua nhiều luồng mà không muốn trả cái giá tranh chấp này, làm sao? Câu trả lời quen thuộc: đừng đập vào một atomic — cho mỗi luồng một ô riêng (trên dòng cache riêng), cộng lại khi cần tổng. Mỗi người một tấm bảng:

fetch_add CHUNG (1 biến)     : 43,6 ns/op  (184 triệu/giây)
fetch_add PER-THREAD (ô riêng): 0,5 ns/op  (17.694 triệu/giây)
chung / per-thread           : 96× chậm hơn

Per-thread nhanh hơn 96 lần (0,5 ns so với 43,6 ns) — vì mỗi luồng chỉ chạm dòng cache của riêng nó, không có nảy, không tranh chấp. Đây chính là LongAdder của Java (thay AtomicLong khi ghi nhiều), là reduction (gộp cục bộ rồi hợp), là sharding. Tất cả cùng một nguyên tắc: tránh điểm ghi chung.

(Môi trường đo: container gcc:13 trên host ARM AArch64, 10 lõi, dòng cache 64B, mỗi số lấy sau warmup. Con số tuyệt đối đổi theo máy; điều bền vững là hình dạng: atomic ghi chung đắt dần theo số luồng, đọc chung rẻ, CAS-loop tệ nhất, per-thread né sạch.)

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với hai niềm tin phổ biến. Thứ nhất: "atomic là lock-free nên luôn rẻ". Sai — atomic không khóa (không ngủ/thức, không convoy), nhưng khi tranh chấp nó vẫn đắt: fetch_add từ 1,6 ns (một luồng) lên 44 ns (tám luồng), vì cùng nảy một dòng cache. "Lock-free" nói về ngữ nghĩa (không dùng khóa, không bị block), không nói về chi phí. Thứ hai: "atomic luôn nhanh hơn mutex". Sai — dưới tranh chấp cao, một atomic ghi (44 ns) không nhanh hơn một khóa cho vùng tới hạn ngắn; cả hai bị chặn bởi cùng cái dòng cache nảy.

Hai lầm tưởng gặp nhau ở một điệp khúc của sê-ri: atomic không xóa chi phí đồng bộ, nó dời chi phí đó xuống tầng coherence — và dưới tranh chấp, chi phí coherence lớn không kém một khóa. Lock-free thắng khi tranh chấp thấp (đường thường không đụng nhau) hoặc khi thao tác là đọc (không invalidate). Nó không thắng chỉ vì cái nhãn "lock-free". Đừng chọn atomic vì nó "nghe nhanh"; đo dưới đúng mức tranh chấp thật, và nếu tranh chấp cao, cách đúng không phải "atomic thay mutex" mà là xóa điểm ghi chung (per-thread/sharded) — thứ nhanh hơn cả hai 96 lần. (Đúng tinh thần đo lường vi mô đúng cách.)

Về đến code hằng ngày

Điều đầu tiên: atomic không phải viên đạn bạc cho hiệu năng — đo dưới tranh chấp thật. Đổi một mutex sang một atomic không tự động nhanh hơn nếu nhiều luồng vẫn đập vào cùng một biến; cả hai đều nảy dòng cache. Atomic thắng rõ khi tranh chấp thấp hoặc thao tác đơn giản không cần khóa; với tranh chấp cao, nghĩ tới xóa điểm ghi chung thay vì đổi cơ chế đồng bộ.

Điều thứ hai: ghi-nhiều dùng per-thread/sharded, không dùng một atomic chung; ưu tiên fetch_add hơn CAS-loop khi có thể. Một biến đếm nhiều luồng cùng tăng nên là LongAdder/sharded (mỗi luồng ô riêng), không phải một AtomicLong (điểm nóng). Và khi chỉ cần tăng/cộng, dùng thao tác phần cứng trực tiếp (fetch_add) thay vì một vòng CAS tự viết — CAS-loop tốn thêm chi phí retry dưới tranh chấp (đo được: 119 so với 44 ns).

Chỗ này cái "điểm ghi nóng" lặp lại ở mọi tầng, và giải pháp luôn là "chia bảng ra". LongAdder của Java (lớp Striped64 bên dưới) ra đời chính vì AtomicLong thành điểm nóng khi nhiều luồng cùng tăng — nó giữ một mảng ô, mỗi luồng cộng vào ô riêng, sum() mới gộp. Go có cùng câu chuyện với atomic.AddInt64 trên một biến chung. Ở tầng database, đây là bài toán hot row kinh điển: một dòng đếm hay một sequence auto-increment mà mọi transaction cùng cập nhật trở thành nút thắt — cách chữa là sharded counter (nhiều dòng cộng lại) hay cấp phát ID theo lô. Và LMAX Disruptor nổi tiếng một phần vì tránh điểm ghi chung: mỗi producer/consumer có con trỏ riêng trên dòng cache riêng (kèm padding chống false sharing). Mẫu số chung khớp đúng phép đo: dưới tranh chấp, thứ đắt là điểm ghi chung, và cách nhanh nhất là xóa nó — không phải đổi khóa lấy atomic.

Muốn tự thấy thì nhìn code của bạn có một biến atomic mà nhiều luồng cùng ghi (một biến đếm, một cờ trạng thái, một con trỏ đầu hàng đợi). Hỏi: bao nhiêu luồng đập vào nó, và bao nhiêu lần mỗi giây? Nếu là nhiều luồng, nhiều lần, biến atomic đó là một điểm nóng coherence — mỗi thao tác nảy dòng cache ~vài chục ns, và bạn đang trả cái giá đó nhân với số lần. Đừng cho rằng "nó atomic nên nhanh"; nếu là biến đếm ghi nhiều, thử đổi sang một bộ đếm per-thread (mỗi luồng một ô, cộng lại khi cần đọc) và đo — bạn rất có thể thấy nhanh hơn hàng chục lần. Và nếu thấy một vòng CAS tự viết chỉ để tăng một biến, thử thay bằng fetch_add trực tiếp. Vài phút hỏi "atomic này có bị nhiều luồng ghi không" phân biệt một atomic rẻ thật với một điểm nóng đội lốt "lock-free nên nhanh" — và nhắc rằng không có gì trong đồng thời là miễn phí, chỉ có chi phí được chuyển tới nơi bạn chưa nhìn.