Mutexes ที่เร็วที่สุด

 (justine.lol)
2 คะแนน โดย GN⁺ 2024-10-03 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Cosmopolitan Libc เป็นที่รู้จักจากการมีไฟล์ไบนารีที่สามารถรันได้บนหลายระบบปฏิบัติการ และเป็นไลบรารี C ที่ให้ประสิทธิภาพยอดเยี่ยมได้แม้ในสภาพแวดล้อมจริง
  • เบนช์มาร์ก mutex เพื่อพิสูจน์ประสิทธิภาพ: เปรียบเทียบสมรรถนะของการติดตั้งใช้งาน mutex ด้วยการทดสอบที่ 30 เธรดเพิ่มค่าจำนวนเต็มตัวเดียวกัน 100,000 ครั้ง
    • Windows
      • pthread_mutex_t ของ Cosmopolitan เร็วกว่า SRWLOCK ของ Microsoft 2.75 เท่า และใช้ทรัพยากร CPU น้อยกว่า 18 เท่า
      • mutex ของ Cygwin มีประสิทธิภาพต่ำมากจนถึงระดับที่ใช้ spin lock จะดีกว่า
    • Linux
      • pthread_mutex_t ของ Cosmopolitan เร็วกว่า glibc 3 เท่า และเร็วกว่า musl libc 11 เท่า
      • การใช้ CPU น้อยกว่า glibc 42 เท่า และน้อยกว่า musl libc 178 เท่า
    • MacOS
      • Apple Libc ให้ประสิทธิภาพดีกว่า mutex ของ Cosmopolitan เล็กน้อย
      • Cosmopolitan ปรับแต่งประสิทธิภาพโดยใช้อัลกอริทึมที่อ้างอิงจากบทความ "Futexes Are Tricky" ของ Ulrich Drepper

ทำแบบนั้นได้อย่างไร?

  • ให้ประสิทธิภาพยอดเยี่ยมด้วยการใช้ ไลบรารี nsync ที่เขียนโดย Mike Burrows วิศวกรชื่อดังของ Google
    • เขาเป็นคนที่เคยเขียนโค้ดให้ Altavista ซึ่งเป็นคู่แข่งของ Google ในอดีต
  • กลเม็ดและการวิเคราะห์ของ nsync
    • nsync ใช้ CAS (compare and swap) แบบมองโลกในแง่ดีทันที เพื่อให้การล็อกเกิดขึ้นได้อย่างรวดเร็วเมื่อไม่มีการแย่งกันใช้
    • เมื่อไม่สามารถยึดล็อกได้ nsync จะเพิ่มเธรดที่เรียกเข้าไปใน doubly linked list ของผู้รอ
      • ผู้รอแต่ละรายจะได้ semaphore ของตัวเองบน cache line อิสระแยกต่างหาก
      • เมื่อเธรดเข้าสู่สถานะรอแล้ว มันจะไม่แตะต้องล็อกหลักอีกต่อไป
      • เหตุผลที่เรื่องนี้สำคัญสามารถดูได้จากเอกสาร "What Every Programmer Should Know About Memory" ของ Ulrich Drepper
      • หากหลายคอร์แตะ cache line เดียวกัน จะเกิด overhead ด้านการสื่อสารภายในโปรเซสเซอร์จำนวนมาก
    • nsync ใช้ futex เพื่อรับความช่วยเหลือจากระบบปฏิบัติการ
      • futex เป็น abstraction ที่ยอดเยี่ยมซึ่งถูกคิดค้นบน Linux เมื่อหลายปีก่อน และเริ่มถูกนำไปใช้บนระบบปฏิบัติการอื่นอย่างรวดเร็ว
      • บน MacOS เรียกว่า ulock และบน Windows เรียกว่า WaitOnAddress()
      • ในบรรดาระบบปฏิบัติการที่ Cosmo รองรับ มีเพียง NetBSD เท่านั้นที่ไม่มี futex (โดยมันติดตั้ง POSIX semaphore ไว้ใน kernel space และแต่ละ semaphore ต้องสร้าง file descriptor ใหม่)
      • ประเด็นสำคัญของ futex และ semaphore คือ OS สามารถทำให้เธรดหลับได้ ทำให้ nsync ไม่ต้องใช้เวลา CPU เมื่อไม่มีงานให้ทำ
    • nsync หลีกเลี่ยง starvation ด้วยแนวคิด "long wait"
      • หากผู้รอถูกปลุก 30 ครั้งและยังยึดล็อกไม่ได้ภายใน ระบบจะเพิ่มบิตในล็อกเพื่อป้องกันไม่ให้เธรดที่ยังไม่เคยรอเข้ามาได้ล็อกก่อน
      • CAS เริ่มต้นจะล้มเหลวสำหรับคนอื่นทั้งหมดจนกว่าคิวรอจะคลี่คลายไปในระดับหนึ่ง
    • nsync ใช้แนวคิด "designated waker" เพื่อทำให้กรณีการใช้งานที่นำมาเบนช์มาร์กไว้เร็วขึ้น (การล็อกแบบมีการแย่งกันใช้และมี critical section ขนาดเล็ก)
      • เมื่อเธรดที่พยายามยึดล็อกยังตื่นอยู่ บิตนี้จะถูกตั้งไว้บนล็อกหลัก
      • ใน nsync ฟังก์ชันปลดล็อกมีหน้าที่ปลุกเธรดถัดไปที่กำลังรอล็อก
      • เมื่อมีบิตนี้ เธรดที่ปลดล็อกจะรู้ว่าไม่จำเป็นต้องปลุกตัวล็อกตัวที่สอง เพราะมีตัวหนึ่งตื่นอยู่แล้ว

หลักฐานออนไลน์

  • สามารถตรวจสอบประสิทธิภาพได้ผ่านเดโมสดของซอฟต์แวร์ที่ใช้ mutex ของ Cosmopolitan
  • เว็บเซิร์ฟเวอร์ http://ipv4.games/ แสดงให้เห็นถึงสมรรถนะที่ทนทานได้แม้เจอกับการโจมตี DDoS ขนาดใหญ่

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

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

 
GN⁺ 2024-10-03
ความคิดเห็นจาก Hacker News

  • การได้เห็นการทำอิมพลีเมนเทชัน mutex แบบใหม่และการเปรียบเทียบประสิทธิภาพของมันเป็นเรื่องน่าสนใจเสมอ แต่เบนช์มาร์กครั้งนี้ดูจะเป็นไมโครบีนช์มาร์กมากกว่า โดยทั่วไปมักทดสอบประสิทธิภาพด้วยโปรแกรมมัลติเธรดขนาดใหญ่กว่า ในเวิร์กโหลดที่ซับซ้อนกว่านี้ ประสิทธิภาพของ mutex อาจออกมาแตกต่างกัน

    • เคยมีประสบการณ์เขียน fast lock ที่ใช้ใน WebKit และเป็นคนคิดค้น abstraction ของ ParkingLot ซึ่งถูกใช้ใน Rust และ Unreal Engine ด้วย

  • เหตุผลที่ Cosmopolitan Mutexes ดูดีเป็นเพราะใช้ไลบรารีชื่อ nsync ซึ่งเขียนโดย Mike Burrows วิศวกรชื่อดังของ Google แต่ก็สงสัยว่าทำไมอิมพลีเมนเทชัน mutex นี้ถึงไม่ถูกรวมอยู่ในเบนช์มาร์ก

    • ถ้าใช้ __ulock บน macOS ก็สามารถทำให้อิมพลีเมนต์ได้ง่ายกว่าด้วยฟังก์ชัน wait() และ notify_one() ในไลบรารี atomic ของ libc++

  • มีความเห็นเชิงบวกต่อ Cosmo/ape/redbean มาก แต่ยังไม่เคยเห็นใครใช้งานจริง เลยสงสัยว่าเครื่องมือเหล่านี้ล้ำจริงแต่ยังไม่แพร่หลาย หรือเป็นอย่างอื่นกันแน่

  • ชื่นชมโครงการ Cosmopolitan แต่ก็ยังสงสัยกับคำกล่าวอ้างความเหนือกว่าที่ดูเกินจริง เหตุผลที่ C library ทุกตัวไม่ได้ใช้เทคนิคเดียวกัน อาจเป็นเพราะมันไม่ได้เร็วกว่าเสมอไป นอกจากกับสถาปัตยกรรม รุ่น CPU หรือเวิร์กโหลดบางแบบเท่านั้น

  • ในสภาพแวดล้อม production ความน่าเชื่อถือสำคัญกว่าความเร็วหรือประสิทธิภาพ สิ่งที่สำคัญกว่าคือทำให้ระบบไม่พัง

  • เคยมีประสบการณ์แก้บั๊กที่พบในฟังก์ชันปลดล็อก mutex ของ nsync และกำลังติดตามการปรับปรุงของ nsync ภายในโครงการ Cosmopolitan อยู่ เลยสงสัยว่าการใช้ upstream nsync จะปลอดภัยหรือไม่

  • เธรดและ mutex เป็นหนึ่งในองค์ประกอบที่ซับซ้อนที่สุดในวิทยาการคอมพิวเตอร์ จึงมักจะยังสงสัยกับอิมพลีเมนเทชันใหม่ ๆ เสมอ จนกว่าจะถูกใช้งานในวงกว้าง เมื่อตอน Java ออกมาใหม่ ๆ ก็มีบั๊กเกี่ยวกับเธรดและ mutex บน Solaris โผล่ออกมาเยอะมาก

  • รู้สึกประหลาดใจที่ nsync เร็วกว่า SRWLOCK มาก เคยมีประสบการณ์รีเวิร์สเอนจิเนียร์ win32 SRWLOCKs มาก่อน

  • ทุกครั้งที่เห็น mutex จะเกิดความรู้สึกด้านลบ เคยทำงานลบ lock ออกจากโค้ดจำนวนมากแล้วแทนที่ด้วย abstraction แบบคิวหรือ messaging ช่วงหลังมานี้กำลังสำรวจอัลกอริทึมการล็อกหลายแบบ และอยากลองใช้เครื่องมือการล็อกที่มีประสิทธิภาพอย่าง nsync