向量化与Codegen：分析引擎Runtime技术领域介绍和实践

1. 向量化 VS. 代码生成: Runtime技术介绍及实践阿里云-EMR 周克勇(一锤)

2. 目录 01 微体系结构分析 03 代码生成 & Hybrid 02 向量化 04 Spark Native Runtime实践

3. 01 微体系结构分析

4. 硬件趋势 Memory Size 上百G 数百G T L1 Cache Size ~32K ~32K ~32K L2 Cache Size ~256K ~256K ~256K L3 Cache Size ~20M ~30M ~40M 10X CPU及访存成为瓶颈

5. 存储架构 CPU NUMA 关键指标

6. CPU指令执行 • 乱序执行分支预测流水线条件：数据无依赖 • • 条件：预测准确条件：指令可重叠；长指令 SIMD 硬件Prefetch • 条件：顺序访存 • 条件：Cache命中操作延迟(cycles) add/sub int 1 float divide ~ 10 Pipeline squash ~100

7. 计算引擎的性能瓶颈 IPC指标 • 科学计算&多媒体计算：2 • 数据库系统：0.7 性能瓶颈及原因 • 指令爆炸：解释执行 • 内存墙：随机访问，访存密度低 • 分支预测失败：解释执行&数据分布

8. 02 向量化

9. 向量化技术特征引擎向量化 != CPU向量化(SIMD) 向量化技术特征 • Batch执行 • 分摊解释执行开销 • 列式存储 • Cache friendly • Primitive的前提 • Primitive计算 • 编译优化 • 提升访存密度

10. Primitive的收益编译优化 • 循环展开 • 充分利用乱序执行 • 提升访存密度 • SIMD指令 Cache命中率 • 中间结果数据保存在cache中分支优化: Branching vs. Non-Branch

11. 执行流程

12. 高级特性: Micro-Adaptivity 动态调整最优执行策略 • 数据分布会发生变化策略清单 • Compiler • Branch vs. No-Branch • Loop Fission • Hand-Unrolling • Full computation 算法 • multi armed bandit

13. 向量化技术总结性能瓶颈的解决 • 指令爆炸 • Batch执行 • 内存墙 • Primitive执行提升访存密度 • 中间结果缓存到Cache • 分支预测 • No-Branch算法实现高级特性 • Micro-Adaptivity 劣势 • 中间结果物化 • 大量load/store指令代表引擎 • MonetDB/X100 • Vectorwise • Snowflake • Spark Photon • CK • StarRocks • Velox (Runtime Lib)

14. 03 代码生成 & Hybrid

15. 代码生成技术特征技术特征 • Pipeline模型 • Pipeline Breaker：需溢出到内存 • Push Mode • Pipeline内，不出寄存器 • 编译执行 • 代码生成(C++/LLVM/JAVA) • 编译执行 • 解决指令爆炸代表引擎 • Hyper • Apache Spark • NoisePage • Impala

16. 代码生成框架 produce/consumer框架 • 仅为了生成代码 • produce: 生成本算子的输出代码 • consume: 生成本算子的执行逻辑代码

17. 分支优化编译执行 • 消除虚函数带来的分支跳转生成高效分支代码

18. 内存墙解法：Partitioned Join Partitioned Join Radix Join

19. 内存墙解法：Software Prefetch

20. Hybrid: Relaxed Operator Fusion Prefer GP over Radix Join

21. 向量化 vs. 代码生成向量化代码生成指令爆炸 Batch执行编译执行额外指令 load/store 内存墙提高访存密度分支预测 Non-Branch算法 SIMD 编译器优化多线程 Unbalanced 自适应 Micro-Adaptivity Hybrid 软件Prefetch 编译执行/算法优化编译器优化 NUMA-Aware Morsel-Driven

22. 04 Spark Native Runtime实践

23. 代码生成实践 • 生成什么 • Weld IR • 怎么生成 • Spark Codegen框架 • Stage级别Fallback • 跟Spark集成 • 统一内存布局 • 执行流程

24. 代码生成实践 select col1 from t where col2 > 1000

25. 向量化实践调研中开源项目 • Velox • Gazelle

26. 非常感谢您的观看