Atomic đắt gấp mấy lần? Từ 6,5 tới 74, tùy đông người

Bạn tra một bảng chi phí lệnh và thấy dòng "atomic đắt hơn lệnh thường khoảng X lần" — một con số duy nhất, gọn gàng, như thể chi phí ấy là hằng số. Phần 9 đã hé ra atomic không cố định theo memory_order; phần này đo một chiều còn quan trọng hơn nhiều: chi phí atomic biến thiên dữ dội theo mức tranh chấp.

Nghĩ tới một cây bút chung đặt giữa bàn họp. Nếu chỉ mình bạn dùng, với tay lấy là viết — gần như không mất thời gian. Nhưng nếu tám người cùng cần ghi vào đúng cây bút đó, phần lớn thời gian trôi qua trong cảnh chuyền tay, chờ, giật qua giật lại — bản thân việc viết vẫn nhanh, cái chậm là tranh nhau cây bút. Biến atomic dùng chung giữa các lõi CPU y hệt vậy. Cùng một phép fetch_add, nó có thể rẻ như một phép tính thường, hoặc đắt gấp hàng chục lần, tùy có bao nhiêu lõi cùng giành một biến. Tôi đo trong container gcc:13 trên host ARM, và khoảng biến thiên lớn hơn tôi tưởng nhiều.

Atomic: giá của nguyên tử, và giá của giành nhau

Một phép atomic (như fetch_add, compare_exchange) bảo đảm thao tác đọc-sửa-ghi diễn ra không bị xen bởi lõi khác. Có hai nguồn chi phí rất khác nhau, và trộn lẫn hai cái là gốc của mọi hiểu lầm. Một là tính nguyên tử tự nó: ngay cả khi không ai tranh, phép atomic vẫn nặng hơn lệnh thường vì phần cứng phải khóa/độc quyền dòng cache trong lúc thao tác. Hai là tranh chấp: khi nhiều lõi cùng ghi một biến atomic, dòng cache chứa nó bị giật qua giật lại giữa các lõi (coherence ping-pong) — đúng cảnh chuyền cây bút — và chi phí này bùng nổ theo số lõi.

Tôi đo ba tình huống: (A) một luồng tăng biến thường so với atomic (không tranh chấp); (B) N luồng cùng đập một atomic (tranh chấp cao); (C) N luồng, mỗi luồng một atomic riêng, đệm ra dòng cache khác nhau (không tranh chấp).

Đo: từ 6,5 lần tới 74 lần

Host ARM, ns mỗi thao tác:

   1 LUỒNG (không tranh chấp):
      plain x++            : 0,244 ns
      atomic fetch_add     : 1,591 ns   <- ~6,5x plain (giá của nguyên tử)

   N LUỒNG cùng đập 1 atomic (tranh chấp):
      T=1 : 1,60   T=2 : 2,94   T=4 : 6,84   T=8 : 18,08 ns/op

   N LUỒNG, mỗi luồng atomic RIÊNG (đệm dòng riêng):
      T=8 : 0,250 ns/op   (plain riêng: 0,192 ns)

Đọc từng tầng một. Một luồng: atomic 1,591 ns so với lệnh thường 0,244 ns — gấp 6,5 lần. Đây là giá của tính nguyên tử, và nó là sàn — không thể rẻ hơn. (Trên ARM, relaxed và seq_cst đều ~1,59 ns như nhau, phần 9.)

Nhiều luồng cùng một atomic: chi phí leo dốc theo số lõi — 1,60 ns (1 luồng) → 2,94 → 6,84 → 18,08 ns ở 8 luồng. Càng nhiều lõi giành một biến, dòng cache càng ping-pong. Ở 8 luồng, mỗi fetch_add ngốn 18 ns — gấp ~11 lần atomic không tranh chấp và gấp ~74 lần một lệnh thường. Đây đúng là con số mà "atomic đắt hơn X lần" cố định không bao giờ nắm được.

Nhiều luồng, mỗi luồng atomic riêng (đệm ra dòng cache khác nhau): 0,250 ns/op ở 8 luồng — scale gần hoàn hảo, và gần bằng lệnh thường riêng (0,192 ns). Khi không có tranh chấp, atomic rẻ — thậm chí song song hóa tốt. So sánh này phơi bày sự thật gọn gàng: cái đắt không phải bản thân phép atomic, mà là nhiều lõi cùng giành một biến.

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

Tôi vào đo với thói quen tra-bảng: "atomic đắt hơn lệnh thường một số lần cố định, cứ nhân lên là ra". Con số bác ngay: chi phí atomic trải từ ~1,6 ns (một luồng) tới 18 ns (tám luồng chung) — chênh 11 lần chỉ do tranh chấp, chưa kể so với lệnh thường thì từ 6,5x tới 74x. Không có "một con số" cho atomic; phải hỏi bao nhiêu lõi cùng chạm biến này. Ước lượng bằng con số cố định là sai một-chục-lần ở đúng chỗ nóng nhất — biến bị tranh chấp.

Nhưng nếu vì thế mà tin điều ngược lại — "atomic luôn đắt, phải tránh bằng mọi giá" — thì cũng sai. Atomic không tranh chấp rẻ (1,6 ns một luồng), và atomic riêng mỗi luồng chỉ 0,25 ns ở tám luồng — gần bằng lệnh thường, scale tốt. Cái cần tránh không phải phép atomic mà là tranh chấp: nhiều lõi giành một biến. Một bộ đếm phân mảnh (mỗi luồng một atomic riêng) rồi gộp cuối vừa đúng đắn vừa nhanh. Sợ atomic đến mức né hết là bỏ lỡ đúng những chỗ nó gần như miễn phí.

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

Việc đầu tiên: giảm tranh chấp, đừng chỉ giảm atomic. Thay một bộ đếm/tổng chung cho mọi luồng bằng bộ đếm phân mảnh (mỗi luồng/mỗi shard một biến riêng, đệm chống false sharing) rồi gộp cuối. Bạn vẫn dùng atomic (đúng đắn), nhưng vì không lõi nào giành nhau, nó gần như miễn phí. Đây là gốc của mọi cấu trúc đồng thời hiệu năng cao: chia tải để khỏi tranh.

Việc thứ hai: giảm tần suất chạm biến chung. Nếu buộc phải có một biến dùng chung (ví dụ tổng toàn cục), cập nhật nó thưa — tích lũy cục bộ rồi thỉnh thoảng mới đẩy lên biến chung — thay vì mỗi thao tác một fetch_add. Tranh chấp tỉ lệ với tần suất các lõi cùng ghi, nên giảm tần suất là giảm chi phí.

Điều đáng nói là nguyên lý "cái đắt là tranh chấp, không phải bản thân đồng bộ" leo thẳng lên mọi tầng, gần như không đổi hình. Java thấy rõ nhất: AtomicLong mà nhiều luồng cùng đập chính là ca 8-luồng-chung ở trên, và chính vì thế JDK có LongAdder — nó là bộ đếm phân mảnh đóng gói sẵn, giữ nhiều ô nội bộ để các luồng khỏi giành, gộp lại khi bạn gọi sum(). Go khuyên chia nhỏ trạng thái theo goroutine hơn là bắt tất cả khóa chung một mutex, cùng một lý do. Và ở tầng cao nhất, database chính là bài toán này phóng đại: một hàng "nóng" mà mọi transaction cùng UPDATE (một bộ đếm tồn kho, một số dư ví) tạo ra lock contention giết chết throughput y như dòng cache ping-pong — và cách chữa cũng đúng khuôn: chia counter thành nhiều hàng rồi cộng lại, hoặc gom cập nhật theo lô. Cùng một sự thật ở mọi quy mô: đồng bộ không đắt, giành nhau mới đắt.

Muốn tự thấy thì viết một bộ đếm và tăng nó vài chục triệu lần, đo ns mỗi lần, ba cách. Một: long x; x++ thường, một luồng — bạn được ~0,2 ns. Hai: std::atomic<long> a; a.fetch_add(1), một luồng — chậm hơn vài lần (giá của nguyên tử), nhưng vẫn là sàn. Ba: cho T luồng cùng fetch_add vào một atomic chung, chia thời gian cho tổng số phép — ns mỗi phép tăng vọt theo T (dòng cache giật giữa các lõi). Cuối cùng, cho mỗi luồng một atomic riêng căn alignas(128) rồi làm lại: lần này nó scale tốt, gần bằng lệnh thường. Chia con số tệ nhất (nhiều luồng chung) cho tốt nhất (per-thread): bạn thấy hàng chục lần, cùng một phép fetch_add. Ba mươi giây đó cho thấy điều mà "atomic đắt hơn X lần" giấu đi: chi phí atomic không phải một con số — nó là hàm của bao nhiêu lõi cùng giành biến đó, và cách nhanh nhất để dùng atomic là đừng để chúng giành nhau.