सबसे तेज़ Mutexes

 (justine.lol)
2 पॉइंट द्वारा GN⁺ 2024-10-03 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Cosmopolitan Libc कई operating systems पर चलने वाली binary files देने के लिए जाना जाता है, और यह एक C library है जो production environment में भी बेहतरीन performance दे सकती है।
  • performance साबित करने के लिए mutex benchmark: 30 threads एक ही integer को 100,000 बार बढ़ाते हैं, इस test के जरिए mutex implementations की performance की तुलना की गई।
    • Windows
      • Cosmopolitan pthread_mutex_t Microsoft के SRWLOCK से 2.75 गुना तेज़ है, और CPU resources 18 गुना कम इस्तेमाल करता है।
      • Cygwin का mutex इतना कमज़ोर प्रदर्शन दिखाता है कि spin lock का इस्तेमाल करना ही बेहतर लगे।
    • Linux
      • Cosmopolitan pthread_mutex_t glibc से 3 गुना, और musl libc से 11 गुना तेज़ है।
      • CPU usage glibc से 42 गुना, और musl libc से 178 गुना कम है।
    • MacOS
      • Apple Libc, Cosmopolitan के mutex से थोड़ा बेहतर प्रदर्शन दिखाता है।
      • Cosmopolitan, Ulrich Drepper के "Futexes Are Tricky" पेपर पर आधारित algorithm का इस्तेमाल करके performance optimize करता है।

यह कैसे संभव है?

  • Google के प्रसिद्ध engineer Mike Burrows द्वारा लिखी गई nsync library की वजह से यह बेहतरीन performance मिलती है।
    • वही पहले Google के पुराने प्रतिद्वंद्वी Altavista को कोड कर चुके थे।
  • nsync की tricks और analysis
    • nsync contention न होने पर lock को तेज़ी से लेने के लिए तुरंत optimistic CAS(compare and swap) का उपयोग करता है।
    • lock हासिल न होने पर nsync calling thread को waiters की doubly linked list में जोड़ देता है।
      • हर waiter को अलग, independent cache line पर अपना semaphore मिलता है।
      • एक बार thread wait state में चला जाए, तो वह base lock को दोबारा छूता नहीं है।
      • यह क्यों महत्वपूर्ण है, यह Ulrich Drepper के "What Every Programmer Should Know About Memory" दस्तावेज़ में देखा जा सकता है।
      • जब कई cores एक ही cache line को छूते हैं, तो processor के भीतर बहुत communication overhead पैदा होता है।
    • nsync operating system की मदद के लिए futex का इस्तेमाल करता है।
      • futex Linux में कुछ साल पहले बनाया गया एक शानदार abstraction है, और बाद में दूसरे OS में भी तेज़ी से अपनाया गया।
      • MacOS में इसे ulock कहा जाता है, और Windows में WaitOnAddress()।
      • Cosmo जिन OS को support करता है, उनमें futex न होने वाला एकमात्र OS NetBSD है (वह POSIX semaphore को kernel space में implement करता है, और हर semaphore के लिए नया file descriptor बनाना पड़ता है)।
      • futex और semaphore की अहम बात यह है कि OS thread को सुला सकता है। इससे nsync उस समय CPU time खर्च नहीं करता जब कोई काम नहीं होता।
    • nsync "long wait" की अवधारणा से starvation से बचता है।
      • अगर कोई waiter 30 बार जागने के बाद भी अंदरूनी तौर पर lock लेने में fail हो जाए, तो lock में एक bit जोड़ दी जाती है जो अभी तक इंतज़ार न करने वाले thread को lock लेने से रोकती है।
      • queue कुछ हद तक खाली होने तक बाकी सभी के लिए शुरुआती CAS fail हो जाती है।
    • nsync benchmark किए गए use case को, यानी छोटे critical section वाले contended lock को, तेज़ बनाने के लिए "designated waker" की अवधारणा का इस्तेमाल करता है।
      • जब lock लेने की कोशिश करने वाला thread जाग रहा होता है, तब base lock पर यह bit set रहती है।
      • nsync में unlock function, lock का इंतज़ार कर रहे अगले thread को जगाने की ज़िम्मेदारी निभाता है।
      • इस bit की मौजूदगी में unlock करने वाला thread जान जाता है कि दूसरा locker जगाने की ज़रूरत नहीं है, क्योंकि एक locker पहले से ही जाग रहा है।

ऑनलाइन प्रमाण

  • Cosmopolitan mutexes का इस्तेमाल करने वाले software के live demo से इसकी performance देखी जा सकती है।
  • http://ipv4.games/ web server बड़े पैमाने के DDOS हमलों को भी झेल सकने वाली performance दिखाता है।

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-10-03
Hacker News राय

  • नई mutex implementations और उनके performance comparisons देखना हमेशा दिलचस्प होता है। लेकिन यह benchmark एक microbenchmark जैसा लगता है। आम तौर पर बड़े multi-threaded programs का उपयोग करके performance test की जाती है। जटिल workloads में mutex का performance अलग तरह से दिखता है

    • मुझे WebKit में इस्तेमाल होने वाला fast lock लिखने का अनुभव है, और मैं ParkingLot abstraction का आविष्कार करने वाला व्यक्ति हूं। इसका उपयोग Rust और Unreal Engine में भी होता है

  • Cosmopolitan Mutexes अच्छे लगने का कारण शायद यह है कि उन्होंने nsync नाम की library इस्तेमाल की है। यह library Google के प्रसिद्ध engineer Mike Burrows ने लिखी थी। लेकिन मुझे यह जानने की उत्सुकता है कि इस mutex implementation को benchmark में शामिल क्यों नहीं किया गया

    • अगर आप macOS पर __ulock इस्तेमाल कर रहे हैं, तो libc++ की atomic library के wait(), notify_one() functions से इसे और सरल तरीके से implement किया जा सकता है

  • Cosmo/ape/redbean के बारे में बहुत सकारात्मक राय दिखती है, लेकिन मैंने वास्तव में किसी को इन्हें इस्तेमाल करते नहीं देखा। सोच रहा हूं कि क्या ये tools सच में revolutionary हैं, लेकिन अभी तक व्यापक रूप से अपनाए नहीं गए हैं

  • मैं Cosmopolitan project की काफ़ी सराहना करता हूं, लेकिन बढ़ा-चढ़ाकर किए गए superiority claims पर संदेह होता है। हो सकता है कि सभी C libraries ने वही tricks इसलिए न अपनाई हों क्योंकि वे सिर्फ कुछ खास architectures, CPU models, या workloads पर ही लगातार तेज़ होती हैं

  • production environment में speed या efficiency से ज़्यादा reliability महत्वपूर्ण होती है। सिस्टम को fail होने से बचाना अधिक ज़रूरी है

  • मुझे nsync के mutex unlock function में मिले एक bug को ठीक करने का अनुभव है। मैं Cosmopolitan project के भीतर nsync में किए गए improvements देख रहा हूं। सोच रहा हूं कि upstream nsync का उपयोग करना सुरक्षित है या नहीं

  • threads और mutexes computer science के सबसे जटिल हिस्सों में से एक हैं। जब तक किसी नई implementation का बड़े पैमाने पर इस्तेमाल न हो, मैं हमेशा skeptical रहता हूं। जब Java आया था, तब Solaris पर threads और mutexes से जुड़े बहुत से bugs सामने आए थे

  • यह देखकर हैरानी हुई कि nsync, SRWLOCK से कहीं तेज़ है। मुझे win32 SRWLOCKs को reverse engineer करने का अनुभव है

  • जब भी mutexes को देखता हूं तो एक नकारात्मक भावना आती है। मैंने बहुत से codebases में locks हटाकर उनकी जगह queue या messaging abstractions लगाए हैं। हाल में मैं अलग-अलग locking algorithms को explore कर रहा हूं। nsync जैसे efficient locking tools को आज़माना चाहता हूं