FreeBSD เปลี่ยน Bubble Sort ของ SYSINIT เป็น Merge Sort

 (twitter.com/cperciva)
10 คะแนน โดย GN⁺ 2023-08-22 | 3 ความคิดเห็น | แชร์ทาง WhatsApp
  • มีรายงานว่า FreeBSD ใช้เวลาระหว่างบูต 7% ไปกับการจัดเรียง SYSINIT ด้วย bubble sort
  • โค้ดนี้ถูกสร้างขึ้นในปี 1996 และในยุคนั้นมี SYSINIT ให้จัดเรียงเพียงราว 30 รายการ แต่ปัจจุบันมีมากกว่าพันรายการแล้ว จึงใช้เวลานานขึ้น
  • ในคอมมิตล่าสุด ได้เปลี่ยน SYSINIT array เป็น SLIST ทำให้สามารถใช้ merge sort ได้ และยังเพิ่ม SYSINIT ใหม่ได้เร็วขึ้นด้วย
    • merge sort เร็วขึ้นได้ประมาณ ~100 เท่า
  • เมื่ออิงตาม Firecracker จึงสามารถประหยัดเวลาได้ 2ms จากเวลาบูตทั้งหมด 28ms

บทความที่เกี่ยวข้อง

3 ความคิดเห็น

 
rousseau 2023-08-23

สำหรับชุดข้อมูลที่มีขนาดไม่เกินระดับหนึ่ง การใช้โค้ดที่เล็กและเข้าใจง่ายก็น่าจะเป็นทางเลือกที่ใช้ได้
จึงน่าจะยังมีกรณีการใช้อัลกอริทึมที่ช้าแบบนี้หลงเหลืออยู่อีกมากจากการตัดสินใจเช่นนั้น
(อาจเป็นอคติของผมเอง) แต่ผมรู้สึกแรงกล้าว่า ถ้ามีใครมาคอยจับผิดเรื่องแบบนี้ ก็คงเป็นคนที่ไม่ค่อยได้ช่วยอะไร แถมบ่นเก่งเสียมากกว่า
 
GN⁺ 2023-08-22
ความคิดเห็นจาก Hacker News
  • FreeBSD เปลี่ยน bubblesort เป็น mergesort ใน SYSINITs ทำให้เวลาในการบูตดีขึ้นอย่างมาก
  • การใช้ bubblesort ไม่ใช่ความผิดพลาด และมันทำงานได้ดีมาหลายปี จนกระทั่งมีกรณีใช้งานเฉพาะที่ทำให้ความไม่มีประสิทธิภาพของมันเด่นชัดขึ้น
  • นี่เป็นการปรับแต่งที่จำเป็นสำหรับกรณีที่มีการบูตบ่อย เช่น AWS Lambda
  • เคอร์เนลของ FreeBSD ใช้เวลา 7% ไปกับการรัน bubblesort ใน SYSINITs เมื่อบูตบน Firecracker
  • การเปลี่ยนไปใช้ mergesort ทำให้โค้ดลดลงสุทธิ 5 บรรทัด และทำให้เวลาในการบูต "เร็วขึ้น 100 เท่า"
  • การตัดสินใจเลือกใช้ bubblesort ในตอนแรกอาจได้รับอิทธิพลจากปัจจัยอย่างเช่นจำนวนงาน
  • การเปลี่ยนไปใช้ mergesort เป็นตัวอย่างที่แสดงให้เห็นว่าการเพิ่มขึ้นเล็กน้อยสามารถสร้างความแตกต่างสำคัญต่อประสิทธิภาพโดยรวมได้
  • ผู้ใช้บางคนตั้งคำถามกับการใช้งานในช่วงแรก เมื่อพิจารณาจากความไม่มีประสิทธิภาพที่เป็นที่รู้กันของ bubblesort และการที่มันไม่ค่อยสอดคล้องกับสัญชาตญาณ
  • การเปลี่ยนแปลงนี้ได้จุดประกายการถกเถียงที่เกี่ยวข้องกับเวลาในการบูตของ FreeBSD และการใช้ bubblesort ใน SYSINITs