FreeBSD, SYSINIT’in bubble sort’unu merge sort ile değiştiriyor

 (twitter.com/cperciva)
10 puan yazan GN⁺ 2023-08-22 | 3 yorum | WhatsApp'ta paylaş
  • FreeBSD’nin açılış sırasında zamanın %7’sini SYSINIT’leri bubble sort ile sıralamaya harcadığı bildirildi
  • Kod 1996’da yazılmıştı; o dönemde sıralanacak yaklaşık 30 SYSINIT vardı, ancak bugün sayı bini aşınca bu işlem uzun sürmeye başladı
  • Yakın tarihli bir commit’te SYSINIT dizileri SLIST’e dönüştürüldü; böylece merge sort mümkün hale geldi ve yeni SYSINIT’ler eklemek de hızlandı
    • Merge sort yaklaşık 100 kata kadar daha hızlı
  • Firecracker baz alındığında, toplam 28 ms’lik açılış süresinde 2 ms tasarruf sağlanabiliyor

İlgili okumalar

3 yorum

 
rousseau 2023-08-23

Belirli bir ölçeğin altındaki veri kümeleri için, küçük ve anlaşılması kolay kod kullanmak geçerli bir tercih olmuş olabilir.
Böyle kararlar yüzünden geriye kalan yavaş algoritma kullanım örnekleri hâlâ epey fazladır muhtemelen.
(Önyargı olabilir ama) böyle şeylere laf eden biri varsa, faydası olmayıp sadece şikâyeti çok olan biri olma ihtimalinin yüksek olduğunu güçlü biçimde düşünüyorum.
 
GN⁺ 2023-08-22
Hacker News yorumu
  • FreeBSD, SYSINIT'lerde bubblesortu mergesort ile değiştirerek önyükleme süresini önemli ölçüde iyileştirdi.
  • bubblesort kullanımı bir hata değildi; belirli bir kullanım senaryosu onun verimsizliğini öne çıkarana kadar uzun yıllar boyunca gayet iyi çalıştı.
  • Bu, AWS Lambda gibi sık sık önyükleme yapılan durumlar için gerekli bir optimizasyondu.
  • FreeBSD çekirdeği, Firecracker üzerinde önyüklenirken zamanının %7'sini SYSINIT'lerde bubblesort çalıştırarak harcıyordu.
  • mergesorta geçiş, kodda net 5 satırlık bir azalma ve "100 kat daha hızlı" önyükleme süresi sağladı.
  • Başlangıçta bubblesort kullanma kararı, iş sayısı gibi etkenlerden etkilenmiş olabilir.
  • mergesorta geçiş, küçük bir artışın genel performansta önemli bir fark yaratabileceğini gösteren bir örnek.
  • Bazı kullanıcılar, bubblesortun bilinen verimsizliği ve sezgisellik eksikliği göz önüne alındığında başlangıçta kullanılmasını sorguluyor.
  • Bu değişiklik, FreeBSD'nin önyükleme süresi ve SYSINIT'lerde bubblesort kullanımına ilişkin ilgili tartışmaları tetikledi.