编程语言理念:避免vtable查找

Question

我一直在想一个编程语言的想法:它本质上是C++和类似Java的语法,用于系统编程(或者实际上任何需要高性能的编程),但在我看来,比C++更令人愉快的语法.我在考虑如何处理分层类结构中的虚方法(我的语言不包括多重继承),以及避免vtable查找的方法.我的问题是双重的:

1. 根据我的理解,vtable查找是如此受性能影响的原因(至少在游戏开发等时间关键场景中)是因为它需要引用对象vtable指针,而这个vtable通常是缓存未命中.这是正确的,还是我错过了部分问题？
2. 我对部分解决方案的想法是:如果编译器可以完全确定对象的类型(即,它不能是从它认为的类型派生的类型),并且该对象作为参数传递给函数,其类型是对象类型的超类,然后函数中调用的虚方法的位置可以作为一种"隐藏"参数传递,该参数在编译时添加.也许一个例子会有所帮助:

考虑以下类层次结构的伪代码:

class Animal {
    public void talk() { /* Generic animal noise... */ }
    // ...
}

class Dog extends Animal {
    public void talk() { /* Override of Animal::talk(). */ }
    // ...
}

void main() {
    Dog d = new Dog();
    doSomethingWithAnimal(d);
}

void doSomethingWithAnimal(Animal a) {
    // ...
    a.talk();
    // ....
}

请记住,这是伪代码,而不是C++或Java或类似代码.另外,假设Animal参数通过引用隐式传递,而不是值.因为编译器可以看到它d绝对是类型Dog,它可以将doSomethingWithAnimal定义转换为如下所示:

void doSomethingWithAnimal(Animal a, methodptr talk = NULL) {
    // ...
    if ( talk != NULL ) {
        talk(a);
    } else {
        a.talk();
    }
    // ...
}

那么main看起来会被编译器翻译成这样的东西:

void main() {
    Dog d = new Dog();
    doSomethingWithAnimal(d, Dog::talk);
}

显然这不会完全消除对vtable的需求,并且当对象确切类型无法确定时,可能仍需要提供一个案例,但您对此有何看法作为性能优化？我计划尽可能使用寄存器传递参数,即使参数必须溢出到堆栈上,堆栈上的methodptr参数更可能是一个缓存命中而不是vtable值,对吧？任何和所有的想法都非常感激.

Answer 1

Re Q1:缓存利用率实际上只是虚拟调用"问题"的一部分.virtual功能的全部要点和一般的后期绑定是调用站点可以调用任何实现而不进行更改.这要求一些间接:

• 间接意味着解决间接的空间和/或时间开销.
• 无论你如何做间接,如果CPU有一个好的分支预测器并且调用站点是单态的(即,只调用一个实现),间接调用只能和静态调用一样快.我甚至不确定一个完美预测的分支是否像所有硬件开发人员所关心的静态分支一样快.
• 在编译时不知道被调用函数也会基于知道被调用函数(内联,但也包括循环不变代码运动以及可能更多)来禁止优化.

您的方法不会改变这种情况,因此会留下大部分性能问题:它仍会浪费一些时间和空间(仅限于额外的参数和分支,而不是vtable查找),它不允许内联或其他优化,并且它不会删除间接调用.

Re 2:这是一种对虚拟化的过程间旋转,C++编译器已经在某种程度上做了(在本地,有@ us2012在评论中描述的限制).它有一些"轻微"问题,但如果有选择地应用它可能是值得的.否则,您会生成更多代码,传递大量额外参数,执行大量额外分支,并且只获得很少甚至净损失.

我认为主要问题是它无法解决上述大多数性能问题.为子类生成专用函数(而不是一个通用主体)以及同一主题的其他变体可能有助于此.但这会产生额外的代码,必须通过性能提升来证明自己的合理性,并且普遍的共识是,即使在性能评估程序中,对于大多数代码而言,这种积极的优化也是不值得的.

特别是,虚拟呼叫开销只在同一个功能的基准测试中很重要,或者如果你已经优化了其他所有东西,并且需要大量微小的间接调用(游戏开发的一个例子:几个虚拟方法)每个几何对象的调用用于绘图或平截头体剔除).在大多数代码中,虚拟调用无关紧要,或者至少不足以保证进一步的优化尝试.此外,这仅适用于AOT编译器,因为JIT编译器还有其他方法可以解决这些问题.查找多态内联缓存,并注意跟踪JIT编译器可以简单地内联所有调用,无论是否为虚拟调用.

总结:vtables已经是实现虚函数的快速通用方法(如果可以使用它们,这就是这里的情况).你可能不太可能对它们有很大的改进,更不用说注意到改进了,除非在极少数情况下.如果你想尝试它,你可以尝试编写一个类似这样的LLVM传递(虽然你必须在较低的抽象级别上工作).