平均查找性能提高了715倍Linux6.2合并华为贡献的代码

12月14日消息，Linux6.2今日合并了来自华为郑磊（ZhenLei，音译）的代码，将核心内核功能的速度提高了715倍。

在合并代码模块介绍中写道：“得益于ZhenLei的代码，Tux（Linux的吉祥物，这里指Linux）在kallsyms_lookup_name()平均查找性能提高了715倍，将我们的旧实现从O(n)升级到O(log(n))，同时还保留了/proc/kallsyms上的旧实现支持”。

，kallsyms_lookup_name()函数用于根据一个符号的名称查询其地址，并可用于内核符号表内任何符号的查询。

华为的ZhenLei在之前的补丁贴中描述了对kallsyms_lookup_name的优化：

目前，为了搜索一个符号，我们需要将'kallsyms_names'中的符号逐一展开，然后使用展开后的字符串进行比较。这是O(n)。

如果我们像地址一样将名字按升序排序，我们也可以使用二进制搜索。而这就是O(log(n))。

为了不改变“/proc/kallsyms”的实现，表kallsyms_names[]仍然以升序与地址一一对应的方式存储。

增加数组kallsyms_seqs_of_names[]，它以排序后的名字的序列号为索引，对应的内容是排序后的地址的序列号。

例如，假设NameX在数组kallsyms_seqs_of_names[]中的索引是'i'，kallsyms_seqs_of_names[i]的内容是'k'，那么NameX的对应地址是kallsyms_addresses[k]。kallsyms_names[]中的偏移是get_symbol_offset(k)。

注意，内存使用量将增加(4*kallsyms_num_syms)字节，接下来的两个补丁将减少(1*kallsyms_num_syms)字节并正确处理CONFIG_LTO_CLANG=y的情况。

性能测试结果（在x86平台上）：

之前：

min=234,max=10364402,avg=5206926

min=267,max=11168517,avg=5207587

之后：

min=1016,max=90894,avg=7272

min=1014,max=93470,avg=7293

kallsyms_lookup_name()的平均查询性能提高了715倍。这是kallsyms_lookup_name一次重大改进，也是Linux6.2的圣诞礼物。