Function and Class Templates

The previous course asked what an operation leaves behind in a resource when auto deduces a type. This course asks something wider: abstraction is not free, the cost only moves. A template removes the type decision at run time, but makes the compiler write a new body for every new type. A lock removes a data race, but puts threads in a queue. The course puts one question to every mechanism: where did this mechanism move the cost?

The Four Kinds

Every measurement in the course falls under one kind, and these four names do not change throughout the course.

Kind	Where the cost is paid
compile	The compiler’s work: no decision step remains at run time, and compiling leaves a product behind (a generated body, a selected candidate)
run	Paid again on every call or every object: the counted steps or allocations are greater than zero
memory	In the layout of the data in memory: the same work touches a different number of storage slots
wait	In the coordination between threads: every synchronization point is a place where one thread may wait for another

The kinds group into two at a higher level. Under compile, the cost is paid before the program runs; under run, memory and wait, it is paid while the program runs. Time is neither measured nor printed in this course; what is counted is steps, bodies, slots, jumps and synchronization points.

Do not confuse this question with the one in M11/K01. K01 asked who makes a decision; here the question is who pays the cost of a mechanism and what that cost is counted with. K01’s compiler kind named a decision; this course’s compile kind names a cost and always carries a product count beside it.

The Measurement Core

The core is three files. cost.hpp defines the four kinds as an enum class and declares two functions; cost.cpp prints each measurement as one line, increments the kind counter and prints the summary.

// cost.hpp — the core that names where a mechanism pays its cost
#ifndef COST_HPP
#define COST_HPP

#include <string>

enum class Cost { compile, run, memory, wait };

// Prints the measurement name, the kind and the observation on one line, bumps the kind counter.
void report(const std::string& measure, Cost c, const std::string& observed);

// Prints the kind counts and the top-level split.
void summary();

#endif

// cost.cpp — classification, line format and counter
#include "cost.hpp"

#include <cstdio>

namespace {
int counts[4] = {0, 0, 0, 0};
const char* const names[4] = {"compile", "run", "memory", "wait"};
}

void report(const std::string& measure, Cost c, const std::string& observed) {
    int i = static_cast<int>(c);
    ++counts[i];
    std::printf("%-26s %-8s %s\n", measure.c_str(), names[i], observed.c_str());
}

void summary() {
    std::printf("kinds: compile %d, run %d, memory %d, wait %d\n",
                counts[0], counts[1], counts[2], counts[3]);
    std::printf("paid at compile time %d, paid at run time %d\n",
                counts[0], counts[1] + counts[2] + counts[3]);
}

// moved_to.cpp — twelve mechanisms, one question each: where did the cost move
#include <atomic>
#include <memory>
#include <mutex>
#include <string>
#include <thread>
#include <type_traits>
#include <utility>
#include <vector>

#include "cost.hpp"

static std::string tag(const char* name, long n) {
    return std::string(name) + "=" + std::to_string(n);
}

/* 1. Templates: every new type yields a new body */
static int bodies = 0;
template <typename T>
T square(T x) {
    static const bool registered = (++bodies, true);
    (void)registered;
    return x * x;
}
static void templates() {
    const int fixed = 4;
    int calls = 0;
    square(2); ++calls;
    square(3); ++calls;
    square(1.5); ++calls;
    square(5L); ++calls;
    square(fixed); ++calls;
    report("template instantiation", Cost::compile,
           tag("calls", calls) + " " + tag("bodies", bodies));
}

/* 2. Specialization: the bool pack keeps eight values in one slot */
template <typename T>
struct Pack {
    T slot[8] = {};
    const void* where(int i) const { return &slot[i]; }
};
template <>
struct Pack<bool> {
    unsigned char bits = 0;
    const void* where(int) const { return &bits; }
};
template <typename T>
static int distinct_slots(const Pack<T>& p) {
    int distinct = 0;
    for (int i = 0; i < 8; ++i) {
        bool fresh = true;
        for (int j = 0; j < i; ++j)
            if (p.where(i) == p.where(j)) fresh = false;
        if (fresh) ++distinct;
    }
    return distinct;
}
static void specialization() {
    Pack<int> general;
    Pack<bool> packed;
    report("bool specialization", Cost::memory,
           tag("int", distinct_slots(general)) + " " + tag("bool", distinct_slots(packed)));
}

/* 3. Variadic parameters: recursive expansion yields a body at every step */
static int rec_bodies = 0;
static long sum_rec() {
    static const bool registered = (++rec_bodies, true);
    (void)registered;
    return 0;
}
template <typename First, typename... Rest>
long sum_rec(First first, Rest... rest) {
    static const bool registered = (++rec_bodies, true);
    (void)registered;
    return first + sum_rec(rest...);
}
static int fold_bodies = 0;
template <typename... T>
long sum_fold(T... x) {
    static const bool registered = (++fold_bodies, true);
    (void)registered;
    return (0L + ... + x);
}
static void variadic() {
    long a = sum_rec(1, 2, 3);
    long b = sum_fold(1, 2, 3);
    report("recursive pack expansion", Cost::compile,
           tag("total", a == b ? a : -1) + " " + tag("recursive", rec_bodies) + " " +
               tag("fold", fold_bodies));
}

/* 4. Type traits: the choice is made at compile time, no query is left at run time */
static int queries = 0;
template <typename T>
const char* kind_of(T) {
    if constexpr (std::is_integral_v<T>) return "integer";
    else return "floating";
}
static const char* kind_tagged(bool is_integer) {
    ++queries;
    return is_integer ? "integer" : "floating";
}
static void type_trait() {
    int same = 0;
    same += std::string(kind_of(1)) == kind_tagged(true);
    same += std::string(kind_of(2L)) == kind_tagged(true);
    same += std::string(kind_of('a')) == kind_tagged(true);
    same += std::string(kind_of(1.0)) == kind_tagged(false);
    same += std::string(kind_of(1.0f)) == kind_tagged(false);
    same += std::string(kind_of(2u)) == kind_tagged(true);
    report("if constexpr selection", Cost::compile,
           tag("same", same) + " queries=0 " + tag("tagged", queries));
}

/* 5. SFINAE: substitution failure is not an error, it is elimination */
template <typename T, typename = void>
struct divisible : std::false_type {};
template <typename T>
struct divisible<T, std::void_t<decltype(std::declval<T>() / 2)>> : std::true_type {};
static const char* yes_no(bool b) { return b ? "yes" : "no"; }
static void sfinae() {
    report("detection with void_t", Cost::compile,
           std::string("int=") + yes_no(divisible<int>::value) +
               " string=" + yes_no(divisible<std::string>::value));
}

/* 6. Static polymorphism: every derived type gets its own body */
static int crtp_bodies = 0;
template <typename D>
struct Shape {
    long area() const {
        static const bool registered = (++crtp_bodies, true);
        (void)registered;
        return static_cast<const D*>(this)->compute_area();
    }
};
struct Square : Shape<Square> {
    long side;
    explicit Square(long s) : side(s) {}
    long compute_area() const { return side * side; }
};
struct Rectangle : Shape<Rectangle> {
    long width, height;
    Rectangle(long w, long h) : width(w), height(h) {}
    long compute_area() const { return width * height; }
};
static void static_poly() {
    long total = Square(3).area() + Rectangle(2, 5).area() + Square(4).area();
    report("dispatch with crtp", Cost::compile,
           tag("total", total) + " " + tag("bodies", crtp_bodies));
}

/* 7. Threads and locks: every increment takes a lock */
static void locks() {
    std::mutex m;
    long value = 0, acquired = 0;
    std::vector<std::thread> workers;
    for (int i = 0; i < 4; ++i)
        workers.emplace_back([&] {
            for (int j = 0; j < 10000; ++j) {
                std::lock_guard<std::mutex> g(m);
                ++value;
                ++acquired;
            }
        });
    for (auto& t : workers) t.join();
    report("locked counter", Cost::wait, tag("acquired", acquired) + " " + tag("value", value));
}

/* 8. Memory model: one release store publishes a thousand plain stores */
static void memory_model() {
    std::vector<long> data(1000);
    std::atomic<bool> ready{false};
    int sync_points = 0;
    std::thread producer([&] {
        for (int i = 0; i < 1000; ++i) data[i] = i;
        ready.store(true, std::memory_order_release);
        ++sync_points;
    });
    while (!ready.load(std::memory_order_acquire)) std::this_thread::yield();
    long total = 0;
    for (long x : data) total += x;
    producer.join();
    report("release/acquire publish", Cost::wait,
           tag("sync", sync_points) + " " + tag("total", total));
}

/* 9. Cache-friendly layout: do the same fields sit side by side */
static int jumps(const float* const* access, int n) {
    int count = 0;
    for (int i = 1; i < n; ++i)
        if (access[i] != access[i - 1] + 1) ++count;
    return count;
}
static void data_layout() {
    float aos[12] = {};  // x y z x y z ...
    float soa[12] = {};  // x x x x y y y y z z z z
    const float* aos_x[4];
    const float* soa_x[4];
    for (int i = 0; i < 4; ++i) {
        aos_x[i] = &aos[i * 3];
        soa_x[i] = &soa[i];
    }
    report("x field only", Cost::memory,
           "aos=" + std::to_string(jumps(aos_x, 4)) + "/3 soa=" +
               std::to_string(jumps(soa_x, 4)) + "/3");
}

/* 10. Profiling: instrumented counters show the hot spot */
static void profile() {
    long prepare = 0, search = 0;
    std::vector<int> v;
    for (int i = 0; i < 100; ++i) {
        v.push_back(i * 7 % 50);
        ++prepare;
    }
    int dupes = 0;
    for (int i = 0; i < 100; ++i)
        for (int j = i + 1; j < 100; ++j) {
            ++search;
            if (v[i] == v[j]) ++dupes;
        }
    report("instrumented profile", Cost::run,
           tag("prepare", prepare) + " " + tag("search", search) + " " + tag("dupes", dupes));
}

/* 11. Compile times: the pimpl idiom makes one allocation per object */
static int allocs = 0;
class Window {
public:
    explicit Window(int id);
    ~Window();
    int id() const;

private:
    struct Impl;
    std::unique_ptr<Impl> impl_;
};
struct Window::Impl {
    int id;
    explicit Impl(int n) : id(n) { ++allocs; }
};
Window::Window(int id) : impl_(std::make_unique<Impl>(id)) {}
Window::~Window() = default;
int Window::id() const { return impl_->id; }
static void pimpl() {
    Window a(1), b(2), c(3);
    report("pimpl idiom", Cost::run,
           tag("objects", (a.id() > 0) + (b.id() > 0) + (c.id() > 0)) + " " + tag("allocs", allocs));
}

/* 12. Package management and build tools: how many units does a changed header rebuild */
struct Unit {
    const char* name;
    std::vector<std::string> headers;
};
static int rebuilt(const std::vector<Unit>& units, const std::string& changed) {
    int count = 0;
    for (const auto& u : units)
        for (const auto& h : u.headers)
            if (h == changed) {
                ++count;
                break;
            }
    return count;
}
static void build_tool() {
    std::vector<Unit> units = {
        {"input.cpp", {"common.hpp"}},
        {"calc.cpp", {"common.hpp"}},
        {"report.cpp", {"common.hpp", "local.hpp"}},
    };
    report("changed header", Cost::compile,
           tag("common", rebuilt(units, "common.hpp")) + " " +
               tag("local", rebuilt(units, "local.hpp")));
}

int main() {
    templates();
    specialization();
    variadic();
    type_trait();
    sfinae();
    static_poly();
    locks();
    memory_model();
    data_layout();
    profile();
    pimpl();
    build_tool();
    summary();
}

moved_to.cpp builds twelve mechanisms; this lesson’s mechanism is at the top, and the others open in later lessons. Compiling the three files together and running them gives the following output.

template instantiation     compile  calls=5 bodies=3
bool specialization        memory   int=8 bool=1
recursive pack expansion   compile  total=6 recursive=4 fold=1
if constexpr selection     compile  same=6 queries=0 tagged=6
detection with void_t      compile  int=yes string=no
dispatch with crtp         compile  total=35 bodies=2
locked counter             wait     acquired=40000 value=40000
release/acquire publish    wait     sync=1 total=499500
x field only               memory   aos=3/3 soa=0/3
instrumented profile       run      prepare=100 search=4950 dupes=50
pimpl idiom                run      objects=3 allocs=3
changed header             compile  common=3 local=1
kinds: compile 6, run 2, memory 2, wait 2
paid at compile time 6, paid at run time 6

MT1. Of the twelve mechanisms, six moved the cost to the compile kind, two to run, two to memory and two to wait; six are paid at compile time and six at run time. The core appears in full only in this lesson; later lessons take only the relevant slice, and each lesson builds its own measurement in plain C++: a local static counter, a step counter or a pointer comparison.

Function Templates and Template Argument Deduction

square is a function template: T is a template parameter, and the body is written without knowing T. At the call, the compiler looks at the argument’s type and deduces T; this is called template argument deduction. If the body for the deduced type has not been generated before, the compiler generates it; this generation is called instantiation. The record is kept in a local static variable inside the body: every instantiation has its own static, and it is incremented once, on the first call.

// square.hpp — a function template defined in a header, counting its bodies
#ifndef SQUARE_HPP
#define SQUARE_HPP

inline int square_bodies = 0;

template <typename T>
T square(T x) {
    static const bool registered = (++square_bodies, true);
    (void)registered;
    return x * x;
}

#endif

We do not have to leave the argument to the compiler: with square<long>(3), T is given explicitly, no deduction takes place and the argument is converted to long. The same idea holds in a class template.

// box.hpp — a class template: a separate class for every T
#ifndef BOX_HPP
#define BOX_HPP

inline int box_bodies = 0;

template <typename T>
class Box {
public:
    explicit Box(T value) : value_(value) {}
    T get() const {
        static const bool registered = (++box_bodies, true);
        (void)registered;
        return value_;
    }

private:
    T value_;
};

#endif

// instantiation.cpp — deduction, explicit arguments and class template bodies
#include <cstdio>

#include "square.hpp"
#include "box.hpp"

int main() {
    int a = square(2);              // T = int deduced
    double b = square(1.5);         // T = double deduced
    long c = square<long>(3);       // T given explicitly as long
    double d = square<double>(3);   // 3 converts to double, the double body is reused

    Box<int> two(2);
    Box<int> three(3);
    Box<double> half(0.5);

    std::printf("square %d %.2f %ld %.1f\n", a, b, c, d);
    std::printf("square bodies %d\n", square_bodies);
    std::printf("box %d %d %.1f\n", two.get(), three.get(), half.get());
    std::printf("box bodies %d\n", box_bodies);
    return 0;
}

square 4 2.25 9 9.0
square bodies 3
box 2 3 0.5
box bodies 2

MT2. square<double>(3) did not yield a new body, because the double body already existed from square(1.5). Box<int> and Box<double> are two separate classes; the two Box<int> objects shared a single get body. In a class template, only the member functions that are used are instantiated.

MT3. Bodies are generated according to the number of types used, not the number of calls: four square calls yielded three bodies, and three Box::get calls yielded two. The cost moved to the compile kind; no type decision is left at run time, and what is paid is the extra code the compiler writes for every new type.

Why a Template Is Defined in a Header

Both templates are defined in a .hpp, together with their declarations.

MT4. Instantiation requires the definition of the template to be visible in the translation unit where the call is made: the compiler can generate the int body for square(2) only if it sees the definition in that unit. If the definition lived only in a .cpp file, a call from another unit could not see it and the body could not be generated. For this reason the definition goes in a header that every translation unit using it sees. This also has a cost; the last lessons of the course return to it: every unit that includes the header is rebuilt.

The Bounding Measurement

What decides the number of bodies is neither the number of calls nor how the argument is written, but the deduced type. We test this with an argument that carries const.

// constant-argument.cpp — a const int argument does not yield a new body
#include <cstdio>

#include "square.hpp"

int main() {
    const int fixed = 4;

    int a = square(fixed);        // T = int, const is dropped in deduction
    int b = square<int>(fixed);   // T given explicitly as int
    int c = square(2);            // T = int

    std::printf("square %d %d %d\n", a, b, c);
    std::printf("bodies %d\n", square_bodies);
    return 0;
}

square 16 16 4
bodies 1

MT5. In the call square(fixed), the argument’s const is dropped during template argument deduction and T becomes int; the call uses the square<int> body and yields no new body. Three calls, one body; this is why the calls=5 bodies=3 line in the core says five calls, three bodies. The kind stays compile, because what is counted is the body that compiling left behind.

Summary

• The mechanism measured in this lesson moves the cost to the compile kind: a template makes the compiler write a separate body for every new type that is used.
• There are four kinds: compile, run, memory, wait; in the core, six mechanisms are paid at compile time and six at run time.
• Template argument deduction finds T from the argument; an explicit template argument skips deduction.
• The deduced type decides the number of bodies: a const int argument drops its const and yields no new body.
• In a class template only the members that are used are instantiated; the definition of a template must be visible in every translation unit that uses it.

Next Step

In this lesson a template produced a body for every new type, and the cost moved to compile time. The next lesson asks where the cost goes when a primary template is replaced by hand for a specific type: when Pack<bool> fits eight values into one slot, the cost moves to the layout of memory, and from there to run time.