Rust 的 match 与查找表的性能对比

  • 主要观点:比较 Rust 中匹配表达式(match expression)和查找表(lookup table)在不同任务下的性能,包括基准测试、生成的汇编代码和 LLVM IR 分析等,最终发现内联查找表更快是因为所需指令更少,同时提出一些未解决的问题。
  • 关键信息

    • 基准测试了不同字母大小和任务下的匹配和查找性能,发现除“mix with rotate”任务外,内联匹配和查找性能基本相同,且在该任务中 4 和 8 字母大小的查找表更快。
    • 生成的汇编代码显示匹配和查找在简单情况下的不同实现,复杂“mix with rotate”任务的汇编代码更复杂。
    • LLVM IR 分析表明 4 字母“mix with rotate”任务中匹配包含分支指令,而查找更简单,循环展开也有所不同。
    • 不同任务的函数生成的 LLVM IR 代码结构不同,通过语义差异工具 llvm-diff 比较匹配和查找的差异不明显。
    • 缓存分析(Cachegrind)未发现“mix”和“mix with rotate”任务在失效率上的差异。
    • 重新运行基准测试发现不使用lazy_static时 2 到 4 字母内联匹配的“mix with rotate”慢化消失,说明lazy_static开销影响了匹配性能。
  • 重要细节

    • 基准测试使用Criterion框架,通过嵌套for循环运行多种函数变体,输入字符串为 10,000 个均匀选择的字符,克隆输入字符串以在每个基准闭包中移动,匹配/查找通过函数指针实现,编译器不能内联。
    • 生成的汇编代码中,匹配和查找的实现方式不同,如匹配中使用比较和条件转移指令,查找使用加载和指针运算。
    • LLVM IR 中函数包含各种属性和指令,如norecurseicmp等,不同任务的函数结构和循环展开方式不同。
    • lazy_static的使用会增加一些开销,影响匹配的性能,不使用时 2 到 4 字母内联匹配的“mix with rotate”性能更好。
    • 提出一些关于 Rust/LLVM 行为的未解决问题,如为何不自动将匹配转换为查找表,以及lazy_static为何使 2 字母“mix with rotate”匹配更快等。
阅读 10
0 条评论