ChatGPT解决这个技术问题 Extra ChatGPT

我可以通过给出整数范围来提示优化器吗?

我正在使用 int 类型来存储值。根据程序的语义,该值总是在一个很小的范围内(0 - 36)变化,并且使用 int(不是 char)只是因为 CPU 效率。

似乎可以在如此小的整数范围内执行许多特殊的算术优化。对这些整数的许多函数调用可能会优化为一小组“神奇”操作,有些函数甚至可以优化为表查找。

那么,是否可以告诉编译器这个 int 总是在那个小范围内,编译器是否可以进行这些优化?

值范围优化存在于许多编译器中,例如。 llvm 但我不知道声明它的任何语言提示。
请注意,如果您从未使用过负数,则使用 unsigned 类型可能会有所收获,因为它们更容易让编译器进行推理。
@RemusRusanu:Pascal 允许您定义 subrange types,例如 var value: 0..36;
“int (not a char) 仅因为 CPU 效率而被使用。”这种古老的传统智慧通常不是很正确。窄类型有时需要零或符号扩展到整个寄存器宽度,尤其是。当用作数组索引时,但有时这是免费发生的。如果你有一个这种类型的数组,缓存占用空间的减少通常比其他任何东西都重要。
忘了说:在大多数具有 64 位指针的系统上,intunsigned int 也需要从 32 位进行符号或零扩展至 64 位。请注意,在 x86-64 上,operations on 32-bit registers zero-extend to 64-bit for free(不是符号扩展,但有符号溢出是未定义的行为,因此编译器可以根据需要只使用 64 位有符号数学)。因此,您只会看到零扩展 32 位函数 args 的额外指令,而不是计算结果。您会使用更窄的无符号类型。

P
Peter Mortensen

对的,这是可能的。例如,对于 gcc,您可以使用 __builtin_unreachable 告诉编译器不可能的条件,如下所示:

if (value < 0 || value > 36) __builtin_unreachable();

我们可以将上面的条件包装在一个宏中:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

并像这样使用它:

assume(x >= 0 && x <= 10);

As you can seegcc 基于此信息执行优化:

#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

产生:

func(int):
    mov     eax, 17
    ret

然而,一个缺点是,如果您的代码违反了此类假设,您将获得未定义的行为。

发生这种情况时它不会通知您,即使在调试版本中也是如此。要更轻松地调试/测试/捕获带有假设的错误,您可以使用混合假设/断言宏(感谢 @David Z),如下所示:

#if defined(NDEBUG)
#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)
#else
#include <cassert>
#define assume(cond) assert(cond)
#endif

在调试版本中(定义了 NDEBUG not),它像普通的 assert 一样工作,打印错误消息和 abort 的程序,而在发布版本中,它使用了一个假设,生成优化代码。

但是请注意,它不能替代常规 assert - cond 仍保留在发布版本中,因此您不应执行 assume(VeryExpensiveComputation()) 之类的操作。


@Xofo,没有得到它,在我的示例中这已经发生,因为编译器从代码中删除了 return 2 分支。
但是,gcc cannot 似乎按照 OP 的预期优化了神奇操作或表查找的功能。
@user3528438,__builtin_expect 是非严格提示。 __builtin_expect(e, c) 应该读作“e 最有可能评估为 c”,并且可用于优化分支预测,但它并不限制 e 始终为 c,因此不允许优化器丢弃其他情况。 Look how branches are organized in assembly
理论上,任何无条件导致未定义行为的代码都可以用来代替 __builtin_unreachable()
除非有一些我不知道的怪癖使这成为一个坏主意,否则将它与 assert 结合起来可能是有意义的,例如,当未定义 NDEBUG 时将 assume 定义为 assert,并将其定义为 {5 } 当 NDEBUG 被定义时。这样,您就可以从生产代码中的假设中受益,但在调试版本中,您仍然有一个明确的检查。当然,您随后必须进行足够的测试以确保自己在野外得到满足。
L
Lundin

对此有标准支持。您应该做的是包含 stdint.h (cstdint),然后使用类型 uint_fast8_t

这告诉编译器您只使用 0 - 255 之间的数字,但如果这样可以提供更快的代码,则可以免费使用更大的类型。同样,编译器可以假设变量的值永远不会超过 255,然后相应地进行优化。


这些类型几乎没有应有的使用(我个人倾向于忘记它们的存在)。他们提供的代码既快速又便携,非常出色。自 1999 年以来,它们一直存在。
对于一般情况,这是一个很好的建议。丹尼斯的回答显示了针对特定场景的更具延展性的解决方案。
编译器仅在 uint_fast8_t 实际上是 8 位类型(例如 unsigned char)的系统上获取 0-255 范围信息,就像在 x86/ARM/MIPS/PPC (godbolt.org/g/KNyc31) 上一样。在 early DEC Alpha before 21164A 上,不支持字节加载/存储,因此任何合理的实现都将使用 typedef uint32_t uint_fast8_t。 AFAIK,对于大多数编译器(如 gcc)来说,类型没有额外的范围限制机制,所以我很确定 uint_fast8_t 的行为与 unsigned int 或在这种情况下的任何行为完全相同。
bool 是特殊的,并且范围限制为 0 或 1,但它是内置类型,不是由 gcc / clang 上的 char 的头文件定义的。就像我说的,我没有认为大多数编译器都有一种机制可以实现这一点。)
无论如何,uint_fast8_t 是一个很好的建议,因为它会在与 unsigned int 一样高效的平台上使用 8 位类型。 (我实际上不确定 fast 类型应该是快速的 for,以及缓存占用空间权衡是否应该是其中的一部分。)。 x86 对字节操作具有广泛的支持,甚至可以使用内存源进行字节添加,因此您甚至不必进行单独的零扩展加载(这也很便宜)。 gcc 使 uint_fast16_t 在 x86 上成为 64 位类型,这对于大多数用途来说是疯狂的(与 32 位相比)。 godbolt.org/g/Rmq5bv
C
Community

当前的答案适用于您确定范围是多少的情况,但是如果您在值超出预期范围时仍需要正确的行为,那么它将不起作用。

对于这种情况,我发现这种技术可以工作:

if (x == c)  // assume c is a constant
{
    foo(x);
}
else
{
    foo(x);
}

这个想法是代码-数据的权衡:您将 1 位 数据(无论是 x == c)移动到 控制逻辑
这暗示优化器x 实际上是一个已知的常量 c,鼓励它内联和优化 foo 的第一次调用,与其余部分分开,可能非常重要。

确保将代码实际分解为单个子例程 foo,但不要复制代码。

例子:

要使这项技术发挥作用,您需要有点幸运——在某些情况下,编译器决定不对事物进行静态评估,而且它们有点随意。但是当它工作时,它工作得很好:

#include <math.h>
#include <stdio.h>

unsigned foo(unsigned x)
{
    return x * (x + 1);
}

unsigned bar(unsigned x) { return foo(x + 1) + foo(2 * x); }

int main()
{
    unsigned x;
    scanf("%u", &x);
    unsigned r;
    if (x == 1)
    {
        r = bar(bar(x));
    }
    else if (x == 0)
    {
        r = bar(bar(x));
    }
    else
    {
        r = bar(x + 1);
    }
    printf("%#x\n", r);
}

只需使用 -O3 并注意 the assembler output 中的预计算常量 0x200x30e


你不想要 if (x==c) foo(c) else foo(x) 吗?如果只是为了捕捉 fooconstexpr 实现?
@MSalters:我知道有人会问这个!!我在 constexpr 出现之前就提出了这种技术,之后再也没有费心去“更新”它(尽管我什至后来也没有真正费心担心过 constexpr),但我没有这样做的原因最初是我想让编译器更容易将它们作为公共代码分解并删除分支,如果它决定将它们保留为正常的方法调用而不是优化。我预计如果我输入 c,编译器真的很难 c (对不起,糟糕的笑话)这两者是相同的代码,尽管我从未验证过这一点。
S
StoryTeller - Unslander Monica

我只是想说,如果您可能想要一个更标准的 C++ 解决方案,您可以使用 [[noreturn]] 属性来编写自己的 unreachable

因此,我将重新使用 deniss' excellent example 来演示:

namespace detail {
    [[noreturn]] void unreachable(){}
}

#define assume(cond) do { if (!(cond)) detail::unreachable(); } while (0)

int func(int x){
    assume(x >=0 && x <= 10);

    if (x > 11){
        return 2;
    }
    else{
        return 17;
    }
}

其中 as you can see 产生几乎相同的代码:

detail::unreachable():
        rep ret
func(int):
        movl    $17, %eax
        ret

缺点当然是,您会收到 [[noreturn]] 函数确实返回的警告。


它适用于 clangwhen my original solution doesn't,非常棒的技巧和 +1。但是整个事情非常依赖于编译器(正如 Peter Cordes 向我们展示的那样,在 icc 中它可能恶化性能),所以它仍然不是普遍适用的。另外,小注:unreachable 定义 must be available to optimizer and inlined for this to work
一个简洁的解决方案,但会生成警告。