Các mutex nhanh nhất

 (justine.lol)
2 điểm bởi GN⁺ 2024-10-03 | 1 bình luận | Chia sẻ qua WhatsApp
  • Cosmopolitan Libc nổi tiếng với việc cung cấp các tệp nhị phân có thể chạy trên nhiều hệ điều hành, đồng thời là một thư viện C có thể đạt hiệu năng rất cao cả trong môi trường production.
  • Benchmark mutex để chứng minh hiệu năng: so sánh hiệu năng của các triển khai mutex thông qua bài kiểm tra trong đó 30 luồng cùng tăng một số nguyên giống nhau 100.000 lần
    • Windows
      • pthread_mutex_t của Cosmopolitan nhanh hơn 2,75 lần so với SRWLOCK của Microsoft, đồng thời dùng ít tài nguyên CPU hơn 18 lần
      • Mutex của Cygwin có hiệu năng rất thấp, đến mức dùng spin lock còn tốt hơn.
    • Linux
      • pthread_mutex_t của Cosmopolitan nhanh hơn 3 lần so với glibc và nhanh hơn 11 lần so với musl libc
      • Mức sử dụng CPU thấp hơn 42 lần so với glibc và 178 lần so với musl libc
    • MacOS
      • Apple Libc cho hiệu năng nhỉnh hơn một chút so với mutex của Cosmopolitan
      • Cosmopolitan tối ưu hiệu năng bằng thuật toán dựa trên bài báo "Futexes Are Tricky" của Ulrich Drepper

Làm sao điều đó có thể xảy ra?

  • Hiệu năng vượt trội đạt được nhờ sử dụng thư viện nsync do kỹ sư nổi tiếng của Google là Mike Burrows viết
    • Ông cũng là người từng viết mã cho Altavista, đối thủ cũ của Google
  • Các mẹo và phân tích của nsync
    • nsync dùng ngay CAS (compare and swap) theo hướng lạc quan để khóa diễn ra nhanh khi không có tranh chấp
    • Khi không thể giành được khóa, nsync sẽ thêm luồng gọi vào một danh sách liên kết kép của các luồng chờ
      • Mỗi waiter nhận semaphore riêng của mình trên một cache line độc lập
      • Khi luồng đi vào trạng thái chờ, nó không còn đụng tới khóa cơ sở nữa
      • Lý do điều này quan trọng có thể xem trong tài liệu "What Every Programmer Should Know About Memory" của Ulrich Drepper
      • Khi nhiều lõi cùng chạm vào một cache line, bên trong bộ xử lý sẽ phát sinh rất nhiều overhead giao tiếp
    • nsync tận dụng sự hỗ trợ của hệ điều hành thông qua futex
      • futex là một lớp trừu tượng tuyệt vời được phát minh trên Linux từ nhiều năm trước, và nhanh chóng được dùng trên các hệ điều hành khác
      • Trên MacOS nó được gọi là ulock, còn trên Windows là WaitOnAddress()
      • Trong các hệ điều hành mà Cosmo hỗ trợ, NetBSD là hệ điều hành duy nhất không có futex (triển khai semaphore POSIX trong không gian kernel, và mỗi semaphore phải tạo một file descriptor mới)
      • Điểm quan trọng của futex và semaphore là hệ điều hành có thể đưa luồng vào trạng thái ngủ. Nhờ đó nsync không phải tiêu tốn thời gian CPU khi không có việc để làm
    • nsync tránh starvation bằng khái niệm "long wait"
      • Khi một waiter bị đánh thức 30 lần và vẫn thất bại trong việc giành khóa ở bên trong, nó sẽ thêm một bit vào khóa để ngăn các luồng chưa phải chờ giành được khóa
      • CAS ban đầu sẽ thất bại với mọi luồng khác cho đến khi hàng đợi được giải tỏa ở một mức nào đó
    • nsync dùng khái niệm "designated waker" để tăng tốc cho trường hợp sử dụng được benchmark (khóa có tranh chấp với critical section nhỏ)
      • Khi có một luồng đang thức và cố gắng lấy khóa, bit này sẽ được đặt trên khóa cơ sở
      • Trong nsync, hàm unlock có trách nhiệm đánh thức luồng tiếp theo đang chờ khóa
      • Với bit này, luồng unlock biết rằng không cần đánh thức luồng thứ hai vì đã có một waiter đang thức rồi

Bằng chứng trực tuyến

  • Có thể kiểm chứng hiệu năng qua bản demo live của phần mềm dùng mutex Cosmopolitan.
  • Máy chủ web http://ipv4.games/ cho thấy hiệu năng đủ sức chống chọi ngay cả trước các cuộc tấn công DDoS quy mô lớn.

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-10-03
Ý kiến trên Hacker News

  • Việc xem các triển khai mutex mới và so sánh hiệu năng của chúng lúc nào cũng thú vị. Nhưng benchmark lần này có vẻ là microbenchmark. Thông thường nên kiểm tra hiệu năng bằng một chương trình đa luồng quy mô lớn. Với tải công việc phức tạp, hiệu năng của mutex sẽ thể hiện khác đi

    • Tôi có kinh nghiệm viết loại khóa nhanh dùng trong WebKit và là người phát minh ra trừu tượng hóa ParkingLot. Nó cũng được dùng trong Rust và Unreal Engine

  • Lý do Cosmopolitan Mutexes tốt là vì nó dùng một thư viện tên là nsync. Thư viện này do Mike Burrows, một kỹ sư danh tiếng của Google, viết. Nhưng tôi thắc mắc vì sao chính triển khai mutex này lại không được đưa vào benchmark

    • Nếu dùng __ulock trên macOS, thì có thể triển khai đơn giản hơn bằng các hàm wait(), notify_one() của thư viện atomic trong libc++

  • Có nhiều ý kiến tích cực về Cosmo/ape/redbean, nhưng tôi chưa từng thấy ai thực sự dùng chúng. Tôi tự hỏi liệu những công cụ này thực sự mang tính cách mạng nhưng vẫn chưa được dùng rộng rãi hay không

  • Tôi đánh giá cao dự án Cosmopolitan, nhưng vẫn nghi ngờ những tuyên bố ưu việt có phần cường điệu. Lý do không phải mọi thư viện C đều áp dụng cùng một mẹo có thể là vì nó chỉ luôn nhanh hơn trên một số kiến trúc, mẫu CPU hoặc tải công việc nhất định

  • Trong môi trường production, độ tin cậy quan trọng hơn tốc độ hay hiệu suất. Điều quan trọng hơn là bảo đảm hệ thống không bị hỏng

  • Tôi từng có kinh nghiệm sửa một lỗi được phát hiện trong hàm mở khóa mutex của nsync. Tôi đang thấy các cải tiến của nsync trong dự án Cosmopolitan. Tôi thắc mắc liệu dùng nsync upstream có an toàn hay không

  • Thread và mutex là một trong những thành phần phức tạp nhất trong khoa học máy tính. Tôi luôn hoài nghi về các triển khai mới cho đến khi chúng được dùng ở quy mô lớn. Khi Java xuất hiện, rất nhiều lỗi về thread và mutex trên Solaris đã bị lộ ra

  • Tôi ngạc nhiên khi nsync nhanh hơn SRWLOCK rất nhiều. Tôi từng có kinh nghiệm reverse engineer win32 SRWLOCKs

  • Mỗi khi nhìn thấy mutex là tôi lại có cảm giác tiêu cực. Tôi đã từng làm việc loại bỏ lock trong rất nhiều đoạn mã và thay chúng bằng queue hoặc các trừu tượng hóa messaging. Gần đây tôi đang khám phá nhiều thuật toán locking khác nhau. Tôi muốn thử dùng các công cụ locking hiệu quả như nsync