FreeBSD ने SYSINIT के bubble sort को merge sort में बदला

• यह रिपोर्ट मिली थी कि FreeBSD boot के समय 7% समय SYSINIT को bubble sort करने में खर्च करता है
• यह कोड 1996 में लिखा गया था, और उस समय sort करने के लिए लगभग 30 SYSINIT थे, लेकिन अब उनकी संख्या 1000 से अधिक हो गई है, इसलिए इसमें ज़्यादा समय लगने लगा
• हाल की commit में SYSINIT arrays को SLIST में बदला गया, जिससे merge sort संभव हो गया और नए SYSINIT जोड़ना भी तेज़ हो गया
  • merge sort लगभग ~100 गुना तक तेज़ है
• Firecracker के आधार पर, कुल 28ms boot समय में से 2ms बचाए जा सकते हैं

[rousseau]

एक निश्चित आकार से छोटे datasets के लिए, छोटे और समझने में आसान code का उपयोग करना शायद प्रभावी रहा होगा.
ऐसे फ़ैसलों की वजह से बचे हुए धीमे algorithm के इस्तेमाल के कई उदाहरण आज भी होंगे.
(यह मेरा पूर्वाग्रह है, लेकिन) अगर कोई ऐसी बातों पर आपत्ति उठाता है, तो मुझे काफ़ी मज़बूती से लगता है कि वह शायद ऐसा व्यक्ति होगा जो मदद तो नहीं करता, लेकिन शिकायतें बहुत करता है.

[xguru]

FreeBSD बूट के समय 7% समय SYSINITs को bubble sort करने में खर्च करता है

[GN⁺]

Hacker News टिप्पणियाँ

• FreeBSD ने SYSINTs में bubblesort को mergesort से बदलकर boot time में बड़ा सुधार किया है।
• bubblesort का उपयोग कोई गलती नहीं था; यह कई वर्षों तक ठीक काम करता रहा, जब तक कि कुछ खास use cases ने इसकी inefficiency को उजागर नहीं किया।
• यह optimization AWS Lambda जैसे उन मामलों के लिए ज़रूरी थी जहाँ बार-बार boot होता है।
• Firecracker पर boot करते समय FreeBSD kernel अपना 7% समय SYSINTs में bubblesort चलाने में खर्च कर रहा था।
• mergesort में बदलाव से code 5 lines कम हुआ और boot time "100 गुना तेज़" हो गया।
• शुरुआत में bubblesort का उपयोग करने का फैसला शायद job count जैसे factors से प्रभावित रहा हो।
• mergesort में बदलाव यह दिखाता है कि छोटे सुधार भी overall performance में महत्वपूर्ण अंतर ला सकते हैं।
• कुछ users ने bubblesort की जानी-पहचानी inefficiency और कम intuitive होने को देखते हुए इसके शुरुआती उपयोग पर सवाल उठाए।
• इस बदलाव ने FreeBSD के boot time और SYSINTs में bubblesort के उपयोग को लेकर संबंधित चर्चाओं को जन्म दिया है.