Tweet
FreeBSD has adopted a change that alters the array sorting algorithm in the kernel initialization code (sysinit). Instead of the previously used bubble sorting algorithm, sysinit uses a more efficient merge sorting algorithm, which reduced kernel load time by 2 ms in Firecracker virtual machines.
The bubble sort method is mainly for training purposes and due to the repetitive search (complexity "O(N^2)") is only effective for small arrays. In sysinit, over a thousand bubble sort operations took approximately 7% of the FreeBSD kernel's total boot time to complete.
Using merge sorting eliminated this delay, as this algorithm solves the same problem about 100 times faster. In addition to changing the algorithm to reduce sorting time and memory allocation, the kernel also uses merge-based optimization to merge sorted lists instead of re-sorting each augmented list.
The bubble sort method is mainly for training purposes and due to the repetitive search (complexity "O(N^2)") is only effective for small arrays. In sysinit, over a thousand bubble sort operations took approximately 7% of the FreeBSD kernel's total boot time to complete.
Using merge sorting eliminated this delay, as this algorithm solves the same problem about 100 times faster. In addition to changing the algorithm to reduce sorting time and memory allocation, the kernel also uses merge-based optimization to merge sorted lists instead of re-sorting each augmented list.
Comment