在C++中使用CodeQL寻找10倍以上性能改进

结合动态和静态分析进行性能优化

在之前的文章中，我主张构建结合静态和动态分析的系统来进行性能优化。通过这种方式，我们可以构建比单独使用任一分析方法更有用的工具。事实上，对于许多静态分析来说，是否有用很可能取决于是否与性能分析器结合使用。

类型别名在C/C++中的性能问题

在C/C++中，char类型（及其类似类型，如uint8_t）可以为其他任何类型起别名。通过此类类型进行内存写入时，编译器必须假设它可能修改了任何其他基于堆的内存位置，即使该位置具有完全不同的类型。

这导致编译器无法安全地自动向量化循环，因为它需要在每次写入后重新加载这些值。在Travis Downs的博客文章中，他展示了一个特别病态的例子，这个问题导致代码比可能的速度慢20倍。

使用CodeQL检测别名写入

我们的目标是构建一个查询，在代码中找到由于通过别名类型写入而导致编译器生成不必要内存加载的模式。

我们寻找的代码序列如下：

1. 通过表达式X从内存加载，其中X表示内存位置
2. 通过别名类型（如char）进行写入
3. 再次通过X从内存加载，且表达式X的组件自步骤1以来未被修改

CodeQL查询示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

predicate isMemCharWriteExpr(Expr e) {
   exists(AssignExpr a, Expr lval |
     a = e.(AssignExpr) and
     lval = a.getLValue() and
     lval.getType().stripType() instanceof CharType and
     (
       lval instanceof PointerDereferenceExpr or
       lval instanceof ArrayExpr or
       lval instanceof OverloadedArrayExpr
     )
   )
}

实际案例与性能改进

Bitcoin案例：bech32::ExpandHRP函数

在Bitcoin代码库中，我们发现bech32::ExpandHRP函数存在此问题：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

data ExpandHRP(const std::string& hrp) {
   data ret;
   ret.reserve(hrp.size() + 90);
   ret.resize(hrp.size() * 2 + 1);
   for (size_t i = 0; i < hrp.size(); ++i) {
       unsigned char c = hrp[i];
       ret[i] = c >> 5;
       ret[i + hrp.size() + 1] = c & 0x1f;
   }
   return ret;
}

通过将data类型从std::vector<uint8_t>改为std::vector<char8_t>（C++20），我们消除了别名问题。在32k输入字节时，优化版本比原版本快12倍。

Monero案例：bulletproof_PROVE函数

在Monero项目中，我们发现类似模式：

1
2
3
4
5

for (size_t i = 0; i < v.size(); ++i) {
   sv[i] = rct::zero();
   sv[i].bytes[0] = v[i] & 255;
   // ... 7 more similar assignments
}

通过将bytes数组的类型改为char8_t，编译器能够一次性执行所有8个赋值，性能提升了3-4倍。

分析与结论

查询有效性

循环条件（LC）查询比其他通用查询产生更少的误报，并且具有更好的投入产出比。专注于循环是有意义的，因为任何改进都会因循环的重复执行而放大。

开发工作流集成

这种分析可以很好地集成到开发工作流中：

• IDE内联分析：开发人员编写新代码时收到警报
• 全代码库分析：结合持续性能分析对结果进行排名

未来工作

开放式问题包括：

1. 我们还能查询哪些属性？除了类型别名问题，是否还有其他语言级属性或API使用模式会导致性能问题？
2. 在汇编级别进行此分析是否更有意义？这样可以避免必须编码我们对源代码如何转换为汇编的理解。

结合动态和静态分析进行性能优化是一个广阔的领域，通过CodeQL等工具，我们能够发现并修复传统方法难以发现的性能问题。