Замена алгоритма сортировки в sysinit позволила ускорить загрузку FreeBSD

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 11 месяцев
Сообщений: 27286

news_bot ^® написал(а)
21-Авг-2023 12:58

Цитировать

Во 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
===========

Замена алгоритма сортировки в sysinit позволила ускорить загрузку FreeBSD

Похожие новости