C++:循环内使用if会带来性能影响

6
我需要迭代大量(2D)数据,有时只处理特殊情况。对于我的应用程序来说,速度是最关键的因素。
我能想到的快速选项有:
选项A:
- 更易读 - 循环内比较导致性能下降?
void ifInLoop(bool specialCase, MyClass &acc) {
  for (auto i = 0; i < n; ++i) {
    for (auto j = 0; j < n; ++j) {
      if (specialCase) {
        acc.foo();
      } else {
        acc.bar();
      }
    }
  }
}

选项 B:

  • 代码重复
void loopsInIf(bool specialCase, MyClass &acc) {
  if (specialCase) {
    for (auto i = 0; i < n; ++i) {
      for (auto j = 0; j < n; ++j) {
        acc.foo();
      }
    }
  } else {
    for (auto i = 0; i < n; ++i) {
      for (auto j = 0; j < n; ++j) {
        acc.bar();
      }
    }
  }
}

选项 C:

  • 模板
  • 调用不太美观
  • 基本上与 B 相同?
template <bool specialCase> 
void templateIf(MyClass &acc) {
  for (auto i = 0; i < n; ++i) {
    for (auto j = 0; j < n; ++j) {
      if (specialCase) {
        acc.foo();
      } else {
        acc.bar();
      }
    }
  }
}

我知道这属于过早优化。然而,从理论角度出发,我对使用-O3(GCC / Clang)编译这些片段的差异以及产生的汇编和速度感兴趣。
(已经存在一个类似的Perl问题,但我想了解特别是C++方面的情况。) (编辑)specialCase在编译时已知吗? 不完全是。调用本身在另一个循环中,并且某些迭代处理方式不同。因此,类似于以下内容(但不一定等距,但与用户输入无关):
for (int i = 0; i < m; ++i) {
  ifInLoop(i % 10, acc);
}

我应该如何在这里使用选项C?引入额外的if语句,因此我希望它与B非常相似。

for (int i = 0; i < m; ++i) {
  if (i % 10)
    templateIf<true>(acc);
  else
    templateIf<false>(acc);
}

3
对其进行简要介绍。没有万能的办法。话虽如此,你的应用程序瓶颈不太可能是那个问题。 - Michael Chourdakis
4
这个网站可以让你查看生成的汇编代码:https://godbolt.org - ForceBru
1
你可以通过将循环行为提取到 template<Fnc> apply(Fnc fnc) 中,并像apply([&](){acc.foo();})apply([&](){acc.bar();}) 这样使用它,而无需重复编写代码来使用 B 选项。 - Quimby
2
选项D)维护两个独立的容器。一个包含所有“specialCase”对象,另一个包含其余对象。然后只需在正确的容器上循环即可。 - Jesper Juhl
2
@dyukha:即使预测完美,也无法消除检查分支条件的指令的前端吞吐量成本,如果编译器不托管if并生成循环的两个版本。如果编译器知道只有一个“if”或“else”主体在每次迭代中运行,则可能存在显着的简化/优化,但是在运行时进行检查和分支会错过这些优化,即使它完美地预测。 - Peter Cordes
显示剩余7条评论
3个回答

12
如果这个函数能够内联到一个传递编译时常量 bool 的调用者中,那么选项 A 就没问题了(只要函数足够小)。也就是说,如果有模板参数,你通常实际上不需要它。除非强制你编写 if(var) { foo<true>(arg); }else {foo<false>(arg); } 来鼓励编译器生成具有 2 个循环版本的汇编代码。

所有现代编译器都足够聪明,可以内联小型函数,然后完全优化掉一个 if(constant)。内联和常量传播是使现代 C++ 能够高效编译的关键。

但是,如果布尔值在编译时未知,选项 B 可能更有效率。(如果该函数不经常运行,则其速度可能在大局中并不重要,差异可能很小。)这是静态代码大小(I-cache 占用空间)与动态指令计数之间的权衡。或者,如果特殊情况很少运行,则该循环版本可能会保持缓存不冷。

for (int i = 0; i < m; ++i) {
  ifInLoop(i % 10, acc);
}
如果您确实有这样的重复模式,编译器可能会为您展开此循环,使布尔值成为编译时常量。或者,如果它不决定自己发明新的内部循环,并且包含另一个整个循环的循环的10次展开对于编译器的启发式算法来说太多了,那么您可以手动指导编译器生成更好的汇编代码。
int i;
for (i = 0; i < m-9; i+=10) {   // potentially runs zero times if signed m <= 9
    ifInLoop(false, acc);    // this is the j=0
    for (int j=1; j<10 ; j++)   // j = i%10
       ifInLoop(true, acc);     // original i = i+j  in case you need it
}
// cleanup loop:
for ( ; i < m ; i++) {
    ifInLoop(i % 10, acc);
}

如果编译器不将if提升并生成两个循环版本,即使预测完美也无法消除检查分支条件的指令的前端+后端吞吐量成本

如果编译器知道每次迭代只有ifelse中的一个体运行,可能会有显着的简化/优化,但是在运行时进行检查和分支,尽管预测完美,也会错过这些优化。


通常情况下,“profile it”的Stack Overflow响应并不像大多数人想象的那样有用。首先,微基准测试很难。很容易完全测量错误的东西,或者因为您对可能重要和不重要的内容了解不足而得出荒谬的结论(确保将CPU预热到最大涡轮频率,并初始化内存,以便不需要写时复制引导到零页,并且第一次计时的通过不付出页面故障+ TLB-miss成本。启用优化进行编译,并检查性能是否与重复次数线性缩放)。

针对一个测试用例进行剖析不能告诉您成本的总体。您错过的优化以及编译器是否愿意为您拆分循环并提升分支取决于循环的细节(可能包括循环主体的复杂程度)。

查看特定情况下使用的编译器的汇编是唯一确定成本的方法。

不同的编译器(或同一编译器的不同版本,或使用不同调优选项的编译器,例如gcc的-mtune = genericgcc -mtune = skylake )肯定会对选择一个在两个循环之间反转/拆分的编译器产生影响。调整选项为这样的决策和循环展开设置启发式常量,其中静态代码大小和动态指令计数之间存在权衡。

其中一部分可能取决于在if()外执行多少工作,并且在拆分时必须重复执行未更改的工作。



“Idiomatic way of performance evaluation?”(https://dev59.com/8lIH5IYBdhLWcg3wR7pm)更多关于如何进行微基准测试的内容。 - Peter Cordes

2

对于这种情况,选项C是最佳选择。如果您可以使用template<bool specialCase>,那么specialCase必须在编译时已知,因此您可以使用if constexpr,如下所示:

最初的回答

if constexpr(specialCase)
{
    acc.foo()
}
else
{
    acc.bar()
}

相反,如果特殊情况在编译时未知,我会选择选项B,因为条件只会被评估一次。

原始答案:Original Answer


内联+常量传播使得选项A在调用者将常量作为布尔参数传递时,在大多数情况下等效于模板。但是,如果您没有编译时常量参数,则选项B可能是最佳选择。 - Peter Cordes

2
一个优化器很可能会对真实的代码和这个虚假代码进行不同的处理,无论foo()bar()做什么,在任何情况下都可能占主导地位。
正如你所说,“从理论角度来看”,问题在于specialCase是循环不变量,因此避免在该值上进行条件评估和分支将带来好处。然而,在实践中,编译器可能会发现它是循环不变量,并为您消除这个问题,因此每个解决方案之间的差异可能不在于循环不变量的评估。
确定最快的解决方案或是否存在足够显著的差异来证明更丑陋、更难以跟踪或维护的代码是否合理的唯一现实手段是对其进行分析;这项活动可能会占用您的生活时间,比任何解决方案节省的时间都要多——编译器优化器可能会产生更大的影响,而您的生产力可能会因不必担心这种微观优化而提高——这很可能是一种虚假的经济效益。
另一个要考虑的选择——给定一个成员函数的指针:void (MyClass::*foobar)() ;,则:
void ifInLoopD( bool specialCase, MyClass& acc )
{
    // FIXME: use a local, not class member, for the pointer-to-member-function
    acc.foobar = specialCase ? &MyClass::foo : &MyClass::bar ;

    for( auto i = 0; i < n; ++i )
    {
        for( auto j = 0; j < n; ++j )
        {
            (acc.*acc.foobar)() ;
        }
    }
}

查看C++调用成员函数指针,了解如何使用存储成员函数指针的本地变量。但请记住,此答案中的基准数据来自此版本,这可能会阻止一些编译器意识到函数指针在调用之间没有更改,因此可以进行内联。(直到编译器尝试内联指向的成员函数,它才会意识到函数不会更改类的指针成员。)

编辑注:版本D的基准数字可能不代表大多数循环体中的使用情况。

展示该成员函数指针具有类似于其他方法的性能的基准测试是基于一个瓶颈在递增static volatile int的延迟上的函数体。
在生成的asm中,这会创建一个包括存储转发延迟在内的循环承载依赖链。首先,这可以隐藏很多循环开销。在像x86这样的现代乱序执行CPU上,成本不仅仅是累加的。事情可以重叠:许多循环开销可以在那个延迟瓶颈的阴影下运行。
更糟糕的是,存储转发延迟不是恒定的,并且在存储和重新加载之间有更多开销,特别是不相关的存储时,它可以变得更快。请参阅带有函数调用的循环比空循环快在没有优化编译的情况下添加冗余赋值会加速代码(其中调试构建将其循环计数器保留在内存中以创建此瓶颈)。即使在经过优化的构建中,使用volatile也会强制生成这样的asm。 在Intel Sandybridge系列中,使用volatile递增可以随着更多的循环开销而变得更快。因此,如果您尝试推广到其他更典型的情况,则此循环体的选择会创建极具误导性的基准数据。正如我(Peter)在我的答案中所说,微基准测试很难。有关详细信息,请参见评论中的讨论。 此问题中的基准数字是针对此代码的,但您应该期望其他循环体在质量上有所不同。

请注意,此答案小心地从任何角度得出可能在实际代码中更快的结论。

但我要补充的是,在内部循环中调用非内联函数几乎总是比内部循环中易于预测的分支更昂贵。非内联函数调用强制编译器更新所有仅在寄存器中临时存在的内存中的值,因此内存的状态与C++抽象机器相匹配。至少对于全局变量和静态变量以及通过函数参数指向/可访问的任何内容(包括成员函数的this),它还会破坏所有被调用的寄存器。
因此,就性能而言,我期望在循环外初始化的成员函数指针与选项A(内部的if())类似,但几乎总是更差。如果它们都从常量传播中优化掉,则相等。
编辑者注:结束
对于每个实现A、B和我的实现D(我将其称为D,因为我无法想象您如何在实际实现中使用C),并给定:
class MyClass
{
    public:
        void foo(){ volatile static int a = 0 ; a++ ; }
        void bar(){ volatile static int a = 0 ; a++ ; }
    // FIXME: don't put a tmp var inside the class object!
    // but keep in mind the benchmark results below *are* done with this
        void (MyClass::*foobar)() ;

} acc ;

static const int n = 10000 ;

我得到了以下结果:

VC++ 2019 默认调试模式:(注意:不要计时调试模式,那几乎总是没有用的。)

Original Answer翻译成"最初的回答"

ifInLoopA( true, acc )  : 3.146 seconds
ifInLoopA( false, acc ) : 2.918 seconds
ifInLoopB( true, acc )  : 2.892 seconds
ifInLoopB( false, acc ) : 2.872 seconds
ifInLoopD( true, acc )  : 3.078 seconds
ifInLoopD( false, acc ) : 3.035 seconds

VC++ 2019 默认发布版本:

最初的回答
ifInLoopA( true, acc )  : 0.247 seconds
ifInLoopA( false, acc ) : 0.242 seconds
ifInLoopB( true, acc )  : 0.234 seconds
ifInLoopB( false, acc ) : 0.242 seconds
ifInLoopD( true, acc )  : 0.219 seconds
ifInLoopD( false, acc ) : 0.205 seconds

最初的回答: 你可以看到,在调试解决方案中,D明显变慢了,而在优化构建中,它明显变快了。此外,选择specialCase值对性能影响很小——尽管我不完全确定原因。
我增加了n到30000以获得更好的分辨率: VC++ 2019 默认发布 n = 30000:
ifInLoopA( true, acc )  : 2.198 seconds
ifInLoopA( false, acc ) : 1.989 seconds
ifInLoopB( true, acc )  : 1.934 seconds
ifInLoopB( false, acc ) : 1.979 seconds
ifInLoopD( true, acc )  : 1.721 seconds
ifInLoopD( false, acc ) : 1.732 seconds

很明显,解决方案A对 specialCase 最为敏感,如果需要确定行为,则可能应避免使用该方案,但是在实际的 foo()bar() 实现中存在差异,这种差异可能会被淹没。

您的结果可能因使用的编译器、目标和编译器选项而异,并且这些差异可能不太显著,以至于您无法为所有编译器得出任何结论。

例如,在 https://www.onlinegdb.com/上使用g ++ 5.4.1编译时,未优化和优化代码之间的差异远不那么显着(可能是由于VC ++调试器中远大于功能的重大开销),并且对于优化代码,解决方案之间的差异要少得多。

编辑说明: MSVC调试模式包括函数调用中的间接寻址,以允许增量重新编译,这可以解释调试模式下额外开销的巨大量。这是不计时调试模式的另一个原因。)

volatile 增量限制了性能,使其与调试模式(将循环计数器保存在内存中)大致相同;两个单独的存储转发延迟链可以重叠。

https://www.onlinegdb.com/ C++14 默认选项,n = 30000

ifInLoopA( true, acc )  : 3.29026 seconds
ifInLoopA( false, acc ) : 3.08304 seconds
ifInLoopB( true, acc )  : 3.21342 seconds
ifInLoopB( false, acc ) : 3.26737 seconds
ifInLoopD( true, acc )  : 3.74404 seconds
ifInLoopD( false, acc ) : 3.72961 seconds

https://www.onlinegdb.com/ C++14默认 -O3优化,n=30000

最初的回答:

ifInLoopA( true, acc )  : 3.07913 seconds                                                                                                      
ifInLoopA( false, acc ) : 3.09762 seconds                                                                                                      
ifInLoopB( true, acc )  : 3.13735 seconds                                                                                                      
ifInLoopB( false, acc ) : 3.05647 seconds                                                                                                      
ifInLoopD( true, acc )  : 3.09078 seconds                                                                                                      
ifInLoopD( false, acc ) : 3.04051 seconds 

我认为你唯一能得出的结论就是,你必须测试每个解决方案,以确定它们在编译器、目标实现和你的真实代码(而不是虚构的循环体)中的表现如何。
如果所有的解决方案都满足你的性能要求,我建议你使用最易读/易于维护的解决方案,并且只有在性能成为问题时才考虑优化,这样你就能够准确地确定整个代码中哪部分会给你带来最大的影响,而又不需要付出太多的努力。
为了完整起见并让你自己进行评估,以下是我的测试代码:
class MyClass
{
    public:
        void foo(){ volatile static int a = 0 ; a++ ; }
        void bar(){ volatile static int a = 0 ; a++ ; }
        void (MyClass::*foobar)() ;

} acc ;

static const int n = 30000 ;

void ifInLoopA( bool specialCase, MyClass& acc ) {
    for( auto i = 0; i < n; ++i ) {
        for( auto j = 0; j < n; ++j ) {
            if( specialCase ) {
                acc.foo();
            }
            else {
                acc.bar();
            }
        }
    }
}

void ifInLoopB( bool specialCase, MyClass& acc ) {
    if( specialCase ) {
        for( auto i = 0; i < n; ++i ) {
            for( auto j = 0; j < n; ++j ) {
                acc.foo();
            }
        }
    }
    else {
        for( auto i = 0; i < n; ++i ) {
            for( auto j = 0; j < n; ++j ) {
                acc.bar();
            }
        }
    }
}

void ifInLoopD( bool specialCase, MyClass& acc )
{
    acc.foobar = specialCase ? &MyClass::foo : &MyClass::bar ;

    for( auto i = 0; i < n; ++i )
    {
        for( auto j = 0; j < n; ++j )
        {
            (acc.*acc.foobar)() ;
        }
    }
}


#include <ctime>
#include <iostream>

int main()
{
    std::clock_t start = std::clock() ;
    ifInLoopA( true, acc ) ;
    std::cout << "ifInLoopA( true, acc )  : " << static_cast<double>((clock() - start)) / CLOCKS_PER_SEC << " seconds\n" ;

    start = std::clock() ;
    ifInLoopA( false, acc ) ;
    std::cout << "ifInLoopA( false, acc ) : " << static_cast<double>((clock() - start)) / CLOCKS_PER_SEC << " seconds\n" ;

    start = std::clock() ;
    ifInLoopB( true, acc ) ;
    std::cout << "ifInLoopB( true, acc )  : " << static_cast<double>((clock() - start)) / CLOCKS_PER_SEC << " seconds\n" ;

    start = std::clock() ;
    ifInLoopB( false, acc ) ;
    std::cout << "ifInLoopB( false, acc ) : " << static_cast<double>((clock() - start)) / CLOCKS_PER_SEC << " seconds\n" ;

    start = std::clock() ;
    ifInLoopD( true, acc ) ;
    std::cout << "ifInLoopD( true, acc )  : " << static_cast<double>((clock() - start)) / CLOCKS_PER_SEC << " seconds\n" ;

    start = std::clock() ;
    ifInLoopD( false, acc ) ;
    std::cout << "ifInLoopD( false, acc ) : " << static_cast<double>((clock() - start)) / CLOCKS_PER_SEC << " seconds\n" ;
}

评论不适合进行长时间的讨论;此对话已被移至聊天室 - Bhargav Rao
好的,我添加了一个总结我在评论中所说的内容的部分。同时指出这个答案小心地不从这些结果中概括出结论;是的,在仔细阅读后,你小心地没有得出结论。但是这确实需要用粗体指出,因为人们喜欢看数字。(另外我在其他地方添加了一些零散的评论。也许我应该只改变关于Visual C++调试器的那一点;调试器不会增加开销,除非你单步执行,这只是代码生成和可能是MSVC在调试版本中用于增量链接的间接性问题。) - Peter Cordes
无论如何,我取消了我的踩。我不知道是否想要点赞;这个答案中的数字是一个警示故事/例子,说明微基准测试很难!缺乏得出结论使其并不是错误的,但价值相当低。总之,感谢您让我编辑我的笔记;有一些有趣的东西需要思考/解释。 - Peter Cordes

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接