相关疑难解决方法(0)

这是一段看似非常特殊的C++代码.出于某种奇怪的原因,奇迹般地对数据进行排序使得代码几乎快了六倍.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c) …

我从各种来源(虽然大多数来自我的同事)中听到过,-O3用g ++ 的优化级别进行编译在某种程度上是"危险的",并且除非被证明是必要的,否则应该避免.

这是真的,如果是的话,为什么？我应该坚持-O2吗？

具体来说,如果我有一系列if... else if语句,并且我事先知道每个语句将评估的相对概率,true它按照概率的顺序对它们进行排序有多大差异？例如,我应该更喜欢这个:

if (highly_likely)
  //do something
else if (somewhat_likely)
  //do something
else if (unlikely)
  //do something

对此？:

if (unlikely)
  //do something
else if (somewhat_likely)
  //do something
else if (highly_likely)
  //do something

很明显,排序版本会更快,但是为了便于阅读或存在副作用,我们可能希望对它们进行非最佳排序.在您实际运行代码之前,很难判断CPU在分支预测方面的表现如何.

因此,在尝试这个过程中,我最终回答了我自己的问题,但我还想听听其他意见/见解.

重要提示:此问题假定if语句可以任意重新排序,而不会对程序的行为产生任何其他影响.在我的回答中,三个条件测试是互斥的,不会产生副作用.当然,如果必须按某种顺序评估陈述以达到某些预期的行为,那么效率问题就没有实际意义.

我遇到了#define他们使用的一个__builtin_expect.

文件说:

内置功能: long __builtin_expect (long exp, long c)

您可以使用__builtin_expect为编译器提供分支预测信息.一般来说,你应该更喜欢使用实际的配置文件反馈(-fprofile-arcs),因为程序员在预测程序实际执行情况方面是非常糟糕的.但是,有些应用程序难以收集此数据.

返回值是值exp,它应该是一个整数表达式.内置的语义是预期的 exp == c.例如:

      if (__builtin_expect (x, 0))
        foo ();

Run Code Online (Sandbox Code Playgroud)

表示我们不打算打电话foo,因为我们预计x会为零.

那么为什么不直接使用:

if (x)
    foo ();

而不是复杂的语法__builtin_expect？

我刚刚进入一个拥有相当庞大代码库的项目.

我主要处理C++,他们编写的很多代码都使用布尔逻辑的双重否定.

 if (!!variable && (!!api.lookup("some-string"))) {
       do_some_stuff();
 }                                   

我知道这些人都是聪明的程序员,很明显他们不会偶然这样做.

我不是经验丰富的C++专家,我唯一猜测他们这样做的原因是他们想要绝对肯定被评估的值是实际的布尔表示.所以他们否定它,然后再次否定它以使其恢复到它的实际布尔值.

这是正确的,还是我错过了什么？

对于英特尔架构,是否有一种方法可以指示GCC编译器生成的代码总是强制分支预测在我的代码中采用特定方式？英特尔硬件是否支持此功能？那么其他编译器或硬件呢？

我会在C++代码中使用它,我知道我希望快速运行的情况,并且不关心当另一个分支需要被采取时,即使它最近采用了该分支.

for (;;) {
  if (normal) { // How to tell compiler to always branch predict true value?
    doSomethingNormal();
  } else {
    exceptionalCase();
  }
}

作为Evdzhan Mustafa的后续问题,该提示是否可以在处理器第一次遇到指令时指定一个提示,所有后续的分支预测都能正常运行？

从可我怎么用C语言格式的数字1123456789来1,123,456,789？我试过使用,printf("%'10d\n", 1123456789);但这不起作用.

你能告诉我什么吗？解决方案越简单越好.

为了说清楚,我不打算在这里使用任何类型的便携性,所以任何将我绑定到某个盒子的解决方案都可以.

基本上,我有一个if语句将99%的时间评估为true,并且我试图剔除每个性能的最后一个时钟,我可以发出某种编译器命令(使用GCC 4.1.2和x86 ISA,如果告诉分支预测器它应该缓存该分支吗？

GCC编译器支持__builtin_expect语句,该语句用于定义可能的和不太可能的宏.

例如.

#define likely(expr)    (__builtin_expect(!!(expr), 1))
#define unlikely(expr)  (__builtin_expect(!!(expr), 0))

是否有Microsoft Visual C编译器的等效声明,或等效的东西？

在另一个帖子中,我被告知在速度和紧凑性方面switch可能比查找表更好.

所以我想了解这个之间的区别:

查找表

static void func1(){}
static void func2(){}

typedef enum
{
    FUNC1,
    FUNC2,
    FUNC_COUNT
} state_e;

typedef void (*func_t)(void);

const func_t lookUpTable[FUNC_COUNT] =
{
    [FUNC1] = &func1,
    [FUNC2] = &func2
};

void fsm(state_e state)
{
    if (state < FUNC_COUNT) 
        lookUpTable[state]();
    else
        ;// Error handling
}

还有这个:

开关

static void func1(){}
static void func2(){}

void fsm(int state)
{
    switch(state)
    {
        case FUNC1: func1(); break;
        case FUNC2: func2(); break;
        default:    ;// Error handling
    }
}

我认为查找表更快,因为编译器尝试在可能的情况下将switch语句转换为跳转表.既然这可能是错的,我想知道为什么!

谢谢你的帮助!