使用CodeQL在C++中发现10倍以上性能提升

引言

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

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

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

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

使用CodeQL检测别名写入

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

通过表达式X从内存加载，其中X表示内存位置
通过别名类型（如char）进行写入
再次通过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函数

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


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;
    }
    ret[hrp.size()] = 0;
    return ret;
}

通过将data类型定义为std::vector<char8_t>（仅限C++20）而不是std::vector<uint8_t>，可以消除别名问题。在32k输入字节时，优化版本比先前版本快12倍。

Monero中的bulletproof_PROVE函数

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;
    // ... 更多赋值操作
}

通过将bytes数组的类型更改为char8_t，编译器可以一次性执行所有8个赋值操作，在128到8192的大小范围内速度提升约3-4倍。

分析与结论

查询效果评估

循环条件（LC）查询比其他通用查询更容易产生真阳性结果，并且具有更好的投入产出比。限制循环体为线性（无分支）并且只调用内联函数，有助于提高真阳性率。

工作流集成建议

在开发人员编写新代码时，如果IDE提醒他们存在匹配我们寻找属性的循环，决定是否调整代码可能很容易。对于整个代码库的分析，连续性能分析可以提供清晰的信号优先级。

未来工作方向

可查询的属性类型：除了类型别名问题，还有哪些语言级属性可以类似地捕获？
汇编级分析：在汇编级别进行分析可以避免必须编码源代码如何转换为汇编的问题

结合动态分析和静态分析的方法为性能优化开辟了广阔的前景，而CodeQL的灵活性使其成为探索这一领域的优秀工具。