C++运行时多态下缓解缓存缺失的设计模式探究

我把多种派生类对象存储在长数组或vector中，每个对象都会被传入一个流程，调用其多个成员函数。当vector中连续对象为不同派生类型时，很容易出现缓存缺失；且由于VTables与成员函数绑定，流程中每一次新的虚函数调用都可能引发缓存缺失。

简化示例代码如下：

#include <iostream>
#include <vector>

// Base Class
class Animal
{
  public:
    virtual void eat() = 0;
    virtual void sleep() = 0;
    virtual void roll_in_mud() = 0;    
};

// Derived class 1 
class Pig : public Animal
{
  public:  
    Pig(){}
    void eat() {std::cout << "The pig is eating" << std::endl;}
    void sleep() {std::cout << "The pig is sleeping" << std::endl;}
    void roll_in_mud() {std::cout << "The pig is rolling in the mud" << std::endl;}
};

// Derived class 2 
class Cow : public Animal
{
  public:  
    Cow(){}
    void eat() {std::cout << "The cow is eating" << std::endl;}
    void sleep() {std::cout << "The cow is sleeping" << std::endl;}
    void roll_in_mud() {std::cout << "The cow is rolling in the mud" << std::endl;}
};

// Process that operates on an Animal instance
void barnyard_activities(Animal& animal)
{
    animal.eat();
    animal.sleep();
    animal.roll_in_mud();
}

int main()
{
    // In reality this vector or array could hold millions of items
    std::vector<Animal*> animals;
    animals.push_back(new Pig);
    animals.push_back(new Cow);

    for (Animal* animal : animals) barnyard_activities(*animal);
    
    return 0;
}

基类仅包含虚方法，理论上流程barnyard_activities在首次虚函数调用后即可知晓当前处理的派生类类型。是否存在设计模式，能让流程直接调用派生类方法，或在首次虚函数调用后消除缓存缺失的可能？若我对VTables的理解有误，或已有类似讨论未被我发现，在此致歉。

1. 按类型分组处理 #

将同类型的派生类对象集中存储、统一处理，而非混合放入单一容器。比如分别维护std::vector<Pig*>和std::vector<Cow*>，依次遍历执行流程逻辑。这样同类型对象的VTables会被连续访问，缓存命中率大幅提升，同时避免频繁切换不同类型的成员函数，减少缓存缺失。

修改后的示例：

int main()
{
    std::vector<Pig*> pigs;
    std::vector<Cow*> cows;
    pigs.push_back(new Pig);
    cows.push_back(new Cow);

    auto process_group = [](auto& group) {
        for (auto animal : group) {
            animal->eat();
            animal->sleep();
            animal->roll_in_mud();
        }
    };

    process_group(pigs);
    process_group(cows);
    
    return 0;
}

2. 合并多步操作为单一虚函数 #

既然barnyard_activities固定调用三个虚函数，可将这三个操作合并为一个单一的虚方法（比如do_barnyard_activities()），这样每个对象仅需一次虚函数调用，后续直接执行派生类的具体实现，避免多次VTables查找和缓存缺失。

修改基类与派生类：

class Animal
{
  public:
    virtual void do_barnyard_activities() = 0;
};

class Pig : public Animal
{
  public:  
    Pig(){}
    void do_barnyard_activities() {
        std::cout << "The pig is eating" << std::endl;
        std::cout << "The pig is sleeping" << std::endl;
        std::cout << "The pig is rolling in the mud" << std::endl;
    }
};

class Cow : public Animal
{
  public:  
    Cow(){}
    void do_barnyard_activities() {
        std::cout << "The cow is eating" << std::endl;
        std::cout << "The cow is sleeping" << std::endl;
        std::cout << "The cow is rolling in the mud" << std::endl;
    }
};

// 简化流程函数
void barnyard_activities(Animal& animal)
{
    animal.do_barnyard_activities();
}

这种方式将三次虚调用压缩为一次，不仅减少VTables访问次数，还让编译器更容易对派生类内的连续操作做优化。

3. 静态多态（CRTP） #

通过**奇异递归模板模式（CRTP）**实现静态多态，完全绕开运行时虚函数的开销和VTables缓存问题。这种方式在编译期就确定要调用的函数，无需动态分发。

示例实现：

template<typename Derived>
class Animal
{
  public:
    void eat() { static_cast<Derived*>(this)->eat_impl(); }
    void sleep() { static_cast<Derived*>(this)->sleep_impl(); }
    void roll_in_mud() { static_cast<Derived*>(this)->roll_in_mud_impl(); }
    void do_barnyard_activities() {
        eat();
        sleep();
        roll_in_mud();
    }
};

class Pig : public Animal<Pig>
{
  public:  
    void eat_impl() { std::cout << "The pig is eating" << std::endl; }
    void sleep_impl() { std::cout << "The pig is sleeping" << std::endl; }
    void roll_in_mud_impl() { std::cout << "The pig is rolling in the mud" << std::endl; }
};

class Cow : public Animal<Cow>
{
  public:  
    void eat_impl() { std::cout << "The cow is eating" << std::endl; }
    void sleep_impl() { std::cout << "The cow is sleeping" << std::endl; }
    void roll_in_mud_impl() { std::cout << "The cow is rolling in the mud" << std::endl; }
};

// 用模板函数处理不同类型
template<typename AnimalType>
void process_animals(std::vector<AnimalType*>& animals) {
    for (auto animal : animals) {
        animal->do_barnyard_activities();
    }
}

int main()
{
    std::vector<Pig*> pigs;
    std::vector<Cow*> cows;
    pigs.push_back(new Pig);
    cows.push_back(new Cow);

    process_animals(pigs);
    process_animals(cows);
    
    return 0;
}

不过这种方式需要提前知晓所有派生类型，且无法像动态多态那样用统一基类指针容器存储不同类型对象，适合类型固定且对性能要求极高的场景。

4. 手动实现类型擦除（替代VTables） #

若必须用统一容器存储不同类型，可手动实现类型擦除，将整个流程逻辑打包为一个函数对象，仅存储一次函数指针，而非依赖编译器生成的VTables。比如用std::function封装barnyard_activities逻辑：

#include <functional>

int main()
{
    std::vector<std::function<void()>> animal_actions;
    
    Pig* pig = new Pig;
    animal_actions.push_back([pig]() {
        pig->eat();
        pig->sleep();
        pig->roll_in_mud();
    });
    
    Cow* cow = new Cow;
    animal_actions.push_back([cow]() {
        cow->eat();
        cow->sleep();
        cow->roll_in_mud();
    });

    for (auto& action : animal_actions) {
        action();
    }
    
    return 0;
}

这种方式每个对象仅需一次函数调用，内部成员函数均为直接调用（非虚），避免了多次VTables查找，缓存友好性大幅提升。缺点是需要手动封装逻辑，灵活性稍差。

内容的提问来源于stack exchange，提问作者StillUsesFORTRAN