22

我正在评估将一个实时软件从 C/汇编语言重写为 C++/汇编语言（由于与代码的问题部分无关的原因在汇编中是绝对必要的）。

一个中断具有 3 kHz 的频率，对于每个中断，大约有 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 次迭代。上述 for 循环每次迭代编译为 5 个循环，产生每秒 3,000,000 个循环的总成本，即 1% 的 CPU 负载。汇编器优化可能会将其减少到四个指令，但是我担心我们可能会由于内存访问彼此接近等而导致一些额外的延迟。简而言之，我相信这五个周期是非常理想的。

现在到 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 次查找；这将占 CPU 负载浪费的 4% 以上。此外，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++：

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。所以再次发现自己拥有一个函数指针数组和一个数据指针数组。

自然，限制是在组装中可以做的事情，现在已经探索过了。考虑到这一点，我现在明白，尽管引入基类是很自然的，但它并不是真正符合要求的。所以我想答案是，如果一个人想要一个函数指针数组，应该让自己成为一个函数指针数组......

4

6 回答 6

27

是什么让您认为 vtable 查找开销是 20 个周期？如果这是真的，你需要一个更好的 C++ 编译器。

我在 Intel 机器上试过这个，对你正在使用的处理器一无所知，正如预期的那样，C 调度代码和 C++ vtable 调度之间的区别是一条指令，这与 vtable 涉及额外的事实有关间接。

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++ 编译器生成以下代码。我根据我对正在发生的事情的理解插入了评论（这可能是错误的）。请注意，（IMO）循环开始的位置比 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);

笔记：

  1. 在 C++ 版本中，编译器似乎决定分两步进行后增量，大概是因为它希望将结果保存在i寄存器中而不是r4. 这无疑与下面的问题有关。

  2. 编译器决定使用对象的 vtable 计算对象的真实类的基地址。这占用了3条指令，想必也需要i4在步骤1中作为临时使用。vtable查找本身占用1条指令。

所以：问题不在于 vtable 查找，它可以在一条额外的指令中完成（但实际上需要两条指令）。问题是编译器觉得需要“找到”对象。但是为什么 gcc/i86 不需要这样做呢？

答案是：它曾经，但现在不再。在许多情况下（例如，在没有多重继承的情况下），将派生类的指针转换为基类的指针不需要修改指针。因此，当我们调用派生类的方法时，我们可以只给它基类指针作为它的this参数。但在其他情况下，这是行不通的，我们必须在进行强制转换时调整指针，然后在调用时将其调整回来。

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

据我了解，VisualDSP++ 是基于 gcc 的，它可能有-fvtable-thunksand-fno-vtable-thunks选项。所以你也许可以用-fvtable-thunks. 但是如果你这样做，你需要编译你使用该选项的所有 C++ 库，因为你不能混合这两种调用样式。此外，（15 年前）gcc 的 vtable-thunks 实现中存在各种错误，因此如果 VisualDSP++ 使用的 gcc 版本足够旧，您也可能会遇到这些问题（IIRC，它们都涉及多重继承，所以它们可能不适用于您的用例。）

（原始测试，更新前）：

我尝试了以下简单的案例（没有多重继承，这会减慢速度）：

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;
}

并使用 -O3 使用 gcc (4.8) 编译它。正如我所料，它生成的汇编代码与您的 C 派发所生成的汇编代码完全相同。这是函数for情况下的循环unary，例如：

.L9:
        movq    (%rbx), %rax
        movq    %rbx, %rdi
        addq    $16, %rbx
        movl    %r13d, %esi
        call    *8(%rax)
        addl    %eax, %ebp
        cmpq    %rbx, %r12
        jne     .L9
于 2013-08-23T15:38:46.033 回答
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 查找，同时为编译器优化提供更多机会，因为可以内联执行内部的代码。

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

于 2013-08-23T15:21:02.137 回答
6

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

您最终可能会为了速度而牺牲多态性。
有必要继承吗？
仅仅因为您切换到 C++ 并不意味着您必须切换到面向对象。

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

另外，您可以将任何功能移出 ISR 吗？功能的任何部分都可以由“后台循环”而不是 ISR 执行吗？这将减少您在 ISR 中的时间。

于 2013-08-23T15:34:28.110 回答
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;
}

在这种情况下，您可以将新函数创建为类型更安全的函数对象。带有虚函数的“正常” OOP 方法在这里没有帮助。

如果是 C++11 环境，您可以在编译时借助可变参数模板创建数组（但语法复杂）。

于 2013-08-23T15:33:11.190 回答
1

这与您的问题无关，但如果您对性能非常感兴趣，您可以使用模板为 todolist 进行循环展开：

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();
于 2013-08-27T07:46:58.183 回答
-1

找出编译器将 vtable 放在哪里并直接访问它以获取函数指针并存储它们以供使用。这样，您将拥有与在 C 中使用函数指针数组的方法几乎相同的方法。

于 2013-08-23T15:10:26.250 回答