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) 会变得非常复杂,所以需要用更快的算法取代冒泡排序。


相關推薦

2023-03-04

输入: 请分别用 C ,C++ ,java ,php ,go ,js 生成冒泡排序代码,以 markdown 格式输出。 那么它就会输出几个代码块,每个代码块对应着一种语言实现的冒泡排序。 你也可以输入: 请根据以下关键字,生成一篇连贯的微

2022-12-19

码转换为 Python 源码: > 木兰 --dump-python 测试\算法\排序\冒泡.ul import sys from math import * ARGV = sys.argv[1:] def 冒泡(数列): 换过 = True while 换过: 换过 = False for i in range(0, len(数列) - 2 + 1): 前项 = 数列[i] 后项 = 数列[i + 1] if (前项 &g

2023-10-08

x86-simd-sort 快速排序库;当 Numpy 将 x86-simd-sort 代码进行合并后发现,对于 16 位到 64 位的数据类型,排序速度提高了10~17倍。如今,英特尔软件工程师又发布了 x86-simd-sort 3.0,OpenJDK 也已经将这一修改版进行了合并。 x86-simd-sort

2022-09-27

菜单中增加了一个新的效果按钮,允许你放置实时效果 合并了混音器栏和仪表栏 增加了一个新的音频设置按钮,默认取代了设备工具栏(设备工具栏可以通过查看 > 工具栏菜单重新添加) 效果菜单得到了一个新的排序,

2023-10-16

FreeBSD 14.0 首个 RC 已发布,这是该项目自 2021 年 4 月发布 13.0 以来的首个大版本更新。 FreeBSD 14.0 计划于 2023 年 11 月 7 日正式发布,支持 amd64、i386、powerpc、powerpc64、powerpc64le、powerpcspe、armv7、aarch64 和 riscv64 架构。 自 14.0-BETA5

2023-01-04

} 占位符现在支持检测 Microsoft Store 版本的 Firefox 当自动排序被激活时试图重新排列条目时,KeePass 现在会询问是否停用自动排序。 在 HTML 输出/打印中为标题添加边框 在 HTML 输出/打印中增加了水平条目分隔线 改进 改

2023-11-15

能差异 功能 本框架 RuoYi 前端项目 采用 Vue3 + TS + ElementPlus 重写 基于Vue2/Vue3 + JS 后端项目结构 采用插件化 + 扩展包形式 结构解耦 易于扩展 模块相互注入耦合严重难以扩展 后端代码风格 严格

2022-12-16

Linux 6.2 近日合并了一个重要补丁,该补丁能够将一个核心内核函数速度提升 715 倍。 从合并的注释可知,贡献此补丁的维护者 Zhen Lei 来自华为,他将 kallsyms_lookup_name() 的平均查找性能提高了 715 倍,从而使内核里面旧实现的

2023-11-16

Vue3 + TS + ElementPlus 基于Vue2/Vue3 + JS 后端项目结构 采用插件化 + 扩展包形式 结构解耦 易于扩展 模块相互注入耦合严重难以扩展 后端代码风格 严格遵守Alibaba规范与项目统一配置的代码格式化 代码书写与常规结

2023-09-26

Vue3 + TS + ElementPlus 基于Vue2/Vue3 + JS 后端项目结构 采用插件化 + 扩展包形式 结构解耦 易于扩展 模块相互注入耦合严重难以扩展 后端代码风格 严格遵守Alibaba规范与项目统一配置的代码格式化 代码书写与常规结

2023-11-28

Vue3 + TS + ElementPlus 基于Vue2/Vue3 + JS 后端项目结构 采用插件化 + 扩展包形式 结构解耦 易于扩展 模块相互注入耦合严重难以扩展 后端代码风格 严格遵守Alibaba规范与项目统一配置的代码格式化 代码书写与常规结

2023-11-28

Vue3 + TS + ElementPlus 基于Vue2/Vue3 + JS 后端项目结构 采用插件化 + 扩展包形式 结构解耦 易于扩展 模块相互注入耦合严重难以扩展 后端代码风格 严格遵守Alibaba规范与项目统一配置的代码格式化 代码书写与常规结

2023-04-03

MidnightBSD 是从 FreeBSD 派生出的操作系统。该项目的一个关键性目标是创建一份易于使用的桌面环境,并使用图形化的 ports 管理,以及 采用 GNUstep 的系统配置。该操作系统的主体将沿用 BSD 许可证。MidnightBSD 是 FreeBSD 6.1 beta 的分

2022-10-11

器。适用于所有平台,包括 Linux、macOS、Windows、Solaris、FreeBSD、Docker、WSL 等。它可以为任何配置和平台创建、上传和下载二进制文件, 甚至交叉编译,节省大量的开发和持续集成时间。 Conan 1.53 正式发布,更新内容如下: 特