4

我需要迭代大量(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();
      }
    }
  }
}

我知道这属于过早的 Optimization。但是,从理论的角度来看,我会对使用-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);
}
4

3 回答 3

10

如果此函数可以内联到传递 compile-time-constant 的调用者中bool,那么您可以使用选项 A(只要该函数足够小可以内联)。即,如果模板参数是可能的,您通常实际上并不需要它。除非 if 强制您编写if(var) { foo<true>(arg); }else {foo<false>(arg); }以鼓励编译器使用 2 个版本的循环生成 asm。

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


但是,如果在编译时不知道 bool 值,则选项 B 可能更有效。 (如果函数不经常运行,它的速度在大局中可能无关紧要,差异可能很小。)

这是静态代码大小(I-cache 占用空间)与动态指令数之间的权衡。或者,如果特殊情况很少运行,则该版本的循环可能会在缓存中保持冷态。


for (int i = 0; i < m; ++i) {
  ifInLoop(i % 10, acc);
}

如果您确实有这样的重复模式,编译器可能会决定为您展开此循环,以便 bool 成为编译时常量。

或者,如果编译器不决定自己发明新的内部循环,您可以手持编译器制作更好的 asm,并且将包含另一个完整循环的循环展开 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 并生成两个版本的循环,则完美预测并不能消除检查分支条件的指令的前端 + 后端吞吐量成本。

如果编译器知道每次迭代中只有一个or主体运行,则可能会有显着的简化/优化,但在运行时检查和分支会错过这些优化,即使它预测得很好。ifelse


“profile it”通常的 Stack Overflow 响应并不像大多数人想象的那么有用。首先,微基准测试很难。很容易完全衡量错误的东西,或者得出无意义的结论,因为你对什么可能重要,什么不重要了解不够。(确保将您的 CPU 预热到最大涡轮频率并首先初始化内存,这样您就不会将 CoW 映射到零页面,并且第一次定时传递不会支付页面错误 + TLB-miss 成本。编译优化启用,并检查性能是否与您的重复次数成线性关系。)

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

使用您关心的编译器查看针对您特定情况的 asm 是唯一确定的方法。

不同的编译器(或同一编译器的不同版本,或具有不同的调整选项,如 gcc -mtune=genericvs. gcc -mtune=skylake)肯定会影响编译器是否决定反转/拆分循环以在两个循环之间选择一次。调整选项为这样的决策设置启发式常量,并在静态代码大小和动态指令数之间进行权衡的地方展开循环。

部分原因可能取决于有多少工作在外部if()并且在拆分时必须保持不变。

于 2019-07-13T10:49:49.007 回答
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 的基准数字可能并不代表大多数循环体使用它。

显示这个指向成员函数的指针与其他方法具有相似性能的基准测试是基于一个函数体,该函数体在增加 a 的延迟上存在瓶颈static volatile int

在生成的 asm 中,这会创建一个循环携带的依赖链,其中包括存储转发延迟。首先,这可以隐藏很多循环开销。在像任何 x86 一样的现代乱序执行 CPU 上,成本不只是累加。事情可能会重叠:大量循环开销可能会在延迟瓶颈的阴影下运行。

更糟糕的是,存储转发延迟不是恒定的,当在存储和重新加载之间存在更多开销时,尤其是不相关的存储,它会变得更快。请参阅函数调用比空循环更快的循环添加冗余分配在没有优化的情况下编译时加速代码(其中调试构建将循环计数器保留在内存中以创建此瓶颈)。volatile即使在优化的构建中也使用这样的 force asm。

在英特尔 Sandybridge 系列上,volatile增量可以通过更多循环开销变得更快 因此,如果您尝试将其推广到其他更典型的情况,这种循环体的选择会产生极具误导性的基准数字。正如我(彼得)在我的回答中所说,微基准测试很难。有关更多详细信息,请参阅评论中的讨论。

此问题中的基准数字是针对此代码的,但您应该期望其他循环体在质量上有所不同。

请注意,此答案小心不要得出任何关于在实际代码中可能更快的结论

但我要补充一点,内循环内的非内联函数调用几乎总是比内循环内易于预测的分支更昂贵。非内联函数调用强制编译器更新内存中暂时仅在寄存器中的所有值,因此内存状态与 C++ 抽象机匹配。至少对于全局变量和静态变量,以及通过函数 args 指向/可访问的任何内容(包括this成员函数)。它还破坏了所有调用破坏的寄存器。

所以在性能方面,我希望在循环外部初始化的指向成员函数的指针类似于选项 A(if()内部),但几乎总是更糟。或者如果它们都优化远离恒定传播,则相等。

编者注结束


对于我将称为 D 的每个实现 A、B 和我的(我省略了 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 默认调试:(注意:不要计时调试模式,这几乎总是没用的。)

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 对 最敏感,如果需要确定性行为,则可以避免这种情况,但实际bar()` 实现specialCase中的差异可能会掩盖这种差异。foo() and

您的结果可能很大程度上取决于您使用的编译器、目标和编译器选项,并且差异可能不是那么显着,以至于您可以对所有编译器得出任何结论。

例如,在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" ;
}
于 2019-07-13T11:48:06.140 回答
2

对于这种情况,选项 C 是最好的。如果你可以使用template<bool specialCase>它意味着在编译时必须知道 specialCase,因此你可以使用if constexpr,如图所示

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

相反,如果在编译时不知道 specialCase,我会选择选项 B,因为条件只评估一次

于 2019-07-13T10:54:42.797 回答