jsc::chunk_evenly Range Adaptor for Distributing Work Across Tasks

• 语言: 英语
• 格式: .pdf
• 来源: github.com/CppCon

摘要

The document introduces a Range adaptor called 'chunk_evenly' designed to distribute work evenly across tasks. It compares the new adaptor with existing methods like 'std::views::chunk' and demonstrates its advantages in terms of efficiency and zero-overhead principle implementation. The adaptor ensures balanced distribution of tasks, leverages branch-less programming for performance, and supports various architectures including x86, ARM, and RISC-V. It also provides examples of integration with execution frameworks like 'std::execution' for parallel processing tasks.

AI总结

《jsc::chunk_evenly Range Adaptor for Distributing Work Across Tasks》

本文介绍了一种新的Range适配器`jsc::chunk_evenly`，用于在任务间均匀分配工作量，优化并行性能。

### 核心内容

1. **背景与问题**
现有的Range适配器（如`std::views::chunk`、`std::views::chunk_by`、`std::views::split`）在分割范围时，无法完全均匀地分配工作量，尤其是在任务数与范围大小不匹配时，可能导致某些任务处理较少的工作量而其他任务等待。

2. **解决方案**
`jsc::chunk_evenly`是一种改进的Range适配器，能够将范围分割为指定数量的块，使每个块的大小尽可能均匀。
- 例如：对16个元素的范围分成5块，`std::views::chunk(5)`生成块大小为4、4、4、4、1，而`jsc::chunk_evenly(5)`生成块大小为3、3、3、4、3，确保任务负载更加平衡。

3. **设计与实现**
- **设计灵感**：来源于D语言的`std.range.evenChunks()`。
- **关键特性**：
- **高效计算**：将昂贵的计算（如除法和取模）一次性完成。
- **无分支编程**：通过分支预测优化，提升性能。
- **零开销原则**：在编译时和运行时均无额外开销。
- **实现细节**：
- 通过计算商和余数，动态调整块大小。
- 使用迭代器将范围划分为均匀块，并支持手动循环和Range适配器模式。

4. **性能与优化**
- **指令与分支比较**：与`std::views::chunk()`相比，`jsc::chunk_evenly()`在指令数上略有增加，但通过无分支设计减少了分支预测开销。
- **汇编代码对比**：在多种架构（如x86、ARM、RISC-V）上，`jsc::chunk_evenly()`的性能表现优于`std::views::chunk()`。

5. **改进的`std::execution`示例**
- 使用`jsc::chunk_evenly`优化并行执行，通过将输入和输出范围划分为均匀块，减少线程等待时间，提升任务调度效率。

6. **讨论与未来方向**
- **优化点**：现有方法可能因固定块大小导致任务数与块数不匹配，`jsc::chunk_evenly()`通过动态调整块大小更好地平衡任务负载。
- **未来计划**：增强`jsc::chunk_evenly_view<>`的随机访问支持，并探索JSC C++库中更通用的组件。

总结：`jsc::chunk_evenly`是一种高效的Range适配器，通过动态调整块大小实现任务间的均匀工作分配，特别适用于并行计算场景，能够显著提升性能和资源利用率。