这是一篇关于在 Rust 中优化并行计算的博客文章，主要内容总结如下：

一、背景与问题

• 在之前的文章中展示了如何使用rayon框架在 Rust 中自动并行化循环计算，但基准测试显示在 8 线程计算机上仅提供 2 倍加速，总“用户”和“系统”时间随线程数线性增加，Python 甚至比 Rust 代码慢两倍，引发了优化之旅。
• 介绍了后续优化的内容结构，包括使用的优化工具、手动实现 Rayon 的替代品、其他优化措施以及对 Rayon 的with_max_len()方法的测试。

二、使用的优化工具

• strace：用于跟踪系统调用，发现大量futex调用可能表示互斥锁争用，使用-f追踪子线程后发现大部分后台线程在循环中调用sched_yield，strace的总结模式-c可展示主要系统调用及时间占比。
• perf：Linux 内置的多功能性能分析工具，可记录程序执行轨迹生成火焰图，记录 CPU 或系统暴露的性能计数器统计信息。通过echo解锁内核配置，编译 Rust 代码时添加-C force-frame-pointers=y，使用perf record和perf report进行时间基准分析，perf annotate可导出汇编，perf script可将perf record的输出转换后加载到 Firefox Profiler 中进行分析，还可使用perf stat记录各种性能计数器统计信息，如-d可添加缓存未命中相关计数器，-r可重复运行程序记录平均计数器值，-e可自定义要收集的事件，-c可控制事件触发堆栈跟踪的频率。
• CPU 缓存：perf stat中的缓存未命中事件很重要，由于硬件限制，优化 CPU 缓存使用对于提高性能至关重要，例如可通过紧凑数据结构使其更适合缓存，并行计算时要考虑 CPU 缓存层次结构对并行性的影响。

三、手动实现 Rayon 的替代品

• Rayon 工作原理：基于可拆分工作项和基本连接原语，通过工作窃取在线程间分布和重新平衡工作，提供标准库IteratorAPI 的替代品。rayon_core crate 管理工作线程池，使用crossbeam::deque分发工作，Rayon 的ParallelIteratorAPI 实现复杂，通过一系列生产者和消费者函数处理迭代器组合器，bridge_producer_consumer()函数连接生产者和消费者，决定是否拆分工作，Rayon 的工作窃取创建了一个工作树，每个叶子节点串行处理，但设计选择会导致一些开销。
• 手动实现线程池：设计简单的并行化策略，创建工作线程池处理输入选票的子切片，通过Mutex和Condvar进行主线程与工作线程的通信，共享只读的选票切片、可读写的权重和结果，通过预先分区选票切片分配工作，但此方法比 Rayon 慢最多 50%。
• CPU 固定：操作系统调度器的 CPU 迁移会导致不必要的开销和缓存失效，通过nix库的sched_setaffinity()函数将线程固定到特定 CPU 核心，防止迁移，提高了手动实现的性能，有时比 Rayon 快 10% - 20%。
• 工作窃取：固定分区策略可能导致线程负载不平衡，通过实现工作窃取来解决，每个线程从自己的范围中弹出项，当空闲时尝试从其他线程窃取范围，窃取时尽量窃取另一半范围以减少对被窃取线程的影响，同时扫描所有线程找到最大可用范围以提高窃取效率，工作窃取具有自适应和细粒度的优势，可动态调整窃取粒度，减少同步开销，总体上性能优于 Rayon，尤其在线程数增加时。

四、结论

• 最初认为 Rayon 框架在多线程时导致同步开销，通过自定义并行机制确实减少了系统调用并提高了性能，但 Rayon 的通用性使其在其他场景更适用，仍在探索将自定义并行机制转化为库。
• 对 Rayon 的with_max_len()方法进行测试，发现对于随机输入该方法会使程序变慢，仅在严重偏斜的对抗性输入上有一定效果但仍比自定义并行机制慢约 4%。

总的来说，通过深入研究和优化，在特定场景下可以超越 Rayon 的性能，但 Rayon 的通用性使其在更广泛的情况下更有价值。