C++动态多态替代方案及异构集合实现性能问询

Hey there! Let's break down your questions step by step, using the C++ polymorphic shape example you provided.

1. Is this heterogeneous collection implementation reasonable when render() is called frequently? #

First off, this inheritance + virtual function-based implementation is totally reasonable for most regular scenarios. It aligns with OOP design principles, making the code readable and easy to extend—adding a new shape just requires inheriting from Shape and implementing draw(), no changes needed to the Container logic.

But if render() is called extremely frequently (like hundreds of thousands of times per frame in a game engine), you need to watch out for a couple of potential pain points:

• Poor cache hit rate: Heterogeneous objects are scattered in memory (since the vector stores pointers to heap-allocated objects of different types). CPU caches can't load batches of contiguous, same-type data, leading to frequent cache misses—this overhead is often bigger than the virtual function call itself.
• Branch prediction pressure: If the render_list alternates between shape types randomly, the CPU's branch predictor might fail, causing pipeline stalls.

2. Does using the vtable cause performance issues? #

Let's be clear: The overhead of a vtable call itself is tiny—it's just one indirect memory access (following the object's vptr to the vtable, then jumping to the draw() function). The real problems come from side effects:

• Cache invalidation: Each class has its own vtable, and if you have many different classes, vtables can be scattered in memory, leading to instruction cache (i-cache) misses.
• Branch prediction failures: If the object types in render() are random, the CPU can't predict which draw() will be called next, forcing the pipeline to flush and refill—this can create noticeable performance losses.

That said, modern CPUs have smart branch predictors. If the render_list has a consistent pattern (e.g., a block of triangles followed by a block of squares), the prediction hit rate will be high, and the virtual function overhead becomes negligible. Only in scenarios with random types and ultra-high call counts does this become a bottleneck.

3. What are the feasible alternatives? #

Here are several practical options, each suited to different use cases:

a. Use std::variant (C++17+) #

std::variant is a type-safe union that can store multiple object types, eliminating inheritance and virtual function overhead. You can rewrite render_list as vector<std::variant<Triangle, Square, Circle>>, then use std::visit to trigger the correct draw():

class Container {
public:
    void addShape(string type) {
        if (type == "triangle") render_list.emplace_back(Triangle{});
        else if (type == "square") render_list.emplace_back(Square{});
        else if (type == "circle") render_list.emplace_back(Circle{});
    }
    void render() {
        for (auto& shape : render_list) {
            std::visit([](auto& s) { s.draw(); }, shape);
        }
    }
private:
    vector<std::variant<Triangle, Square, Circle>> render_list;
};

Pros: No virtual function overhead, objects are stored contiguously in the vector for better cache hits, fully type-safe.
Cons: Adding a new shape requires updating the variant template parameters, which is less flexible than inheritance.

b. Data-Oriented Design (DOD) - Batch same-type objects #

If performance is your top priority, DOD is the way to go. Store objects of the same type in separate containers, then iterate through each container in render():

class Container {
public:
    void addShape(string type) {
        if (type == "triangle") triangles.emplace_back();
        else if (type == "square") squares.emplace_back();
        else if (type == "circle") circles.emplace_back();
    }
    void render() {
        for (auto& t : triangles) t.draw();
        for (auto& s : squares) s.draw();
        for (auto& c : circles) c.draw();
    }
private:
    vector<Triangle> triangles;
    vector<Square> squares;
    vector<Circle> circles;
};

Pros: Extreme cache efficiency—same-type objects are stored contiguously, so the CPU can load batches at once. No virtual function calls, zero branch prediction pressure, and draw() can be inlined by the compiler for extra speed.
Cons: Poor extensibility—adding a new shape requires adding a new container and update the render logic. It also breaks rendering order if you need to preserve the sequence of added shapes.

c. Manual Type Erasure (without virtual functions) #

You can implement type erasure manually using function pointers instead of vtables, wrapping objects in a helper class that stores destruction and draw() function pointers:

class ShapeErasure {
public:
    template<typename T>
    ShapeErasure(T obj) : 
        obj_(new T(std::move(obj))),
        draw_fn_([](void* obj) { static_cast<T*>(obj)->draw(); }),
        destroy_fn_([](void* obj) { delete static_cast<T*>(obj); }) {}
    
    ~ShapeErasure() { destroy_fn_(obj_); }
    void draw() { draw_fn_(obj_); }
private:
    void* obj_;
    void (*draw_fn_)(void*);
    void (*destroy_fn_)(void*);
};

class Container {
public:
    void addShape(string type) {
        if (type == "triangle") render_list.emplace_back(Triangle{});
        else if (type == "square") render_list.emplace_back(Square{});
        else if (type == "circle") render_list.emplace_back(Circle{});
    }
    void render() {
        for (auto& shape : render_list) shape.draw();
    }
private:
    vector<ShapeErasure> render_list;
};

Pros: Avoids compiler-generated vtable overhead, gives you manual control over function pointers, and is more flexible than inheritance (can erase any type with a draw() method, no base class required).
Cons: Requires manual memory management (easy to make mistakes), increases code complexity, and performance is similar to virtual functions—this is mainly a win for flexibility, not raw speed.

d. Template-Based Polymorphism (CRTP) #

Use the Curiously Recurring Template Pattern (CRTP) to implement static polymorphism, eliminating runtime virtual function overhead:

template<typename Derived>
class Shape {
public:
    void draw() { static_cast<Derived*>(this)->draw_impl(); }
};

class Triangle : public Shape<Triangle> {
public:
    void draw_impl() { /* Triangle drawing logic */ }
};

class Square : public Shape<Square> {
public:
    void draw_impl() { /* Square drawing logic */ }
};

Note: CRTP is static polymorphism, so you can't directly put objects into a heterogeneous vector. You'll need to pair it with type erasure or std::variant to build a heterogeneous collection. It's best used as a supplement to other schemes to eliminate virtual function overhead.

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