C++中vtable查找的性能影响

Question

C++中vtable查找的性能影响

23

我正在评估将一款实时软件从C/汇编语言重写为C++/汇编语言（原因与问题无关的部分必须以汇编语言完成）。

每秒有3,000次中断，对于每个中断，需要按照顺序执行大约200个不同的操作。处理器运行速度为300 MHz，给我们100,000个周期来完成这项工作。通过一个函数指针数组，在C语言中已经解决了这个问题：

// Each function does a different thing, all take one parameter being a pointer
// to a struct, each struct also being different.
void (*todolist[200])(void *parameters);

// Array of pointers to structs containing each function's parameters.
void *paramlist[200];

void realtime(void)
{
  int i;
  for (i = 0; i < 200; i++)
    (*todolist[i])(paramlist[i]);
}

速度很重要。上面的200次迭代每秒执行3,000次，因此实际上我们每秒执行600,000次迭代。上述循环每迭代5个周期，总共耗费3,000,000个周期，即1%的CPU负载。汇编优化可能将其降到4条指令，但我担心由于接近彼此的内存访问等原因会导致额外的延迟。简而言之，我认为这些五个周期是非常优化的。

现在转到C++重写。我们所做的这200件事情有某种联系。它们所有需要和使用的参数都属于一个子集，并在各自的结构体中使用。在C ++实现中，它们可以被整洁地视为继承自一个公共基类：

class Base
{
  virtual void Execute();
  int something_all_things_need;
}
class Derived1 : Base
{
  void Execute() { /* Do something */ }
  int own_parameter;
  // Other own parameters
}
class Derived2 : Base { /* Etc. */ }

Base *todolist[200];

void realtime(void)
{
  for (int i = 0; i < 200; i++)
    todolist[i]->Execute(); // vtable look-up! 20+ cycles.
}

我的问题是vtable查找。我无法每秒执行600,000个查找；这将占用超过4％的CPU负载浪费。此外，todolist在运行时从不更改，它只在启动时设置一次，因此查找要调用的函数的工作确实是浪费的。在问自己“最优结果可能是什么”的问题时，我查看了C解决方案给出的汇编代码，并重新发现了一个函数指针数组...

在C ++中，如何正确地处理这个问题？制作一个好的基类、派生类等等，在最后为了性能原因再次挑选函数指针感觉相当无意义。

更新（包括循环开始位置的更正）：

处理器是ADSP-214xx，编译器是VisualDSP++ 5.0。启用#pragma optimize_for_speed时，C循环为9个周期。在我的想法中进行汇编优化可得4个周期，但我没有测试，因此不能保证。C++循环为14个周期。我知道编译器可以做得更好，但我不想把它归咎于编译器问题——在嵌入式环境中，没有多态仍然是首选，并且设计选择仍然让我感兴趣。供参考，以下是结果的汇编代码：

C:

i3=0xb27ba;
i5=0xb28e6;
r15=0xc8;

以下是实际的循环：

r4=dm(i5,m6);
i12=dm(i3,m6);
r2=i6;
i6=i7;
jump (m13,i12) (db);
dm(i7,m7)=r2;
dm(i7,m7)=0x1279de;
r15=r15-1;
if ne jump (pc, 0xfffffff2);

C++ :

(Note: This is already in Chinese. If you want me to translate it into another language, please let me know.)

i5=0xb279a;
r15=0xc8;

这是实际的循环：

i5=modify(i5,m6);
i4=dm(m7,i5);
r2=i4;
i4=dm(m6,i4);
r1=dm(0x3,i4);
r4=r2+r1;
i12=dm(0x5,i4);
r2=i6;
i6=i7;
jump (m13,i12) (db);
dm(i7,m7)=r2;
dm(i7,m7)=0x1279e2;
r15=r15-1;
if ne jump (pc, 0xffffffe7);

同时，我认为我已经找到了一种答案。最少的周期数是通过尽可能做最少的工作来实现的。我需要获取一个数据指针，获取一个函数指针，并将带有数据指针的参数调用该函数。获取指针时，索引寄存器会自动修改一个常量，而这个常量可以设置为1。因此，我们再次得到一个函数指针数组和一个数据指针数组。

当然，在汇编中能够做到的是极限，这已经得到了探索。有了这个想法，我现在明白了，即使引入一个基类很自然，但它并不是真正适合要求的东西。所以，我想答案是，如果你想要一个函数指针数组，你应该自己创建一个函数指针数组...

- user2711077

2

我把它作为注释，但你不觉得你的“中断处理程序”负载过重吗？你能不能实现一些类似的东西：中断处理程序 + N个工作线程与调度器，这样一旦中断到达，你只需“记录”来自中断的重要参数（如时间戳、一些硬件数据等），然后通知调度器数据已到达，这样你的线程就可以并行处理它们，或者根据某种顺序进行处理，你可以像实现状态机或其他方式一样。 - evilruff

想法是中断代码应该尽可能“轻量化”，以便准备好接收新数据，而实际处理则发生在其他地方。 - evilruff

2

如果你担心延迟，避免使用VTABLES，在C++中使用一个带有T函数对象的模板，就可以避免额外的查找。 - pyCthon

@evilruff 就 CPU 而言，所有减轻处理器负载的功能都已被使用。CPU 支持指令级并行性和数据级并行性。有效利用这些功能的工作是汇编代码能够完成的。一些过滤器已经进行了硬件加速，尽可能地做到了这一点。CPU 的负载在 90% 以上时几乎已经达到了极限，无法更多地利用。即使使用更强大的 CPU，上述问题仍然存在。 - user2711077

有一种叫做抽象惩罚的东西。如果你承受不起，就使用更低级别的结构或者更低级别的语言。 - n. m.

显示剩余8条评论

6个回答

9

如前所述，您可以使用模板来摆脱动态调度。以下是一个执行此操作的示例：

template <typename FirstCb, typename ... RestCb>
struct InterruptHandler {
    void execute() {
        // I construct temporary objects here since I could not figure out how you
        // construct your objects. You can change these signatures to allow for 
        // passing arbitrary params to these handlers.
        FirstCb().execute();
        InterruptHandler<RestCb...>().execute();
    }
}

InterruptHandler</* Base, Derived1, and so on */> handler;

void realtime(void) {
    handler.execute();
}

通过这种方式，完全消除了vtable查找的同时提供了更多的编译器优化机会，因为execute内部的代码可以被内联。

但需要注意的是，您需要根据如何初始化处理程序来更改某些部分。基本框架应保持不变。此外，这需要您拥有符合C++11标准的编译器。

- Ajit Singh

6

我建议在您的派生类中使用静态方法，并将这些函数放入数组中。这将消除虚函数表搜索的开销。这与您的C语言实现最接近。

您可能会为了速度而牺牲多态性。
继承是否必要？
仅因为您转向C++并不意味着您必须转向面向对象编程。

此外，您尝试在ISR中展开循环了吗？
例如，在返回循环顶部之前执行2个或更多执行调用。

还可以将任何功能移出ISR吗？后台循环能否执行某些功能而不是ISR？这将减少ISR中的时间。

- Thomas Matthews

简单快速的解决方案真是太棒了。仅仅因为你有一个C++编译器，并不意味着你需要使用所有那些闪亮的花哨功能。 - johnwbyrd

2

你可以在模板内部隐藏 void* 类型擦除和类型恢复。结果应该是相同的函数指针数组。这将有助于转换并兼容你的代码：

#include <iostream>

template<class ParamType,class F>
void fun(void* param) {
  F f;
  f(*static_cast<ParamType*>(param));
}

struct my_function {
  void operator()(int& i) {
    std::cout << "got it " << i << std::endl;
  }
};


int main() {
  void (*func)(void*) = fun<int, my_function>;

  int j=4;
  func(&j);

  return 0;
}

在这种情况下，您可以创建新的函数对象，并具有更多类型安全性。使用虚函数的“常规”面向对象编程方法在这里没有帮助。

在C++11环境中，您可以通过可变模板在编译时创建数组（但语法比较复杂）。

- Jan Herrmann

1

这与您的问题无关，但如果您非常关注性能，可以使用模板来对待办事项列表进行循环展开：

void (*todo[3])(void *);
void *param[3];

void f1(void*) {std::cout<<"1" << std::endl;}
void f2(void*) {std::cout<<"2" << std::endl;}
void f3(void*) {std::cout<<"3" << std::endl;}

template<int N>
struct Obj {
    static void apply()
    {
        todo[N-1](param[N-1]);
        Obj<N-1>::apply();
    }
};

template<> struct Obj<0> { static void apply() {} };

todo[0] = f1;
todo[1] = f2;
todo[2] = f3;

Obj<sizeof todo / sizeof *todo>::apply();

- Serve Laurijssen

0

找出编译器放置虚函数表的位置，直接访问并获取其中的函数指针，存储以备使用。这样，您就可以使用类似于 C 中的函数指针数组来实现相同的方法。

- user1764961

11

亲爱的上帝，请不要让这样的事情发生在您美丽的地球上。谢谢。 - n. m.

6

只要你不出差错，就可以在这个竖杆上平衡汽车。 - Mooing Duck

2

@user1764961：仅仅因为你的可执行文件没有改变并不意味着代码路径是相同的。库和DLL经常会被更新。此外，如果编译器发生了变化，或者你更改了编译器选项，或者在不同的时间编译，虚函数表可能会不同，从而导致你所有的努力崩溃。 - Mooing Duck

3

你不会每天更换15次编译器。
即使你这样做了，你也可以看到位置是否已更改。
如果只是升级当前的编译器，那么 vtbl 很可能仍然在同一个位置。例如，微软几十年来都没有改变 vtbl 的位置。如果你正在编写编译器，你会像你建议的那样在每个构建中实现 vtbl 移动吗？我不这么认为。因此，让我们从所有的理论可能性转向实践。

- user1764961

1

不要忘记这是嵌入式世界。这里的代码变化很少，而c/c++编译器更像是高级汇编器。这可能是你需要做出的权衡，以解决一个糟糕的优化c++编译器。我不是说这是正确的方法，但它绝对是一种选择。 - Agoston Horvath

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

你怎么认为虚函数表查找的开销是20个CPU周期呢？如果真是这样，那你需要一个更好的C++编译器。

我在一台英特尔电脑上试过这个，不知道你在用什么处理器，和预期中的一样，C调度代码和C++虚函数表调度之间的差别只有一条指令，这和虚函数表涉及到的额外间接有关。

C代码（基于OP）：

void (*todolist[200])(void *parameters);                                  
void *paramlist[200];
void realtime(void)
{       
  int i;
  for (i = 0; i < 200; i++)                                               
    (*todolist[i])(paramlist[i]);                                         
}

C++代码：

class Base {
  public:
    Base(void* unsafe_pointer) : unsafe_pointer_(unsafe_pointer) {}
    virtual void operator()() = 0;
  protected:
    void* unsafe_pointer_;
};

Base* todolist[200];
void realtime() {
  for (int i = 0; i < 200; ++i)
    (*todolist[i])();
}

两者都是使用gcc 4.8编译的，-O3优化：

realtime:                             |_Z8realtimev:
.LFB0:                                |.LFB3:
        .cfi_startproc                |        .cfi_startproc
        pushq   %rbx                  |        pushq   %rbx
        .cfi_def_cfa_offset 16        |        .cfi_def_cfa_offset 16
        .cfi_offset 3, -16            |        .cfi_offset 3, -16
        xorl    %ebx, %ebx            |        movl    $todolist, %ebx
        .p2align 4,,10                |        .p2align 4,,10
        .p2align 3                    |        .p2align 3
.L3:                                  |.L3:
        movq    paramlist(%rbx), %rdi |        movq    (%rbx), %rdi
        call    *todolist(%rbx)       |        addq    $8, %rbx
        addq    $8, %rbx              |        movq    (%rdi), %rax
                                      |        call    *(%rax)
        cmpq    $1600, %rbx           |        cmpq    $todolist+1600, %rbx
        jne     .L3                   |        jne     .L3
        popq    %rbx                  |        popq    %rbx
        .cfi_def_cfa_offset 8         |        .cfi_def_cfa_offset 8
        ret                           |        ret

在C++代码中，第一个movq获取vtable的地址，然后call通过它进行索引。因此，这是一个指令开销。

根据 OP 的说法，DSP 的 C++ 编译器生成以下代码。我根据自己对正在发生的事情的理解插入了注释（可能是错误的）。请注意，（在我看来）循环比 OP 所指示的位置早一个位置开始；否则，对我来说就没有意义。

# Initialization.
# i3=todolist; i5=paramlist           | # i5=todolist holds paramlist
i3=0xb27ba;                           | # No paramlist in C++
i5=0xb28e6;                           | i5=0xb279a;
# r15=count
r15=0xc8;                             | r15=0xc8;

# Loop. We need to set up r4 (first parameter) and figure out the branch address.
# In C++ by convention, the first parameter is 'this'
# Note 1:
r4=dm(i5,m6); # r4 = *paramlist++;    | i5=modify(i5,m6); # i4 = *todolist++
                                      | i4=dm(m7,i5);     # ..
# Note 2:                            
                                      | r2=i4;            # r2 = obj
                                      | i4=dm(m6,i4);     # vtable = *(obj + 1)
                                      | r1=dm(0x3,i4);    # r1 = vtable[3]
                                      | r4=r2+r1;         # param = obj + r1

i12=dm(i3,m6); # i12 = *todolist++;   | i12=dm(0x5,i4);   # i12 = vtable[5]

# Boilerplate call. Set frame pointer, push return address and old frame pointer.
# The two (push) instructions after jump are actually executed before the jump.
r2=i6;                                | r2=i6;
i6=i7;                                | i6=i7;
jump (m13,i12) (db);                  | jump (m13,i12) (db);
dm(i7,m7)=r2;                         | dm(i7,m7)=r2;
dm(i7,m7)=0x1279de;                   | dm(i7,m7)=0x1279e2;

# if (count--) loop
r15=r15-1;                            | r15=r15-1;
if ne jump (pc, 0xfffffff2);          | if ne jump (pc, 0xffffffe7);

注：

在 C++ 版本中，编译器似乎决定分两步执行后缀递增操作，这可能是因为它希望将结果存储到i寄存器而不是r4寄存器。这无疑与下面的问题有关。
编译器已决定使用对象的vtable计算对象真实类别的基地址。这需要三个指令，并且很可能也需要将i4用作步骤1的临时变量。vtable查找本身占据一个指令。

所以：问题不在于vtable查找，该操作可以通过单个额外指令（但实际上需要两个）完成。问题在于编译器感觉需要“查找”对象。但是，为什么gcc/i86不需要这样做呢？

答案是：以前是需要的，但现在不需要了。在许多情况下（例如没有多重继承的情况下），将指向派生类的指针强制转换为指向基类的指针不需要修改指针。因此，当我们调用派生类的方法时，只需将基类指针作为其this参数传递即可。但在其他情况下，这种方法不起作用，我们必须在进行强制转换时调整指针，并在调用时将其重新调整回来。

执行第二次调整有（至少）两种方式。一种是由生成的DSP代码显示的方式，其中调整存储在vtable中——即使它为0——然后在调用期间应用该调整。另一种方法（称为vtable-thunks）是创建一个thunk——一小段可执行代码——来调整this指针，然后跳转到方法入口点，并将指向此thunk的指针放入vtable中。（所有这些都可以在编译时完成。）thunk解决方案的优点在于，在不需要进行调整的常见情况下，我们可以优化掉thunk，并且没有调整代码留下。（缺点是如果我们确实需要调整，则生成了额外的分支。）

据我所知，VisualDSP++ 基于 gcc，可能具有 -fvtable-thunks 和 -fno-vtable-thunks 选项。因此，您可能可以使用 -fvtable-thunks 进行编译。但是，如果您这样做，您需要使用该选项编译您使用的所有 C++ 库，因为不能混合两种调用样式。此外，gcc 的 vtable-thunks 实现曾经存在各种错误（15年前），因此如果 VisualDSP++ 使用的 gcc 版本太旧，则也可能遇到这些问题（我回忆起来，所有这些问题都涉及多重继承，因此可能不适用于您的用例。）

（更新前的原始文本）：

我尝试了以下简单情况（没有多重继承，因为这可能会使事情变慢）：

class Base {
  public:
    Base(int val) : val_(val) {}
    virtual int binary(int a, int b) = 0;
    virtual int unary(int a) = 0;
    virtual int nullary() = 0;
  protected:
    int val_;
};

int binary(Base* begin, Base* end, int a, int b) {
  int accum = 0;
  for (; begin != end; ++begin) { accum += begin->binary(a, b); }
  return accum;
}

int unary(Base* begin, Base* end, int a) {
  int accum = 0;
  for (; begin != end; ++begin) { accum += begin->unary(a); }
  return accum;
}

int nullary(Base* begin, Base* end) {
  int accum = 0;
  for (; begin != end; ++begin) { accum += begin->nullary(); }
  return accum;
}

我使用gcc（4.8）并使用-O3编译它。正如我所预期的那样，它生成了与您的C调度程序完全相同的汇编代码。例如，这是unary函数中的for循环：

.L9:
        movq    (%rbx), %rax
        movq    %rbx, %rdi
        addq    $16, %rbx
        movl    %r13d, %esi
        call    *8(%rax)
        addl    %eax, %ebp
        cmpq    %rbx, %r12
        jne     .L9