Hacker News 中文摘要

文章摘要

本文介绍了作者在开发基于s表达式的语言purple-garden时，如何通过优化策略使其词法分析器（lexer）达到极速。词法分析器是编译流程中的第一步，负责将字符序列转换为有意义的标记（tokens），供后续的解析器生成抽象语法树（AST）。作者强调，这些策略可能不适用于所有场景，但提供了性能验证的基准测试作为参考。

文章总结

本文详细介绍了如何通过一系列优化策略来实现一个非常快速的词法分析器（Lexer），作者以自己开发的基于S表达式的编程语言purple-garden为例，展示了如何通过多种技术手段提升词法分析器的性能。以下是文章的主要内容总结：

1. 词法分析器简介

词法分析器是编译器和语言处理流程中的第一步，负责将字符流转换为有意义的词法单元（Token），供后续的解析器生成抽象语法树（AST）。
词法分析器的输出是Token列表，解析器会进一步处理这些Token生成AST，编译器再将AST转换为字节码，最后由虚拟机执行。

2. purple-garden的Token定义

Token不仅包含字符，还包含Token类型和位置信息（如起始位置、长度、行号等）。
purple-garden的Token定义尽可能简洁，主要包含一个字符串和Token类型。

3. 最小化词法分析器的架构

词法分析器通过遍历输入字符，尝试将字符匹配为关键词、数字或符号等Token。
作者展示了如何通过简单的状态管理来实现一个基本的词法分析器，并逐步优化。

4. 优化策略

计算跳转表（Computed Gotos）：通过跳转表替换传统的switch语句，减少分支预测错误和缓存未命中，提升性能。
零拷贝、零分配字符串窗口：通过自定义的字符串结构Str，避免不必要的内存分配和拷贝，提升字符串处理的效率。
哈希一切：在词法分析过程中，对字符串、数字等原子类型进行哈希处理，便于后续的快速比较和去重。
Token内联化：对于常见的Token（如+、-等），通过静态分配的方式减少内存分配的开销。
预哈希关键词：在启动时预计算关键词的哈希值，减少运行时的计算量。

5. 内存分配优化

通过Bump Allocator（一种高效的内存分配器）来管理Token的内存分配，减少内存分配的开销。
使用mmap将文件直接映射到内存中，避免传统的文件读取和内存分配操作，显著提升文件读取速度。

6. 性能基准测试

作者通过一系列基准测试展示了优化后的词法分析器的性能，能够在毫秒级别处理数百万行的代码。
在笔记本电脑上，处理100万行代码仅需44毫秒，而在台式机上仅需30毫秒。

7. 未来优化方向

使用SIMD指令集进一步优化注释和空白字符的处理。
替换FNV-1a哈希算法为更快的哈希算法（如xxHash）。
通过预取字节减少L1和L2缓存的延迟。

8. 总结

作者通过多种优化手段，成功将词法分析器的性能提升到了一个新的高度，处理速度达到了580-848 MB/s。
文章最后提供了完整的代码实现，展示了如何将这些优化策略应用到实际的词法分析器中。

编译流程

通过本文，读者可以深入了解如何通过优化技术来提升词法分析器的性能，并为其他编译器或语言处理器的开发提供参考。

评论总结

主要观点总结：

对性能优化的关注：
- skeptrune 赞赏了代码中的基准测试，特别是数字处理的记忆化加速效果显著。
  - 引用："The memoization speedup for number processing was particularly surprising."
- duped 质疑手动跳转表的实际影响，指出其效果依赖于目标微架构和程序本身。
  - 引用："Do you have benchmarks that show the hand rolled jump table has a significant impact?"
语言和工具的选择：
- cratermoon 指出代码是用C编写的，不确定这些优化是否适用于其他语言。
  - 引用："Not sure how many of these translate to other languages."
- sparkie 提出使用[[musttail]]属性替代计算跳转，认为其具有更好的兼容性和模块化。
  - 引用："This approach has the advantage that it will work everywhere and not only on compilers that support the computed gotos."
词法分析器的设计：
- thechao 分享了自己的词法分析器设计，强调尽量减少决策，并重用本地字符串。
  - 引用："I try to minimize 'decision making' during lexing."
- o11c 认为逐字节处理限制了性能，建议使用SIMD或SWAR来加速。
  - 引用："A truly performant lexer needs to jump ahead as far as possible."
词法分析器是否成为瓶颈：
- zahlman 质疑词法分析器是否真的会成为性能瓶颈，认为优化重点应放在其他地方。
  - 引用："Is lexing really ever the bottleneck? Why focus effort here?"
- aappleby 也认为词法分析器很少成为瓶颈，更希望看到“可读性强的词法分析器策略”。
  - 引用："Lexing is almost never a bottleneck. I'd much rather see a 'Strategies for Readable Lexers'."
其他优化技巧：
- psanchez 分享了自己在布尔表达式解析器中的优化经验，包括减少内存分配和分支预测优化。
  - 引用："No string allocations: used the input *str directly, relying on pointer manipulation instead of allocating memory for substrings."
- kklisura 提到Postgres使用完美哈希来加速关键字比较，建议在已知关键字的情况下使用。
  - 引用："Since you know in advance what your keywords are, you can design such hashing functions that for each w(i) in list of i keywords W, h(w(i)) = i."

总结：

评论主要围绕词法分析器的性能优化展开，讨论了跳转表、SIMD、内存分配等技术的应用。部分评论质疑词法分析器是否真的会成为瓶颈，认为优化重点应放在其他方面。同时，也有评论分享了具体的优化经验和技巧，如完美哈希、[[musttail]]属性等。

快速词法分析器策略 -- Strategies for Fast Lexers