Making `wc` 20x faster with parallel state machines
2 days ago
- 这篇博文解释了如何使用状态机让 Unix 的 wc 命令更快，其灵感来自 Robert Graham 的 wc2 仓库。
- 基本的 wc 实现通过跟踪前一个字符是否为空白来统计单词数，而状态机方法则为每个输入字符的状态转换建模。
- 状态机方法使用转换表和字符类型表，形成一个简单循环，能高效处理每个字节。
- 基准测试表明，在 ASCII 输入下，由于分支预测的优势，状态机版本比 GNU wc 慢，但在处理 UTF-8 文本时则更快。
- 状态机支持 UTF-8 需要为多字节序列增加额外状态，但每个字符的开销保持不变，因此比使用 mbrtowc 和 iswspace 的标准 wc 实现快得多。
- 作者通过将输入分割成多个线程处理的块来并行化状态机，使用带有工作队列和空闲队列的生产者-消费者模型。
- 并行化在大型输入上实现了 5 到 20 倍的加速，吞吐量达到约 4 GB/s，由于缓存的缘故超过了磁盘读取速度。
- 附录比较了反汇编和分支未命中情况：与 GNU wc 相比，状态机将分支预测错误减少了 99.5%。
- 提供了对 Unicode 和 UTF-8 的简要介绍，解释了字节编码的工作原理。