C++ template code COMDAT folding

Reference:
Reducing C++ template bloat by factoring out the type-dependent portions of the function

COMDAT folding (also known as Identical Code Folding or ICF/Safe ICF) is a link-time optimization where the linker detects functions or read-only data sections that compile into byte-for-byte identical machine code, merges them into a single instance, and points all call sites to that unified copy.

When instantiates templates over types that share the same underlying memory layout and operations, the compiler often emits redundant assembly:

template <typename T>
void push_item(T* item) {
    // Operations on item...
}

// In translation unit A:
push_item<Dog>(dog_ptr);

// In translation unit B:
push_item<Cat>(cat_ptr);

Because Dog* and Cat* are both raw machine pointers (typically 8 bytes), the generated machine instructions for push_item and push_item are identical. 

Normally, C++ templates emit code into COMDAT sections (Common Data sections) with "link-once" semantics (select any). This allows the linker to discard duplicates of push_item compiled across multiple .cpp files. However, normal deduplication only matches identical symbol names. It cannot eliminate the identical assembly between push_item and push_item because their mangled symbol names differ.

How COMDAT Folding Works

During the link step, the linker inspects all candidate sections:

Content Comparison: The linker compares the byte streams, relocation targets, and alignment requirements of functions marked as foldable (typically COMDAT sections generated by inline functions, template instantiations, and virtual tables).

Section Merging: If two distinct functions (e.g., std::vector<int*>::size() and std::vector<char*>::size()) produce identical instructions and reference identical offsets, the linker discards one function body.

Symbol Redirection: The symbol table entry for the discarded function is updated to point directly to the entry point of the retained function.

Key Benefits

Reduced Binary Footprint: Prevents template-heavy code (like std::vector<T*> for hundreds of pointer types) from inflating executable size.

Instruction Cache (I-Cache) Efficiency: Multiple logically distinct types share hot cache lines instead of thrashing the instruction cache with duplicate code.

The Function Pointer Quirk

Under strict C++ rules, every distinct function must have a unique address:

assert(&push_item<Dog> != &push_item<Cat>);

When COMDAT folding collapses these functions, &push_item<Dog> == &push_item<Cat> evaluates to true. This can break code that relies on function pointer uniqueness for type-tagging or callback registries.

To handle this, linkers provide different safety levels:

LLVM (lld)  --icf=safe Only merges functions whose addresses are never taken, preserving C++ address-uniqueness guarantees.

LLVM (lld)  --icf=all Aggressively merges all identical functions, even if addresses are taken.

Instead of generating redundant machine code for hundreds of pointer instantiations and hoping the linker cleans it up with COMDAT folding / ICF, standard library implementations and runtime systems use type erasure with non-templated (or void-pointer-based) base classes.

By shifting the heavy procedural logic into a shared base class, the exposed template becomes a thin, inline wrapper that carries zero runtime binary overhead.

The Architecture: Base-Derived Split

The pattern divides a container or utility into two layers:

The Erased Base Class: Implements memory allocation, capacity resizing, buffer shifts, and element index arithmetic using void* or raw byte buffers. This code is compiled once into the runtime library or translation unit.

The Typed Template Wrapper: Derives from or wraps the base class. It only exposes strongly typed interfaces, using zero-cost casts (reinterpret_cast or static_cast) to translate between T* and void*.

// --- Shared Implementation (compiled once into binary/lib) ---
class VectorPtrBase {
protected:
    void** data_ = nullptr;
    size_t size_ = 0;
    size_t capacity_ = 0;

    void grow_and_insert(size_t index, void* element) {
        // All heavy buffer reallocation, index shifting,
        // and boundary checks happen HERE once.
        if (size_ == capacity_) {
            size_t new_cap = capacity_ == 0 ? 8 : capacity_ * 2;
            void** new_data = new void*[new_cap];
            for (size_t i = 0; i < size_; ++i) new_data[i] = data_[i];
            delete[] data_;
            data_ = new_data;
            capacity_ = new_cap;
        }
        data_[index] = element;
        ++size_;
    }

    void* get_element(size_t index) const {
        return data_[index];
    }
};

// --- Thin Typed Wrapper (specialization for any pointer type) ---
template <typename T>
class Vector<T*> : private VectorPtrBase {
public:
    void push_back(T* val) {
        // Zero-cost static cast; inlines down to a direct call to the base
        grow_and_insert(size_, static_cast<void*>(val));
    }

    T* operator[](size_t index) const {
        return static_cast<T*>(get_element(index));
    }

    size_t size() const { return size_; }
};

Why This Beats Relying Purely on COMDAT Folding

Faster Compilation Times: The compiler does not have to parse, instantiate, type-check, and generate intermediate representation (IR) / assembly for grow_and_insert across Vector<Apple*>, Vector<Banana*>, and Vector<Car*>.

Lower Linker Overhead: Linker-time ICF requires analyzing section hashes, inspecting instruction bytes, and walking relocation tables to prove equivalence. Pointer erasure eliminates the duplicate sections before the object files reach the linker.

Guaranteed Code Sharing: COMDAT folding is sensitive to subtle differences (such as debug information emission, compiler optimization levels, or platform-specific pointer calling conventions). The base-class approach enforces code sharing by construction.

Preserved Pointer Address Guarantees: Because the wrapper's member functions inline entirely into the caller or delegate to the shared base, it avoids issues where --icf=safe refuses to fold functions whose addresses were taken.