FreeBSD mengubah bubble sort di SYSINIT menjadi merge sort

 (twitter.com/cperciva)
10 poin oleh GN⁺ 2023-08-22 | 3 komentar | Bagikan ke WhatsApp
  • Ada laporan bahwa saat boot, FreeBSD menghabiskan 7% waktunya untuk melakukan bubble sort pada SYSINIT
  • Kode ini dibuat pada 1996, dan pada masa itu hanya ada sekitar 30 SYSINIT yang perlu diurutkan, tetapi sekarang jumlahnya sudah lebih dari seribu sehingga memakan waktu lebih lama
  • Dalam commit terbaru, array SYSINIT diubah menjadi SLIST sehingga merge sort dapat digunakan, dan penambahan SYSINIT baru juga menjadi lebih cepat
    • Merge sort sekitar ~100x lebih cepat
  • Berdasarkan Firecracker, dari total waktu boot 28 ms, sekitar 2 ms bisa dihemat

Bacaan terkait

3 komentar

 
rousseau 2023-08-23

Untuk dataset di bawah ukuran tertentu, mungkin masuk akal memakai kode yang kecil dan mudah dipahami.
Masih banyak contoh penggunaan algoritme lambat yang tersisa karena keputusan seperti itu.
(Mungkin ini prasangka, tapi) saya jadi kuat merasa bahwa kalau ada orang yang mempermasalahkan hal seperti ini, kemungkinan besar dia tipe orang yang tidak membantu apa-apa dan hanya banyak mengeluh.
 
GN⁺ 2023-08-22
Komentar Hacker News
  • FreeBSD mengganti bubblesort dengan mergesort di SYSINITs, sehingga waktu boot meningkat secara signifikan.
  • Penggunaan bubblesort bukanlah sebuah kesalahan, dan telah bekerja dengan baik selama bertahun-tahun sampai kasus penggunaan tertentu menyoroti inefisiensinya.
  • Ini adalah optimasi yang diperlukan untuk kasus seperti AWS Lambda, yang sering melakukan boot.
  • Kernel FreeBSD menghabiskan 7% waktunya untuk menjalankan bubblesort di SYSINITs saat boot di Firecracker.
  • Perubahan ke mergesort menghasilkan pengurangan bersih 5 baris kode dan waktu boot yang "100 kali lebih cepat".
  • Keputusan awal untuk menggunakan bubblesort mungkin dipengaruhi oleh faktor-faktor seperti jumlah tugas.
  • Perubahan ke mergesort menunjukkan bahwa peningkatan kecil dapat membuat perbedaan penting pada performa keseluruhan.
  • Beberapa pengguna mempertanyakan penggunaan awalnya, mengingat inefisiensi bubblesort yang sudah dikenal dan kurangnya sifat intuitif.
  • Perubahan ini memicu diskusi terkait waktu boot FreeBSD dan penggunaan bubblesort di SYSINITs.