FreeBSD đổi bubble sort của SYSINIT sang merge sort

 (twitter.com/cperciva)
10 điểm bởi GN⁺ 2023-08-22 | 3 bình luận | Chia sẻ qua WhatsApp
  • Có báo cáo cho biết khi khởi động, FreeBSD dành 7% thời gian để bubble sort các SYSINIT
  • Đây là đoạn mã được viết từ năm 1996; vào thời điểm đó chỉ có khoảng 30 SYSINIT cần sắp xếp, nhưng hiện nay con số đã vượt quá một nghìn nên thời gian xử lý trở nên đáng kể
  • Trong commit gần đây, các mảng SYSINIT đã được chuyển sang SLIST, nhờ đó có thể dùng merge sort và việc thêm các SYSINIT mới cũng nhanh hơn
    • Merge sort nhanh hơn khoảng tới ~100 lần
  • Theo mốc Firecracker, có thể tiết kiệm 2ms trên tổng thời gian khởi động 28ms

Bài viết liên quan

3 bình luận

 
rousseau 2023-08-23

Với các tập dữ liệu dưới một quy mô nhất định, việc dùng đoạn mã nhỏ và dễ hiểu hẳn đã từng là một lựa chọn hợp lý.
Và có lẽ vẫn còn khá nhiều trường hợp dùng thuật toán chậm tồn tại vì những quyết định như vậy.
(Dù có phần thiên kiến) tôi khá có cảm giác rằng nếu có ai bắt bẻ chuyện kiểu này, thì đó sẽ là người chẳng giúp được gì mà chỉ giỏi phàn nàn.
 
GN⁺ 2023-08-22
Bình luận trên Hacker News
  • FreeBSD đã thay bubblesort bằng mergesort trong SYSINIT, nhờ đó thời gian khởi động được cải thiện đáng kể.
  • Việc dùng bubblesort không phải là nhầm lẫn; nó đã hoạt động ổn suốt nhiều năm cho đến khi một trường hợp sử dụng cụ thể làm lộ rõ sự kém hiệu quả của nó.
  • Đây là một tối ưu hóa cần thiết cho các trường hợp khởi động thường xuyên như AWS Lambda.
  • Khi khởi động trên Firecracker, kernel FreeBSD đã dành 7% thời gian để chạy bubblesort trong SYSINIT.
  • Việc chuyển sang mergesort giúp giảm ròng 5 dòng mã và mang lại thời gian khởi động "nhanh hơn 100 lần".
  • Quyết định ban đầu sử dụng bubblesort có thể đã bị chi phối bởi các yếu tố như số lượng tác vụ.
  • Việc chuyển sang mergesort là một ví dụ cho thấy những cải tiến nhỏ có thể tạo ra khác biệt quan trọng đối với hiệu năng tổng thể.
  • Một số người dùng đặt câu hỏi về việc dùng bubblesort ban đầu, xét đến sự kém hiệu quả đã được biết đến và việc nó thiếu tính trực quan.
  • Thay đổi này đã làm dấy lên các cuộc thảo luận liên quan về thời gian khởi động của FreeBSD và việc sử dụng bubblesort trong SYSINIT.