c++ - 比较优化构建与 switch case 和多态性

Question

我需要对两种解决方案进行性能测试 - 一种使用多态来执行类型切换，另一种使用 switch case 来选择要执行的某些函数。我真的需要优化这段代码。我写了下面的测试用例(你可以简单地复制粘贴代码，用 g++ -std=c++14 -O3 编译它并用 echo 1 | ./a.out 运行它!)如果你读了它，代码真的很简单!

#include <iostream>
#include <chrono>
#include <functional>
#include <array>
#include <cassert>
#include <vector>
#include <memory>
using namespace std;

struct profiler
{
    std::string name;
    std::chrono::high_resolution_clock::time_point p;
    profiler(std::string const &n) :
        name(n), p(std::chrono::high_resolution_clock::now()) { }
    ~profiler()
    {
        using dura = std::chrono::duration<double>;
        auto d = std::chrono::high_resolution_clock::now() - p;
        std::cout << name << ": "
            << std::chrono::duration_cast<dura>(d).count()
            << std::endl;
    }
};
#define PROFILE_BLOCK(pbn) profiler _pfinstance(pbn)

class Base {
public:
    virtual int increment(int in) {
        return in + 2;
    }
};
class Derived : public Base {
public:
    int increment(int in) override {
        return ++in;
    }
};

int increment_one(int in) {
    return in + 2;
}
int increment_two(int in) {
    return ++in;
}
int increment_three(int in) {
    return in + 4;
}
int increment_four(int in) {
    return in + 2;
}

static constexpr unsigned long long NUMBER_LOOP{5000000000};
int main() {

    int which_function;
    cin >> which_function;

    {
        PROFILE_BLOCK("nothing");
    }

    {
        PROFILE_BLOCK("switch case");
        auto counter = 0;
        for (unsigned long long i  = 0; i < NUMBER_LOOP; ++i) {
            switch(which_function) {
            case 0:
                counter = increment_one(counter);
                break;
            case 1:
                counter = increment_two(counter);
                break;
            case 2:
                counter = increment_three(counter);
                break;
            case 3:
                counter = increment_four(counter);
                break;
            default:
                assert(false);
                break;
            }
        }
        cout << counter << endl;
    }

    {
        PROFILE_BLOCK("polymorphism");
        auto counter = 0;
        std::unique_ptr<Base> ptr_base{new Derived()};
        for (unsigned long long i = 0; i < NUMBER_LOOP; ++i) {
            counter = ptr_base->increment(counter);
        }
    }

    return 0;
}

使用 g++ -std=c++14 -O3 构建时得到的输出并使用 echo 1 | ./a.out 运行是

nothing: 1.167e-06
705032704
switch case: 4.089e-06
polymorphism: 9.299

我无法理解究竟是什么导致 switch-case 几乎和 nothing 一样快案件。这是因为内联吗？是不是因为编译器预先计算了每个输入场景的值并将它们放在查找表中？是什么导致 switch-case 这么快？

我该如何为这种情况编写更公平的性能测试？一般来说，我永远不明白代码是否很快是因为 C++ 代码和程序集之间的直接未优化转换，或者它的编译器是否预先计算了一个值并完全跳过编译并生成“无操作样式”代码。

备注 profiler struct 已直接从另一个 SO 答案中复制出来，并且与该问题无关，只是它测量时间这一事实

备注 正如@dau_sama 在下面的评论中指出的那样，在使用 gcc 而不是 clang 的 linux 机器上运行相同的测试导致 switch 情况需要更长的时间(在这种情况下为 3.34)，但仍然比多态情况少得多。

Answer 1

你的代码的问题是，当你做这样的基准测试时，为了获得有意义的结果，你不能简单地使用 for 循环和一个大数字。当您使用 -O3 优化进行编译时，编译器可以将计算提升到循环之外，执行循环展开等类似操作，并在编译时计算结果并将它们硬编码到二进制文件中。因为在“as-if”规则下，你无法区分。这使得像这样对一小段代码进行基准测试变得很困难，但优化器的工作也是使代码尽可能快。如果优化器可以看到您只是一遍又一遍地做同样的事情，它可能会将所有计算折叠在一起并击败基准机制。

要修复它，您基本上需要混淆基准循环和基准框架的某些部分，以便编译器害怕展开循环或以其他方式尝试分析被测代码的独立运行。

在我修改过的代码版本中，我使用了谷歌基准测试库中的两段代码。了解这里发生的事情的最好方法是观看 Chandler Carruth 在 2015 年 CppNow 上的精彩演讲。https://www.youtube.com/watch?v=nXaxk27zwlk

简而言之，添加的是两个内联汇编指令，“DoNotOptimize”和“ClobberMemory”。这些是汇编的空块，在编译后的代码中没有实际指令，但它们被标记为 asm volatile ，这会通知优化器它们具有不可知的副作用，并且不应尝试分析程序集本身。 "memory"指令意味着它们可能读取/写入所有内存地址。任何标记为“DoNotOptimize”的变量都被认为是该程序集“已知的”，因此当调用这些函数中的任何一个时，该变量会被优化器的推理有效地“扰乱”——即使这些是空集合在指令中，需要假设在调用这些函数后值可能会以一种不可知的方式发生变化，因此循环展开和其他类型的优化变得不健全。

这是我的代码和输出的修改版本:

#include <iostream>
#include <chrono>
#include <functional>
#include <array>
#include <cassert>
#include <vector>
#include <memory>
using namespace std;

// From google benchmarks framework
// See also Chandler Carruth's talk on microoptimizations and benchmarking
// https://www.youtube.com/watch?v=nXaxk27zwlk
namespace bench {

#if defined(__GNUC__)
#define BENCHMARK_ALWAYS_INLINE __attribute__((always_inline))
#else
#define BENCHMARK_ALWAYS_INLINE
#endif

template <class Tp>
inline BENCHMARK_ALWAYS_INLINE void
DoNotOptimize(Tp const & value) {
  asm volatile("" : : "g"(value) : "memory");
}

inline BENCHMARK_ALWAYS_INLINE void
ClobberMemory() {
  asm volatile("" : : : "memory");
}

} // end namespace bench

struct profiler
{
    std::string name;
    std::chrono::high_resolution_clock::time_point p;
    profiler(std::string const &n) :
        name(n), p(std::chrono::high_resolution_clock::now()) { }
    ~profiler()
    {
        using dura = std::chrono::duration<double>;
        auto d = std::chrono::high_resolution_clock::now() - p;
        std::cout << name << ": "
            << std::chrono::duration_cast<dura>(d).count()
            << std::endl;
    }
};
#define PROFILE_BLOCK(pbn) profiler _pfinstance(pbn)

class Base {
public:
    virtual int increment(int in) {
        return in + 2;
    }
};
class Derived : public Base {
public:
    int increment(int in) override {
        return ++in;
    }
};

int increment_one(int in) {
    return in + 2;
}
int increment_two(int in) {
    return ++in;
}
int increment_three(int in) {
    return in + 4;
}
int increment_four(int in) {
    return in + 2;
}

static constexpr unsigned long long NUMBER_LOOP{5000000000};
int main() {

    int which_function;
    cin >> which_function;

    {
        PROFILE_BLOCK("nothing");
    }

    {
        PROFILE_BLOCK("switch case");
        auto counter = 0;
        bench::DoNotOptimize(counter);
        for (unsigned long long i  = 0; i < NUMBER_LOOP; ++i) {
            bench::DoNotOptimize(i);
            switch(which_function) {
            case 0:
                counter = increment_one(counter);
                break;
            case 1:
                counter = increment_two(counter);
                break;
            case 2:
                counter = increment_three(counter);
                break;
            case 3:
                counter = increment_four(counter);
                break;
            default:
                assert(false);
                break;
            }
            bench::ClobberMemory();
        }
        cout << counter << endl;
    }

    {
        PROFILE_BLOCK("polymorphism");
        auto counter = 0;
        bench::DoNotOptimize(counter);
        std::unique_ptr<Base> ptr_base{new Derived()};
        for (unsigned long long i = 0; i < NUMBER_LOOP; ++i) {
            bench::DoNotOptimize(i);
            counter = ptr_base->increment(counter);
            bench::ClobberMemory();
        }
    }

    return 0;
}

这是我运行时得到的:

$ g++ -std=c++14 main.cpp
$ echo 1 |./a.out
nothing: 3.864e-06
705032704
switch case: 20.385
polymorphism: 91.0152
$ g++ -std=c++14 -O3 main.cpp
$ echo 1 |./a.out
nothing: 6.74e-07
705032704
switch case: 4.59485
polymorphism: 2.5395

实际上我对此感到非常惊讶，我认为 switch case 应该总是更快。所以也许混淆指令需要调整，或者我错了。

要尝试了解区别是什么，您可以查看生成的程序集。您可以使用 perf 来做到这一点像钱德勒那样，或者使用像godbolt这样的东西。

这是 godbolt gcc of your code 的链接.我没有阅读所有内容，但对我来说突出的一件事是在本节中:

        pushq   %r13
        pushq   %r12
        leaq    16(%rdi), %r12
        pushq   %rbp
        pushq   %rbx
        subq    $24, %rsp
        testq   %rsi, %rsi
        movq    %r12, (%rdi)
        je      .L5
        movq    %rdi, %rbx
        movq    %rsi, %rdi
        movq    %rsi, %r13
        call    strlen
        cmpq    $15, %rax
        movq    %rax, %rbp
        movq    %rax, 8(%rsp)
        ja      .L16
        cmpq    $1, %rax
        je      .L17
        testq   %rax, %rax
        jne     .L18
.L9:
        movq    8(%rsp), %rax
        movq    (%rbx), %rdx
        movq    %rax, 8(%rbx)
        movb    $0, (%rdx,%rax)
        addq    $24, %rsp
        popq    %rbx
        popq    %rbp
        popq    %r12
        popq    %r13
        ret
.L16:
        leaq    8(%rsp), %rsi
        xorl    %edx, %edx
        movq    %rbx, %rdi
        call    std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::_M_create(unsigned long&, unsigned long)
        movq    8(%rsp), %rdx
        movq    %rax, (%rbx)
        movq    %rax, %rdi
        movq    %rdx, 16(%rbx)
.L7:
        movq    %rbp, %rdx
        movq    %r13, %rsi
        call    memcpy
        jmp     .L9
.L17:
        movzbl  0(%r13), %eax
        movb    %al, 16(%rbx)
        jmp     .L9
.L5:
        movl    $.LC3, %edi
        call    std::__throw_logic_error(char const*)
.L18:

你有这些连续的跳转指令: ja .L16 , je .L17 , jne .L18 .所以我认为这是您的 switch声明大概。但是，当您查看这些语句跳回的位置时，它们都会跳回 .L9，而不会通过 switch 返回。陈述。所以我怀疑优化器正在做的是提升 switch在您的循环之外，这使它可以轻松地为每个可能的输入计算循环的输出结果，并使基准测试看起来在零时间内运行。

另一方面，当我查看为我的版本生成的程序集时，它仍然具有相同的 .L16 , .L17 , 和 .L18跳跃，他们都跳到 .L9 .所以......我不确定这到底是什么意思。但希望这能帮助你弄清楚。

编辑:

跟进@Holt 发表的评论，我调整了您的代码以制作 virtual案例匹配 switch case 更好，这样就有四个派生类和一个抽象基类。这给了我更像我预期的结果。我能给出的最好解释是，也许当只有一个派生类时，编译器能够执行“去虚拟化”之类的。 gcc 的现代版本将在 -O3 时进行链接时间优化例如通过。

结果:

$ g++ -std=c++14 -O3 main.cpp
$ echo 1|./a.out 
nothing: 4.92e-07
705032704
switch case: 4.56484
polymorphism: 9.16065
$ echo 2|./a.out 
nothing: 6.25e-07
-1474836480
switch case: 5.31955
polymorphism: 9.22714
$ echo 3|./a.out 
nothing: 5.42e-07
1410065408
switch case: 3.91608
polymorphism: 9.17771

调整后的代码:

#include <iostream>
#include <chrono>
#include <functional>
#include <array>
#include <cassert>
#include <vector>
#include <memory>
using namespace std;

// From google benchmarks framework
// See also Chandler Carruth's talk on microoptimizations and benchmarking
// https://www.youtube.com/watch?v=nXaxk27zwlk
namespace bench {

#if defined(__GNUC__)
#define BENCHMARK_ALWAYS_INLINE __attribute__((always_inline))
#else
#define BENCHMARK_ALWAYS_INLINE
#endif

template <class Tp>
inline BENCHMARK_ALWAYS_INLINE void
DoNotOptimize(Tp const & value) {
  asm volatile("" : : "g"(value) : "memory");
}

inline BENCHMARK_ALWAYS_INLINE void
ClobberMemory() {
  asm volatile("" : : : "memory");
}

} // end namespace bench

struct profiler
{
    std::string name;
    std::chrono::high_resolution_clock::time_point p;
    profiler(std::string const &n) :
        name(n), p(std::chrono::high_resolution_clock::now()) { }
    ~profiler()
    {
        using dura = std::chrono::duration<double>;
        auto d = std::chrono::high_resolution_clock::now() - p;
        std::cout << name << ": "
            << std::chrono::duration_cast<dura>(d).count()
            << std::endl;
    }
};
#define PROFILE_BLOCK(pbn) profiler _pfinstance(pbn)

int increment_one(int in) {
    return in + 2;
}
int increment_two(int in) {
    return ++in;
}
int increment_three(int in) {
    return in + 4;
}
int increment_four(int in) {
    return in + 2;
}

class Base {
public:
    virtual int increment(int in) = 0;
};

class Derived1 : public Base {
public:
    int increment(int in) override {
        return increment_one(in);
    }
};

class Derived2 : public Base {
public:
    int increment(int in) override {
        return increment_two(in);
    }
};

class Derived3 : public Base {
public:
    int increment(int in) override {
        return increment_three(in);
    }
};

class Derived4 : public Base {
public:
    int increment(int in) override {
        return increment_four(in);
    }
};


static constexpr unsigned long long NUMBER_LOOP{5000000000};
int main() {

    int which_function;
    cin >> which_function;

    {
        PROFILE_BLOCK("nothing");
    }

    {
        PROFILE_BLOCK("switch case");
        auto counter = 0;
        bench::DoNotOptimize(counter);
        bench::DoNotOptimize(which_function);
        for (unsigned long long i  = 0; i < NUMBER_LOOP; ++i) {
            bench::DoNotOptimize(i);
            switch(which_function) {
            case 0:
                counter = increment_one(counter);
                break;
            case 1:
                counter = increment_two(counter);
                break;
            case 2:
                counter = increment_three(counter);
                break;
            case 3:
                counter = increment_four(counter);
                break;
            default:
                assert(false);
                break;
            }
            bench::ClobberMemory();
        }
        cout << counter << endl;
    }

    {
        PROFILE_BLOCK("polymorphism");
        auto counter = 0;
        bench::DoNotOptimize(counter);
        std::unique_ptr<Base> ptr_base;
        switch(which_function) {
        case 0:
          ptr_base.reset(new Derived1());
          break;
        case 1:
          ptr_base.reset(new Derived2());
          break;
        case 2:
          ptr_base.reset(new Derived3());
          break;
        case 3:
          ptr_base.reset(new Derived4());
          break;
        default:
          assert(false);
          break;
        }
        bench::DoNotOptimize(*ptr_base);
        for (unsigned long long i = 0; i < NUMBER_LOOP; ++i) {
            bench::DoNotOptimize(i);
            counter = ptr_base->increment(counter);
            bench::ClobberMemory();
        }
    }

    return 0;
}