Ở bài về futex ta thấy một khóa không tranh chấp gần như miễn phí, còn tranh chấp thì đắt. Bài này hỏi câu tiếp theo, thực tế hơn: khi bạn thêm luồng để chạy nhanh hơn nhưng chúng đều giành cùng một khóa, thông lượng thay đổi thế nào? Tôi đo trong container — và câu trả lời không chỉ là "không nhanh hơn" mà là "chậm đi", cộng một tranh chấp vô hình mà tôi suýt không thấy.
Vì sao một khóa chung không mở rộng
Ý tưởng "thêm luồng thì nhanh hơn" chỉ đúng khi các luồng làm việc độc lập. Nếu mọi luồng đều phải lấy cùng một khóa trước khi làm việc, thì vùng găng (đoạn code trong khóa) chỉ có thể chạy một luồng tại một thời điểm — dù bạn có bao nhiêu lõi. Tệ hơn, mỗi lần khóa chuyển từ luồng này sang luồng khác, dòng cache (cache line) chứa trạng thái khóa phải nảy từ lõi này sang lõi kia, một thao tác tốn hàng chục tới trăm nano giây. Càng nhiều luồng tranh, càng nhiều lần nảy.
Tôi đo thông lượng (triệu lần lock/unlock mỗi giây) khi tăng số luồng, mỗi luồng liên tục lấy khóa, tăng một biến, thả khóa:
Một khóa chung:
1 luồng: 226 triệu ops/giây
2 luồng: 27 triệu ops/giây <-- SỤP
4 luồng: 50
8 luồng: 44
Đi từ 1 lên 2 luồng, thông lượng sụp từ 226 xuống 27 triệu ops/giây — chậm hơn tám lần, không phải nhanh gấp đôi. Với một luồng, khóa không tranh chấp nên cực nhanh (~vài ns mỗi lần). Ngay khi có luồng thứ hai, chúng bắt đầu giành khóa và nảy cache line, và thông lượng rơi xuống rồi lẹt đẹt ở mức 40-50 triệu bất kể thêm bao nhiêu luồng. Đây là mở rộng âm (negative scaling): thêm tài nguyên làm mọi thứ chậm đi. Nếu tôi thêm luồng để tăng tốc, tôi đã đạt điều ngược lại.
Một lần tôi đo hớ: chia khóa rồi mà vẫn tụt
Cách chữa hiển nhiên là giảm tranh chấp: đừng bắt mọi luồng dùng chung một khóa. Tôi cho mỗi luồng một khóa riêng và một bộ đếm riêng (kỹ thuật chia nhỏ khóa, sharding), rồi đo lại, kỳ vọng thông lượng bây giờ tăng theo số luồng:
Chia khóa (mỗi luồng một khóa riêng, đặt sát nhau):
1 luồng: 235 2 luồng: 440 4 luồng: 347 8 luồng: 213
Từ 1 lên 2 luồng thì đúng là tăng (235 lên 440), nhưng rồi tụt trở lại ở 4 và 8 luồng (347, rồi 213). Ơ hay — mỗi luồng đã có khóa riêng, không còn giành khóa của nhau, sao vẫn tụt? Con số này mâu thuẫn với mô hình "khóa riêng thì hết tranh chấp" của tôi, nghĩa là có một biến ẩn tôi chưa thấy.
Đọc kỹ mới lộ ra: các khóa riêng và bộ đếm riêng của tôi nằm sát nhau trong bộ nhớ — nhiều cái lọt vào cùng một dòng cache 64 byte. Phần cứng quản lý nhất quán bộ nhớ ở mức cả dòng cache, không phải từng byte. Nên khi lõi 0 ghi vào bộ đếm của luồng 0 và lõi 1 ghi vào bộ đếm của luồng 1, dù đó là hai biến khác nhau, chúng ở chung một dòng cache, và hai lõi vẫn phải giành nhau chính dòng cache đó, nảy nó qua lại. Đây gọi là chia sẻ giả (false sharing): không có chia sẻ dữ liệu logic nào, nhưng phần cứng vẫn xử lý như thể có, vì chúng ở cùng một dòng cache. Tôi đã gỡ tranh chấp nhìn thấy được (khóa) nhưng bỏ sót tranh chấp vô hình (dòng cache).
Sửa nốt: đệm mỗi luồng ra riêng một dòng cache (thêm khoảng trống để mỗi khóa+bộ đếm chiếm trọn 64 byte, không đụng hàng xóm):
Chia khóa + đệm mỗi luồng một dòng cache:
1 luồng: 225 2 luồng: 448 4 luồng: 863 8 luồng: 1361
Bây giờ thông lượng mới scale gần như tuyến tính: 8 luồng đạt 1361 triệu ops/giây, gấp sáu lần một luồng. Cùng một thuật toán, cùng số khóa — chỉ khác việc các biến có nằm chung dòng cache hay không, mà kết quả một trời một vực (213 so với 1361).
Bài học đo lường: gỡ được tranh chấp nhìn thấy chưa chắc đã hết; phải đọc bằng chứng để tìm tranh chấp vô hình bên dưới. Con số "chia khóa rồi vẫn tụt" chính là tín hiệu có biến ẩn — và biến ẩn ở đây là bố cục bộ nhớ, một thứ không hiện ra trong logic chương trình mà chỉ lộ khi ta hiểu phần cứng quản lý cache theo dòng.
Ngay cả bỏ khóa cũng không thoát dòng cache
Có thể nghĩ: vậy bỏ hẳn mutex, dùng thao tác nguyên tử (atomic) không khóa thì hết chuyện? Không hẳn. Nếu nhiều luồng cùng thực hiện atomic trên cùng một biến (một bộ đếm chung atomic long), chúng vẫn phải giành cùng một dòng cache để đảm bảo nhất quán — chính cái nảy cache line đã giết thông lượng ở trên, chỉ khác là không có lời gọi khóa. Atomic bỏ được chi phí gọi mutex và nguy cơ ngủ/đánh thức, nhưng không bỏ được cái giá vật lý của việc nhiều lõi giành một dòng cache. Đó là lý do bài đo trên cho thấy vấn đề nằm ở dòng cache bị chia sẻ, không riêng ở khóa — và cùng một lời giải (đệm ra riêng dòng cache, hoặc mỗi luồng một biến rồi cộng lại) áp dụng cho cả hai. Bài tiếp theo của sê-ri sẽ đo chính atomic so với khóa để thấy rõ ranh giới đó.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: thêm luồng không tự động cho thông lượng cao hơn. Một vùng găng dùng chung bị khóa là một nút cổ chai tuần tự; theo định luật Amdahl, phần tuần tự đó đặt trần cho tốc độ dù bạn có bao nhiêu lõi. Khi một dịch vụ không nhanh lên (hay chậm đi) lúc thêm luồng, nghi phạm số một là một khóa nóng ở đâu đó mà mọi luồng đều đi qua. Cách chữa là thu nhỏ vùng găng (giữ khóa càng ngắn càng tốt) và chia nhỏ khóa (nhiều khóa cho nhiều phần dữ liệu độc lập), không phải thêm luồng.
Hệ quả thứ hai: chia sẻ giả là kẻ giết hiệu năng vô hình. Hai biến hoàn toàn độc lập, được hai luồng khác nhau ghi, vẫn có thể làm chậm nhau nếu chúng vô tình ở chung một dòng cache. Đây là lý do các cấu trúc dữ liệu hiệu năng cao đệm các trường mà nhiều luồng ghi ra những dòng cache riêng (ví dụ mỗi bộ đếm theo lõi được căn thẳng 64 byte). Khi tối ưu code đa luồng mà thấy nó không scale dù đã chia khóa, hãy nghi chia sẻ giả và kiểm bố cục bộ nhớ.
Hệ quả thứ ba là bài học đo lường: đo scaling ở nhiều mức luồng, đừng đo ở một mức rồi ngoại suy. Con số mang theo: một khóa chung khiến thông lượng SỤP khi thêm luồng (226 xuống 27 triệu ops/giây ở 2 luồng, mở rộng âm); chia nhỏ khóa vẫn tụt sau 2 luồng vì chia sẻ giả (các biến chung dòng cache); chỉ khi đệm mỗi luồng ra riêng một dòng cache thì mới scale ~tuyến tính (gấp 6 ở 8 luồng). "Song song" chỉ có thật khi các luồng thật sự độc lập — cả về khóa lẫn về dòng cache.
Thử ba mươi giây
Nếu code của bạn dùng một cấu trúc đếm hay tích lũy được nhiều luồng ghi, xem thử các trường đó có bị nhồi sát nhau không: một mảng long counters[N] mà mỗi luồng ghi một phần tử là mẫu chia sẻ giả kinh điển (8 phần tử long lọt vừa một dòng cache 64 byte). Thử đo thông lượng chương trình đa luồng của bạn với 1, 2, 4, 8 luồng và vẽ ra: nếu đường cong phẳng ra hay đi xuống thay vì đi lên, bạn đang đụng trần tranh chấp — hoặc ở một khóa chung, hoặc ở một dòng cache bị nhiều lõi giành. Thêm đệm (alignas(64) trong C++, hay padding thủ công) để tách mỗi biến nóng ra riêng một dòng cache, rồi đo lại — đúng cái nhảy vọt từ 213 lên 1361 mà bài này đo.
