libc++ 的 uniform_int_distribution 性能问题¶

背景¶

前段时间，@lwpie 发现一段 C++ 代码在 macOS 下，分别用自带的 Clang 编译和用 Homebrew 的 GCC 编译，性能差距接近一个数量级，下面是运行时间：

GCC-13 Homebrew: 300
Apple Clang: 2170

代码如下：

#include <algorithm>
#include <array>
#include <chrono>
#include <iostream>
#include <memory>
#include <random>

constexpr size_t FILE_N = 1e8;
constexpr size_t DATA_R = (1 << 23);

int main() {
  for (size_t i = 0; i < 4; ++i) {
    auto start = std::chrono::high_resolution_clock::now();
    std::random_device rd;
    std::mt19937_64 gen(rd());
    std::uniform_int_distribution<> dis(0, DATA_R);
    std::shared_ptr<std::array<size_t, FILE_N>> data(
        new std::array<size_t, FILE_N>());
    std::generate(data->begin(), data->end(),
                  [&dis, &gen]() { return dis(gen); });
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end -
                                                                       start)
                     .count()
              << std::endl;
    auto mean = std::accumulate(data->begin(), data->end(), 0.0) / FILE_N;
    std::cout << mean << std::endl;
  }
  return 0;
}

首先上结论：GCC-13 Homebrew 用的是 libstdc++，而 Apple Clang 用的是 libc++；libstdc++ 优化了 uniform_int_distribution 的实现，而 libc++ 采用的是朴素的实现，同时参数的选取正好触发了朴素实现的最坏情况，因此性能差距巨大。

探究¶

从现象上来看，看起来是 GCC 和 Clang 的性能差异很大，但由于这里涉及到了 STL 的实现，因此控制变量很重要：经过测试，发现 Clang + libstdc++ 性能好，GCC + libstdc++ 性能好，Clang + libc++ 性能差。

因此问题大概可以定位在 libc++ 上。那么，就去找 libc++ 的 uniform_int_distribution 实现：

// https://github.com/llvm/llvm-project/blob/9b2dfff57a382b757c358b43ee1df7591cb480ee/libcxx/include/__random/uniform_int_distribution.h#L233-L257
typename uniform_int_distribution<_IntType>::result_type
uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
{
    static_assert(__libcpp_random_is_valid_urng<_URNG>::value, "");
    typedef __conditional_t<sizeof(result_type) <= sizeof(uint32_t), uint32_t, __make_unsigned_t<result_type> >
        _UIntType;
    const _UIntType __rp = _UIntType(__p.b()) - _UIntType(__p.a()) + _UIntType(1);
    if (__rp == 1)
        return __p.a();
    const size_t __dt = numeric_limits<_UIntType>::digits;
    typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
    if (__rp == 0)
        return static_cast<result_type>(_Eng(__g, __dt)());
    size_t __w = __dt - std::__countl_zero(__rp) - 1;
    if ((__rp & (numeric_limits<_UIntType>::max() >> (__dt - __w))) != 0)
        ++__w;
    _Eng __e(__g, __w);
    _UIntType __u;
    do
    {
        __u = __e();
    } while (__u >= __rp);
    return static_cast<result_type>(__u + __p.a());
}

可以看到，它的实现思路是，为了生成 [a, b] 之间的均匀整随机数，它先找一个比 b-a 大的二的幂，然后生成随机数，模这个二的幂，接着采用拒绝采样：如果采样得到的值大于 b-a，那就重新采样。

但是前面测试的代码中，正好区间的大小就是二的幂，那么向上取整到二的幂次的时候，相当于每次采样有一半的概率需要重试。这样需要重新生成随机数的次数很多，而且分支预测错误率也很高。@Harry-Chen 用 perf 测试得到的数据：

branch-misses: 30% of all branches
Top-down: 44.6% Bad Speculation

说明分支预测确实成为了瓶颈。那么 libstdc++ 是怎么实现的，为什么它没有这个问题？经过搜索，发现了一篇博客：Doubling the speed of std::uniform_int_distribution in the GNU C++ library (libstdc++)：

论文 Fast Random Integer Generation in an Interval 提出了新的 uniform_int_distribution 实现，比原来的实现得到了两倍的性能提升，并且合并到了 libstdc++ 的实现当中。

所以到这里，问题就比较清晰了：libstdc++ 实现了更好的算法，同时 libc++ 的算法遇到了最坏情况，二者合起来，就观测到了巨大的性能差距。

如果把代码里 DATA_R 改成 (1 << 23)-1，那么 libc++ 算法的采样失败概率就会降到最小，此时的性能情况是：

GCC-13 Homebrew: 253
Apple Clang: 490

可见这里就是大概两倍的性能差距，这个差距就来源于 libstdc++ 实现的更好的采样算法。

解决方法就是，等 libc++ 也实现更好的算法，或者在需要用 uniform_int_distribution 的时候，避免链接 libc++，或者自己实现更好的算法。

libc++ 的 uniform_int_distribution 性能问题¶

背景¶

探究¶

评论