20 августа 2023 года мейнтейнер FreeBSD Колин Персиваль (Colin Percival) объявил, что проект FreeBSD переходит с сортировки пузырьком в SYSINIT на сортировку слиянием, которая примерно в 100 раз быстрее.
27 лет назад сортировка пузырьком была введена во FreeBSD, когда сортировалось всего около 30 процессов и тасков, а скорость сортировки тогда не имела значения.
«Когда ядро FreeBSD загружается в Firecracker (1 ЦП, 128 МБ ОЗУ), то тратит 7% своего системного времени на выполнение пузырьковой сортировки своих SYSINIT. O(N^2) может сильно укусить, когда вы сортируете более тысячи элементов. Пришло время заменить пузырьковую сортировку чем-то более быстрым», — пояснил Персиваль.
Мейнтейнер FreeBSD пояснил, что переход на сортировку слиянием SYSINIT позволил сократить время загрузки Firecracker примерно на 2 мс.
Источник новости: habr.com
