Linux早期内存分配器提速 268秒变50毫秒
报价宝综合消息Linux早期内存分配器提速 268秒变50毫秒
Linux 7.4内核合并窗口里，一批memblock子系统改进带来了一项惊人的提速：在最坏情况下，KHO内存检索的耗时从约268秒降到约50毫秒，直接砍掉三个多数量级。
memblock是内核在完整的页分配器就位之前使用的早期物理内存分配器。谷歌工程师Tarun Sahu发现，mm/memblock.c中的memblock_add_range()与memblock_isolate_range()两个函数在寻找候选内存区域时，用的竟然是线性搜索。
平时这不算什么问题，但在碎片化严重的场景下代价巨大——比如启用KHO（Kernel Handover，内核交接）并携带大量不连续folio时。KHO这套机制被Live Update Orchestrator等实时更新功能用来在内核之间交接内存，检索碎片化内存的时间会随碎片数量急剧膨胀。
补丁将线性搜索替换为二分查找后，最坏复杂度从线性级降到O(N log N)，顺序追加场景仍保持O(N)。补丁原文明确写道：这一改动把KHO内存检索时间从约268秒削减到约50毫秒。
这批memblock改动已随维护者的拉取请求进入Linux 7.4主线。有内核观察者感叹，一段线性搜索能在内核代码里活到今天多少有些出人意料——好在它终于被换掉了。
编译自 Phoronix，原标题："Linux's Early Boot-Time Physical Memory Allocator Sees Big Speed-Up: ~268s To ~50ms"
