2

我有这个函数，给定一个格雷码，返回下一个格雷码。您可以在此处找到有关其工作原理的更完整说明。问题是我想让这个增量函数模块化，以便递增对应的格雷码UINT_MAX返回对应的格雷码0（分别是最高有效位和0）。由于这不是默认行为，因此我为这种特殊情况添加了检查。这是完整的算法：

unsigned next_gray(unsigned gray)
{
    static const unsigned msb
        = 1u << (CHAR_BITS - sizeof(unsigned) - 1u);

    // gray is odd
    if (__builtin_parity(gray))
    {
        if (__builtin_expect(gray == msb, false))
        {
            return 0u;
        }
        else
        {
            unsigned y = gray & -gray;
            return gray ^ (y << 1u);
        }
    }

    // gray is even
    return gray ^ 1;
}

所以，实际的问题实际上是关于分支预测的。我经常读到__builtin_expect只有当一个分支真的很可能被选中或不太可能被选中时才使用它，常见的例子是在没有错误的情况下加速程序。

考虑到我没有处理错误情况，我不确定使用__builtin_expect这样的边界检查是否是一个好主意。这是一个使用的好地方__builtin_expect还是增加最大值是一个足够常见的操作来欺骗分支预测？

注意：与往常一样，评论和答案会突出显示我的问题中不清楚的事情:)

我将提供更多背景信息：此函数旨在成为库的一部分，为了成为库而开发，并且不被任何已知的实际项目使用。因此，添加__builtin_expect意味着我希望人们主要增加其他值而不是最大值；手头没有任何实际项目，我想知道这是否是一个安全的假设。

4

1 回答 1

0

取自GCC 在线文档：

您可以使用__builtin_expect为编译器提供分支预测信息。一般来说，您应该更喜欢为此使用实际的配置文件反馈 ( -fprofile-arcs)，因为众所周知，程序员不善于预测他们的程序实际执行情况。但是，有些应用程序很难收集这些数据。

这是使用 __builtin_expect 的好地方，还是增加最大值是欺骗分支预测的常见操作？

这一切都取决于您的应用程序。如果 的值gray是均匀分布的，那么它将是 1 中的 1 (UINT_MAX+1)，但你能肯定地说吗？这就是文档建议使用-fprofile-arcs.

gcov维基百科文章实际上包含一个很好的简单示例，说明如何使用-fprofile-arcs和gcov获取信息以做出明智的决定。

更新：

如果您无法配置文件，那么在所有条件相同的情况下，边缘情况gray == msb的可能性很小，因此您可能安全地使用__builtin_expect. 但是，如果您因为不知道将如何使用您的库而无法配置文件，这听起来更像是悲观而不是优化。如果我使用你的库并且总是传入gray它等于msb你的库对我来说不会那么快。没有考虑特定应用程序编写的通用库通常会尝试对一般情况有利，或者不对输入做出任何假设。这就是为什么您会看到不同的实现，malloc例如jemalloc和tcmalloc. 两者都针对非常特定的用例进行了优化，如果您以一种与它所优化的方式不同的方式使用它，它的效果也不会那么好。此外，您可能会对这篇博客文章感兴趣。

于 2015-06-17T10:36:06.230 回答