Hacker News 中文摘要

文章摘要

文章介绍了如何在Rust中优化数学表达式解析器的性能。首先，作者展示了基线实现的性能，随后通过一系列优化手段逐步提升解析速度，包括减少向量分配、直接从输入字节解析以及避免使用Peekable等。这些优化使得解析时间从43.1秒大幅减少到3.21秒，显著提升了效率。

文章总结

文章总结：优化 Rust 数学表达式解析器

本文详细介绍了如何在 Rust 中优化一个数学表达式解析器，使其在速度和内存使用上达到最佳性能。文章从基础实现开始，逐步进行优化，最终将解析器的执行时间从 43 秒缩短到不到 1 秒。

1. 基础实现（43.1 秒）

功能：解析包含加减法和括号的简单数学表达式，如 (1 + 2) - 3。
实现：通过 tokenize 函数将输入字符串分割为标记（如 Operand(1)、Plus 等），然后递归解析表达式。
问题：虽然功能正确，但处理 1.5GB 文件时耗时 43 秒，存在优化空间。

2. 优化步骤

优化 1：避免在分词时分配向量（43.1 秒 → 6.45 秒，–85% 提升）

改进：将 tokenize 函数改为返回一个惰性迭代器，避免一次性分配所有标记的向量。
效果：执行时间从 43 秒降至 6.45 秒。

优化 2：零分配——直接从输入字节解析（6.45 秒 → 3.68 秒，–43% 提升）

改进：使用 &[u8] 处理原始字节，避免中间字符串分配。
效果：执行时间从 6.45 秒降至 3.68 秒。

优化 3：不使用 `Peekable`（3.68 秒 → 3.21 秒，–13% 提升）

改进：重构解析逻辑，避免使用 Peekable 迭代器，减少开销。
效果：执行时间从 3.68 秒降至 3.21 秒。

优化 4：多线程和 SIMD（3.21 秒 → 2.21 秒，–31% 提升）

改进：使用多线程和 SIMD（单指令多数据）技术并行处理表达式，并快速找到分割点。
效果：执行时间从 3.21 秒降至 2.21 秒。

优化 5：内存映射 I/O（2.21 秒 → 0.98 秒，–56% 提升）

改进：使用内存映射文件（mmap）避免将文件内容复制到用户空间，减少内存开销和假共享问题。
效果：执行时间从 2.21 秒降至 0.98 秒。

3. 结论

通过一系列优化，数学表达式解析器的性能得到了显著提升。以下是优化步骤的总结： 1. 避免一次性分配所有标记：从 43 秒降至 6.45 秒。 2. 直接处理字节：从 6.45 秒降至 3.68 秒。 3. 简化代码逻辑：从 3.68 秒降至 3.21 秒。 4. 并行处理和 SIMD：从 3.21 秒降至 2.21 秒。 5. 内存映射文件：从 2.21 秒降至 0.98 秒。

最终，解析器在不到 1 秒的时间内完成了 1.5GB 文件的解析。

作者：Ricardo Pallas

λ 软件工程师

完整代码：GitHub 链接

评论总结

以下是评论内容的总结：

关于解析器的改进：
- tialaramex 提到他希望在 Rust 的 realistic crate 中实现一个更“自然”的算术表达式解析器，而不是当前的 Lisp 风格解析器。
  - 引用：“But it would be nice to write "(40^0.5) * (90^0.5)" or similar and have that work instead or as well.”
- noelwelsh 指出，当前的实现是一个融合了解析和解释的代码，避免了生成中间 AST，从而减少了内存分配，但这种方法对于复杂语言可能不适用。
  - 引用：“It doesn't have to produce an intermediate AST, and therefore can avoid the majority of the allocation that most parsers will perform.”
关于优化策略：
- makapuf 建议在优化时不仅关注执行时间，还应考虑 CPU 时间、内存使用和代码复杂度等指标。
  - 引用：“what could be interesting is to look at benchmarks not only wall time but also other metrics.”
- combinator_y 讨论了优化顺序的影响，认为某些优化可能在实际应用中已经带来足够高的性能提升，无需进一步使用 SIMD 或多线程。
  - 引用：“by Optimization 3 you would reach already a high throughput that you wouldn't bother with manual simd nor Multithreading.”
关于 Rust 的细节讨论：
- catfacts 对 Rust 中的字符串处理和文件读取提出了疑问，认为 Common Lisp 在某些方面可能更优化。
  - 引用：“I find strange using input = readinputfile()? and then using eval(&input), what happens when there is an error reading the file?”
- amelius 询问了 Rust 编译器如何推导类型，引发了对语言特性的讨论。
  - 引用：“How does the compiler derive the type of n?”
关于工具和方法的建议：
- IshKebab 推荐使用 Go 版本的 pprof 和 Samply 作为更好的性能分析工具，认为它们比传统的 Perl 版本更强大。
  - 引用：“Use the Go version of pprof: https://github.com/google/pprof”
- pornel 讨论了内存映射文件的作用，认为其速度提升可能来自于操作系统并行预取数据，而非防止缓存冲突。
  - 引用：“The speedup may be from just starting the work before the whole file is loaded, allowing the OS to prefetch the rest in parallel.”
其他观点：
- ramon156 认为这是一个适合课堂的项目，可以让学生探索优化策略。
  - 引用：“This would be a perfect class project.”
- taeric 对优化顺序的影响表示好奇，认为某些优化可能在不同顺序下产生相似的效果。
  - 引用：“I'm somewhat curious on if these optimizations would all have roughly the same impact if done in other orders?”

总结：评论主要围绕 Rust 解析器的改进、优化策略、语言特性、工具使用等方面展开，提出了多种观点和建议，反映了开发者对性能优化和语言细节的关注。

优化Rust中的数学表达式解析器 -- Optimizing a Math Expression Parser in Rust