Mutex Tercepat

• Cosmopolitan Libc dikenal karena menyediakan berkas biner yang dapat dijalankan di berbagai sistem operasi, dan merupakan pustaka C yang juga dapat menunjukkan performa sangat baik di lingkungan produksi.
• Benchmark mutex untuk membuktikan performa: membandingkan kinerja implementasi mutex melalui pengujian di mana 30 thread menaikkan integer yang sama sebanyak 100.000 kali
  • Windows
    • pthread_mutex_t dari Cosmopolitan 2,75 kali lebih cepat daripada SRWLOCK milik Microsoft, dan menggunakan sumber daya CPU 18 kali lebih sedikit
    • Mutex milik Cygwin memiliki performa yang sangat rendah sampai-sampai lebih baik memakai spin lock.
  • Linux
    • pthread_mutex_t dari Cosmopolitan 3 kali lebih cepat daripada glibc, dan 11 kali lebih cepat daripada musl libc
    • Penggunaan CPU 42 kali lebih rendah daripada glibc, dan 178 kali lebih rendah daripada musl libc
  • MacOS
    • Apple Libc menunjukkan performa yang sedikit lebih baik daripada mutex Cosmopolitan
    • Cosmopolitan mengoptimalkan performa dengan menggunakan algoritme yang didasarkan pada makalah Ulrich Drepper, "Futexes Are Tricky"

Bagaimana ini bisa terjadi?

• Menghasilkan performa luar biasa dengan menggunakan library nsync yang ditulis oleh insinyur ternama Google, Mike Burrows
  • Ia adalah orang yang dulu menulis kode untuk Altavista, yang pernah menjadi pesaing Google
• Trik dan analisis nsync
  • nsync langsung menggunakan CAS (compare and swap) yang optimistis agar penguncian terjadi cepat saat tidak ada kontensi
  • Saat kunci tidak bisa diperoleh, nsync menambahkan thread pemanggil ke daftar tunggu taut ganda para penunggu
    • Setiap penunggu menerima semaphore-nya sendiri pada cache line terpisah yang independen
    • Begitu thread masuk ke status menunggu, ia tidak lagi menyentuh kunci dasar
    • Alasan ini penting dapat dilihat pada dokumen Ulrich Drepper, "What Every Programmer Should Know About Memory"
    • Jika banyak core menyentuh cache line yang sama, akan timbul banyak overhead komunikasi di dalam prosesor
  • nsync menggunakan futex untuk mendapatkan bantuan dari sistem operasi
    • futex adalah abstraksi hebat yang ditemukan beberapa tahun lalu di Linux, lalu mulai cepat diadopsi di OS lain
    • Di MacOS disebut ulock, dan di Windows disebut WaitOnAddress()
    • Dari OS yang didukung Cosmo, satu-satunya OS tanpa futex adalah NetBSD (yang mengimplementasikan semaphore POSIX di ruang kernel, dan setiap semaphore harus membuat file descriptor baru)
    • Hal penting tentang futex dan semaphore adalah OS dapat menidurkan thread. Dengan ini, nsync tidak perlu menghabiskan waktu CPU saat tidak ada pekerjaan yang harus dilakukan
  • nsync menghindari starvation dengan konsep "long wait"
    • Jika seorang penunggu terbangun 30 kali dan secara internal gagal memperoleh kunci, bit akan ditambahkan ke kunci untuk mencegah thread yang belum menunggu mengambilnya terlebih dahulu
    • CAS awal kemudian gagal untuk semua pihak lain sampai antrean agak terurai
  • nsync menggunakan konsep "designated waker" untuk mempercepat kasus penggunaan yang di-benchmark (kunci yang diperebutkan dengan critical section kecil)
    • Bit ini disetel pada kunci dasar ketika thread yang mencoba memperoleh kunci sedang dalam keadaan bangun
    • Dalam nsync, fungsi unlock bertugas membangunkan thread berikutnya yang menunggu kunci
    • Dengan bit ini, thread yang melakukan unlock tahu bahwa tidak perlu membangunkan thread kedua karena sudah ada satu pemegang kunci yang terbangun

Bukti online

• Performa dapat dikonfirmasi melalui demo langsung perangkat lunak yang menggunakan mutex Cosmopolitan.
• Server web http://ipv4.games/ menunjukkan performa yang mampu bertahan bahkan terhadap serangan DDOS berskala besar.

[GN⁺]

Komentar Hacker News

• Selalu menarik melihat implementasi mutex baru dan perbandingan performanya. Namun, benchmark kali ini tampak seperti microbenchmark. Biasanya performa diuji menggunakan program multithread berskala besar. Pada beban kerja yang kompleks, performa mutex bisa terlihat berbeda

  • Saya punya pengalaman menulis fast lock yang digunakan di WebKit, dan saya adalah orang yang menciptakan abstraksi ParkingLot. Ini juga digunakan di Rust dan Unreal Engine

• Alasan Cosmopolitan Mutexes bagus adalah karena menggunakan pustaka bernama nsync. Pustaka ini ditulis oleh insinyur ternama Google, Mike Burrows. Namun, saya penasaran mengapa implementasi mutex ini tidak dimasukkan dalam benchmark

  • Jika menggunakan __ulock di macOS, ini bisa diimplementasikan dengan lebih sederhana lewat fungsi wait() dan notify_one() dari pustaka atomic milik libc++

• Ada banyak opini positif tentang Cosmo/ape/redbean, tetapi saya belum pernah melihat orang benar-benar menggunakannya. Saya penasaran apakah alat-alat ini memang sangat inovatif tetapi belum banyak dipakai

• Saya sangat menghargai proyek Cosmopolitan, tetapi saya ragu terhadap klaim superioritas yang berlebihan. Alasan semua pustaka C tidak mengadopsi trik yang sama mungkin karena hal itu hanya selalu cepat pada arsitektur, model CPU, atau beban kerja tertentu

• Dalam lingkungan produksi, keandalan lebih penting daripada kecepatan atau efisiensi. Yang lebih penting adalah memastikan sistem tidak rusak

• Saya pernah memperbaiki bug yang saya temukan di fungsi unlock mutex milik nsync. Saya melihat ada peningkatan pada nsync di dalam proyek Cosmopolitan. Saya penasaran apakah aman menggunakan nsync upstream

• Thread dan mutex adalah salah satu elemen paling kompleks dalam ilmu komputer. Saya selalu skeptis sampai implementasi baru dipakai dalam skala besar. Saat Java muncul, banyak bug thread dan mutex terungkap di Solaris

• Saya terkejut nsync jauh lebih cepat daripada SRWLOCK. Saya pernah punya pengalaman melakukan reverse engineering pada win32 SRWLOCKs

• Setiap kali melihat mutex, saya punya perasaan negatif. Saya sudah banyak menghapus lock dari kode dan menggantinya dengan abstraksi queue atau messaging. Akhir-akhir ini saya juga mengeksplorasi berbagai algoritma locking. Saya ingin mencoba alat locking yang efisien seperti nsync