无侵入的代码和产物优化：二进制优化与Profile预测

开发运维 2023-10-09 向阳逐梦 手机阅读

背景信息

编译优化手段及其缺陷

目前广泛使用的优化手段主要发生在：

  • 源代码和中间产物（IR）层面，如编译优化（参考编译过程与编译优化基础概念：以C语言为例）
  • 链接时优化（link time optimisation, LTO）在链接时将项目当作whole-program，允许编译优化组件进一步对IR进行优化。
  • 基于剖析（profiling）的优化，一般需要对程序进行插桩（源代码或二进制）、运行、收集性能数据（如不常访问的函数、分支、cache miss等），然后基于性能数据（profile）对指令进行优化和重排，从而减少cache miss、提高产物性能，这个过程又被称为feedback-guided optimisation （FGO）或profile-guided optimisation（PGO）。

    • Profile data可以在编译的各个阶段指导优化

    上述方式的主要缺点有：

  • 针对源代码和中间产物的编译优化，往往需要获得项目的源代码，并重新进行编译。为了达到最好的编译效果，可能需要重复几次编译过程，同时对于大型项目来说，编译过程较为耗时。
  • 编译优化往往只针对单个源文件及其产生的object，多个object进行链接后的结果没有进一步优化。
  • 对于无法获得源代码的第三方已编译的库，即使我们拥有更好的优化手段，也无法再次进行编译优化。
  • 对于PGO 而言，收集profile的过程非常消耗内存和计算资源，且每次重新编译后都要重新运行收集profile，整个PGO过程较为耗时，而且对profile的收集方法非常敏感。

    • 一些概念

    空间局部性（spatial locality）

    空间局部性是指需要连续访问的cache或程序指令的空间位置，离得越紧，程序性能越好，因为减少了miss时的重定向的性能损耗。在本文中，我们指的主要是指令的空间局部性。

    We call spatial locality a measure of the distance between the virtual memory addresses of two consecutively executed instructions of a program. Instructions that are located at close memory addresses are said to have high spatial locality. If instructions tend to be executed together in time (for instance, if the execution of an instruction succeeds the execution of another), then it is desirable that they have high spatial locality. In this way, they are likely to be fetched in the same cache line, via one single memory access.

    常见的提高空间局部性的方法有：

  • 将caller（调用函数的函数），callee（被调函数）按顺序挨个放在一起；
  • 将倾向于一起按顺序执行的bb（basic blocks）放在一起（连续的内存地址）。这一类问题往往出现在分支结构中：我们希望将更大概率被执行的branch（由bb组成）放在前面。这一类问题又被称为basic-block placement problem。举个例子：

    • (a) 一个以CFG表示的有分支的程序片段（黑框中的文字为branch被选择执行的频率）；(b)和(c)表示了两种不同的placement，cost分别为1+2+98+100=201和1+2+2+100=105。本土取自Vespa的论文

    cost的计算方法：如果一个从bb_i到bb_j的概率（顺序执行则为0）

    Profiling

    在本文中，profiling是指（通常在待优化程序运行时）收集CFG的边和边被选择执行的概率的过程。

    profiling分为动态和静态两种方式：

  • 动态（dynamic profiling）：在运行时观测待优化程序并收集信息

  • 静态（static profiling）：通过分析程序代码，预估branch概率。无需运行程序。

    • 本文调研工作的贡献

    针对以上问题，本文主要介绍两种新的、对生产过程无侵入的优化方式：

  • BOLT：对二进制产物进行优化，优点：无需项目源代码，可在编译优化后的产物上进行再次优化。
  • Vespa：无需运行程序而是通过预测手段获得profile，基于profile对产物进行优化。

    • 二进制优化 - BOLT

    Panchenko, M., Auler, R., Nell, B. and Ottoni, G., 2019, February. Bolt: a practical binary optimizer for data centers and beyond. In 2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO) (pp. 2-14). IEEE.

    Blog post: engineering.fb.com/2018/06/19/…

    BOLT全称Binary Optimisation and Layout Tool，顾名思义，BOLT是在二进制产物层面，通过对指令进行重布局，从而提升cache命中率和提高分支预测能力，从而对应用的性能进行优化。

    总结

  • BOLT基于LLVM构建
  • 在大型实际应用上，BOLT可在FDO和LTO的基础上再次提升20.4%的性能。
  • BOLT依赖于采样的profile data

    • Motivation

  • 如何收集profile data？SBF

  • 优化时机的选取？在binary层优化

  • 动态还是静态优化？静态优化

    • 设计思路

  • 初版设计

  • 重定位模式（relocations mode）

  • Pipeline重写

  • C++异常处理和Debug信息

    • BOLT的优化

    BOLT：

  • 使用pass概念，在code transformation和analysis时使用相应的优化pass。部分pass架构无关、部分架构依赖（architecture-dependent）
  • BOLT使用了一个数据流（Data flow）分析组件，供需要的pass使用

    • BOLT的Intel x86-64优化组件

    BOLT为Intel x86-64架构开发的优化pass（有序）

  • 针对AMD处理器的特殊优化

  • 在Linker的基础上fold更多的函数（以HHVM为例，在linker的基础上多fold了3%的函数）

  • 基于function call frequency，提升indirect call。llvm.org/devmtg/2015…

  • 基于架构的一些简单的优化，如

  • 简化load指令

  • 再次2

  • 类似3.www.intel.com/content/www…

  • 基于executed paths的frequency，重排或拆分hot/cold basic blocks

  • 再次4

  • 删除不可达的bb

  • 再次8

  • 基于HFSort（）——重排函数顺序

    • Optimizing Function Placement for Large-Scale Data-Center Applications.pdf

  • 简化条件语句的tail calls。en.wikipedia.org/wiki/Tail_c…
  • 移除不必要的caller-saved寄存器溢出
  • 将called-saved寄存器溢出移到被调用更近的位置

    • 如何进行profiling

    在intel的微处理器中，LBR是一个包含最后32个执行的branches的list。BOLT基于LBR进行profile data采集。

    收益

    Facebook

    加速

    细分优化

    Clang和GCC

    加速

    细分优化

    Thats' it!

    VESPA

    Moreira, A.A., Ottoni, G. and Quintão Pereira, F.M., 2021. VESPA: static profiling for binary optimization. Proceedings of the ACM on Programming Languages, 5(OOPSLA), pp.1-28.

    Blog post: engineering.fb.com/2022/03/15/…

    总结

  • 基于机器学习进行profile预测，因为没有运行时的动态信息采集（dynamic profiler），本方法是一个static profiler
  • 表现比dynamic profiler差很多，但是还是比编译器原生的优化好很多：比clang O3加速6%、减少10%的cache miss
  • 实现上基于BOLT

    • Vespa的设计

    举个例子：

    (a)从程序（见总结-一些背景信息-空间局部性）中提取的一个代码片段；(b)特征提取；(c)特征向量；(d)一个简单的预测器；(e)预测的branch概率

    在本例中，代码片段特征取自程序的syntax，需要记录的特征取自下表。特征被向量化后用于生成预测。

    收益

    benchmark选择：clang、GCC、MySQL、PostgreSQL

  • 性能提升（over clang-O3）

  • L1 instruction cache miss的减少

  • Cache miss减少与性能提升的相关性

  • 机器学习耗时

  • 应用耗时（用于生成binary的时间，以秒计）

    • That's it!

    基于机器学习的PGO

    总结

    提出了一种新型的统计方法来推测branch概率：

  • Offline training：从大量有branch概率信息的binary采集数据、训练
  • 编译器使用learned model来预测branch信息、做优化决策
  • 嵌入了LLVM，替换了人工规则集
  • 在应用中，省去了profiling采集的运行时间、对编译耗时几乎没有影响。

    • Motivation

    设计

    本方法主要是两步：离线学习和在线推理

  • 离线学习

  • 编译时预测

  • 特征采集

    • 数据集：llvm-test-suite benchmarks, abseil, bash, box2d, bzip2, diffutils, distorm, fmt, fpm, graphviz, grep, hermes, jsonnlohmann, leveldb, liblinear, libpng, libuv, clang, lua, myhtml, oggvorbis, povray, python, sela, smallpt, sqlite, tscp, xxhash, z3

    采集的特征包括：

  • 模型训练

  • 代码生成、概率推理

    • 将训练完的模型转换成一个可以被嵌入编译器的C代码

    在编译器运行时，branch信息被用于模型匹配、获得两个branch的概率。

    收益

    在benchmark中收集到了200MB的信息，训练后的模型大小2MB。生成的1k的预测代码。每秒可以查询预测25万次。

    被编译项目的运行加速：

    That's it!