Бинарный поиск ускорил раннюю загрузку ядра Linux: с 268 секунд до 50 миллисекунд

Сегодня в ядро Linux 7.4 отправили набор улучшений подсистемы memblock. Самое заметное из них — оптимизация в файле mm/memblock.c, где реализован ранний аллокатор физической памяти, работающий ещё до запуска полноценного постраничного аллокатора.

Суть изменения проста. Инженер Google Тарун Саху обратил внимание, что функции memblock_add_range() и memblock_isolate_range() искали подходящие области памяти линейным перебором. Он заменил его бинарным поиском.

Где это важно

При обычной загрузке разница почти незаметна. Но при сильной фрагментации памяти — например, при использовании механизма Kernel Handover (KHO), на котором строится Live Update Orchestrator и смежные инструменты, — в системе возникает множество разрозненных фрагментов памяти. Линейный перебор по ним превращается в мучительно долгий процесс.

Цифры говорят сами за себя. По словам авторов патча, переход на бинарный поиск снижает сложность в худшем случае до O(N log N) (и до O(N) для последовательного добавления), а время извлечения памяти при KHO сокращается примерно с 268 секунд до примерно 50 миллисекунд.

Остаётся лишь удивляться, что линейный поиск продержался в коде ядра так долго. С другой стороны, он затрагивал лишь аллокатор ранней загрузки, где раньше никто особо не замечал потерь.

Оптимизация вошла в pull-запрос memblock, отправленный сегодня для ядра Linux 7.4.

Источник: Phoronix