เอนจิน Peredvizhnikov: เกมเอนจินแบบล็อกฟรีที่เขียนด้วย C++20

 (github.com/eduard-permyakov)
4 คะแนน โดย GN⁺ 2023-09-11 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เป็น เกมเอนจินแบบล็อกฟรี อย่างสมบูรณ์ที่เขียนด้วย C++20 โดยนำโมเดล actor สำหรับการคำนวณพร้อมกันไปใช้งานบน primitive ของ coroutine ของภาษา
  • ใช้ abstraction แบบ actor model เพื่อให้พัฒนา logic แบบขนานที่ซับซ้อนได้โดยถูกแยกออกจากรายละเอียดการซิงโครไนซ์ระหว่างเธรด
  • การใช้งานแบบล็อกฟรีทั้งหมดให้การรับประกันความคืบหน้าแม้ในสถานการณ์ที่เธรดใด ๆ ยุติลง, ป้องกัน deadlock, ให้ latency ที่คาดการณ์ได้สำหรับการตอบสนองต่อเหตุการณ์สำคัญ และรองรับ fault tolerance
  • ให้การรับประกันว่าเอนจินจะยังคงทำงานต่อไป แม้หนึ่งใน worker thread จะยุติลงแบบ asynchronous
  • การใช้งานครอบคลุม Software Transactional Memory, คิวแบบล็อกฟรี, primitive สำหรับ serialization แบบล็อกฟรี, std::atomic_shared_ptr, scheduler แบบล็อกฟรี, memory allocator แบบล็อกฟรี, DAG ณ เวลา compile เป็นต้น
  • อัลกอริทึมแบบล็อกฟรี, เหตุผลด้านการออกแบบ และ benchmark อธิบายไว้ในเอกสาร Peredvizhnikov Engine: Design and Implementation of a Completely Lock-Free Scheduler
  • เพื่อช่วยการออกแบบแบบ data-oriented มีการใช้งาน ฐานข้อมูลในหน่วยความจำ ที่ปรับให้เหมาะกับการเข้าถึงเป็นหน่วย component และรองรับชุดข้อมูลขนาดใหญ่
  • ฐานข้อมูลในหน่วยความจำอิงกับโครงสร้างข้อมูล Flat Hash Map และ Bitwise Trie with Bitmap
  • แพลตฟอร์มที่รองรับในปัจจุบันมีเพียง Linux และการ build จากซอร์สต้องใช้ Clang++ 16
  • ซอร์สโค้ดเผยแพร่ภายใต้ไลเซนส์ GPLv3 และสิทธิ์ในการใช้โค้ดบางส่วนหรือทั้งหมดภายใต้ไลเซนส์อื่นอาจได้รับอนุญาตเป็นกรณีไป

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-09-11
ความคิดเห็นบน Hacker News

  • ในเฟรมเวิร์ก Actor ใช้ std::deque ธรรมดาเป็นคิวของพอยน์เตอร์เมธอด และเมื่อนำข้อความเข้า enqueue จะล็อกด้วยแนวทาง Benaphore
    เดิมทีเหมือน Futex คือใช้ทั้ง atomic operation และ primitive การล็อกร่วมกัน แต่ primitive การล็อกของผมจะทำงานเป็นชุดผสมระหว่าง spinlock/mutex ตามจำนวนครั้งที่ลองซ้ำ จาก benchmark ฟังก์ชัน push ข้อความแทบไม่เคยถูกบล็อก และโอกาสเกิด context switch ของระบบปฏิบัติการก็ต่ำ ดังนั้นแม้บางครั้งเธรดที่ถูกล็อกจะถูก swap out ก็ไม่ได้เกิดบ่อยพอจะคุ้มกับต้นทุนของอัลกอริทึม lock-free
    สรุปคือคิวที่ไม่ใช่ lock-free เร็วกว่าคิว lock-free มาก แต่ต้องยอมรับ latency ยาว ๆ ที่เกิดขึ้นนาน ๆ ครั้งจาก context switch ที่ไม่มีใครได้ล็อก บนฮาร์ดแวร์สมัยใหม่ สามารถ enqueue ได้ 10 ล้านข้อความต่อวินาที ต่อ worker thread

    • แม้จะบอกว่า “เดิมทีเหมือน Futex” แต่ Benaphore เป็นไอเดียที่เก่าพอสมควร และ Futex ก็ไม่ได้เป็นแค่ “Benaphore แบบ Linux”
      แก่นสำคัญคือไม่จำเป็นต้องมี kernel object หรือ primitive การล็อกแยกต่างหากจริง ๆ นี่คือจุดที่ไอเดียเปลี่ยนจาก “วิธีที่ใคร ๆ ก็รู้” ไปเป็น “ฟีเจอร์ที่ควรใส่ลงระบบปฏิบัติการเดี๋ยวนี้”
      ในการออกแบบ Futex แทนที่จะใช้อ็อบเจ็กต์ซิงโครไนซ์ของระบบปฏิบัติการเพื่อจัดการ collision ระบบปฏิบัติการจะรักษารายการแมป address→thread ไว้ ถ้าเธรด T หลับอยู่ที่ futex ของที่อยู่ X ก็จะถูกใส่ในรายการให้ X ชี้ไปยัง T และเมื่อมีคำขอให้ปลุก X futex ระบบปฏิบัติการจะไล่ดูรายการแล้วปลุก T
      ความต่างเห็นได้จากข้อจำกัด สิ่งอย่าง Benaphore เป็นทรัพยากรระดับทั้งระบบที่มีราคาแพง ผมจำได้ว่า BeOS อนุญาตแค่ประมาณ 65,536 ตัวต่อเครื่อง แต่ Futex เป็นแค่หน่วยความจำ จึงไม่มีเหตุผลต้องจำกัด
    • ถ้าเป็นบทความที่น่าสนใจแบบนี้ ควรใส่ ลิงก์ไปยังโค้ด ด้วย จะได้พิสูจน์ข้อกล่าวอ้าง และคนอย่างผมเห็นว่าไอเดียน่าสนใจจนอยากดู implementation ทันที
    • ขึ้นกับรายละเอียดของสถานการณ์มาก ถ้ามี contention สูง ประสิทธิภาพจะตกฮวบ และแม้แต่คำสั่ง atomic ก็อาจกลายเป็นคอขวดได้(https://stackoverflow.com/q/2538070)
      ผมเห็นด้วยกับข้อสังเกตที่ว่าในหลายกรณีใช้ล็อกไปเลยแล้วไม่ต้องกังวลก็พอ แต่ก็มีแอปพลิเคชันหรือสถานการณ์ที่ทำได้ดีกว่านั้น ถ้าผู้บริโภคดึงรายการทั้งหมดในคิวออกมาด้วยการล็อกครั้งเดียว และให้ผู้ผลิตส่งสัญญาณถึงผู้บริโภค วิธีนี้หากระวังให้ดีก็เพิ่มประสิทธิภาพของคิวและ throughput ได้ เช่น อย่าส่งสัญญาณทุกครั้งที่ใส่รายการ แต่ส่งเฉพาะตอนที่คิวเปลี่ยนจากว่างเป็นไม่ว่างเท่านั้น
    • โครงสร้างข้อมูลแบบ lock-free ไม่ได้มีความหมายมากกว่าในแง่การลด ผลกระทบของ contention มากกว่าการเพิ่ม throughput ตอน contention ต่ำหรือ?
    • คำว่า “ต้นทุนยอมรับได้” นั้นเป็นข้อยกเว้นสำหรับคนที่มี ข้อกำหนดเข้มงวด ว่า latency ยาว ๆ ที่คาดเดาไม่ได้และเกิดขึ้นนาน ๆ ครั้งตามที่พูดถึงต้องไม่มีทางเกิดขึ้นเลย

  • scheduler แบบ lock-free ดูน่าสนใจอย่างแน่นอน โดยเฉพาะ linearizability ของ event broadcast ที่สะดุดตา แต่ใน benchmark ของบทความ ค่าสูงสุดอยู่ที่ 43,500 ข้อความต่อวินาทีเมื่อมี actor 12 คู่ (และ 12 คอร์?) และกราฟแบบ single-core ก็ประมาณ 5,000 ข้อความต่อวินาที ซึ่งถือว่าต่ำจนน่าประหลาดใจสำหรับ benchmark ประเภทนี้
    เอนจินต้องใช้ Linux และที่สำคัญกว่านั้นคือต้องใช้ x86 (เพราะคำสั่ง assembly) เลยยังทำซ้ำผลไม่ได้ แต่ผมคาดหวังอย่างน้อยราว 1 ล้าน request ต่อวินาทีต่อ actor หนึ่งคู่ ถ้าคิดถึงกรณีอย่าง Erlang หากต่ำกว่านั้น overhead ก็จะสูงจนแทบห้ามใช้
    เอนจินนี้เน้น message passing แต่จากประสบการณ์ วิธีนี้จัดการยากมาก state machine นั้นยาก และยิ่งยากขึ้นเมื่อทำงานกับ actor ย่อยหลายตัว โดยแก่นแล้วผมมองว่า actor ใกล้เคียงกับการแยกสถานะโดยไม่ต้องล็อก มากกว่าการส่งข้อความ ผมคิดว่า Swift actors ทำได้ถูกทางแล้ว การใช้ method call แทน message ไม่เพียงทำให้ reasoning ง่ายขึ้น แต่ยังบอกจุดที่ context อาจเปลี่ยนได้ใน runtime เพิ่มเติม และไม่จำเป็นต้องให้ scheduler เข้ามาเกี่ยวเสมอไป shared state ช้าและทำให้ scalability แย่
    เมื่อไม่นานมานี้ผมทำไลบรารี header-only ด้วย C++20 coroutine ที่คล้าย Swift actors ถ้าสนใจก็ลองค้นหา “coroactors” ได้ ตอนที่ไม่มี contention ได้ประมาณ 10 ล้าน request ต่อวินาที ส่วนตอนมี contention และต้องพึ่ง scheduler ได้ 1–3 ล้าน request ต่อวินาที ผมยังคิดว่า overhead สูงเกินไป โดยเฉพาะเมื่อเทียบกับ method call ปกติบน shared state ที่ป้องกันด้วย mutex coroutine แพร่กระจายได้ง่าย ทำให้ฟังก์ชันมากขึ้นเรื่อย ๆ กลายเป็น async coroutine และใน codebase ที่ไม่เล็ก การเรียก coroutine หรือ message passing จะมีจำนวนมาก ดังนั้น overhead ต้องต่ำที่สุดเท่าที่ทำได้ ไม่อย่างนั้นจะใช้เวลากับการสลับงานมากกว่าทำงานที่มีประโยชน์

  • ระบุว่าเป็นแบบ actor-based และอธิบายว่าการส่งข้อความไปยัง actor เทียบเท่ากับการรันฟังก์ชันของ actor ภายใต้ mutex กล่าวคือ แม้จะมี N เธรดส่งข้อความ เธรดที่รันโค้ดของ actor ก็มีแค่ 1 เธรด จึงถูก serialize เหมือน mutex
    ดังนั้นในเชิงเทคนิค แม้อาจเป็น “lock-free อย่างสมบูรณ์” ได้ แต่ตราบใดที่ใช้ actor ก็ไม่มี การปรับปรุงด้านการทำ parallelization

    • ไม่จำเป็นต้องเป็นอย่างนั้นเสมอไป ใน actor ที่ใช้ mutex ถ้าเธรดของ actor ถูกหยุดชั่วคราว mutex นั้น หรือก็คือโค้ดของ actor จะยังคงถูกล็อกไว้จนกว่าเธรดเดิมจะกลับมาทำงานต่อ เนื่องจาก mutex ที่เธรดที่ถูกหยุดเป็นเจ้าของยังล็อกอยู่ จึงไม่สามารถ “เริ่มใหม่” หรือ “ทำต่อ” โค้ดของ actor นั้นได้ แม้จะมี parallelism มากกว่านั้นก็ตาม
      implementation นี้พึ่งพา ฟังก์ชันที่เริ่มใหม่ได้ อย่างมาก เพื่อให้เธรด parallel อื่นหยิบงานของ actor ที่กำลังดำเนินอยู่แต่ถูกหยุดไปทำต่อได้ ดูหน้า 3 ของเอกสารออกแบบที่ยอดเยี่ยมได้ที่: https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
      ดังนั้นถ้าพูดอย่างเคร่งครัด อาจไม่ได้ “parallel มากขึ้น” (เพราะจำนวน actor เท่าเดิม) แต่ดูเหมือนว่าจะใช้ parallelism ที่มากขึ้นได้ดีกว่าในการทำชุดงานเดียวกันให้เสร็จ
    • คำว่า “การส่งข้อความไปยัง actor เทียบเท่ากับการรันฟังก์ชันของ actor ภายใต้ mutex” อยู่ตรงไหน? ตามที่ผมเข้าใจ actor model หมายถึงการส่งข้อความและการทำงานแบบ asynchronous ยิ่งไปกว่านั้น ถ้ามี actor N ตัว เธรด N ตัวก็สามารถรันแบบ parallel ได้
    • ที่ว่าไม่มีการปรับปรุงด้านการทำ parallelization นั้นถูกต้อง แต่ก็ไม่ได้ลด parallelism เช่นกัน มันเป็นอีกวิธีหนึ่งในการคิดเรื่อง concurrency และสำหรับผมเป็นวิธีที่ง่ายกว่า
      ถ้าคิดได้ง่าย ก็จะเห็นได้ดีขึ้นว่าจุดไหนจะเกิด contention กับทรัพยากรเดียวกัน และในทางปฏิบัติก็ช่วยปรับปรุง parallelism ที่เป็นไปได้ หากสังเกตเห็นโอกาสเฉพาะที่ SMP จะช่วยเพิ่มความเร็วได้ ก็สามารถออกนอก actor model ไปเล็กน้อย โดยให้หลายเธรดรับจาก message queue ได้ หรือถ้าทำไม่ได้ ก็เพิ่ม actor ให้มากขึ้นเพื่อแบ่งข้อมูลให้ดีขึ้น

  • มีใครเคย debug หรือ profile critical section ที่มี contention สูงของ STM เทียบกับ implementation แบบ mutex ดั้งเดิมไหม? สุดท้ายก็ยังต้องมีอะไรบางอย่างมาควบคุมการเข้าถึง shared memory พร้อมกัน และไม่มีของฟรี mutex ได้รับการ optimize, profile และทำความเข้าใจมาอย่างดีมาก
    ในทางกลับกัน ผมไม่แน่ใจว่า STM อยู่ในระดับเดียวกันหรือไม่ transaction อาจถูกลองใหม่อย่างไม่มีกำหนด(?) ได้ไม่ใช่หรือ?

    • ในกรณีนี้ ตัวกลางควบคุมคือ scheduler จริง ๆ แล้วมันเป็นตัวที่เรียก block แบบ asynchronous และถ้าล้มเหลวก็อาจลองใหม่ ในโค้ดต้นฉบับมี atomic block, การรัน block ตามลำดับ และ block ที่มี state เพื่อรับประกันว่ามีการเข้าถึงทีละครั้ง
      แกนหลักคือ scheduler.cpp และใช้ std::coroutines
      คล้ายกับ async/await ในภาษาอื่น scheduler มี queue ของงาน (coroutine) และ thread pool (N>0) สำหรับรันงานเหล่านั้น
      ที่นี่งานที่มีข้อมูลจะส่งข้อความหากัน ไม่จำเป็นต้องใช้ lock โดยแลกกับการใช้หน่วยความจำเพิ่มขึ้น
    • จริง ๆ แล้วใน STM ที่ไม่มี starvation จำนวนครั้งที่ transaction ถูก retry จะถูกจำกัด ตัวอย่างหนึ่งคือ 2PLSF และยังมีวิธีอื่น ๆ อีกหลายแบบ https://zenodo.org/record/7886718

  • ให้ความรู้สึกเหมือน BEAM ไหม?
    https://youtu.be/bo5WL5IQAd0?feature=shared

  • ยังไม่เห็นมีการพูดถึงว่าการ debug engine แบบนี้ยากแค่ไหน

  • ไม่มีเวลาอ่าน implementation แต่ดูจาก README แล้วฟังดูเหมือน distributed system แบบคลาสสิกระหว่างเธรดของเกม น่าจะมี pattern อย่าง retry-backoff อยู่ทั่วไป

    • paper อธิบายรายละเอียดมากกว่าโดยไม่ต้องลงไปขุด implementation และดูเหมือนจะก้าวหน้ากว่านั้นพอสมควร
      https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...

  • คำว่า lock-free ฟังดูเท่ก็จริง แต่ผมคิดว่าโค้ดที่ใช้ atomic operation ในระดับที่มีนัยสำคัญควรมาพร้อม proof ที่เป็นทางการ และถ้าเป็นไปได้ควรผ่านการตรวจสอบโดยเครื่องด้วย การใช้ atomic ordering ที่ไม่ใช่ sequential consistency ให้ถูกต้องนั้นยากเกินไป ผมเคยเห็นโค้ดที่เขียนผิดมาหลายครั้ง และ bug ที่เกิดจากตรงนั้นแย่ที่สุด

  • เกมเดโมอยู่ไหน? ทุกวันนี้ถ้าจะมองว่าเป็น game engine ก็ต้องมีเครื่องมือจริง, exporter อย่าง Maya หรือ 3DSMax และเครื่องมือ collaboration, metrics, alert อะไรทำนองนั้นด้วย

    • ไม่เห็นด้วย “game engine” ไม่ได้แปลว่าต้องเป็น “สิ่งที่ทดแทน Unity หรือ Unreal ได้” เสมอไป

  • บอกว่า “lock-free” แต่ดูเหมือนว่ายังไม่ใช่
    export std::mutex iolock{};
    export std::mutex errlock{};
    SDL_PollEvent