Skip to content

static-dynamic.md

Latest commit

 

History

History
205 lines (149 loc) · 9.72 KB

static-dynamic.md

File metadata and controls

205 lines (149 loc) · 9.72 KB
Raw

Static and Dynamic Inheritance in C++

1. Static Inheritance (CRTP — Curiously Recurring Template Pattern)

Static inheritance resolves polymorphic behavior entirely at compile time via C++ templates. The canonical mechanism is the Curiously Recurring Template Pattern (CRTP):

template <typename Derived>
class Base {
public:
    void interface() {
        // Downcast is resolved at compile time — zero runtime cost
        static_cast<Derived*>(this)->implementation();
    }

    // Default implementation (optionally overridable)
    void implementation() {
        std::cout << "Base::implementation\n";
    }
};

class Derived : public Base<Derived> {
public:
    void implementation() {
        std::cout << "Derived::implementation\n";
    }
};

How It Works Internally

The compiler, upon instantiating Base<Derived>, has full knowledge of the concrete type. The static_cast<Derived*>(this) is not a runtime operation — it is a reinterpret at the type-system level, with no emitted machine instruction beyond what the call itself requires. The method dispatch is a direct call, identical to a non-virtual member function call.

Because the full type hierarchy is visible to the optimizer at instantiation time, the compiler can:

  • Inline implementation() aggressively.
  • Perform constant folding and dead branch elimination across the inheritance boundary.
  • Apply loop unrolling when CRTP is used in tight numerical loops (e.g., expression templates in linear algebra libraries like Eigen).

Key Characteristics

Property Detail
Dispatch mechanism Direct call / inlined
Vtable None
Type resolution Compile time
Binary size Can increase due to template instantiation
Runtime overhead Zero
Open/closed principle Closed — hierarchy fixed at compile time

2. Dynamic Inheritance (Virtual Dispatch)

Dynamic inheritance relies on runtime polymorphism through the vtable (virtual function table) mechanism, which is part of the ABI but not mandated by the C++ standard (all major implementations use it).

class Base {
public:
    virtual void implementation() {
        std::cout << "Base::implementation\n";
    }
    virtual ~Base() = default; // Essential for correct destruction via base pointer
};

class Derived : public Base {
public:
    void implementation() override {
        std::cout << "Derived::implementation\n";
    }
};

The Vtable Mechanism in Detail

When a class declares or inherits a virtual function, the compiler:

  1. Emits a vtable (a static array of function pointers) per concrete class, stored in the .rodata or .data.rel.ro segment.
  2. Injects a hidden vptr (virtual pointer) into every object instance — typically at offset 0, consuming one pointer width (8 bytes on x86-64). This inflates every object's sizeof.
  3. At a virtual call site, the generated code performs:
; Pseudoassembly for obj->implementation()
mov  rax, [rdi]         ; load vptr from object (indirect memory read)
call [rax + offset]     ; dispatch through vtable slot (second indirect)

This is a two-level pointer indirection at runtime. It categorically prevents the compiler from inlining across the call boundary (unless the compiler can perform devirtualization — see §4).

Multiple and Virtual Inheritance

In multiple inheritance, each base subobject may have its own vptr, and this pointer adjustments (thunks) are emitted to correct the receiver address when calling through a non-primary base's vtable. Virtual inheritance (used to solve the diamond problem) adds an additional layer: a vbase offset stored either in the vtable or as a hidden member, making object layout and dispatch even more complex and expensive.

class A { virtual void f(); };
class B : virtual public A {};
class C : virtual public A {};
class D : public B, public C {}; // Diamond — A's subobject shared

Here, D carries multiple vptrs, and calls through B* or C* to A's interface involve thunk adjustments.

3. Comparative Analysis

Memory Layout

// CRTP object — no overhead
[ Derived data members ]

// Virtual object — vptr injected
[ vptr (8 bytes) | Base data members | Derived data members ]

Call Site Code Generation

// Static (CRTP) — after inlining, may reduce to zero instructions
template<typename D> void Base<D>::interface() {
    static_cast<D*>(this)->implementation(); // direct call or inlined
}

// Dynamic — always at minimum two loads + indirect call
void call(Base* b) {
    b->implementation(); // load vptr, index vtable, call
}

4. Execution Speed Evaluation

4.1 Direct Overhead

The raw virtual dispatch penalty on modern x86-64 hardware involves:

  • Two memory indirections: loading the vptr then indexing the vtable. If these addresses are cold in the L1/L2 cache, each miss costs ~4ns (L1), ~12ns (L2), or ~40ns (L3) — orders of magnitude more than a direct call.
  • Branch misprediction: The indirect call goes through the CPU's indirect branch predictor (IBP). If many derived types flow through the same call site (megamorphic dispatch), the IBP fails to predict the target, incurring a ~15–20 cycle pipeline flush on modern microarchitectures (e.g., Intel Golden Cove). This is a primary bottleneck in polymorphic hot loops.
  • Inlining barrier: Because the callee is unknown at compile time, the compiler cannot inline across the call site. This forecloses the entire downstream optimization graph: no constant propagation, no vectorization of the callee's body relative to the caller's context, no CSE across the boundary.

4.2 Devirtualization (The Compiler's Mitigation)

Modern compilers (GCC, Clang) implement several devirtualization strategies:

  • Speculative devirtualization: The compiler emits a type guard and a direct call for the most likely type, with a fallback to the vtable path. This allows inlining on the fast path.
  • Whole-program devirtualization (WPD) via LTO (Link-Time Optimization): With -flto -fwhole-program-vtables, the linker can prove, across translation units, that a virtual call site is monomorphic and replace it with a direct call entirely.
  • Final/sealed classes: Marking a class final is a direct hint to the compiler that no further derivation exists, enabling unconditional devirtualization at any call site where the static type is known.
class Derived final : public Base { // 'final' enables devirtualization
    void implementation() override { ... }
};

4.3 CRTP Speed Advantages

  • Zero-cost abstraction: The abstraction completely disappears after compilation. In benchmarks of numerical kernels (e.g., matrix operations using expression templates), CRTP-based designs match the speed of hand-written monomorphic code.
  • Auto-vectorization friendly: Since the compiler sees the full call graph, it can vectorize loops that cross the "inheritance boundary" — impossible with virtual dispatch.
  • No object size inflation: Absence of vptr improves cache line utilization, particularly critical when storing arrays of polymorphic objects.

4.4 When Virtual Dispatch Is Acceptable or Necessary

  • Cold paths: If the polymorphic call is not on a hot path (e.g., factory construction, error handling, UI events), the virtual dispatch overhead is negligible and the design flexibility is worth it.
  • Plugin/ABI boundaries: When derived types are loaded at runtime (shared libraries, plugins), the full type is structurally unknowable at compile time — CRTP is impossible. Virtual dispatch (or a C-compatible function pointer table) is mandatory.
  • Type erasure: std::function, std::any, and similar vocabulary types internally use virtual dispatch (or equivalent manual vtable tricks) precisely because the concrete type must be erased.

4.5 Modern Alternatives and the std::variant / std::visit Pattern

A middle ground that avoids both CRTP complexity and virtual overhead for closed type sets is:

using Shape = std::variant<Circle, Square, Triangle>;

std::visit([](auto& s) { s.draw(); }, shape); // Resolved via jump table, not vtable

std::visit generates a static jump table (similar to a vtable but with no per-object pointer) and dispatches in O(1). Crucially, each arm of the visit can be individually inlined and optimized. This is strictly more performant than virtual dispatch for closed hierarchies and avoids the template code-bloat of CRTP.

Summary

Dimension CRTP (Static) Virtual (Dynamic) std::variant/visit
Dispatch cost Zero (inlined) 2 indirections + IBP Jump table (O(1), inlinable)
Inlining Full Blocked (unless devirt.) Full per-arm
Vectorization Yes Blocked Yes
Open hierarchy No Yes No
Runtime type switching No Yes Yes (within set)
Object size No overhead +8 bytes (vptr) sizeof(largest) + tag
Code bloat risk High (template inst.) Low Low
ABI/plugin support No Yes No

The decisive rule for performance-critical systems: use static inheritance (CRTP) or std::variant/visit whenever the full type set is known at compile time and the call is on a hot path. Reserve virtual dispatch for open hierarchies, ABI boundaries, and cold paths — and leverage final, LTO, and PGO (Profile-Guided Optimization) to allow the compiler to recover direct-call performance wherever possible.

Note

Generated by Claude.ai

Model: Sonet 4.6

Prompt: Provide a thorough description of static and dynamic inheritance in a C++ program. This description is intended for a computer science expert. Then, evaluate its applicability in the context of the final program's execution speed.