我正在使用 int
类型来存储值。根据程序的语义,该值总是在一个很小的范围内(0 - 36)变化,并且使用 int
(不是 char
)只是因为 CPU 效率。
似乎可以在如此小的整数范围内执行许多特殊的算术优化。对这些整数的许多函数调用可能会优化为一小组“神奇”操作,有些函数甚至可以优化为表查找。
那么,是否可以告诉编译器这个 int
总是在那个小范围内,编译器是否可以进行这些优化?
unsigned
类型可能会有所收获,因为它们更容易让编译器进行推理。
var value: 0..36;
。
int
和 unsigned int
也需要从 32 位进行符号或零扩展至 64 位。请注意,在 x86-64 上,operations on 32-bit registers zero-extend to 64-bit for free(不是符号扩展,但有符号溢出是未定义的行为,因此编译器可以根据需要只使用 64 位有符号数学)。因此,您只会看到零扩展 32 位函数 args 的额外指令,而不是计算结果。您会使用更窄的无符号类型。
对的,这是可能的。例如,对于 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 see、gcc
基于此信息执行优化:
#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())
之类的操作。
对此有标准支持。您应该做的是包含 stdint.h
(cstdint
),然后使用类型 uint_fast8_t
。
这告诉编译器您只使用 0 - 255 之间的数字,但如果这样可以提供更快的代码,则可以免费使用更大的类型。同样,编译器可以假设变量的值永远不会超过 255,然后相应地进行优化。
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。
当前的答案适用于您确定范围是多少的情况,但是如果您在值超出预期范围时仍需要正确的行为,那么它将不起作用。
对于这种情况,我发现这种技术可以工作:
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 中的预计算常量 0x20
和 0x30e
。
if (x==c) foo(c) else foo(x)
吗?如果只是为了捕捉 foo
的 constexpr
实现?
constexpr
出现之前就提出了这种技术,之后再也没有费心去“更新”它(尽管我什至后来也没有真正费心担心过 constexpr
),但我没有这样做的原因最初是我想让编译器更容易将它们作为公共代码分解并删除分支,如果它决定将它们保留为正常的方法调用而不是优化。我预计如果我输入 c
,编译器真的很难 c (对不起,糟糕的笑话)这两者是相同的代码,尽管我从未验证过这一点。
我只是想说,如果您可能想要一个更标准的 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]]
函数确实返回的警告。
clang
、when my original solution doesn't,非常棒的技巧和 +1。但是整个事情非常依赖于编译器(正如 Peter Cordes 向我们展示的那样,在 icc
中它可能恶化性能),所以它仍然不是普遍适用的。另外,小注:unreachable
定义 must be available to optimizer and inlined for this to work。
不定期副业成功案例分享
return 2
分支。__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
被定义时。这样,您就可以从生产代码中的假设中受益,但在调试版本中,您仍然有一个明确的检查。当然,您随后必须进行足够的测试以确保自己将在野外得到满足。