Spice: Kỹ thuật xử lý song song siêu hạt trong Zig với overhead dưới nano giây

• Spice là một dự án nghiên cứu nhằm giữ overhead dưới 1ns ngay cả khi thêm khả năng thực thi song song vào hàm trong Zig bằng heartbeat scheduling
• Thiết kế cốt lõi là dùng fork để đánh dấu công việc mà luồng khác có thể xử lý, nhưng nếu không có luồng nào lấy thì luồng hiện tại sẽ tự chạy tại join theo một cấu trúc fallback
• Trong benchmark cộng tổng cây nhị phân 100 triệu nút, Rayon có overhead khoảng 15ns ở 1 luồng và ở 16 luồng chỉ nhanh hơn baseline khoảng 4,5 lần, còn Spice đạt gần như nguyên vẹn mức tăng tốc khoảng 11 lần so với baseline ở 16 luồng
• Với các tác vụ có thời gian chạy rất ngắn như 1000 nút, Rayon có trường hợp chậm hơn tổng cộng 60 lần ở 32 luồng, còn Spice nếu đánh giá là không cần xử lý song song thì sẽ giữ các luồng bổ sung ở trạng thái ngủ và không khởi động multithreading
• Bản triển khai hiện tại còn thiếu test, tài liệu, hỗ trợ mảng và slice, benchmark bổ sung, dùng nhiều @panic, và tác giả cho biết cần nhận thức rõ nhiều hạn chế trước khi dùng trong production

---

Vấn đề mà Spice muốn giải quyết

• Spice là một dự án nhằm hiện thực hóa xử lý song song rất hạt mịn trong Zig với overhead thấp
• Mục tiêu là người dùng không còn phải luôn lo lắng rằng việc thêm song song hóa sẽ làm chương trình chậm đi
• Để tối đa hóa hiệu năng vẫn cần benchmark tinh vi, nhưng nhìn chung Spice được thiết kế để việc thêm tính song song hầu như không tạo ra overhead đáng kể
• Dự án chủ yếu là một dự án nghiên cứu, và nếu cân nhắc dùng trong production thì nên kiểm tra các hạn chế trước
• Trong bản cập nhật tháng 9/2024, Chili, bản port ý tưởng này sang Rust, đã được giới thiệu

Cách dùng và API cốt lõi

• Hàm song song của Spice nhận *spice.Task làm tham số để điều phối công việc
• Các lời gọi đệ quy hoặc lời gọi tới hàm có thể song song hóa không được gọi trực tiếp mà phải thông qua t.call
• fork thiết lập công việc mà luồng khác có thể thực thi
• Sau fork, bản thân hàm cũng phải tiếp tục thực hiện công việc có ý nghĩa
• join chờ xem luồng khác đã hoàn thành công việc hay chưa, nhưng có thể trả về null
  • null là tín hiệu cho biết không có luồng nào khác lấy công việc đó
  • Khi đó, luồng hiện tại phải tự thực thi công việc đó

Thiết kế “không phải mọi công việc đều đến từ queue”

• Ý tưởng cốt lõi của Spice là không phải mọi công việc đều bắt đầu từ queue
• fork báo rằng có công việc mà luồng khác có thể chạy, nhưng nếu các luồng khác đang bận thì luồng hiện tại sẽ xử lý nó giống như thực thi tuần tự ban đầu
• Khi không có khả năng thực thi song song, trên hot path Spice chỉ push/pop vào queue chứ không thực sự xem nội dung mục trong queue
• Việc điều phối thực sự với các luồng khác diễn ra ở các heartbeat cố định
  • Cứ khoảng mỗi 100 micro giây, một luồng sẽ kiểm tra queue công việc hiện tại
  • Công việc ở đỉnh queue được chuyển cho một luồng khác đang chờ
  • Vì tần suất heartbeat thấp, ngay cả khi tốn vài trăm ns thì tổng overhead vẫn nhỏ

So sánh với benchmark của Rayon

• Việc cộng tổng cây nhị phân 100 triệu nút là trường hợp cho thấy rõ overhead của framework song song vì bản thân phép tính thực tế rất nhanh
• Cả Rayon của Rust và Spice đều được so sánh dưới dạng API fork/join dễ đọc và dễ suy luận
• Trong benchmark của Rayon, overhead đo được khoảng 15ns
  • Tăng từ 7.48ns lên 22.99ns
  • Ở 4 luồng, hiệu năng quay về mức gần như tuần tự nhưng CPU bị dùng gấp 4 lần
  • Ở 16 luồng, tốc độ tăng khoảng 14 lần theo chuẩn riêng của Rayon, nhưng chỉ khoảng 4,5 lần so với baseline
• Spice cho thấy mức tăng tốc khoảng 11 lần khi đi từ 1 luồng lên 16 luồng
  • Scale hơi kém hơn Rayon một chút, nhưng nhờ overhead thấp nên mức tăng tốc so với baseline hầu như vẫn được giữ nguyên
• Benchmark được chạy trên instance c4-standard-16 của Google Cloud, môi trường 16 lõi
• Chưa rõ vì sao baseline của Zig lại nhanh hơn baseline của Rust khoảng 2 lần
  • Theo compiled assembly, Rust lưu 5 thanh ghi lên stack còn Zig lưu 3 thanh ghi

Hành vi với tác vụ nhỏ

• Việc cộng tổng cây nhị phân 1000 nút là tác vụ rất ngắn, với tổng thời gian chạy chỉ ở mức vài micro giây
• Trong trường hợp này Rayon cho thấy overhead cao hơn, khoảng 19ns, và hiệu năng càng xấu đi khi thêm nhiều luồng
• Khi dùng 32 luồng trên máy 16 lõi, tổng thời gian thực thi chậm hơn 60 lần
  • Không thể khẳng định hiện tượng chậm tương tự sẽ xảy ra trên máy 32 lõi
  • Dù vậy, kiểu scale như vậy vẫn bị đánh giá là đáng lo ngại
• Cách đánh giá song song truyền thống thường là “chỉ đáng khi có đủ nhiều việc”
  • Ngưỡng “đủ nhiều việc” có thể phải xác định bằng benchmark theo từng input
  • Với input như cây nhị phân, chỉ nhìn root thì khó biết toàn bộ kích thước để quyết định đó có phải tác vụ nhỏ hay không
  • Nếu 90% khối lượng công việc là input nhỏ thì hiện tượng chậm cực mạnh có thể trở thành vấn đề
  • Khi chương trình tiến hóa, tiêu chuẩn thế nào là đủ nhiều việc cũng thay đổi
• Với cùng trường hợp 1000 nút, Spice đánh giá thời gian thực thi quá ngắn nên không khởi động multithreading
  • Các luồng bổ sung tiếp tục ở trạng thái ngủ
  • Các lõi có thể được dùng để chạy chương trình khác

Khác biệt giữa work-stealing và Spice

• Spice cung cấp mô hình fork/join, vốn thường được triển khai bằng work-stealing
• Work-stealing thông thường để mỗi luồng có queue công việc cục bộ, và khi queue trống thì sẽ lấy trộm công việc từ cuối queue của luồng khác
• Các điểm kém hiệu quả của work-stealing được tóm lại thành ba ý
  • Mọi công việc đều trở thành dạng generic “gọi hàm động”, phát sinh chi phí dynamic dispatch
  • Queue cục bộ thực chất là queue mà mọi luồng đều có thể trộm, nên cần các phép toán nguyên tử
  • Khi tranh chấp queue sẽ xảy ra spinning, và trong một số điều kiện có thể chậm hơn 10 đến 100 lần
• Spice trực tiếp giảm các điểm kém hiệu quả này
  • Dynamic dispatch của queue công việc chỉ được dùng khi gửi công việc sang luồng khác
  • Công việc thực thi trong một luồng đơn dùng lời gọi hàm thông thường
  • Việc push vào queue công việc được xử lý bằng stack pointer, stack frame hiện tại và lưu thanh ghi, không đồng bộ với luồng khác
  • Không có vòng lặp while chạy mà không gọi wait(), nên không có spinning

Chi tiết triển khai

• Tối ưu static dispatch

  • Spice giả định rằng phần lớn công việc được fork sẽ không bị luồng khác lấy đi, nên nó đặt trùng đường thực thi mã tương ứng ngay trong hàm
  • Nếu công việc không bị luồng khác thực thi, chương trình hoạt động như một phiên bản tuần tự chỉ được thêm vài nhánh dự đoán được
  • Cấu trúc này có lợi cho tối ưu mã như inlining và cho quá trình thực thi của CPU

• Tín hiệu heartbeat overhead thấp

  • Heartbeat scheduling thực hiện việc lập lịch cục bộ với tần suất thấp
  • Khoảng mỗi 100 micro giây, một luồng xem queue công việc cục bộ và gửi việc sang luồng khác
  • Nếu cứ mỗi 100 micro giây tốn 100ns, tổng overhead chỉ ở mức 0,1%
  • Thay vì OS signaling, hệ thống dùng cách hợp tác bằng cách gọi tick()
    • Khi dùng helper t.call, tick() được gọi tự động
    • Một heartbeat thread riêng sẽ định kỳ đổi giá trị heartbeat dạng atomic của từng luồng từ false sang true
    • tick() đọc giá trị này và khi là true thì chạy mã heartbeat
  • Hàm heartbeat phải được đánh dấu là cold, nếu không overhead sẽ lớn hơn nhiều

• Global mutex không có tranh chấp

  • Thread pool của Spice có một mutex duy nhất được khóa ở nhiều nơi
  • Global mutex chỉ trở thành vấn đề khi luồng thực sự bị block
  • Trong Spice, do có heartbeat nên thông thường chỉ một luồng thực thi heartbeat tại một thời điểm
  • Khi đang giữ lock, không có mã người dùng nào được chạy; nó chỉ bảo vệ các thao tác đọc/ghi bộ nhớ đơn giản kết thúc trong thời gian hằng số

• Danh sách liên kết kép không có nhánh

  • Spice dùng doubly linked list để theo dõi queue công việc
  • fork() append vào cuối, join() nếu vẫn còn sẽ pop ở cuối, còn khi gửi cho background worker thì pop ở đầu
  • Cách append thông thường cần một câu lệnh điều kiện để kiểm tra danh sách rỗng hay không
  • Spice dùng một sentinel head node luôn tồn tại để danh sách không bao giờ rỗng, nhờ đó push/pop không cần nhánh

• Tối thiểu hóa sử dụng stack

  • Future có thể ở trạng thái queued hoặc executing
  • Heartbeat chuyển queued future sang executing
  • Trạng thái bổ sung cần cho executing được đặt trong một struct cấp phát từ pool riêng để giảm sử dụng stack của queued future
  • Hệ thống dùng dạng tagged union thủ công, phân biệt queued/executing bằng việc trường đầu tiên prev_or_null có phải là null hay không

• Truyền giá trị bằng thanh ghi

  • Task giữ con trỏ tới worker sở hữu và con trỏ tail của queue công việc
  • LLVM thường xử lý truyền struct qua stack, nên Spice định nghĩa callWithContext nhận riêng worker và job_tail làm tham số hàm
  • Hàm này luôn được gọi theo cách có thể inline để các tham số con trỏ được truyền qua thanh ghi

Cơ sở nghiên cứu và công trình liên quan

• Spice được xây dựng dựa trên nghiên cứu về heartbeat scheduling
• “The best multicore-parallelization refactoring you've never heard of” là bài báo giới thiệu ngắn gọn khái niệm heartbeat scheduling; nó tập trung vào một use case duy nhất nhưng giải thích theo cách có thể khái quát hóa
  • Lời giải trong bài báo này biến đổi mã sang continuation-passing style để chuyển đổi giữa thực thi tuần tự và song song
  • Spice bắt đầu từ thử nghiệm với cách tiếp cận đó, nhưng cho thấy overhead vượt quá 10ns
• “Heartbeat scheduling: provable efficiency for nested parallelism” là bài báo đầu tiên giới thiệu heartbeat scheduling
  • Bài có nhiều thông tin về khái niệm, nhưng phần triển khai dựa trên tích hợp interpreter và tập trung nhiều hơn vào bảo đảm lý thuyết
• “Task parallel assembly language for uncompromising parallelism” là nghiên cứu tiếp theo cải thiện hiệu năng heartbeat bằng ngôn ngữ assembly tùy biến và OS signaling
  • Cách này được đánh giá là khó tích hợp vào các ngôn ngữ hiện có

Hạn chế hiện tại

• Spice có thể hành xử thô ráp khi bị dùng sai
  • Đặc biệt nhạy với cách dùng fork và join
  • Cần cải thiện bằng kiểm tra compile-time, assertion ở debug mode và thay đổi API
• Có nhiều mã đồng thời nhưng độ phủ test hiện là 0
• Chưa có hỗ trợ native cho việc xử lý từng phần tử của mảng và slice, một use case phổ biến của xử lý song song hạt mịn
• Tài liệu hướng dẫn sử dụng còn thiếu
• Hiện mới chỉ được kiểm thử chủ yếu bằng một benchmark nhỏ duy nhất
  • Tác giả cho rằng benchmark đó nên có tính đại diện, nhưng vẫn cần thêm benchmark để kiểm chứng kết quả
• Phần xử lý lỗi dùng nhiều @panic
  • Muốn được xem là thư viện Zig phù hợp thì cần cân nhắc nhiều hơn đến các trường hợp lỗi
• Cần thêm benchmark và test để biết nó hoạt động tốt đến mức nào trong ReleaseSafe của Zig
• Toàn bộ codebase chỉ khoảng 500 dòng, và hiện tác giả không có kế hoạch phát triển tích cực để cải thiện Spice vì thiếu thời gian
• Việc cải thiện thông qua fork hoặc tái triển khai bằng ngôn ngữ khác được khuyến khích

[GN⁺]

Các ý kiến trên Hacker News

• Cách triển khai này dựa trên heartbeat scheduling, một hướng nghiên cứu gần đây, giúp phân bổ dần chi phí tạo song song để đạt được một dạng kiểm soát đơn vị công việc tự động, động
  Các bài báo liên quan:
  (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
  (2021) Task Parallel Assembly Language for Uncompromising Parallelism. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
  (2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
  (2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf

  • Cái này thật sự thú vị; khi viết Spice tôi chỉ biết hai bài đầu
    Tôi chắc chắn sẽ xem cả hai bài sau

• Tôi chưa đọc kỹ mã, nhưng cụm overhead dưới 1 nano giây nghe như một câu marketing dễ gây hiểu nhầm
  Thoạt nhìn, có vẻ đó là một phép đo “thời gian trên mỗi công việc” phức tạp được tính trong tình huống số luồng ít hơn nhiều so với số “công việc”

  • Tôi là tác giả
    Tôi biết một số người sẽ phản ứng tiêu cực với cách diễn đạt đó, nhưng mục đích là giúp mọi người hiểu rõ hơn chính xác khi nào và nên dùng Spice hay Rayon như thế nào
    Tôi khuyên nên đọc tài liệu benchmark: https://github.com/judofyr/spice/blob/main/bench/README.md
    Thông thường khi so sánh mã song song, người ta chỉ so sánh bản tuần tự/cơ sở với bản song song dùng tất cả luồng (16 luồng). Trong trường hợp 100M, số liệu của Rayon là bản tuần tự 7,48ns, Rayon 1,64ns; khi đó rất dễ kết luận “Rayon nhanh hơn 4,5 lần trong bài toán này nhưng dùng 16 luồng nên không phù hợp”. Câu đó đúng, nhưng khó học được cách áp dụng cho các loại bài toán khác
    Khi chạy cùng benchmark với nhiều số lượng luồng khác nhau, sẽ thấy những điểm thú vị hơn. Scheduler của Rayon khá giỏi trong việc chia công việc sang các luồng riêng, nhưng toàn bộ cơ chế thực thi công việc có khoảng 15ns overhead. Dù chương trình này là một ví dụ hoàn toàn vô dụng, ta vẫn học được một thực tế có thể áp dụng về sau: nếu muốn dùng Rayon, đơn vị công việc nhỏ nhất nhiều khả năng phải lớn hơn khoảng 7ns. Ngoại lệ là khi việc giảm độ trễ tổng thể quan trọng hơn, dù phải hy sinh thông lượng tổng
    Tài liệu của Rayon không đưa ra con số, mà chỉ nói “về mặt khái niệm, lời gọi join() giống như tạo hai luồng để mỗi luồng chạy một closure, nhưng triển khai thì rất khác và có overhead rất thấp”: https://docs.rs/rayon/latest/rayon/fn.join.html
    Nếu muốn gây hiểu nhầm, tôi đã nói “Spice tăng tốc 10 lần còn Rayon 4,5 lần, nên Spice nhanh gấp đôi Rayon” rồi
  • Để “overhead dưới 1 nano giây” trở thành câu marketing gây hiểu nhầm, thì Spice 1 luồng - bản cơ sở không song song phải lớn hơn 1ns
    Kết quả kiểm thử ủng hộ tuyên bố đó: https://github.com/judofyr/spice/tree/main/bench
  • Tôi nghĩ điều này cũng giống với vị trí sinh thái của Rayon được trích dẫn
    Khi cần xử lý từ hàng nghìn đến hàng triệu công việc, muốn song song hóa tối đa trong phạm vi vài chục lõi, và không muốn bị overhead lập lịch nuốt mất, thì cấu trúc sẽ tính overhead trên mỗi công việc
  • Hôm qua khi bài này được đăng trên Reddit, tôi đã nêu lo ngại về benchmark
    Benchmark tuyên bố 0,36ns overhead cho mỗi lần gọi, nhưng chỉ bao gồm hàm tính toán. Có một luồng thứ hai làm nhiệm vụ lập lịch, nhưng không được tính vào con số overhead. Có vẻ nó được chạy trên máy 8 lõi có hyper-threading, tức 16 luồng; giả sử 3GHz thì nghĩa đen là overhead một chu kỳ
    Với mỗi luồng bổ sung, overhead tăng do tranh chấp khóa. Ở 16 luồng, nó tăng gấp 10 lần lên 3,6ns. Tôi đoán nếu vậy thì overhead 0,36ns có bao gồm một khóa không bị tranh chấp, nhưng điều đó là không thể. Dữ liệu benchmark còn có những điểm lạ khác. Có thể tôi không hiểu thật ra nó đang đo gì, hoặc mã benchmark có lỗi
    Nếu nhân tất cả các giá trị lên, có vẻ thời gian được đo theo mili giây. Thời gian chạy được tính rồi chuyển sang mili giây thì rơi vào số nguyên. Chẳng phải các công cụ benchmark thường dùng độ chính xác tốt hơn thế sao? Có thể họ chỉ dùng time prog nên dữ liệu rất nhiễu, hoặc đã chọn một chỉ số hoàn toàn vô dụng cho mục đích này
  • Đọc README thì tôi thấy nó giải thích rất chính xác tuyên bố trong tiêu đề nghĩa là gì
    Không có tiêu đề nào hoàn toàn không thể gây hiểu nhầm, và tiêu đề này ổn. Điều tôi hiểu là đây là một thư viện có độ trễ cực thấp theo một tiêu chí đo nào đó, và chỉ cần xem README để biết tiêu chí đó là gì. Khá rõ ràng

• Tôi không quá quen thuộc với lĩnh vực này, nhưng tôi thích mô hình concurrency được trình bày ở đây
  README cũng được viết rất tốt, chỉ cần đọc là đã nắm được đại khái chuyện gì đang diễn ra. Tuy vậy có vài chỗ khiến tôi hơi băn khoăn. May là code khá dễ đọc

  • Khi build bằng zig build ở chế độ Debug, tôi nhận được Baseline,3.92809172, Spice 1 thread,19.1012624
    Khi build bằng zig build --release=safe ở chế độ ReleaseSafe, tôi nhận được Baseline,3.264224280000001, Spice 1 thread,3.78043278
    Vì vậy Spice bị giảm hiệu năng khá nhiều nếu không phải bản build release. Phần triển khai làm mốc thì không chậm đi ở mức tương tự trong chế độ build Debug của Zig
    Phiên bản dùng là zig 0.13.0

• Đây là một công trình nghiên cứu thú vị; không chỉ bản thân code mà cả cơ sở lập luận cũng tốt, tài liệu cũng được viết tốt
  Bài báo năm 2018 về heartbeat scheduling cũng đáng đọc: https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf

• Danh sách hạn chế của dự án: https://github.com/judofyr/spice?tab=readme-ov-file#limitati...

  • Dự án này rất tuyệt, và tác giả rất đáng được khen vì đã dành thời gian làm cho nó chạy được rồi chia sẻ với cộng đồng HN
    HN nhìn chung cũng nổi tiếng là nơi có phản ứng quá chỉ trích hoặc bi quan
    Việc tác giả thừa nhận các giới hạn của dự án cũng tốt, nhờ vậy đã chặn trước phần lớn kiểu châm biếm thường thấy
    Ở phần “Thiếu kiểm thử: Spice có rất nhiều code concurrency khó, nhưng độ phủ kiểm thử là 0. Để dùng Spice một cách có trách nhiệm cho công việc quan trọng, điều này cần được cải thiện”, ngoài việc kiểm thử tính đúng đắn khi chạy các công việc quan trọng là chuyện riêng, tôi cho rằng một thư viện triển khai code concurrency khó thì ít nhất cũng nên có regression test
    Ở góc nhìn người dùng cuối, tôi tự hỏi có gì đảm bảo rằng tính năng hôm nay còn chạy sẽ không bị một regression tinh vi và tai hại làm hỏng vào ngày mai
    SQLite có lượng code kiểm thử và script kiểm thử nhiều hơn 590 lần so với mã nguồn C thuần https://www.sqlite.org/testing.html. Bên cạnh độ ổn định và tính di động, đây cũng là một trong nhiều lý do SQLite trở thành cơ sở dữ liệu nhúng tiêu chuẩn trên thực tế trên toàn thế giới
    Đây là ví dụ hơi gượng ép kiểu so sánh táo với cam, nhưng ý chính vẫn còn nguyên giá trị. Regression test tạo ra sự ổn định và niềm tin cho dự án
    Ở nơi tôi làm việc, nếu bắt buộc phải hoãn các regression test cơ bản, thì thường chúng tôi sẽ tạo ticket tiếp theo trong cùng epic để ít nhất chúng được viết trước khi phát hành feature/epic

• Theo phần giải thích, để đạt độ trễ mức nano giây, các worker dùng busy-waiting
  Tôi tự hỏi busy-waiting thực tế đến đâu trong các ứng dụng lớn có hàng chục nghìn tác vụ. Nếu tác vụ không dựa trên thread mà là async, thì có thể vẫn khả thi vì chỉ có số waiter bằng kích thước N của thread pool executor. Dù sao cấu trúc như vậy sẽ tiêu thụ năng lượng cao hơn
  Liên quan đến chuyện này, từ lâu tôi vẫn thắc mắc liệu có cách nào để producer đánh thức consumer nhanh hơn mà không cần busy-waiting không. Chẳng hạn tôi nghĩ liệu có thể chạy consumer ngay trong time slice của producer hay không
  Cũng liên quan, tôi tự hỏi liệu nếu có thể thực hiện thao tác FUTEX_WAKE trong user space, chi phí đánh thức consumer có thể giảm còn một nửa thông thường, tức chỉ còn chi phí phía consumer hay không

• Có liên kết đến cả những bài báo gọn gàng và hay
  Tuy nhiên tôi ước đối tượng so sánh là OpenMP tasks. Tôi từng nghe nhận xét rằng Rayon hơi chậm

• Cooperative scheduling là nền tảng của nhiều pattern cho ra các chỉ số rất tốt

  • Nhưng đây không phải cooperative scheduling theo nghĩa các tác vụ nhường quyền cho nhau
    Chủ yếu là cách chúng hợp tác để có thể chuyển một số tác vụ sang thread khác, và cũng không phải lúc nào cũng làm vậy mà chỉ xảy ra một lần mỗi heartbeat. Vì scheduling diễn ra thưa, chi phí phân bổ bình quân thấp

• README trong thư mục bench cũng đáng tham khảo: https://github.com/judofyr/spice/blob/main/bench/README.md