Động cơ Peredvizhnikov: engine game lock-free viết bằng C++20

 (github.com/eduard-permyakov)
4 điểm bởi GN⁺ 2023-09-11 | 1 bình luận | Chia sẻ qua WhatsApp
  • Một engine game hoàn toàn lock-free được viết bằng C++20, triển khai mô hình actor cho tính toán đồng thời trên nền các primitive coroutine của ngôn ngữ
  • Có thể phát triển logic song song phức tạp trong trạng thái tách biệt khỏi các chi tiết đồng bộ hóa giữa các luồng bằng cách sử dụng trừu tượng mô hình actor
  • Triển khai hoàn toàn lock-free mang lại bảo đảm tiến triển ngay cả khi luồng bất kỳ bị kết thúc, ngăn deadlock, độ trễ có thể dự đoán cho phản ứng với các sự kiện quan trọng và khả năng chịu lỗi
  • Cung cấp bảo đảm rằng engine vẫn tiếp tục chạy ngay cả khi một trong các worker thread bị kết thúc bất đồng bộ
  • Phần triển khai bao gồm Software Transactional Memory, hàng đợi lock-free, primitive tuần tự hóa lock-free, std::atomic_shared_ptr, bộ lập lịch lock-free, bộ cấp phát bộ nhớ lock-free và DAG thời gian biên dịch
  • Các thuật toán lock-free, cơ sở thiết kế và benchmark được trình bày trong tài liệu Peredvizhnikov Engine: Design and Implementation of a Completely Lock-Free Scheduler
  • Để hỗ trợ thiết kế hướng dữ liệu, dự án triển khai một cơ sở dữ liệu trong bộ nhớ được tối ưu cho truy cập theo đơn vị component và hỗ trợ các tập dữ liệu lớn
  • Cơ sở dữ liệu trong bộ nhớ dựa trên các cấu trúc dữ liệu Flat Hash Map và Bitwise Trie with Bitmap
  • Hiện tại chỉ hỗ trợ nền tảng Linux, và việc build từ mã nguồn yêu cầu Clang++ 16
  • Mã nguồn được cung cấp theo giấy phép GPLv3, và quyền sử dụng một phần hoặc toàn bộ mã với giấy phép khác có thể được cấp theo từng trường hợp

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-09-11
Ý kiến trên Hacker News

  • Trong framework Actor, họ dùng một std::deque bình thường làm hàng đợi con trỏ phương thức, và khi đưa thông điệp vào hàng đợi thì khóa theo kiểu Benaphore
    Về cơ bản giống Futex, dùng kết hợp thao tác nguyên tử và primitive khóa, nhưng primitive khóa của tôi hoạt động như một tổ hợp spinlock/mutex tùy theo số lần thử lại. Theo benchmark, trường hợp hàm push thông điệp bị chặn là rất hiếm, khả năng chuyển ngữ cảnh của hệ điều hành cũng thấp, nên ngay cả khi thỉnh thoảng một luồng đang bị khóa bị swap out, điều đó cũng không xảy ra đủ thường xuyên để biện minh cho chi phí của thuật toán lock-free
    Tóm lại, hàng đợi không lock-free nhanh hơn hàng đợi lock-free rất nhiều, nhưng phải chấp nhận độ trễ dài cực hiếm do chuyển ngữ cảnh khi không ai lấy được khóa. Trên phần cứng hiện đại, có thể đưa 10 triệu thông điệp mỗi giây vào hàng đợi cho mỗi worker thread

    • Dù nói là “về cơ bản giống Futex”, Benaphore là một ý tưởng khá cũ, còn Futex không đơn thuần là “Benaphore kiểu Linux”
      Điểm cốt lõi là thực ra không cần kernel object, tức một primitive khóa riêng. Đây là chỗ ý tưởng này chuyển từ “cách làm ai cũng biết” thành “tính năng cần đưa ngay vào hệ điều hành”
      Trong thiết kế Futex, thay vì dùng đối tượng đồng bộ hóa của hệ điều hành để xử lý xung đột, hệ điều hành duy trì một danh sách ánh xạ địa chỉ → luồng. Khi luồng T ngủ trên futex ở địa chỉ X, X được đưa vào danh sách để trỏ tới T; khi có yêu cầu đánh thức futex X, hệ điều hành duyệt danh sách và đánh thức T
      Sự khác biệt thể hiện ở giới hạn. Những thứ như Benaphore là tài nguyên toàn hệ thống đắt đỏ, nên tôi nhớ BeOS chỉ cho phép khoảng 65.536 cái trên mỗi máy. Nhưng Futex chỉ là bộ nhớ, nên không có lý do gì để đặt giới hạn
    • Với một bài thú vị như thế này thì nên gắn liên kết tới mã nguồn. Vừa chứng minh được các tuyên bố, vừa khiến những người như tôi, vì thấy ý tưởng thú vị, muốn xem ngay phần triển khai
    • Còn tùy rất nhiều vào chi tiết tình huống. Nếu tranh chấp nhiều, hiệu năng sẽ giảm mạnh, và ngay cả lệnh nguyên tử cũng có thể trở thành nút thắt (https://stackoverflow.com/q/2538070)
      Tôi nghĩ nhận xét rằng trong nhiều trường hợp chỉ cần dùng khóa và đừng lo lắng là đúng. Nhưng cũng có những ứng dụng hoặc tình huống có thể làm tốt hơn. Nếu người tiêu thụ lấy tất cả mục trong hàng đợi chỉ bằng một thao tác khóa, còn các nhà sản xuất gửi tín hiệu cho người tiêu thụ, thì nếu cẩn thận cũng có thể tăng hiệu quả hàng đợi và thông lượng. Chẳng hạn, đừng gửi tín hiệu mỗi khi thêm một mục; chỉ nên gửi khi hàng đợi đang rỗng rồi trở thành không rỗng
    • Chẳng phải cấu trúc dữ liệu lock-free có ý nghĩa hơn ở việc giảm tác động của tranh chấp, hơn là tăng thông lượng khi tranh chấp thấp sao?
    • Việc “chi phí có thể chấp nhận được” đó là ngoại lệ đối với những người có yêu cầu mạnh rằng những độ trễ dài hiếm gặp và khó dự đoán như đã nói tuyệt đối không được xảy ra

  • Bộ lập lịch lock-free chắc chắn trông thú vị, đặc biệt là tính khả tuyến hóa của broadcast sự kiện rất đáng chú ý. Tuy nhiên, trong benchmark của bài báo, mức cao nhất với 12 cặp actor (và 12 lõi?) là 43.500 thông điệp/giây, còn đồ thị một lõi cũng chỉ khoảng 5.000 thông điệp/giây, thấp đến đáng ngạc nhiên đối với kiểu benchmark này
    Engine yêu cầu Linux và quan trọng hơn là x86 (vì các lệnh assembly) nên tôi chưa tái hiện được, nhưng tôi kỳ vọng ít nhất khoảng 1 triệu request/giây cho mỗi cặp actor. Nếu nghĩ tới những trường hợp như Erlang, thấp hơn mức đó thì overhead lớn đến mức không chấp nhận được
    Engine này tập trung vào truyền thông điệp, nhưng theo kinh nghiệm của tôi, cách này rất khó xử lý. Máy trạng thái đã khó, làm việc với nhiều actor con còn khó hơn. Về cốt lõi, tôi cho rằng actor gần với việc cô lập trạng thái mà không cần khóa hơn là truyền thông điệp. Tôi nghĩ Swift actors đã làm đúng: dùng lời gọi phương thức thay vì thông điệp không chỉ dễ suy luận hơn, mà còn cho biết thêm những điểm mà ngữ cảnh có thể thay đổi ở runtime, đồng thời không nhất thiết phải kéo scheduler vào. Trạng thái dùng chung thì chậm và làm hại khả năng mở rộng
    Gần đây tôi đã làm một thư viện header-only triển khai thứ tương tự Swift actors bằng coroutine C++20. Nếu quan tâm thì có thể tìm “coroactors”. Khi không có tranh chấp đạt khoảng 10 triệu request/giây, còn khi có tranh chấp và phải dựa vào scheduler thì 1–3 triệu request/giây tôi cũng đã thấy overhead quá lớn. Đặc biệt là khi so với lời gọi phương thức thông thường trên trạng thái dùng chung được bảo vệ bằng mutex. Coroutine dễ lan truyền, khiến ngày càng nhiều hàm trở thành coroutine async, và trong các codebase không tầm thường thì sẽ có nhiều lời gọi coroutine hoặc truyền thông điệp. Vì vậy overhead phải thấp nhất có thể; nếu không, bạn sẽ dành nhiều thời gian cho chuyển đổi tác vụ hơn là làm việc hữu ích

  • Được mô tả là dựa trên actor, và giải thích rằng việc gửi message cho actor tương đương với việc chạy hàm của actor dưới một mutex. Tức là dù N thread gửi message, chỉ có 1 thread thực thi code của actor, nên nó được tuần tự hóa như mutex
    Vì vậy về mặt kỹ thuật có thể là “hoàn toàn lock-free”, nhưng chừng nào còn dùng actor thì không có cải thiện về song song hóa

    • Không hẳn vậy. Trong actor dựa trên mutex, nếu thread của actor bị dừng, mutex đó — tức code của actor — vẫn bị khóa cho đến khi thread ban đầu được tiếp tục. Vì mutex do thread bị dừng sở hữu vẫn đang bị khóa, nên dù có thêm tính song song, cũng không thể “khởi động lại” hay “tiếp tục” code actor đó
      Cách triển khai này phụ thuộc rất nhiều vào hàm có thể khởi động lại để một thread song song khác có thể nhặt và tiếp tục công việc của actor đang chạy dở nhưng bị dừng. Xem trang 3 của tài liệu thiết kế rất hay: https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
      Vì vậy, nói nghiêm ngặt thì có thể nó không “song song hơn” (vì số actor vẫn như nhau), nhưng có vẻ nó tận dụng tốt hơn nhiều tính song song hơn để hoàn thành cùng một tập công việc
    • Câu “việc gửi message cho actor tương đương với việc chạy hàm của actor dưới một mutex” nằm ở đâu? Theo tôi hiểu, mô hình actor nghĩa là truyền message và thực thi bất đồng bộ. Ngược lại, nếu có N actor thì N thread có thể chạy song song
    • Nói không có cải thiện về song song hóa thì đúng, nhưng nó cũng không làm giảm tính song song. Đây là một cách khác để nghĩ về concurrency, và theo tôi là cách dễ hơn
      Khi dễ suy nghĩ hơn, bạn cũng thấy rõ hơn chỗ nào sẽ có tranh chấp trên cùng tài nguyên, và trên thực tế điều đó giúp cải thiện tính song song tiềm năng. Nếu nhận ra một cơ hội cụ thể để SMP tăng tốc, trong mô hình actor bạn có thể hơi đi chệch đi một chút bằng cách để nhiều thread nhận cùng message queue; nếu không thể làm vậy thì thêm nhiều actor hơn để chia dữ liệu tốt hơn

  • Có ai từng debug hoặc profile vùng critical section có mức tranh chấp cao của STM so với triển khai mutex truyền thống chưa? Sau cùng vẫn cần thứ gì đó để điều phối truy cập đồng thời vào shared memory, và không có bữa trưa miễn phí. Mutex được tối ưu hóa, profile và hiểu rất kỹ
    Còn STM thì tôi không chắc có ở cùng mức đó không. Chẳng phải transaction có thể bị retry vô hạn(?) sao?

    • Trong trường hợp này, bộ điều phối là scheduler. Nó thực sự gọi các khối bất đồng bộ, và nếu thất bại thì có thể retry. Trong code của bài gốc có các atomic block, thực thi tuần tự các block, block có state, v.v. để bảo đảm mỗi lần chỉ có một truy cập
      Phần cốt lõi là scheduler.cpp và dùng std::coroutines
      Nó giống async/await trong các ngôn ngữ khác. Scheduler có queue các task (coroutine) và một thread pool (N>0) để chạy chúng
      Ở đây các task chứa dữ liệu gửi message cho nhau. Đổi lại mức dùng bộ nhớ tăng lên, nhưng không cần lock
    • Trên thực tế, trong STM không bị starvation, số lần retry transaction bị giới hạn. Một ví dụ là 2PLSF, và còn nhiều cách khác nữa https://zenodo.org/record/7886718

  • Có cảm giác giống BEAM nhỉ?
    https://youtu.be/bo5WL5IQAd0?feature=shared

  • Tôi chưa thấy nhắc đến việc debug một engine như thế này khó đến mức nào

  • Không có thời gian đọc phần triển khai, nhưng chỉ nhìn README thì nghe giống một hệ thống phân tán cổ điển giữa các game thread. Có vẻ các pattern như retry-backoff sẽ khá phổ biến

  • Lock-free nghe thì hay, nhưng tôi nghĩ code dùng atomic operation ở mức có ý nghĩa nên đi kèm chứng minh hình thức, và nếu có thể thì được máy kiểm chứng. Dùng đúng thứ tự atomic không phải sequential consistency là quá khó. Tôi đã thấy nhiều code viết sai, và bug từ đó là loại tệ nhất

  • Demo game đâu? Ngày nay để gọi là game engine thì cũng cần công cụ thực tế, exporter cho Maya hay 3DSMax, và những thứ như công cụ cộng tác, metric, thông báo nữa

    • Không đồng ý. “Game engine” không nhất thiết có nghĩa là “thứ có thể thay thế Unity hay Unreal”

  • Gọi là “lock-free” nhưng có vẻ chưa phải
    export std::mutex iolock{};
    export std::mutex errlock{};
    SDL_PollEvent