Бинарный поиск в memblock ускорил работу KHO в ядре Linux 7.4 с ~268 с до ~50 мс
Бинарный поиск в memblock ускорил работу KHO в ядре Linux 7.4 с ~268 с до ~50 мс Ядро Linux 7.4 получило оптимизацию memblock, аллокатора физической памяти, который работает на раннем этапе загрузки, до запуска полноценного page allocator. Инженер Google Тарун Саху заметил, что mm/memblock.c ищет подходящие регионы линейным перебором. Теперь в memblock_add_range() и memblock_isolate_range() используется бинарный поиск. Проблема проявлялась при сильной фрагментации, например при работе с Kernel Handover (KHO), на котором построен Live Update Orchestrator, и большом количестве разрозненных folio. По данным патча, время извлечения памяти KHO сократилось с ~268 с до ~50 мс. Сложность в худшем случае снижена до O(N log N), а для последовательных добавлений до O(N). Для геймеров прямого эффекта нет: изменение касается раннего этапа загрузки и сценариев с KHO. Патч вошёл в pull request memblock для ядра Linux 7.4.