FreeBSD 为 SYSINT 采用合并排序取代冒泡排序

FreeBSD 维护者 Colin Percival 发帖称，他们已经为 SYSINIT 采用合并排序 (mergesort) 来取代冒泡排序 (bubblesort)。

SYSINIT 是通用调用排序和调度机制的框架，FreeBSD 目前使用它来动态初始化内核。

当加载内核或其模块之一时，SYSINIT 允许在内核链接时对 FreeBSD 的内核子系统进行重新排序、添加、删除和替换，而无需编辑静态排序的初始化路由并重新编译内核。

该框架还允许内核模块（目前称为 KLD）在引导时单独编译、链接和初始化，甚至在系统运行时加载。该操作使用“内核链接器”和“链接器集” ("kernel linker" and "linker sets") 来完成。

via FreeBSD 文档

Colin Percival 表示，使用合并排序后的运行速度比之前快了大约 100 倍。

他此前解释过更换算法的原因，当 FreeBSD 内核在 Firecracker（单核 CPU、128 MB RAM）中启动时，会花费 7% 的时间在其 SYSINIT 上运行冒泡排序。当对一千多个项目进行排序时，O(N^2) 会变得非常复杂，所以需要用更快的算法取代冒泡排序。