优化的重新排序

Question

我有这种C函数的分支被称为比别人多。

我的目标是找出安排if语句以尽量减少分支的最佳方式。

我能想到的唯一方法就是写入文件，以便每条条件都分支到，从而创建直方图。这似乎是一个乏味的方式。有更好的方法，更好的工具吗？

我在AS3 Linux上使用gcc 3.4构建它;使用oprofile（opcontrol）进行分析。

Answer 1

这不便携，但是GCC的许多版本都支持一个名为__builtin_expect()功能，可以用来告诉编译器我们所期望的值是：

if(__builtin_expect(condition, 0)) { 
    // We expect condition to be false (0), so we're less likely to get here 
} else { 
    // We expect to get here more often, so GCC produces better code 
} 

Linux内核使用这些作为宏来使得他们更直观，更清洁，更便携（即重新定义非GCC系统宏）：

#ifdef __GNUC__ 
# define likely(x) __builtin_expect((x), 1) 
# define unlikely(x) __builtin_expect((x), 0) 
#else 
# define likely(x) (x) 
# define unlikely(x) (x) 
#endif 

有了这个，我们可以重写上面的：

if(unlikely(condition)) { 
    // we're less likely to get here 
} else { 
    // we expect to get here more often 
} 

当然，这可能是不必要的，除非你的目标是原始速度和/或你已经分析并发现这是一个问题。

Answer 2

尝试一个分析器（gprof？） - 它会告诉你花了多少时间。我不记得gprof是否会计数分支，但如果没有，只需在每个分支中调用一个单独的空方法。

Answer 3

将每个分支中的代码包装到函数中，并使用分析器查看每个函数被调用的次数。

Answer 4

逐行分析可以让您了解哪些分支更经常被调用。

使用像LLVM这样的东西可以自动进行此优化。

Answer 5

某些计数器可能会有所帮助。在看到计数器之后，并且有很大差异，您可以按降序对条件进行排序。

 
static int cond_1, cond_2, cond_3, ... 

void foo(){ 
    if (condition){ 
     cond_1 ++; 
     ... 
    } 
    else if(/*another_condition*/){ 
     cond_2 ++; 
     ... 
    } 
    else if (/*another_condtion*/){ 
     cond_3 ++; 
     ... 
    } 
    else{ 
     cond_N ++; 
     ... 
    } 
} 

编辑：一个“析构函数”，可以在测试运行结束打印计数器：

void cond_print(void) __attribute__((destructor)); 

void cond_print(void){ 
    printf("cond_1: %6i\n", cond_1); 
    printf("cond_2: %6i\n", cond_2); 
    printf("cond_3: %6i\n", cond_3); 
    printf("cond_4: %6i\n", cond_4); 
} 

我认为这是足以只修改以包含foo（）函数的文件。

Answer 6

在Callgrind下运行您的程序将为您提供分支信息。另外，我希望你能够分析并确定这段代码是有问题的，因为这看起来好像是一种微型优化。编译器将会从if/else if/else生成一个分支表，如果它能够不需要分支的话（显然这取决于条件是什么）0，并且甚至会使处理器上的分支预测器失效（假设这不适用于嵌入式工作，如果可以随意忽略我）非常适合确定分支目标。

Answer 7

它实际上并不重要，你改变它们到IMO的顺序。分支预测器将存储最常见的分支，并自动进行分析。

这就是说，有一些你可以尝试......你可以保持一组工作队列，然后，根据该if语句，他们执行他们陆续之前分配到正确的工作队列最后。

这可以通过使用条件移动等来进一步优化（尽管这需要汇编程序，AFAIK）。这可以通过有条件地将1移入一个寄存器中来完成，该条件在条件a时被初始化为0。将指针值放在队列末尾，然后决定是否增加队列计数器，方法是将该条件1或0添加到计数器。

突然之间，你已经消除了所有的分支，它变得无关紧要，有多少分支预测失误。当然，与其中任何一种情况一样，你最好的方式是分析，因为尽管看起来它会提供胜利......但它可能不会。

Answer 8

我们用这样一种机制：

// pseudocode 
class ProfileNode 
{ 
public: 
    inline ProfileNode(const char * name) : m_name(name) 
    { } 
    inline ~ProfileNode() 
    { 
     s_ProfileDict.Find(name).Value() += 1; // as if Value returns a nonconst ref 
    } 

    static DictionaryOfNodesByName_t s_ProfileDict; 
    const char * m_name; 
} 

然后在你的代码

void foo() 
{ 
    if (/*condition*/) 
    { 
     ProfileNode("Condition A"); 
     // ... 
    } 
    else if(/*another_condition*/) 
    { 
     ProfileNode("Condition B"); 
     // ... 
    } // etc.. 
    else 
    { 
     ProfileNode("Condition C"); 
     // ... 
    } 
} 

void dumpinfo() 
{ 
    ProfileNode::s_ProfileDict.PrintEverything(); 
} 

你可以看到它是如何的容易把这些节点也秒表计时，看看哪些分支消耗的时间最多。

Answer 9

作为剖析技术，this是我所依赖的。

你想知道的是：花在评估这些条件上的时间是执行时间的一小部分吗？

样品会告诉你，如果没有，它没关系。

如果如果条件包括函数调用是在栈上的时间显著的一部分，你要避免花费太多的时间在那些假比较什么事做，例如。你说的这种方式是，如果你经常看到它从比如第一个或第二个if语句中调用一个比较函数，那么在这个例子中捕获它，然后退出来看它是否返回false或true。如果它通常返回false，它可能应该更靠近列表。