Замена алгоритма сортировки в sysinit позволила ускорить загрузку FreeBSD
Дата публикации:Mon, 21 Aug 2023 09:30:26 +0300
Во FreeBSD принято изменение, меняющее в коде инициализации ядра (sysinit) алгоритм сортировки массивов. Вместо ранее применявшегося алгоритма пузырьковой сортировки в sysinit задействован более эффективный алгоритм сортировки слиянием, что позволило на 2 мс сократить время загрузки ядра в виртуальных машинах Firecracker.
Метод пузырьковой сортировки предназначен в основном для учебных целей и из-за повторяющегося перебора (сложность "O(N^2)") эффективен только для небольших массивов. В sysinit на выполнение более тысячи операций пузырьковой сортировки уходило примерно 7% от всего времени загрузки ядра FreeBSD.
Использование сортировки слиянием позволило устранить эту задержку, так как данный алгоритм решает ту же задачу примерно в 100 раз быстрее. Кроме смены алгоритма для сокращения времени сортировки и уменьшения операций выделения памяти в ядре также задействована оптимизация на основе слияния отсортированных списков, вместо повторной сортировки каждого дополненного списка.
Дополнительно можно отметить формирование второго альфа-выпуска будущей ветки FreeBSD 14.0. Сборки FreeBSD 14.0-BETA2 доступны для архитектур amd64, i386, aarch64 и riscv64. Релиз FreeBSD 14.0 намечен на 23 октября 2023 года. На 25 августа запланировано создание ветки stable/14, а на 8 сентября создание ветки releng/14.0 и формирование первой бета-версии. Среди изменений во FreeBSD 14: обновление компилятора Clang до ветки 16 и увеличение с 256 до 1024 числа поддерживаемых ядер CPU (параметр MAXCPU) в системах на базе архитектуры amd64 и arm64.
Новость позаимствована с opennet.ru
Ссылка на оригинал: https://www.opennet.ru/opennews/art.shtml?num=59634