---
title: 'Templates and Performance'
source: 'https://academia.sh/en/courses/cpp-templates'
language: en
updated: '2026-10-21T05:02:45+00:00'
license: 'CC BY-SA 4.0'
lessons: 12
outcomes:
    - 'Builds compile-time polymorphism with templates'
    - 'Uses the memory model and concurrency primitives correctly'
    - 'Backs performance claims with profiling and measurement'
    - 'Tells whether a technique moves the cost to compilation, run time, memory layout or waiting, and shows that cost by counting it'
---

# Templates and Performance

In C++ a cost does not disappear, it moves: the course measures every mechanism with a single question — where did this technique move the cost; to compilation, to run time, to memory layout, or to waiting? Templates, specialization, variadic parameters, type traits, SFINAE, static polymorphism, threads, the memory model, data layout, profiling, compile times and package management all pass through the same frame.

## Template Metaprogramming

Function and class templates, specialization, variadic template parameters, type traits, overload resolution and SFINAE, static polymorphism — each paired with the question of where the cost moved.

### Function and Class Templates

Source: https://academia.sh/en/courses/cpp-templates/function-and-class-templates

Function templates, template argument deduction, explicit template arguments and class templates; the compiler writing a new body for every new type, and that cost moving to compile time.

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.

```cpp
// 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
```

```cpp
// 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]);
}
```

```cpp
// 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.

```text
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.

```cpp
// 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**.

```cpp
// 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
```

```cpp
// 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;
}
```

```text
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`.

```cpp
// 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;
}
```

```text
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.

### Template Specialization

Source: https://academia.sh/en/courses/cpp-templates/template-specialization

Full and partial specialization, the primary template, selection of the most specialized match, the memory layout of the bool pack, and the cost that reading from a bit leaves to run time.

The previous lesson showed that a template makes the compiler write a new body for every new type,
and that this cost stays in the **compile** kind. The body a template produces is the same pattern
for every type, but for some types the pattern may be wrong or wasteful. This lesson covers replacing
the pattern by hand in that case, which is **specialization**. The question has not changed: where did
this mechanism move the cost? Here the answer is not the number of bodies but how many slots the data
is spread across in memory.

#### The Primary Template and Full Specialization

Consider a `Pack<T>` that holds eight values. The **primary template** reserves one slot for each
value: `T slot[8]`. For `bool` this is wasteful, because a value carries one bit but occupies one
byte. A **full specialization** (`template <>`) replaces the primary template entirely for a given
type; here `Pack<bool>` keeps the eight values in a single `unsigned char`. The interface stays the
same, the body changes.

```cpp
// pack.hpp — primary template and full specialization for bool
#ifndef PACK_HPP
#define PACK_HPP

template <typename T>
struct Pack {
    T slot[8] = {};
    const void* where(int i) const { return &slot[i]; }
    void write(int i, T value) { slot[i] = value; }
    T read(int i, int&) const { return slot[i]; }
};

template <>
struct Pack<bool> {
    unsigned char bits = 0;
    const void* where(int) const { return &bits; }
    void write(int i, bool value) {
        if (value) bits = static_cast<unsigned char>(bits | (1u << i));
        else bits = static_cast<unsigned char>(bits & ~(1u << i));
    }
    bool read(int i, int& steps) const {
        steps += 2;   // one shift, one mask
        return ((bits >> i) & 1) != 0;
    }
};

#endif
```

`where` shows which slot a value sits in; we will count slots with **pointer equality**, without
printing addresses. If two pointers are equal, the two values are in the same slot. The program
below fills both packs with the same pattern, reads them and prints the distinct slot count.

```cpp
// specialization.cpp — same interface, different slot count
#include <cstdio>

#include "pack.hpp"

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;
}

template <typename T>
static void try_pack(const char* name, Pack<T>& p) {
    int steps = 0;
    p.write(1, true);
    p.write(6, true);
    std::printf("%s ", name);
    for (int i = 0; i < 8; ++i) std::printf("%d", static_cast<int>(p.read(i, steps)));
    std::printf(" slots=%d\n", distinct_slots(p));
}

int main() {
    Pack<int> general;
    Pack<bool> packed;
    try_pack("int ", general);
    try_pack("bool", packed);
    return 0;
}
```

```text
int  01000010 slots=8
bool 01000010 slots=1
```

**MT6.** The two packs read the same values in the same order; the only difference is the slot
count: `Pack<int>` uses eight distinct slots, `Pack<bool>` uses one. The `int=8 bool=1` counts in the
`bool specialization` row of the core are this measurement. The cost falls under the **memory**
kind: the same work touches a different number of storage slots depending on the layout of the data.

#### Partial Specialization and Selecting the Most Specialized Match

A full specialization names types one by one. A **partial specialization** captures a pattern of
parameters instead: "if the two parameters are the same type" or "if the type is a pointer". For a
two-parameter `Pair<T, U>`, the primary template captures distinct types, the `Pair<T, T>` partial
specialization captures identical types, and the `Pair<int, int>` full specialization captures only
the `int` pair. When more than one specialization fits a use, the compiler picks **the most
specialized one**.

```cpp
// pair.hpp — primary template, partial and full specialization
#ifndef PAIR_HPP
#define PAIR_HPP

template <typename T, typename U>
struct Pair {
    static const char* kind() { return "different"; }
};

template <typename T>
struct Pair<T, T> {
    static const char* kind() { return "same"; }
};

template <>
struct Pair<int, int> {
    static const char* kind() { return "integer"; }
};

#endif
```

```cpp
// pair-select.cpp — which specialization was chosen
#include <cstdio>

#include "pair.hpp"

int main() {
    std::printf("int,double    %s\n", Pair<int, double>::kind());
    std::printf("double,double %s\n", Pair<double, double>::kind());
    std::printf("int,int       %s\n", Pair<int, int>::kind());
    return 0;
}
```

```text
int,double    different
double,double same
int,int       integer
```

**MT7.** `Pair<int, int>` fits both the partial pattern (`T, T`) and the full specialization; the
compiler chooses the full one. `Pair<double, double>` fits only the partial pattern. The selection
ends at compile time and leaves no decision step at run time. There is one more rule: a
specialization must be visible **before** the first instantiation of that type; a specialization
that comes after the type has already been generated from the primary template makes the program
ill-formed, and the compiler is not required to report it. Function templates, on the other hand,
cannot be partially specialized; overloading is used for the same job, which the Overload Resolution
and SFINAE lesson covers.

#### The Pointer Pattern and the Limit of Specialization

A partial specialization can also capture the shape of a type. `Access<T*>` captures every type
that is a pointer, whatever `T` is; the primary template returns the value as it is. A limit shows
up here: a specialization **does not inherit the members of the primary template**. A specialization
is a new class definition on its own; every member that exists in the primary template and that we
expect to be callable has to be written again in it. Keeping the interface common is not a compiler
guarantee but a contract the author takes on. That `Pack<bool>` carries the members `where`, `write`
and `read` under the same names as the primary template is this contract being honored.

```cpp
// pointer.hpp — a partial specialization captures the pointer pattern
#ifndef POINTER_HPP
#define POINTER_HPP

template <typename T>
struct Access {
    static const char* name() { return "value"; }
    static T get(const T& x) { return x; }
};

template <typename T>
struct Access<T*> {
    static const char* name() { return "pointer"; }
    static T get(T* const& p) { return *p; }
};

#endif
```

```cpp
// pointer-select.cpp — same call, two separate bodies
#include <cstdio>

#include "pointer.hpp"

int main() {
    int x = 7;
    int* p = &x;
    std::printf("%s %d\n", Access<int>::name(), Access<int>::get(x));
    std::printf("%s %d\n", Access<int*>::name(), Access<int*>::get(p));
    return 0;
}
```

```text
value 7
pointer 7
```

**MT8.** `Access<int*>` comes not from the primary template but from the partial specialization that
captures the pointer pattern, and it reads the value from where the pointer points. Both uses print
seven, but the bodies behind them are different; which one is used is decided at compile time and no
query is left at run time. The kind of this lesson still stays **memory**: the memory measurement is
only the `Pack<bool>` row, and this section is a supporting example that shows the limit of
specialization.

#### Full Specialization of a Function Template

Function templates cannot be partially specialized, but they can be **fully** specialized. There is a
trap here concerning headers: a full specialization is no longer a template but an ordinary
function, so if it is defined in a header it must be `inline`; otherwise every unit that includes
the header defines the same function and the linker sees a duplicate definition. The primary template
`label` below says `other` for every type, and the full specialization for `int` says `integer`.

```cpp
// label.hpp — a function template and an inline full specialization
#ifndef LABEL_HPP
#define LABEL_HPP

template <typename T>
const char* label() { return "other"; }

template <>
inline const char* label<int>() { return "integer"; }

#endif
```

```cpp
// label-select.cpp — which label was chosen
#include <cstdio>

#include "label.hpp"

int main() {
    std::printf("%s %s %s\n", label<double>(), label<int>(), label<long>());
    return 0;
}
```

```text
other integer other
```

**MT9.** `label<int>` goes to the specialization, while `label<double>` and `label<long>` go to the
primary template; the primary template yields two separate bodies, the specialization one. Here too
the selection ends at compile time. For function templates, overloading is often preferred over
specialization, because overload resolution picks candidates by different rules than specialization;
the Overload Resolution and SFINAE lesson shows the difference.

#### `std::vector<bool>` and the Proxy Object

The standard library uses this idea itself: `std::vector<bool>` is a specialization, and the
standard suggests for it a representation that packs the values into bits and saves space; common
implementations do this the way `Pack<bool>` does. The result has a cost: it is not possible to take
the **address** of an element, because the element is not a separate `bool` object. For this
reason `operator[]` returns not the element itself but a **proxy object** that reads and writes that
bit. Trying to take the address of an element is not run here; the defined alternative is to work with
the proxy object.

```cpp
// proxy.cpp — access to a vector<bool> element through a proxy object
#include <cstdio>
#include <vector>

int main() {
    std::vector<bool> v(8, false);
    v[3] = true;      // operator[] returns a proxy object, the assignment writes the bit
    bool three = v[3];   // the proxy object converts to bool

    int filled = 0;
    for (std::size_t i = 0; i < v.size(); ++i) filled += v[i];
    std::printf("filled %d, v[3] %d\n", filled, three ? 1 : 0);
    return 0;
}
```

```text
filled 1, v[3] 1
```

Packing the bits pays back the cost gained in memory somewhere else. Where, the next section
measures.

#### The Most Specialized Specialization Wins

More than one partial specialization can match the same type. The compiler picks the one whose
pattern is more specific than the others: the `T*` pattern is more general than the `const T*`
pattern, because `const int*` fits both and the second pattern is a subset of the first. If none is
more specific than the other, the use is ambiguous and compilation stops; I leave that to prose,
because code that does not compile is not written as a block. A full specialization always comes
before a partial one.

```cpp
// most-specific.cpp — the most specific pattern is chosen
#include <cstdio>

template <typename T>
struct TypeName { static const char* name() { return "generic"; } };

template <typename T>
struct TypeName<T*> { static const char* name() { return "pointer"; } };

template <typename T>
struct TypeName<const T*> { static const char* name() { return "const pointer"; } };

template <>
struct TypeName<int*> { static const char* name() { return "int pointer"; } };

int main() {
    std::printf("int          %s\n", TypeName<int>::name());
    std::printf("double*      %s\n", TypeName<double*>::name());
    std::printf("const char*  %s\n", TypeName<const char*>::name());
    std::printf("int*         %s\n", TypeName<int*>::name());
    return 0;
}
```

```text
int          generic
double*      pointer
const char*  const pointer
int*         int pointer
```

**MT10.** `int` fits no pattern, so the primary template stays. `double*` fits only the `T*`
pattern. `const char*` fits both the `T*` and the `const T*` pattern, and the second is more
specific. For `int*` there is a full specialization, and it beats the partial one. This selection
ends at compile time: one class definition is chosen for every type used, and no query is left at
run time.

#### Function Templates Cannot Be Partially Specialized

Partial specialization exists only for class templates; for a function template only a full
specialization can be written. The partial equivalent on the function side is overloading: two
separate function templates are written for `T` and `T*`, and overload resolution decides which
one is more specific. That decision is the subject of the next lessons; here seeing the result is
enough. Full specializations of function templates, for their part, are mostly replaced with
overloading, because specializations do not take part in overload resolution: the compiler first
chooses among the primary templates, and then uses the specialization of the template it chose.

```cpp
// function-overload.cpp — overloading instead of partial specialization for functions
#include <cstdio>

template <typename T>
const char* describe(T) { return "value"; }

template <typename T>
const char* describe(T*) { return "pointer"; }

int main() {
    int n = 5;
    std::printf("describe(n)  %s\n", describe(n));
    std::printf("describe(&n) %s\n", describe(&n));
    return 0;
}
```

```text
describe(n)  value
describe(&n) pointer
```

**MT11.** For `describe(n)` only the `T` template is viable. For `describe(&n)` both are viable
and the `T*` template is more specific, so it is chosen. What partial specialization does on the
class side comes down to what overload resolution does on the function side; in both, the selection
ends at compile time and the cost is in the **compile** kind.

#### The Bounding Measurement

`Pack<bool>` lowered the memory cost by fitting eight values into one slot. But to read a bit, the
slot first has to be shifted and then masked; `Pack<int>` reads the value directly. The counter
counts two steps (the shift and the mask) inside `Pack<bool>::read` and zero steps inside
`Pack<int>::read`. The program below makes eight reads on each pack.

```cpp
// read-steps.cpp — steps per read
#include <cstdio>

#include "pack.hpp"

template <typename T>
static void count_steps(const char* name, const Pack<T>& p) {
    int steps = 0;
    int reads = 0;
    for (int i = 0; i < 8; ++i) {
        p.read(i, steps);
        ++reads;
    }
    std::printf("%s reads=%d steps=%d per_read=%d\n", name, reads, steps, steps / reads);
}

int main() {
    Pack<int> general;
    Pack<bool> packed;
    count_steps("int ", general);
    count_steps("bool", packed);
    return 0;
}
```

```text
int  reads=8 steps=0 per_read=0
bool reads=8 steps=16 per_read=2
```

**MT12.** `Pack<bool>` pays two steps on every read, `Pack<int>` pays zero. The cost gained in memory
returned to run time: the slot count dropped from eight to one, but every read asks for a shift and a
mask. The central measurement of this lesson stays in the **memory** kind, because the number in the
core is the slot count; the steps per read are the bound that shows the cost is not gained in one
direction only. The step count here is a model: the shift and the mask are counted by the counter
lines, and it is not a measured time.

#### Summary

- The mechanism measured in this lesson moves the cost to the **memory** kind: `Pack<bool>` keeps
  eight values in one slot (`int=8 bool=1`).
- A full specialization (`template <>`) replaces the body of a single type; a partial
  specialization captures a pattern of parameters; when several match, the most specialized one is
  chosen.
- A specialization must be visible before the first instantiation of the type; function templates
  cannot be partially specialized, and their full specialization must be `inline` in a header.
- A specialization does not inherit the members of the primary template; a pattern like `Access<T*>`
  is captured with a partial specialization, and the author keeps the interface contract.
- The address of a `std::vector<bool>` element cannot be taken; `operator[]` returns a proxy object.
- Reading from a bit asks for two steps on every access: the cost gained in memory returns to run
  time.

#### Next Step

In this lesson the specialization put the cost into the slot, and the step per read carried it back
to run time. The next lesson turns the number of template parameters from a constant into a variable:
as a parameter pack is expanded, it measures how many bodies the compiler produces.

### Variadic Templates

Source: https://academia.sh/en/courses/cpp-templates/variadic-templates

Parameter packs, sizeof..., pack expansion, comparing recursive expansion with fold expressions, forwarding with std::forward, and how many bodies the expansion method makes the compiler write.

The previous lesson measured specialization: `Pack<bool>` took the cost out of the slot and put it
into a step at run time. This lesson also frees the number of template parameters. Can a function
accept all of its arguments, however many are given? A **variadic template** makes that possible,
but the expansion method changes how many bodies the compiler has to write. The question of the
lesson is that number: how many bodies does expanding a pack produce?

#### Parameter Packs and sizeof...

The declaration `typename... T` with three dots defines a **parameter pack**: it gathers zero or
more types under a single name. The function parameter `T... x` is the matching **function parameter
pack**. The number of elements in the pack is known not at run time but at compile time, and is read
with `sizeof...(T)`. To use the pack, `x...` is written; this is called **pack expansion**: the
compiler turns every element of the pack into a comma-separated list.

To pass a pack on to another function, `std::forward` is used. Whether an argument is an lvalue or
an rvalue is preserved in a parameter of the form `A&&`; `std::forward<A>` passes that information
on intact. The program below shows three things together.

```cpp
// pack-operations.cpp — sizeof..., forwarding and a unary fold
#include <cstdio>
#include <utility>

template <typename... T>
constexpr int count_args(T...) { return static_cast<int>(sizeof...(T)); }

template <typename... T>
bool all_positive(T... x) { return (... && (x > 0)); }

static long sum3(long a, long b, long c) { return a + b + c; }

template <typename F, typename... A>
long forward_call(F f, A&&... a) { return f(std::forward<A>(a)...); }

int main() {
    std::printf("count %d %d %d\n", count_args(), count_args(1), count_args(1, 'a', 2.0));
    std::printf("all %d %d %d\n", all_positive(1, 2, 3) ? 1 : 0,
                all_positive(1, -2) ? 1 : 0, all_positive() ? 1 : 0);
    std::printf("forward %ld\n", forward_call(sum3, 1, 2L, 3));
    return 0;
}
```

```text
count 0 1 3
all 1 0 1
forward 6
```

**MT13.** `count_args` gives zero for an empty pack and three for three arguments; the number is a
constant at compile time. `all_positive` uses a **fold expression**: `(... && (x > 0))` folds the
pack into a single expression with the `&&` operator. When the pack is empty, an `&&` fold gives
`true`. `forward_call` sends the arguments to `sum3` without adding any copy; `std::forward` is
needed only here, for forwarding.

#### Recursive Expansion and the Base Case

The classic way to expand a pack by hand has three steps: take the first argument, call the same
function with the rest, and write a **base case** that stops when the pack runs out. Every call is
made with a pack one element shorter, so every step is **a separate template body**.

We build the sum in two ways. `sum_rec` expands recursively; `sum_fold` gives the same sum with
a single fold expression. Every body increments its own local `static` once, on the first call, so
the counter counts the generated bodies.

```cpp
// sum.hpp — recursive and fold sums, counting bodies
#ifndef SUM_HPP
#define SUM_HPP

inline int rec_bodies = 0;
inline int fold_bodies = 0;

inline 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...);
}

template <typename... T>
long sum_fold(T... x) {
    static const bool registered = (++fold_bodies, true);
    (void)registered;
    return (0L + ... + x);
}

#endif
```

```cpp
// pack-expansion.cpp — the same sum, two expansion methods
#include <cstdio>

#include "sum.hpp"

int main() {
    long a = sum_rec(1, 2, 3);
    long b = sum_fold(1, 2, 3);
    std::printf("sum %ld %ld\n", a, b);
    std::printf("recursive %d fold %d\n", rec_bodies, fold_bodies);
    return 0;
}
```

```text
sum 6 6
recursive 4 fold 1
```

**MT14.** Both methods give six, but their body counts are different. `sum_rec(1, 2, 3)` uses three
template bodies (`<int,int,int>`, `<int,int>`, `<int>`) and one base function: four. `sum_fold(1, 2,
3)` gives the same sum with a single body. The `recursive=4 fold=1` counts in the `recursive pack
expansion` row of the core are this measurement. The cost falls under the **compile** kind: no
decision step is left at run time, and the compiler writes a different amount of code for each
expansion form.

#### Forms of the Fold Expression

A fold expression is written in four forms. A **unary** fold, `(... + x)` or `(x + ...)`, carries
only the pack; a **binary** fold, `(0L + ... + x)`, adds an initial value. A left fold groups like
`((x1 + x2) + x3)`, a right fold like `(x1 + (x2 + x3))`. A unary fold that carries no initial value
is valid for an empty pack only with the `&&`, `||` and `,` operators: `(... && ...)` gives `true`
on an empty pack, `(... || ...)` gives `false`, and a comma gives `void()`. A unary fold with `+`
does not compile on an empty pack; this is why the `0L` initial value is needed for the call
`sum_fold()`. A fold expression works with a single body in every instantiation, because pack
expansion is not a recursion but a single expression that the compiler generates.

#### The Expansion Pattern: The Right Side of the Three Dots

The meaning of the three dots depends on the expression to their left. `x...` expands only `x`; but
`(x * 2)...` writes the whole pattern once for each element. If there is more than one pack in the
pattern, they must all have the same length and are expanded together, element by element. The place
of expansion matters too: a pack can be expanded in a function call argument list, in a brace
initializer, in a template argument list, or in a fold expression. The program below shows two of
these, the brace initializer and the fold expression.

```cpp
// pattern.cpp — pattern expansion and the same-type query
#include <cstdio>
#include <type_traits>

template <typename... T>
int doubled(T... x) {
    int d[] = {static_cast<int>(x * 2)..., 0};
    int t = 0;
    for (int v : d) {
        t += v;
    }
    return t;
}

template <typename First, typename... T>
constexpr bool all_same_v = (std::is_same_v<First, T> && ...);

template <typename... T>
void print_all(T... x) {
    int index = 0;
    (std::printf("%s%d", index++ ? "," : "", static_cast<int>(x)), ...);
    std::printf("\n");
}

int main() {
    std::printf("doubled %d\n", doubled(1, 2, 3));
    std::printf("same %d %d\n", all_same_v<int, int, int>,
                all_same_v<int, int, long>);
    print_all(7, 8L, 'a');
    return 0;
}
```

```text
doubled 12
same 1 0
7,8,97
```

**MT15.** `doubled(1, 2, 3)` writes the pattern three times: the set `{2, 4, 6, 0}` adds up to twelve.
The trailing zero provides a valid set in place of `{}` for an empty pack. `all_same_v` is a type
query, and the fold expression collects all the matches with `&&`. `print_all` is folded with the
comma operator; in a comma fold the elements are evaluated from left to right, which the standard
guarantees, and the order in the output shows it (97 is the code of the character `a`).

#### The Forwarding Constructor: Packs and std::forward

The most common use of a pack is to pass arguments to a constructor as they are when building an
object. Parameters of the form `A&&...` make up a **forwarding reference** pack, and
`std::forward<A>(a)...` preserves whether each element is an lvalue or an rvalue. To see this, let
us write a type whose copies and moves we count.

```cpp
// forwarding.cpp — forwarding constructor, copy and move counts
#include <cstdio>
#include <utility>

struct Trace {
    static inline int copies = 0;
    static inline int moves = 0;
    int value;
    explicit Trace(int v) : value(v) {}
    Trace(const Trace& o) : value(o.value) { ++copies; }
    Trace(Trace&& o) noexcept : value(o.value) { ++moves; }
};

struct Wrapper {
    Trace a;
    Trace b;
    template <typename A, typename B>
    Wrapper(A&& x, B&& y) : a(std::forward<A>(x)), b(std::forward<B>(y)) {}
};

template <typename T, typename... A>
T create(A&&... a) {
    return T(std::forward<A>(a)...);
}

int main() {
    Trace lvalue(1);
    Wrapper s1 = create<Wrapper>(lvalue, Trace(2));
    std::printf("copies=%d moves=%d\n", Trace::copies, Trace::moves);
    Wrapper s2 = create<Wrapper>(Trace(3), Trace(4));
    std::printf("copies=%d moves=%d\n", Trace::copies, Trace::moves);
    std::printf("values %d %d %d %d\n", s1.a.value, s1.b.value, s2.a.value, s2.b.value);
    return 0;
}
```

```text
copies=1 moves=1
copies=1 moves=3
values 1 2 3 4
```

**MT16.** In the first construction, `lvalue` is an lvalue and `std::forward<Trace&>` copies it; the
temporary `Trace(2)` is an rvalue and is moved. In the second construction both temporaries are moved.
Without `std::forward`, every argument would go to the constructor as a named lvalue and would be
copied each time. The counters are cumulative, so the second line includes both moves of the second
construction; these are product counts, not a claim about time. This forwarding chain also makes the
compiler write a separate `create` body for each combination of argument types, so the cost is again
in the **compile** kind.

#### Packs and Class Templates

A pack is found not only in functions but also in class templates. `std::tuple<int, double, char>`
is an example. We can write an empty class that carries our own type list and ask for the number of
elements with `sizeof...`; the class itself holds no value, it only names the types.

```cpp
// list.cpp — a class template that carries a type list
#include <cstdio>
#include <type_traits>

template <typename... T>
struct TypeList {
    static constexpr int size = static_cast<int>(sizeof...(T));
};

template <typename L>
struct SizeOf;

template <typename... T>
struct SizeOf<TypeList<T...>> {
    static constexpr int value = sizeof...(T);
};

static_assert(TypeList<int, char>::size == 2);
static_assert(SizeOf<TypeList<>>::value == 0);

int main() {
    using L = TypeList<int, double, char>;
    std::printf("size %d %d\n", L::size, SizeOf<L>::value);
    std::printf("empty %d\n", TypeList<>::size);
    return 0;
}
```

```text
size 3 3
empty 0
```

**MT17.** `TypeList<>` is an empty pack and is valid; `sizeof...` gives zero. The `SizeOf` partial
specialization collects the pack back with the `TypeList<T...>` pattern: the partial specialization
of the previous lesson, this time with a pack. There is no run-time cost, because the two
`static_assert`s and the members are fixed at compile time.

#### Storing a Pack: tuple, apply and index_sequence

A pack cannot be stored directly; it cannot be assigned to a variable or put in a container. To
store it, the standard library gives `std::tuple`: it gathers elements of different types into a
single value. `std::apply` expands the elements of a tuple as the arguments of a function, which
builds a bridge between a tuple and a pack. If the elements need to be reached by index,
`std::index_sequence<I...>` produces the sequence `0, 1, 2, ...` at compile time as a pack. These
three tools process the elements of a pack together with their positions without writing a
recursion.

```cpp
// tuple.cpp — tuple, apply and index_sequence
#include <cstdio>
#include <tuple>
#include <type_traits>
#include <utility>

template <typename T, std::size_t... I>
long weighted(const T& t, std::index_sequence<I...>) {
    return (((static_cast<long>(I) + 1) * std::get<I>(t)) + ...);
}

template <typename... A>
long weighted_sum(A... a) {
    auto t = std::make_tuple(a...);
    return weighted(t, std::index_sequence_for<A...>{});
}

int main() {
    auto t = std::make_tuple(2, 3, 4);
    long plain = std::apply([](auto... e) { return (0L + ... + e); }, t);
    std::printf("apply %ld\n", plain);
    std::printf("weighted %ld\n", weighted_sum(2, 3, 4));
    using second = std::tuple_element_t<1, std::tuple<int, double, char>>;
    std::printf("type %d\n", std::is_same_v<second, double>);
    return 0;
}
```

```text
apply 9
weighted 20
type 1
```

**MT18.** `std::apply` expands the tuple, and the fold expression gives the sum `2 + 3 + 4`.
`weighted` multiplies each element by its position number: `1*2 + 2*3 + 3*4`. `index_sequence_for<A...>`
produces a sequence of the same length as the pack, and `I...` is expanded together with `A...`
using this sequence. In the third line, `tuple_element_t<1, ...>` selects the second type from the
pack; it is expected to be `double`, and the query confirms it. All of it is resolved at compile time
and makes the compiler write a separate body for every different element count, so it is again in
the **compile** kind.

A pack has limits too. An empty `std::tuple<>` is valid, but an empty pack has no position such as
`[0]`. Pack expansion can be done only inside a pattern; a bare `x...` is not an expression on its
own. In a class template, the pack parameter must be the last parameter. In a function template a
parameter may follow the pack, but that parameter must be deducible or carry a default argument; an
order such as `template <typename... A, typename B>` cannot be used if `B` cannot be deduced. That the
pack is written together with a first element (`First, Rest...`) in recursive expansion rests on a
different reason: separating the first element and recursing on the rest.

#### The Bounding Measurement

The number of bodies depends not on the number of calls but on the **type list**. A second call
with the same type list uses the existing bodies; a call with different types produces new ones.

```cpp
// pack-reuse.cpp — the same type list reuses bodies
#include <cstdio>

#include "sum.hpp"

int main() {
    sum_rec(1, 2, 3);
    sum_fold(1, 2, 3);
    std::printf("first      recursive %d fold %d\n", rec_bodies, fold_bodies);

    sum_rec(4, 5, 6);
    sum_fold(4, 5, 6);
    std::printf("second     recursive %d fold %d\n", rec_bodies, fold_bodies);

    sum_rec(1, 2, 3L);
    sum_fold(1, 2, 3L);
    std::printf("new types  recursive %d fold %d\n", rec_bodies, fold_bodies);
    return 0;
}
```

```text
first      recursive 4 fold 1
second     recursive 4 fold 1
new types  recursive 7 fold 2
```

**MT19.** The `(4, 5, 6)` calls are also an `int, int, int` list: the body counts do not change,
four to four. `(1, 2, 3L)` is a new type list: `<int,int,long>`, `<int,long>` and `<long>` produce
three new recursive bodies, taking the count from four to seven; the base function stays the same.
On the fold side too, the new list adds one new body. For this reason the number is not the
measurement itself; it is the evidence that shows which kind the cost is written to: recursive
expansion makes the compiler write new bodies as type variety grows, and this cost stays in the
**compile** kind.

#### Summary

- The mechanism measured in this lesson moves the cost to the **compile** kind: expanding a pack
  produces a different number of bodies depending on the expansion method.
- `typename... T` is a parameter pack; `sizeof...(T)` gives the element count at compile time, and
  `x...` expands the pack.
- Recursive expansion needs a separate template body at every step and a base case
  (`recursive=4`); a fold expression needs a single body for the same job (`fold=1`).
- A unary fold accepts an empty pack only with `&&`, `||` and `,`; a binary fold carries an initial
  value.
- The same type list reuses bodies (4 to 4); a new type list produces new bodies (4 to 7).

#### Next Step

In this lesson pack expansion made the compiler write bodies according to the type list, and the
cost stayed at compile time. The next lesson covers the tools that put questions to a type itself,
type traits: when a choice is made inside a template with `if constexpr`, how many queries does it
leave at run time?

### Type Traits

Source: https://academia.sh/en/courses/cpp-templates/type-traits

Standard type traits, selection at compile time with if constexpr, static_assert, writing your own type trait, and the selection leaving zero queries at run time.

The previous lesson counted how many bodies pack expansion makes the compiler write. When a template
has to look at a type and change its behavior, a second question comes up: when is that look taken,
and who pays for it? A **type trait** is a small template that answers a question about a type during
compilation. The claim of the lesson is this: when the selection is made at compile time, no query is
left at run time. The cost stays in the **compile** kind and carries a product count beside it.

This distinction answers a different question from M11/K01. K01 asked who makes a decision; this
course asks who pays the cost of a mechanism and what it is counted with. K01's `compiler` kind named
a decision. The **compile** kind here names a cost, and always carries a product count beside it.

#### Queries and Transformations

`<type_traits>` provides two kinds of traits. **Queries** produce a `bool`: `std::is_integral_v<T>`
is true if the type is an integer type, and `std::is_same_v<A, B>` is true if two types are
identical. **Transformations** produce a new type: `std::remove_cvref_t<T>` strips the `const`,
`volatile` and reference qualifiers from a type; `std::conditional_t<K, A, B>` becomes `A` if the
condition is true and `B` otherwise. The suffixed `_v` and `_t` forms are shorthand for writing
`::value` and `::type`. All of them are evaluated at compile time.

```cpp
// traits.cpp — queries and transformations
#include <cstdio>
#include <string>
#include <type_traits>

int main() {
    std::printf("integral %d %d %d\n", std::is_integral_v<int>,
                std::is_integral_v<double>, std::is_integral_v<bool>);
    std::printf("same %d %d\n", std::is_same_v<int, int>,
                std::is_same_v<int, long>);
    std::printf("strip %d %d\n",
                std::is_same_v<std::remove_cvref_t<const int&>, int>,
                std::is_same_v<std::remove_cvref_t<std::string&&>, std::string>);
    using selected = std::conditional_t<(sizeof(int) >= 2), int, long>;
    std::printf("condition %d\n", std::is_same_v<selected, int>);
    return 0;
}
```

```text
integral 1 0 1
same 1 0
strip 1 1
condition 1
```

`bool` is an integer type, so the third query is true. When `const int&` is stripped, it becomes
`int`; the reference qualifier (`&&`) is stripped as well. `conditional_t` selects a type, not a
value: here `selected` is equal to `int`. This output is guaranteed by the standard; the result of
the first two queries does not change in any implementation.

#### Selection with if constexpr

The way to use a query result to select a branch is `if constexpr`. The condition is evaluated at
compile time, and **the discarded branch is not compiled in that instantiation**. An ordinary `if`,
on the other hand, compiles both branches; if you write `x.size()` in one branch and give `int` as
`T`, compilation stops even if that branch never runs. `if constexpr` solves this problem: if `T` is
an integer, the compiler does not look at the `.size()` branch.

Below, `kind_of` gives every type a label. `kind_tagged` does the same job with a run-time
parameter, that is, with a decision supplied while running, and counts a query on every call.

```cpp
// kind.hpp — selection at compile time and at run time
#ifndef KIND_HPP
#define KIND_HPP

#include <string>
#include <type_traits>

inline int queries = 0;
inline int tagged_queries = 0;

template <typename T>
const char* kind_of(T) {
    if constexpr (std::is_integral_v<T>) {
        return "integer";
    } else if constexpr (std::is_floating_point_v<T>) {
        return "floating";
    } else {
        return "other";
    }
}

template <typename T>
const char* kind_tagged(T, int tag) {
    ++tagged_queries;
    if (tag == 0) {
        return "integer";
    }
    if (tag == 1) {
        return "floating";
    }
    return "other";
}

template <typename T>
long length(T x) {
    if constexpr (std::is_same_v<std::remove_cvref_t<T>, std::string>) {
        return static_cast<long>(x.size());
    } else {
        return static_cast<long>(x);
    }
}

#endif
```

```cpp
// kind-select.cpp — same result, different query count
#include <cstdio>
#include <string>

#include "kind.hpp"

int main() {
    int same = 0;
    same += std::string(kind_of(1)) == kind_tagged(1, 0);
    same += std::string(kind_of(2L)) == kind_tagged(2L, 0);
    same += std::string(kind_of('a')) == kind_tagged('a', 0);
    same += std::string(kind_of(1.5)) == kind_tagged(1.5, 1);
    same += std::string(kind_of(2.5f)) == kind_tagged(2.5f, 1);
    same += std::string(kind_of(std::string("x"))) == kind_tagged(std::string("x"), 2);
    std::printf("same=%d queries=%d tagged=%d\n", same, queries, tagged_queries);
    std::printf("length %ld %ld\n", length(std::string("abcd")), length(7));
    return 0;
}
```

```text
same=6 queries=0 tagged=6
length 4 7
```

**MT20.** In all six calls the two methods give the same label (`same=6`). `kind_of` makes no
query at run time (`queries=0`): which branch is selected has been decided in the compiler, and a
single `return` is left in each instantiation. `kind_tagged` reads a tag on every call
(`tagged=6`). This row is the `if constexpr selection` measurement in the core. `length` also shows
why the discarded branch is not compiled: for `int` there is no `x.size()` branch, and for `string`
there is no `static_cast<long>(x)` branch. With a plain `if`, both would be compile errors.

#### static_assert and Constraints

`static_assert(condition, "message")` checks the condition at compile time. If the condition is
false, compilation stops and the message appears in the compiler output; if it is true, no code is
generated. The failure is described in prose here, because code that does not compile is not written
as a block: instantiating a template that contains `static_assert(std::is_integral_v<T>)` with
`double` stops compilation; compilers usually show, next to the message, where the instantiation was
requested from. This way, a wrong use is caught at compile time instead of as an error at run time.

#### Writing Your Own Type Trait

The standard traits are built on `std::true_type` and `std::false_type`. Both have a `::value`
member. To write your own trait, the **primary template** derives from `false_type`, and the
**partial specialization** for the type you are interested in derives from `true_type`.

```cpp
// custom-trait.cpp — a custom type trait
#include <cstdio>
#include <string>
#include <type_traits>
#include <vector>

template <typename T>
struct is_vector : std::false_type {};

template <typename U>
struct is_vector<std::vector<U>> : std::true_type {};

template <typename T>
inline constexpr bool is_vector_v = is_vector<T>::value;

static_assert(is_vector_v<std::vector<int>>, "a vector is a vector");
static_assert(!is_vector_v<int>, "an int is not a vector");

int main() {
    std::printf("is_vector %d %d %d\n", is_vector_v<std::vector<double>>,
                is_vector_v<std::string>, is_vector_v<int>);
    return 0;
}
```

```text
is_vector 1 0 0
```

The partial specialization from the Template Specialization lesson is put to work here: if the
`std::vector<U>` pattern matches, `true_type` is chosen, and if none matches, the primary template
remains. As seen in that lesson, a specialization has to be visible before the first use. The two
`static_assert`s generate no code in this file; if the program compiled, both of them passed.

#### Relations Between Types

Some queries look not at a single type but at the relation between two types.
`std::is_base_of_v<B, D>` is true if `D` derives from `B`. `std::is_convertible_v<A, B>` asks
whether a value of `A` can be implicitly converted to `B`. `std::is_trivially_copyable_v<T>` says
whether the type can be copied with a memory copy; since a `std::string` carries ownership inside it,
it gives `false` to this question: its copy is made not byte by byte but by its own copy constructor.
`std::decay_t<T>` performs the type conversion that happens when a value is passed to a function by
value: it strips the reference and the `const`, and turns an array type into a pointer.

```cpp
// relations.cpp — type relations and decay
#include <cstdio>
#include <string>
#include <type_traits>

struct Base {};
struct Derived : Base {};

int main() {
    std::printf("base %d %d\n", std::is_base_of_v<Base, Derived>,
                std::is_base_of_v<Derived, Base>);
    std::printf("convert %d %d\n", std::is_convertible_v<int, double>,
                std::is_convertible_v<std::string, int>);
    std::printf("copy %d %d\n", std::is_trivially_copyable_v<int>,
                std::is_trivially_copyable_v<std::string>);
    std::printf("decay %d %d\n",
                std::is_same_v<std::decay_t<const int&>, int>,
                std::is_same_v<std::decay_t<int[3]>, int*>);
    return 0;
}
```

```text
base 1 0
convert 1 0
copy 1 0
decay 1 1
```

**MT21.** `is_base_of` is directional: `Derived` derives from `Base`, and the reverse is not true.
`int` converts to `double`; `std::string` does not convert to `int`. `int` can be copied with a
memory copy, while `std::string` cannot. `decay_t<int[3]>` reduces the array type to `int*`. All of
these queries are answered at compile time; the lines in the output are the answers that compilation
produced, not a duration. None of them leaves a query at run time: for `int` and `std::string` the
values are already in the compiler's hands.

#### Writing Your Own Transformation

Transformations are written with the same pattern. The primary template leaves the type as it is, and
partial specializations strip a pattern. The standard `std::remove_pointer_t` strips one layer of
pointer; here we build a recursive version that strips all the layers, together with a `_t` alias.
The `::type` member defined with `using` takes the place of the standard library's `::type`.

```cpp
// strip.cpp — a custom transformation trait
#include <cstdio>
#include <type_traits>

template <typename T>
struct strip_pointer {
    using type = T;
};

template <typename T>
struct strip_pointer<T*> {
    using type = typename strip_pointer<T>::type;
};

template <typename T>
using strip_pointer_t = typename strip_pointer<T>::type;

static_assert(std::is_same_v<strip_pointer_t<int>, int>);
static_assert(std::is_same_v<strip_pointer_t<int*>, int>);

int main() {
    std::printf("strip %d %d %d\n", std::is_same_v<strip_pointer_t<char**>, char>,
                std::is_same_v<strip_pointer_t<const int*>, const int>,
                std::is_same_v<strip_pointer_t<double>, double>);
    return 0;
}
```

```text
strip 1 1 1
```

**MT22.** The partial specialization strips one layer of pointer and descends to the remaining type
by calling itself: `char**` becomes `char` in two steps. This recursion lives inside the compiler;
it makes the compiler write one instantiation for each layer and leaves no trace at run time. One
point to watch is the `const int*` example: it is not the pointer itself but the type it points to
that is `const int`, so the result stays `const int`. The `const`ness of the pointer itself is in a
different position, and this pattern does not look at it.

#### Combining Type Traits with Constraints

Type traits can be asked not only one at a time but also together. If we want a function to work only
for an unsigned integer type, we check several traits together with `static_assert`:
`std::is_integral_v<T> && std::is_unsigned_v<T>`. Conditions that can be combined with logical
operators can also be written with `std::conjunction_v`, `std::disjunction_v` and `std::negation_v`;
this second form short-circuits, that is, it does not instantiate the later traits once the condition
is settled.

```cpp
// combine.cpp — combining traits
#include <cstdio>
#include <type_traits>

template <typename T>
constexpr bool unsigned_integer_v = std::is_integral_v<T> && std::is_unsigned_v<T>;

template <typename T>
constexpr bool non_numeric_v =
    std::conjunction_v<std::negation<std::is_integral<T>>,
                       std::negation<std::is_floating_point<T>>>;

int main() {
    std::printf("unsigned %d %d %d\n", unsigned_integer_v<unsigned>,
                unsigned_integer_v<int>, unsigned_integer_v<double>);
    std::printf("non_numeric %d %d\n", non_numeric_v<int>,
                non_numeric_v<const char*>);
    return 0;
}
```

```text
unsigned 1 0 0
non_numeric 0 1
```

**MT23.** `unsigned` is both an integer and unsigned, `int` is signed, and `double` is not an
integer. `non_numeric_v` is true only for types that are neither integer nor floating point: false
for `int`, true for a pointer. What is worth recording here is that these combinations too are
resolved entirely in the compiler; no trace is left at run time, and the cost is again in the
**compile** kind.

#### The Return Type Is Selected Too

The branches of `if constexpr` can return values of different types; the discarded branch does not
take part in return type deduction. For this reason an `auto` return type sees a single `return` in
every instantiation. Returning `long` and `double` in the same function with an ordinary `if` is a
compile error, because the two `return`s deduce different types. If we want to write the return type
explicitly, `std::conditional_t` computes a type name.

```cpp
// return-type.cpp — return type by branch
#include <cstdio>
#include <type_traits>

template <typename T>
auto twice(T x) {
    if constexpr (std::is_integral_v<T>) {
        return x * 2L;
    } else {
        return x * 2.0;
    }
}

template <typename T>
using wide_t = std::conditional_t<std::is_integral_v<T>, long long, double>;

int main() {
    std::printf("twice %d %d\n",
                std::is_same_v<decltype(twice(1)), long>,
                std::is_same_v<decltype(twice(1.5f)), double>);
    std::printf("wide %d %d\n", std::is_same_v<wide_t<short>, long long>,
                std::is_same_v<wide_t<float>, double>);
    std::printf("value %ld %.1f\n", twice(21), twice(1.25f));
    return 0;
}
```

```text
twice 1 1
wide 1 1
value 42 2.5
```

**MT24.** `twice(1)` selects the integer branch and returns `long`; `twice(1.5f)` selects the other
branch and returns `double`. The two return types live in two instantiations of a single function, and
they have separate bodies. `wide_t` moves the same decision into a type alias. The `short` and
`float` arguments in the second line fall into separate branches as an integer and a floating-point
type. Because the selection ends at compile time, it leaves no branch query at run time.

If you want to forbid unsupported types with a `static_assert` in an `else` branch, the condition has
to depend on `T`; a condition that does not depend on it may be evaluated when the template is
defined, even if that branch is never selected, and may stop compilation. For this reason, in such
branches use a type trait that ties the condition to `T`.

#### The Bounding Measurement

A decision made at compile time leaves no step at run time, but writing `constexpr` alone does not
guarantee this. A `constexpr` function means it can be called both at compile time and at run time.
The context decides which one it will be: the initial value of a `constexpr` variable, or a context
that requires constant evaluation such as `static_assert`, moves the evaluation to compile time.
`std::is_constant_evaluated()` tells these two cases apart.

```cpp
// constant-evaluation.cpp — the same constexpr function, two contexts
#include <cstdio>
#include <type_traits>

inline int steps = 0;

constexpr int sum_of_squares(int n) {
    int t = 0;
    for (int i = 1; i <= n; ++i) {
        if (!std::is_constant_evaluated()) {
            ++steps;
        }
        t += i * i;
    }
    return t;
}

int main() {
    constexpr int a = sum_of_squares(10);
    std::printf("compile  result=%d steps=%d\n", a, steps);

    volatile int n = 10;
    int b = sum_of_squares(n);
    std::printf("run      result=%d steps=%d\n", b, steps);
    return 0;
}
```

```text
compile  result=385 steps=0
run      result=385 steps=10
```

**MT25.** The same function gives the same result; the call assigned to a `constexpr` variable is
evaluated at compile time and does not touch the counter (`steps=0`). A `volatile` argument, on the
other hand, prevents the compiler from knowing the value; the call is made at run time and ten
iterations are counted (`steps=10`). For this reason `constexpr` is not a promise but a permission:
what moves the cost to compile time is a context that requires constant evaluation. The number is
the evidence for the classification; the answer to the measurement question is a kind name, and here
that name is the **compile** kind.

#### Summary

- The mechanism measured in this lesson moves the cost to the **compile** kind: the type query and
  the selection of the branch end at compile time, and `queries=0` is left at run time.
- Queries (`is_integral_v`, `is_same_v`) give a `bool`; transformations (`remove_cvref_t`,
  `conditional_t`) give a type.
- `if constexpr` does not compile the discarded branch in that instantiation; a plain `if` compiles
  both branches.
- A custom type trait is built by having the primary template derive from `false_type` and the
  partial specialization from `true_type`; `static_assert` stops a wrong use at compile time.
- `constexpr` does not guarantee the move: the same function gives `steps=0` in constant evaluation
  and `steps=10` at run time.

#### Next Step

In this lesson the type query pulled the selection to compile time and left zero queries at run time.
The next lesson takes the same query one step back: how does the compiler eliminate a candidate
template that is not viable without raising an error, and what does overload resolution choose after
this elimination?

### Overload Resolution and SFINAE

Source: https://academia.sh/en/courses/cpp-templates/overload-resolution-and-sfinae

Candidates and viable candidates, the contest between a template and a non-template function, candidate elimination with enable_if_t, detection with void_t, and constraints with C++20 concepts.

The previous lesson showed how to look at a type and select a branch: the decision was made inside an
`if constexpr`. One step earlier there is another question. When several functions share a name, which
one does the compiler call, and what happens to a template that does not fit in the candidate list?
This lesson measures how a call is chosen and how a template is eliminated without an error when it
meets the wrong type. The selection ends at compile time, and the cost is again in the **compile**
kind.

#### Candidate, Viable Candidate, Best Candidate

For a function call, the compiler goes through three stages. First it collects every function and
function template visible under the called name as a **candidate**. Then it moves the ones whose
argument count and conversions fit into the list of **viable candidates**. Finally, the one that best
fits the arguments among the viable candidates is chosen as the **best candidate**. If two candidates
remain equally good and no tie-breaking rule favors one of them, the call is ambiguous and
compilation stops.

If a template and a non-template function compete on equal terms, the non-template function wins. But
if the template matches the argument type exactly while the non-template function needs a conversion,
the template wins, because an exact match is better than a conversion.

```cpp
// overload.cpp — template and non-template candidates
#include <cstdio>
#include <string>

const char* pick(int) { return "int"; }
const char* pick(double) { return "double"; }

template <typename T>
const char* pick(T) { return "template"; }

int main() {
    std::printf("pick(1)      %s\n", pick(1));
    std::printf("pick(1.5)    %s\n", pick(1.5));
    std::printf("pick('a')    %s\n", pick('a'));
    std::printf("pick(2.5f)   %s\n", pick(2.5f));
    std::printf("pick(string) %s\n", pick(std::string("x")));
    return 0;
}
```

```text
pick(1)      int
pick(1.5)    double
pick('a')    template
pick(2.5f)   template
pick(string) template
```

For `pick(1)` and `pick(1.5)`, the non-template function is an exact match and wins the tie. `'a'` is
a `char`; the `int` candidate needs an integral promotion, while the template matches exactly with
`T = char`, so the template wins. The same holds for `float`. For `string`, only the template is a
viable candidate.

#### SFINAE: Substitution Failure Is Not an Error

After the template argument is deduced, the compiler puts the deduced type into the template's
declaration. If this substitution produces an invalid type or expression, that template silently drops
out of the candidate list and compilation raises no error. The principle is known as **SFINAE**:
substitution failure is not an error. An error is raised only if no candidate remains.

The classic way to use SFINAE on purpose is `std::enable_if_t<condition, type>`: if the condition is
true it is equal to `type`, and if it is false the substitution fails and the template is eliminated.
It is usually placed in the type of a non-type template parameter, and that parameter is given a
default value such as `= 0`.

```cpp
// enable-if.cpp — candidate elimination with enable_if_t
#include <cstdio>
#include <type_traits>

template <typename T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
const char* category(T) { return "integer"; }

template <typename T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
const char* category(T) { return "floating"; }

int main() {
    std::printf("category(7)   %s\n", category(7));
    std::printf("category(2.5) %s\n", category(2.5));
    return 0;
}
```

```text
category(7)   integer
category(2.5) floating
```

**MT26.** For `category(7)`, the declaration of the second template becomes `enable_if_t<false, int>`,
the substitution fails, and the second candidate is eliminated; `integer` remains. For `category(2.5)`
it is the reverse. The signatures of the two templates look the same, but the types of their template
parameters depend on different conditions, so the signatures differ and there is no clash. The
selection is made at compile time and leaves no query at run time.

#### Conversion Ranking

What "best" means among viable candidates depends on the conversion that binds the argument to each
candidate. Conversions rank from best to worst as follows: exact match, integral or floating-point
promotion, standard conversion, user-defined conversion, and last the ellipsis parameter. A candidate
is best if it is not worse than the others on any argument and is better on at least one. If two
candidates cannot beat each other, the call is ambiguous and compilation stops; I describe this error
in prose, because code that does not compile is not written as a block.

```cpp
// ranking.cpp — conversion ranking
#include <cstdio>

const char* h(int) { return "int"; }
const char* h(long) { return "long"; }
const char* h(double) { return "double"; }

const char* g(long) { return "long"; }
const char* g(...) { return "ellipsis"; }

int main() {
    short s = 1;
    std::printf("h('a')  %s\n", h('a'));
    std::printf("h(s)    %s\n", h(s));
    std::printf("h(1.5f) %s\n", h(1.5f));
    std::printf("h(2L)   %s\n", h(2L));
    std::printf("g(1)    %s\n", g(1));
    std::printf("g(1.5)  %s\n", g(1.5));
    return 0;
}
```

```text
h('a')  int
h(s)    int
h(1.5f) double
h(2L)   long
g(1)    long
g(1.5)  long
```

**MT27.** The `char` and `short` arguments bind to `int` by promotion, and a promotion is better than
a standard conversion to `long`; so both choose the `int` candidate. `float` binds to `double` by
promotion. For `2L`, `long` is an exact match. For `g(1)`, a standard conversion to `long` competes
with the ellipsis: the conversion wins. For `g(1.5)` there is also a standard conversion from `double`
to `long`, and it is better than the ellipsis. The standard determines this ranking; the output only
confirms it.

#### Ordering Candidates with a Priority Tag

If more than one of the candidates eliminated with `enable_if` is viable at the same time, the call
becomes ambiguous. An old method for establishing priority is to build a derivation chain of tag
types. `priority<2>` derives from `priority<1>`, and that from `priority<0>`. Each candidate takes a
different tag as its last parameter, and the call is made with the highest tag: the exact match is the
highest tag, the eliminated ones drop out of the list, and among the rest the one with the shortest
derivation distance is chosen.

```cpp
// priority.cpp — candidate order by tag
#include <cstdio>
#include <string>
#include <type_traits>
#include <utility>

template <int N>
struct priority : priority<N - 1> {};
template <>
struct priority<0> {};

template <typename T>
auto classify(const T& x, priority<2>) -> decltype(x.size(), "sized") {
    return "sized";
}

template <typename T, std::enable_if_t<std::is_pointer_v<T>, int> = 0>
const char* classify(const T&, priority<1>) { return "pointer"; }

template <typename T>
const char* classify(const T&, priority<0>) { return "generic"; }

template <typename T>
const char* classify(const T& x) { return classify(x, priority<2>{}); }

int main() {
    int n = 3;
    std::printf("string  %s\n", classify(std::string("ab")));
    std::printf("pointer %s\n", classify(&n));
    std::printf("int     %s\n", classify(n));
    return 0;
}
```

```text
string  sized
pointer pointer
int     generic
```

**MT28.** For `std::string`, two candidates are viable, because the pointer candidate is eliminated by
`enable_if`; `priority<2>` is the highest tag and needs no derivation step, so `sized` wins. For
`int*`, the `size()` query fails in the declaration, the first candidate is eliminated, and the
`priority<1>` candidate is chosen. For `int`, both are eliminated and `generic` remains. C++17
`if constexpr` and C++20 concepts replace this chain; but the tag method is still common in old code,
so it has to be readable.

#### Detection with void_t

`enable_if` writes a condition out explicitly. Sometimes the question is whether an expression is
valid for a type. `std::void_t<...>` ties this question to SFINAE: whatever its arguments are, it
becomes `void`, but if one of the arguments is invalid, the substitution fails. The primary template
derives from `false_type`; the partial specialization tries the expression inside `void_t`.

```cpp
// divisible.cpp — detection with void_t
#include <cstdio>
#include <string>
#include <type_traits>
#include <utility>

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 {};

int main() {
    std::printf("divisible<int>         %s\n", divisible<int>::value ? "yes" : "no");
    std::printf("divisible<double>      %s\n", divisible<double>::value ? "yes" : "no");
    std::printf("divisible<std::string> %s\n", divisible<std::string>::value ? "yes" : "no");
    return 0;
}
```

```text
divisible<int>         yes
divisible<double>      yes
divisible<std::string> no
```

The expression `std::declval<T>() / 2` is valid for `int` and invalid for `std::string`. If it is
invalid, the partial specialization is eliminated and the primary template remains. This is the answer
to the question asked at the start of the lesson: a candidate that does not fit raises no error; it
drops out of the candidate list.

#### C++20: Concepts and requires

`enable_if` and `void_t` do the job but are hard to read. C++20 brought **concepts** and the
`requires` expression to write the same constraint directly. If a **constraint** is not satisfied, the
template is not a candidate, and in the error message compilers usually show the unsatisfied
constraint instead of a long substitution dump.

```cpp
// concept.cpp — constraint with requires
#include <cstdio>
#include <string>

template <typename T>
concept Divisible = requires(T x) { x / 2; };

template <Divisible T>
const char* half(T) { return "divisible"; }

const char* half(...) { return "indivisible"; }

int main() {
    std::printf("half(8)   %s\n", half(8));
    std::printf("half(str) %s\n", half(std::string("x")));
    return 0;
}
```

```text
half(8)   divisible
half(str) indivisible
```

The constrained template is a viable candidate for `int`, and it wins because the ellipsis candidate
is less good. For `std::string`, the constraint is not satisfied, the template is eliminated, and the
ellipsis candidate remains. A concept names a query; the selection still ends at compile time.

#### The Body of an Eliminated Candidate Is Not Written

A count shows where the cost of SFINAE lies. If a candidate is eliminated, its body is never
instantiated. Below, the bodies of two candidates are recorded with a local `static`; a body that is
not called leaves no record.

```cpp
// body-count.cpp — body of an eliminated candidate
#include <cstdio>
#include <type_traits>

inline int integer_bodies = 0;
inline int floating_bodies = 0;

template <typename T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
int twice(T x) {
    static const bool record = (++integer_bodies, true);
    (void)record;
    return static_cast<int>(x) * 2;
}

template <typename T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
int twice(T x) {
    static const bool record = (++floating_bodies, true);
    (void)record;
    return static_cast<int>(x * 2);
}

int main() {
    twice(7);
    twice(8);
    twice(9L);
    std::printf("integer=%d floating=%d\n", integer_bodies, floating_bodies);
    twice(2.5);
    std::printf("integer=%d floating=%d\n", integer_bodies, floating_bodies);
    return 0;
}
```

```text
integer=2 floating=0
integer=2 floating=1
```

**MT29.** After three integer calls, only integer bodies exist: one for `int` and one for `long`, so
two bodies; the floating body count is zero. Then a `double` call makes the floating body count one.
The eliminated candidate has dropped out of the list and its body was never written; for this reason
the cost of SFINAE is only the elimination itself. The numbers are a product count, not a duration.

#### Ordering with Concepts: Subsumption

C++20 resolution with concepts chooses the more constrained one if two constrained versions of the
same candidate are viable. If one concept includes another (`std::signed_integral` subsumes
`std::integral`), the subsuming concept is more specialized. This rule replaces the tag chain: the
order comes from the structure of the concepts themselves.

```cpp
// constraint-order.cpp — concept subsumption
#include <concepts>
#include <cstdio>

template <typename T>
const char* grade(T) { return "general"; }

template <std::integral T>
const char* grade(T) { return "integer"; }

template <std::signed_integral T>
const char* grade(T) { return "signed"; }

int main() {
    std::printf("grade(1)   %s\n", grade(1));
    std::printf("grade(1u)  %s\n", grade(1u));
    std::printf("grade(1.5) %s\n", grade(1.5));
    return 0;
}
```

```text
grade(1)   signed
grade(1u)  integer
grade(1.5) general
```

**MT30.** `int` is both `integral` and `signed_integral`; the more constrained one, `signed`, is
chosen. `unsigned` is only `integral`, so `integer` remains. `double` satisfies neither, so `general`
remains. This selection is again made at compile time and leaves no query at the call site. The cost
is in the **compile** kind; only the collecting of candidates and the checking of constraints are
added to the compiler's work.

#### The Bounding Measurement

SFINAE covers only substitution errors in the **immediate context** of the declaration: errors that
arise directly while the return type, the parameter types, and the template parameters are written.
If another template has to be instantiated in the meantime and the error arises inside it, there is
no elimination and compilation stops. The body of a function is instantiated after the candidate is
chosen. An error in the body no longer eliminates from the candidate list; it stops compilation. For
example, if a template that writes the call `x.size()` in its body is called with `int`, the compiler
counts that template as a viable candidate, chooses it, raises an error while instantiating the body,
and compilation stops.

When the same call is moved into the declaration, it turns into elimination. The version below makes
the `size()` query in the return type.

```cpp
// declaration.cpp — query in the declaration, body without error
#include <cstdio>
#include <string>

template <typename T>
auto size_of(const T& x) -> decltype(x.size(), long()) {
    return static_cast<long>(x.size());
}

long size_of(...) { return -1; }

int main() {
    std::printf("string %ld\n", size_of(std::string("abcd")));
    std::printf("int    %ld\n", size_of(7));
    return 0;
}
```

```text
string 4
int    -1
```

**MT31.** For `std::string`, the return type is valid and the template is chosen. For `int`, `x.size()`
is invalid, the substitution fails, and the ellipsis candidate remains. Had the same query been in the
body, compilation would have stopped. For this reason the number is the evidence of the elimination
event; the answer to the measurement question is the stage at which this elimination takes place:
**compile**.

#### Summary

- The mechanism measured in this lesson moves the cost to the **compile** kind: collecting candidates,
  eliminating the viable ones, and choosing the best candidate end at compile time, and no query is
  left at run time.
- Candidate, viable candidate, and best candidate are collected, eliminated, and chosen in that
  order; on a tie the non-template function wins, and an exact match beats a conversion.
- In SFINAE, substitution failure is not an error: with `enable_if_t`, `category(7)` selects integer
  and `category(2.5)` selects floating.
- `void_t` detects the validity of an expression: `divisible<int>` yes, `divisible<std::string>` no.
- C++20 `concept` and `requires` write the same constraint readably; SFINAE covers only the
  declaration, and an error in the body stops compilation.

#### Next Step

In this lesson candidate elimination ended at compile time and left no query at run time. The next
lesson applies this idea to a class hierarchy: if a template is used instead of a virtual function,
dispatch moves to compile time, but a separate body is written for every type. What is the measure of
this trade?

### Static Polymorphism

Source: https://academia.sh/en/courses/cpp-templates/static-polymorphism

Dispatch at compile time with CRTP, the contrast with the virtual function version, policy classes and mixins, a static interface constrained by a concept, and selection returning to run time with variant.

The previous lesson moved candidate elimination to compile time: a template that did not fit dropped
out of the list without an error. This lesson applies the same idea to a class hierarchy. If a base
class knows at compile time which derived class it works with, there is no need to choose the call
while running. This is **static polymorphism**. Our question is who pays the cost of this selection:
when the decision is made at compile time, what is added to the compiler, and what drops out of the
run?

M11/K04 treated dynamic polymorphism with virtual functions: a single interface, a body chosen while
running. The "separate body for every type" seen in Rust in M10/K03 is the same concept; this lesson
does not compare the two languages. This lesson does not establish a superiority either. Both methods
pay at a different place for a single call. On the static side a separate body is written for every
derived type, and this cost is in the **compile** kind; on the dynamic side the compiler does not
produce bodies per type, there are only as many bodies as derived classes written, and the selection
is made while running.

#### CRTP: The Base Knowing the Derived Class

**CRTP** (Curiously Recurring Template Pattern) does the following: the base class is a class
template, and its parameter is the derived class itself. `Square` derives from `Shape<Square>`. The
base converts itself to the derived type with `static_cast<const D&>(*this)` and calls the derived
class's function. There is no virtual function: which body will be called is known at compile time.

```cpp
// shape.hpp — CRTP base and two derived classes
#ifndef SHAPE_HPP
#define SHAPE_HPP

inline int bodies = 0;

template <typename D>
struct Shape {
    long area() const {
        static const bool record = (++bodies, true);
        (void)record;
        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;
    long height;
    Rectangle(long w, long h) : width(w), height(h) {}
    long compute_area() const { return width * height; }
};

#endif
```

```cpp
// crtp.cpp — dispatch with crtp
#include <cstdio>

#include "shape.hpp"

int main() {
    Square a(3);
    Rectangle b(2, 5);
    Square c(4);
    long total = a.area() + b.area() + c.area();
    std::printf("total=%ld bodies=%d\n", total, bodies);
    return 0;
}
```

```text
total=35 bodies=2
```

**MT32.** The total is `9 + 10 + 16 = 35`. Because `Shape<D>::area` is instantiated for two
different types, there are two bodies: `Shape<Square>::area` and `Shape<Rectangle>::area`. The third
call (`Square(4)`) reuses the first body. The `dispatch with crtp` row in the core is this count:
three calls, two bodies. The cost has moved to the **compile** kind and carries a product count beside
it.

In this arrangement `Shape<D>` is not a single class but separate classes of a family; there is no
derivation relation between `Shape<Square>` and `Shape<Rectangle>`. `static_cast<const D&>(*this)` is
correct only if the object really is a `D`. If `D` does not derive from `Shape<D>` at all, the
conversion is rejected at compile time. But if a class derives from `Shape<B>` and writes another
derived class as `B`, the compiler cannot catch it: the object is not really that type, and the
behavior is undefined. For this reason making the constructor of the base class protected and marking
the derived class `final` are common defenses.

#### The Virtual Function Counterpart

We write the same computation with a virtual function. There is a single base class and two
derived classes; the bodies are written once, and the call is chosen while running through a base
reference. This selection is generally realized with a memory structure called the virtual function
table; here we do not print its size or contents, because what we measure is the number of bodies and
calls.

```cpp
// virtual.cpp — the same computation with a virtual function
#include <cstdio>
#include <memory>
#include <vector>

inline int virtual_bodies = 0;
inline int indirect_calls = 0;

struct VirtualShape {
    virtual ~VirtualShape() = default;
    virtual long area() const = 0;
};

struct VirtualSquare : VirtualShape {
    long side;
    explicit VirtualSquare(long s) : side(s) {}
    long area() const override {
        static const bool record = (++virtual_bodies, true);
        (void)record;
        return side * side;
    }
};

struct VirtualRectangle : VirtualShape {
    long width;
    long height;
    VirtualRectangle(long w, long h) : width(w), height(h) {}
    long area() const override {
        static const bool record = (++virtual_bodies, true);
        (void)record;
        return width * height;
    }
};

int main() {
    std::vector<std::unique_ptr<VirtualShape>> v;
    v.push_back(std::make_unique<VirtualSquare>(3));
    v.push_back(std::make_unique<VirtualRectangle>(2, 5));
    v.push_back(std::make_unique<VirtualSquare>(4));
    long total = 0;
    for (const auto& s : v) {
        ++indirect_calls;
        total += s->area();
    }
    std::printf("total=%ld bodies=%d indirect=%d\n", total, virtual_bodies, indirect_calls);
    return 0;
}
```

```text
total=35 bodies=2 indirect=3
```

**MT33.** The result is the same, a total of 35 and again two bodies, because two derived classes write
two bodies. The difference is in how the bodies are chosen: here all three of the three calls are
indirect through a base reference (`indirect=3`), and which body will run is determined while running.
In the CRTP version none of the three calls is indirect. These two rows tell the kinds apart: the
number of indirect calls is written to **run**, and a separate body per type is written to the
**compile** kind. Both are a product count; which one is faster is not claimed in this lesson.

#### Splitting into Components: Policy and Mixin

The second use of CRTP is to add behavior to a class. In this use, called a **mixin**, the base class
template adds a function to the derived class; the derived class builds its own interface by choosing
the base. A **policy class** is a class given as a template parameter that determines a part of the
behavior. Both make the selection at compile time.

```cpp
// mixin.cpp — mixin and policy class
#include <cstdio>

template <typename D>
struct Printable {
    void print() const {
        std::printf("%s area=%ld\n", D::name(), static_cast<const D&>(*this).area());
    }
};

struct MeterUnit {
    static long convert(long v) { return v * 100; }
};

struct CentimeterUnit {
    static long convert(long v) { return v; }
};

template <typename Unit>
struct Square : Printable<Square<Unit>> {
    long side;
    explicit Square(long s) : side(s) {}
    static const char* name() { return "square"; }
    long area() const { return Unit::convert(side) * Unit::convert(side); }
};

int main() {
    Square<CentimeterUnit> a(3);
    Square<MeterUnit> b(3);
    a.print();
    b.print();
    return 0;
}
```

```text
square area=9
square area=90000
```

**MT34.** `Printable<D>` adds the `print` function; `Square<Unit>` takes both the mixin base and the
policy parameter. With `CentimeterUnit` the area is 9, and with `MeterUnit` it is 90000. Each `Unit`
choice has a separate `Square` and a separate `print` body written. The more components a policy is
split into, the more the number of bodies can multiply by the number of combinations used; the cost of
this combination accumulates in the **compile** kind, and no selection is left while running.

#### A Static Interface Constrained by a Concept

In CRTP the interface is implicit: the base calls `compute_area`, but if the derived class does not
have this function, the error arises inside the body of the base class, and compilers generally show
it as a long instantiation message. C++20 concepts write the interface explicitly. The function below
accepts every type for which the `area()` call is valid and whose result can convert to `long`, and
checks the constraint at the call site.

```cpp
// interface.cpp — static interface constrained by a concept
#include <concepts>
#include <cstdio>

#include "shape.hpp"

template <typename T>
concept AreaShape = requires(const T& t) {
    { t.area() } -> std::convertible_to<long>;
};

template <AreaShape T>
long doubled(const T& s) { return s.area() * 2; }

struct NoArea {};

static_assert(AreaShape<Square>);
static_assert(AreaShape<Rectangle>);
static_assert(!AreaShape<NoArea>);

int main() {
    Square k(3);
    Rectangle d(2, 5);
    std::printf("doubled %ld %ld\n", doubled(k), doubled(d));
    return 0;
}
```

```text
doubled 18 20
```

**MT35.** `Square` and `Rectangle` satisfy the concept through the `area` member; `NoArea` does not, and
`static_assert` verifies this at compile time. The concept gives the calling side a contract: if the
constraint is not satisfied, the error arises at the call site, and compilers generally show the name
of the constraint. In addition, the concept adds no product count; the check ends during compilation
and writes nothing to the running code.

#### Default Behavior and Hiding

In a virtual function, the derived class redefines a function of the base class with the same
signature; in CRTP the arrangement is different. A default body is written in the base, and if the
derived class defines a function with the same name, it hides it, and because the base function
redirects the call to the derived class, it sees the derived class's body. Everything is resolved at
compile time: whichever scope the called name comes from, that body is chosen. Below, the `Describable`
base writes a default `describe`; `Circle` defines its own version and the call in the base goes to it.

```cpp
// default.cpp — default in the base, hiding in the derived
#include <cstdio>

template <typename D>
struct Describable {
    const char* describe() const {
        return static_cast<const D&>(*this).name();
    }
    const char* name() const { return "shape"; }
};

struct Triangle : Describable<Triangle> {};

struct Circle : Describable<Circle> {
    const char* name() const { return "circle"; }
};

int main() {
    Triangle t;
    Circle c;
    std::printf("triangle %s\n", t.describe());
    std::printf("circle %s\n", c.describe());
    return 0;
}
```

```text
triangle shape
circle circle
```

**MT36.** Because `Triangle` does not define its own `name` function, the base's default is found and
`describe` returns `shape`. Because `Circle` defines a function with the same name, `circle` is found
through `static_cast<const D&>`. Both are resolved at compile time; that is, the default in the base
causes a body to be written only for the place the derived class did not write. In place of a selection
made while running, name lookup at compile time works here.

#### A Separate Static Member for Every Type

Every instantiation of a class template carries its own static member. In CRTP this is used to give
each derived class its own counter: the counter sits inside the base, but because `Counted<Square>` and
`Counted<Rectangle>` are separate classes, the counters are separate too. In a non-template base, a
single counter would add up all the derived classes.

```cpp
// counted.cpp — counter per type
#include <cstdio>

template <typename D>
struct Counted {
    static inline int count = 0;
    Counted() { ++count; }
    Counted(const Counted&) { ++count; }
    ~Counted() { --count; }
};

struct Square : Counted<Square> {};
struct Rectangle : Counted<Rectangle> {};

int main() {
    Square a;
    Square b;
    Rectangle c;
    std::printf("square=%d rectangle=%d\n", Counted<Square>::count, Counted<Rectangle>::count);
    {
        Square temp = a;
        std::printf("square=%d\n", Counted<Square>::count);
    }
    std::printf("square=%d\n", Counted<Square>::count);
    return 0;
}
```

```text
square=2 rectangle=1
square=3
square=2
```

**MT37.** When two `Square` objects and one `Rectangle` are created, the counters count separately: two
and one. The copy raises the counter to three on entering the scope, and it becomes two on leaving the
scope. For a design that wants a shared counter, the base must not be a template; when separate
counters are wanted, CRTP gives this in one line. This behavior means a separate counter object is
written for every derived class, and the cost is written to the **compile** kind; at run time only the
counter increment remains.

#### Which One When

This comparison is a guide, not a ranking. If the set of types is closed at compile time and the
bodies for each type can be made to be written by the compiler, CRTP sets up dispatch without an
indirect call; but it does not carry different types in a single collection. If the set of types grows
while running, or different types are to be held in a single container, the virtual function version
is needed; bodies are not produced per type but every call is chosen while running. For a closed but
mixed set, `std::variant` stands between the two: it gives a single collection and leaves the selection
to run time. All three methods gave the same area total (35); the difference is in which kind the
number is paid.

#### The Bounding Measurement

The limit of CRTP is that the derived classes have no common base. `Shape<Square>` and
`Shape<Rectangle>` are separate types; a pointer to one does not convert to a pointer to the other.
For this reason `Square` and `Rectangle` cannot be put into a single collection with CRTP. If a single
collection is needed, for a closed set of types `std::variant<Square, Rectangle>` and `std::visit` are
used. Which alternative is held sits in an index while running, that is, the selection returns to run
time.

```cpp
// variant.cpp — single collection with variant
#include <cstdio>
#include <variant>
#include <vector>

#include "shape.hpp"

int main() {
    std::vector<std::variant<Square, Rectangle>> v;
    v.emplace_back(Square(3));
    v.emplace_back(Rectangle(2, 5));
    v.emplace_back(Square(4));
    int choice = 0;
    long area = 0;
    for (const auto& s : v) {
        ++choice;
        area += std::visit([](const auto& x) { return x.area(); }, s);
    }
    std::printf("choice=%d area=%ld\n", choice, area);
    return 0;
}
```

```text
choice=3 area=35
```

**MT38.** Three elements, three `std::visit` calls: `choice=3`, total `area=35`. The bodies are again
compiled as `Shape<Square>::area` and `Shape<Rectangle>::area`, but which one will be called is now
chosen for every element by looking at an index while running. That is, `variant` gives back to run
time the decision CRTP took at compile time; in this version the cost has moved to the **run** kind. A
single collection, a closed set of types, and the payment of the selection come together. If the set
must be open (if new types will be added later), the virtual function version is suitable.

#### Summary

- The mechanism measured in this lesson moves the cost to the **compile** kind: with CRTP three calls
  are made with two bodies (`total=35 bodies=2`) and none of them is indirect.
- In CRTP the base class template knows the derived class; the call goes to the derived class with
  `static_cast`.
- The virtual function version gives the same total, but all three of the three calls are chosen while
  running (`indirect=3`); the two methods pay in different kinds, and no superiority is established.
- Mixins and policy classes split behavior into components at compile time; each combination causes a
  separate body to be written. A concept checks the static interface explicitly and at the call site.
- Different CRTP classes cannot be put in one collection through a common base; with `variant` the
  selection returns to run time (`choice=3 area=35`).

#### Next Step

In this lesson static dispatch moved the question of which body will run to compile time; the cost
showed up in the number of bodies and in the code written. But there is no need to stay in a single
thread: how many synchronization points does a counter protected by a lock add on every update?

## Concurrency and Performance

Threads and locks, the memory model, cache-friendly data layout, profiling and benchmarking, managing compile times, package management and build tools — each paired with the question of where the cost moved.

### Threads and Locks

Source: https://academia.sh/en/courses/cpp-templates/threads-and-locks

std::thread and join, std::jthread, std::mutex with std::lock_guard, std::scoped_lock, std::unique_lock with std::condition_variable, a producer/consumer queue, and counting how many synchronization points a lock adds.

The previous lesson showed that when the set of types is closed at compile time, the cost
of polymorphism moves to compiling: a function call pays nothing at run time, but a
separate body is produced for every type that is instantiated. This lesson measures a case
where the payment goes somewhere else: the locks added to protect shared data once work is
split across several threads. The question the course measures stays the same here: where
does a mechanism move the cost? The answer falls under the kind **wait**. This measure does
not count actual waiting; it counts the **points where a thread may be forced to wait**. No
time is printed, because time depends on the machine and the load at that moment, while the
number of points can be read from the code.

One distinction first. In M10/K03, the question "how many times did it run" made the count
the measurement itself. Here the count is only a tool of evidence: the lesson does not
answer "how many times was the lock acquired" but the kind that count points to, which is
**wait**. The question of M08/K04, "which thread runs the step", is also not asked in this
lesson; what is measured is not which thread does what, but how many synchronization points
there are.

#### Starting and Joining a Thread

`std::thread` starts running the function it is given on a separate thread at the moment it
is constructed. Before the object is destroyed it must either be waited for with `join()` or
released with `detach()`; an object destroyed with neither done terminates the program. For
this reason every example calls `join()`, and results are read only after `join()` returns:
`join()` guarantees that everything the thread wrote is visible to the caller.

If two threads write shared data with no protection at all, the behavior of the program is
**undefined**: this is called a data race. Four threads each incrementing an unprotected
counter ten thousand times does not guarantee that the result will be forty thousand; it
guarantees no result at all. We do not run undefined behavior; we run only its defined
counterpart and explain in prose why it is needed.

#### jthread: A Thread That Joins Itself

`std::jthread` arrives with C++20 and removes the most common mistake with `std::thread`.
If the thread has not yet been joined, its destructor first sends a stop request and then
calls `join()`; even if a `return` or an exception intervenes, the thread is finished before
the scope is left. A `std::thread` destroyed without being joined, on the other hand,
terminates the program. The difference is less about convenience than about **safety**: a
forgotten `join()` is no longer a crash.

The second difference is that a `jthread` carries a stop request. If the function takes a
`std::stop_token` parameter, it can leave its loop when `request_stop()` is called from the
outside. Because when the request is seen depends on timing, we do not run that; we use only
the joining behavior at the end of the scope. The subject of the measurement is not how the
thread is started, but how it protects shared data once started.

#### Lock and lock_guard

The defined counterpart is to put the shared data behind a mutex. Once a `std::mutex` is
locked, no other thread can acquire it until it is released; a thread that cannot acquire it
waits. `std::lock_guard` acquires the lock when it is constructed and releases it when it is
destroyed; because it ties the release to the end of the scope, neither a `return` nor an
exception can leave the lock held.

The header below defines the shared counter and two ways of incrementing it. `acquired` is
the second field, which counts how many times the lock was acquired; it is touched only
while the lock is held. The first way acquires the lock on every increment. We will explain
the second shortly.

```cpp
// lock_measure.hpp — shared counter and two ways of incrementing
#pragma once
#include <mutex>

struct LockedCounter {
    std::mutex lock_m;
    long value = 0;
    long acquired = 0;
};

inline void increment_every_time(LockedCounter& c, int times) {
    for (int i = 0; i < times; ++i) {
        std::lock_guard<std::mutex> guard(c.lock_m);
        ++c.value;
        ++c.acquired;
    }
}

inline void increment_local(LockedCounter& c, int times) {
    long local = 0;
    for (int i = 0; i < times; ++i) ++local;
    std::lock_guard<std::mutex> guard(c.lock_m);
    c.value += local;
    ++c.acquired;
}
```

#### Several Locks and scoped_lock

One lock protects one variable. An operation that changes two objects at once must acquire
the locks of both. If two threads acquire these locks in opposite order, each waits for the
lock the other holds and neither can make progress: this is called deadlock. The common
root of deadlock is locks being acquired in an **inconsistent order**.

There are two ways out. The first is to fix a single order across all the code; for example,
always acquiring locks from the smaller account number to the larger. This works but takes
discipline: the order is only a rule, and every new function that is written must obey it.
The second is `std::scoped_lock`: it acquires several locks in one step, in an order that
prevents deadlock; the standard requires a deadlock-avoidance algorithm for this. The order
in which you write the locks no longer matters.

```cpp
// account.hpp — operations that take two and three locks at once
#pragma once
#include <mutex>

struct Account {
    std::mutex lock_m;
    long balance = 0;
};

inline void transfer(Account& source, Account& target, long amount) {
    std::scoped_lock both(source.lock_m, target.lock_m);
    source.balance -= amount;
    target.balance += amount;
}

inline long total_balance(Account& a, Account& b, Account& c) {
    std::scoped_lock three(a.lock_m, b.lock_m, c.lock_m);
    return a.balance + b.balance + c.balance;
}
```

Even if `transfer(a, b, 1)` and `transfer(b, a, 1)` are called at the same time, no deadlock
occurs. Had we written `a.lock_m.lock()` followed by `b.lock_m.lock()` by hand, deadlock
would have been possible whenever two calls acquired them in opposite order; we do not run
that, because the result may leave the program hanging. `total_balance` takes three locks at
once: transfers hold only two locks, so a reader of the total never lands in the middle of
any transfer.

#### Condition Variable and unique_lock

Sometimes a thread needs more than to protect shared data: it needs to **wait for something
to happen**. `std::condition_variable` exists for this: the waiting thread releases the lock
and sleeps, and wakes when another thread makes the condition true and gives notice. So that
the waiting side can release the lock it holds, `std::lock_guard` is not enough; a
`std::unique_lock`, which can be released and reacquired, is needed. `unique_lock` does
everything `lock_guard` does and, on top of that, allows `unlock()` and `lock()` to be
called; the price is a small piece of extra state.

```cpp
// handoff.hpp — a one-time wake-up with a condition variable
#pragma once
#include <condition_variable>
#include <mutex>

struct Handoff {
    std::mutex lock_m;
    std::condition_variable wake;
    bool ready = false;
    int value = 0;
};

inline void prepare(Handoff& h, int v) {
    {
        std::lock_guard<std::mutex> guard(h.lock_m);
        h.value = v;
        h.ready = true;
    }
    h.wake.notify_one();
}

inline int await_value(Handoff& h) {
    std::unique_lock<std::mutex> locked(h.lock_m);
    h.wake.wait(locked, [&h] { return h.ready; });
    return h.value;
}
```

`wait` takes the condition as a predicate and checks it while the lock is held; the wake-up
notice may have come for nothing, or the condition may have become true before it came, so
the condition is retested on every wake-up. The flag and the value are written and read only
under the lock.

#### Producer and Consumer

When a stream of values is carried instead of a single value, the same mechanism turns into
a queue. The producer puts values in the queue and gives notice; the consumer takes values
while the queue is full and sleeps while it is empty. When the work is done, the producer
raises a `done` flag, because the consumer has no other answer to the question "the queue is
empty, but will more values come".

After the consumer takes a value from the queue, it **releases** the lock, does the work
without the lock, and reacquires it. This is where `unique_lock` differs from `lock_guard`:
the lock is held only for as long as shared data is being touched, and processing a value
does not shut the queue to others.

```cpp
// work_queue.hpp — producer/consumer queue
#pragma once
#include <condition_variable>
#include <mutex>
#include <queue>

struct WorkQueue {
    std::mutex lock_m;
    std::condition_variable wake;
    std::queue<int> items;
    bool done = false;
};

inline void produce(WorkQueue& q, int count) {
    for (int i = 0; i < count; ++i) {
        {
            std::lock_guard<std::mutex> guard(q.lock_m);
            q.items.push(i);
        }
        q.wake.notify_one();
    }
    {
        std::lock_guard<std::mutex> guard(q.lock_m);
        q.done = true;
    }
    q.wake.notify_one();
}

inline long consume(WorkQueue& q, int& received) {
    long total = 0;
    std::unique_lock<std::mutex> locked(q.lock_m);
    for (;;) {
        q.wake.wait(locked, [&q] { return !q.items.empty() || q.done; });
        if (q.items.empty()) break;
        int v = q.items.front();
        q.items.pop();
        locked.unlock();
        total += v;
        ++received;
        locked.lock();
    }
    return total;
}
```

How many times the consumer woke and how many times it waited depends on the schedule and is
not printed. What is printed is two numbers that do not depend on the schedule: how many
values were received, and the sum of the values.

#### Measurement: How Many Times Was the Lock Acquired

Now we run the two ways of incrementing with four threads, each making ten thousand
increments. `transfer`, `Handoff` and `WorkQueue` also run in the same program; each result
is printed only after `join()` returns, so the output does not depend on the order of the
threads.

```cpp
// lock_measurement.cpp — lock acquisition count and supporting checks
#include <functional>
#include <iostream>
#include <thread>
#include <vector>

#include "account.hpp"
#include "handoff.hpp"
#include "lock_measure.hpp"
#include "work_queue.hpp"

namespace {

void four_threads(LockedCounter& c, void (*work)(LockedCounter&, int)) {
    std::vector<std::thread> workers;
    for (int i = 0; i < 4; ++i) workers.emplace_back(work, std::ref(c), 10000);
    for (auto& worker : workers) worker.join();
}

}  // namespace

int main() {
    LockedCounter every_time;
    four_threads(every_time, increment_every_time);
    std::cout << "locked counter wait acquired=" << every_time.acquired
              << " value=" << every_time.value << "\n";

    LockedCounter local;
    four_threads(local, increment_local);
    std::cout << "local total wait acquired=" << local.acquired
              << " value=" << local.value << "\n";

    Account a, b;
    a.balance = 1000;
    b.balance = 1000;
    {
        std::thread forward([&] { for (int i = 0; i < 500; ++i) transfer(a, b, 1); });
        std::thread backward([&] { for (int i = 0; i < 500; ++i) transfer(b, a, 1); });
        forward.join();
        backward.join();
    }
    std::cout << "two-way transfer wait total=" << a.balance + b.balance << "\n";

    Account x, y, z;
    x.balance = y.balance = z.balance = 1000;
    int violations = 0;
    {
        std::thread t1([&] { for (int i = 0; i < 300; ++i) transfer(x, y, 1); });
        std::thread t2([&] { for (int i = 0; i < 300; ++i) transfer(y, z, 1); });
        std::thread t3([&] { for (int i = 0; i < 300; ++i) transfer(z, x, 1); });
        std::thread checker([&] {
            for (int i = 0; i < 200; ++i)
                if (total_balance(x, y, z) != 3000) ++violations;
        });
        t1.join();
        t2.join();
        t3.join();
        checker.join();
    }
    std::cout << "three-account ring wait total=" << total_balance(x, y, z)
              << " violations=" << violations << "\n";

    Handoff handoff;
    int received = 0;
    {
        std::jthread consumer([&] { received = await_value(handoff); });
        prepare(handoff, 42);
    }
    std::cout << "condition variable wait received=" << received << "\n";

    WorkQueue queue;
    int received_items = 0;
    long item_total = 0;
    {
        std::jthread consumer([&] { item_total = consume(queue, received_items); });
        produce(queue, 1000);
    }
    std::cout << "producer consumer wait received=" << received_items
              << " total=" << item_total << "\n";
    return 0;
}
```

```text
locked counter wait acquired=40000 value=40000
local total wait acquired=4 value=40000
two-way transfer wait total=2000
three-account ring wait total=3000 violations=0
condition variable wait received=42
producer consumer wait received=1000 total=499500
```

**CP1.** The first line shows that the four threads acquired the lock on each of the forty
thousand increments: `acquired=40000`, `value=40000`. Each acquisition is a point where a
thread may be forced to wait for a lock held by another thread; the lesson measures the
number of these points, not how many times waiting actually happened. The result
`value=40000` is defined because every increment was made under the lock; this correctness
is the guarantee the lock gives.

**CP2.** The `total=2000` on the third line shows that the transfers made in opposite order
in the two directions left neither a deadlock nor a loss, thanks to `std::scoped_lock`: the
sum of the two balances did not change. The order in which we wrote the locks did not matter
here; `transfer(a, b, …)` and `transfer(b, a, …)` asked for the same two locks in opposite
order.

**CP3.** The fourth line tests a ring of three locks: while three threads transferred from
`x` to `y`, from `y` to `z` and from `z` to `x`, a fourth thread took all three locks at
once two hundred times and read the total. The total showed `3000` every time and
`violations=0` came out. The reader never landed in the middle of a transfer, because no
transfer changed a balance while holding only one of the two locks.

**CP4.** On the fifth line the waiting thread woke when `prepare` was called and received
the value `42`. `std::jthread` performed `join()` at the end of the scope, so `received` was
written before it was read. At what moment the wake-up happened was not printed; only what
was received was printed.

**CP5.** The last line shows that the consumer received all one thousand values and that the
total is `499500`, which is the sum of the numbers from zero to nine hundred ninety-nine. No
value was lost and none was received twice. The `done` flag made sure that the consumer did
not leave while the producer had not finished even if the queue emptied, and that it did not
stay stuck waiting once the producer had finished and the queue was empty.

**CP6.** The two `std::jthread` objects on the fifth and sixth lines were also finished
without a hand-written `join()`: the destructor joined as the scope closed. This is the only
basis for the result being readable; without `join()`, or a destructor that calls it,
`received` and `item_total` could have been read while the thread was still writing.

#### The Bounding Measurement

The mechanism this lesson measured is protecting shared data with a lock, and the second line
reduces its cost. `increment_local` makes the ten thousand increments in each thread in its
own local total, acquires the lock only once at the end, and adds the total to the shared
counter. The result is the same, `value=40000`; but the synchronization points fell from
forty thousand to **four**: `acquired=4`. The synchronization points were reduced ten
thousand times over, and correctness was kept.

The lesson drawn from this is that the cost comes not from the lock itself but from **how
many times it is acquired**. The same `std::mutex` was acquired forty thousand times in one
way of writing and four times in another. The limit of this is as follows: a local total
works only where the work can be split into parts and combined at the end. If every step
must see the shared state, that is, if the result of one thread entered the next step of
another, the lock is acquired at every step and the count does not fall. In that case the way
to reduce the cost is not to let go of the lock but to divide the shared state; we will see
this in the next two lessons as memory ordering and data layout.

#### Summary

- The mechanism this lesson measured moves the cost to the kind **wait**: a lock increases
  the number of points where a thread may be forced to wait; the measure is the number of
  these points, not the actual waiting time.
- A `std::thread` is waited for with `join()` once constructed; everything the thread wrote
  is read only after `join()` returns. `std::jthread` does the same work in its destructor.
- Writing shared data without protection is a data race and its behavior is undefined;
  `std::mutex` with `std::lock_guard` ends the race and releases the lock at the end of the
  scope.
- `std::scoped_lock` acquires several locks in an order that does not lead to deadlock; no
  ordering discipline is needed.
- `std::condition_variable` is for waiting on a condition and requires `std::unique_lock`;
  the condition is retested on every wake-up. Because `unique_lock` can release and
  reacquire the lock, it allows the work in a producer/consumer queue to be done without the
  lock.
- `locked counter` acquired the lock forty thousand times and `local total` four times, with
  the same result: the cost is determined not by the lock but by how many times it is
  acquired.

#### Next Step

A lock says whose hands a piece of data is in, and it makes what one thread wrote under the
lock visible to whoever acquires the lock next; but it does not say which ordering is really
needed for visibility, or how many synchronization points that ordering costs. The next
lesson opens the memory model: with the question of how many synchronization points a memory
order asks for, we will measure `std::atomic` and the release and acquire relation.

### The Memory Model

Source: https://academia.sh/en/courses/cpp-templates/memory-model

std::atomic, read-modify-write operations, the seq_cst, acquire, release and relaxed memory orders, the happens-before relation, and counting how many synchronization points a release/acquire publish asks for.

The previous lesson showed how to protect shared data with a lock, and that the cost of a
lock is determined by how many times it is acquired: for four threads, forty thousand lock
acquisitions could fall to four with a local total. A lock does everything at once: it ties
the data to a single thread and makes what was written visible to the next acquirer. This
lesson separates those two. `std::atomic` makes a single operation on a variable
indivisible; and the memory order determines when the writes **around** that operation
become visible to others. The question the course measures is the same again: where does a
mechanism move the cost? The answer falls under the kind **wait**, and here too the measure
counts not actual waiting but how many synchronization points a data publish asks for. The
count is a tool of evidence; the lesson is answered with the name of the kind.

#### Indivisibility and Ordering Are Not the Same Thing

A read or a write on a `std::atomic<int>` cannot be seen half done: another thread sees
either the old value or the new value, nothing in between. Read-modify-write operations such
as `fetch_add` extend this indivisibility over all three steps: reading the value,
incrementing it and writing it back are a single operation, and no other increment can slip
in between. For this reason, incrementing a counter without a lock is not a data race once
the variable is a `std::atomic`.

But indivisibility says nothing about what happens to **other** variables. Every atomic
operation takes a memory order, and four orders matter in this lesson.
`std::memory_order_seq_cst` is the default: all `seq_cst` operations appear in one common
order for all threads. `memory_order_release` is given to a store and `memory_order_acquire`
to a load, and the two work together. `memory_order_relaxed` gives only indivisibility and
orders nothing else.

The relation between release and acquire is expressed as the **happens-before relation**. If
one thread stores to an atomic variable with release and another thread loads that stored
value with acquire, all writes before the release become visible to all reads after the
acquire. Plain, non-atomic variables are included in this; the publish flag may be atomic
while the published data is plain.

#### A Publish: A Thousand Plain Values, One Release Store

The producer writes a thousand plain values into an array, then writes only once to an
atomic flag with release. The consumer loads the flag with acquire, and once it sees the
flag it sees all thousand values. The synchronization point is the number of release stores
made on the producer side; the mechanism asks for one point per store. We do not write the
counter by hand: right after each release store, the producer side increments its own plain
counter, and the counter is read only after `join()`.

```cpp
// publish.hpp — two publish forms: a single flag and every element atomic
#pragma once
#include <atomic>
#include <thread>

constexpr int ELEMENTS = 1000;

struct SingleFlag {
    int data[ELEMENTS];
    std::atomic<int> ready{0};
    long sync_points = 0;
    long total = 0;
};

inline void produce_single(SingleFlag& p) {
    for (int i = 0; i < ELEMENTS; ++i) p.data[i] = i;
    p.ready.store(1, std::memory_order_release);
    ++p.sync_points;
}

inline void consume_single(SingleFlag& p) {
    while (p.ready.load(std::memory_order_acquire) == 0) std::this_thread::yield();
    long t = 0;
    for (int i = 0; i < ELEMENTS; ++i) t += p.data[i];
    p.total = t;
}

struct EveryElement {
    std::atomic<int> cells[ELEMENTS];
    long sync_points = 0;
    long total = 0;
    EveryElement() {
        for (auto& e : cells) e.store(-1, std::memory_order_relaxed);
    }
};

inline void produce_all(EveryElement& p) {
    for (int i = 0; i < ELEMENTS; ++i) {
        p.cells[i].store(i, std::memory_order_release);
        ++p.sync_points;
    }
}

inline void consume_all(EveryElement& p) {
    long t = 0;
    for (int i = 0; i < ELEMENTS; ++i) {
        int v;
        while ((v = p.cells[i].load(std::memory_order_acquire)) == -1) std::this_thread::yield();
        t += v;
    }
    p.total = t;
}
```

The `SingleFlag` array is a plain `int` array; the `ready` flag is atomic. The producer
writes before the flag, and the consumer touches no element of the array until it has seen
the flag. `EveryElement` is the second form and will be read in The Bounding Measurement
section. The array is initialized before the threads are started: constructing a
`std::thread` makes everything done up to the call of the constructor visible to the new
thread.

#### What Relaxed Does Not Give

The `relaxed` order gives nothing except indivisibility. This means that a relaxed
`fetch_add` counter still gives the correct total: if four threads each call
`fetch_add(1, std::memory_order_relaxed)` ten thousand times, the result is forty thousand,
because indivisibility protects every increment. But if the same `relaxed` operation is used
as a publish flag, the producer's plain writes may not be visible to the consumer; the flag
may be seen as `1` while the thousand values remain as they were. This is a data race and
its behavior is undefined, so we do not run it. The fix is to use `release` and `acquire` on
the publish flag.

#### The Difference Between seq_cst and release/acquire

If we had written the publish above without specifying an order, every operation would be
`seq_cst`. The result is the same: the side that loads the flag with acquire sees what was
written. The difference is that `seq_cst` adds one more thing: there is **a single total
order** for all `seq_cst` operations, and every thread obeys this order. Release/acquire
establishes only the relation between a store and the load that reads it; it does not
require two observers to agree on which of two unrelated flags was written first. Consider
two independent writers and two readers: one of the readers may see `x` written before `y`,
and the other may see the opposite. Release/acquire does not forbid this; if both stores and
both loads are all `seq_cst`, this outcome is forbidden. We do not run this case, because
which outcome is seen depends on the schedule and the hardware; the lesson only separates
the scope of the guarantee.

This extra guarantee comes at a price: providing the common total order requires extra
barriers on some hardware. The synchronization point you count does not change, though; it
is still a store. So rather than choosing `seq_cst` deliberately, going down to
release/acquire is a choice when you can see that the publish rests on only one store and
one load. If you are not sure, the default `seq_cst` is correct; this is a preference for
correctness, not a claim about speed.

```cpp
// ordering.hpp — the same publish, with the default seq_cst order
#pragma once
#include <atomic>
#include <thread>

#include "publish.hpp"

struct DefaultPublish {
    int data[ELEMENTS];
    std::atomic<int> ready{0};
    long sync_points = 0;
    long total = 0;
};

inline void produce_default(DefaultPublish& p) {
    for (int i = 0; i < ELEMENTS; ++i) p.data[i] = i;
    p.ready.store(1);
    ++p.sync_points;
}

inline void consume_default(DefaultPublish& p) {
    while (p.ready.load() == 0) std::this_thread::yield();
    long t = 0;
    for (int i = 0; i < ELEMENTS; ++i) t += p.data[i];
    p.total = t;
}
```

#### Read-Modify-Write and compare_exchange

`fetch_add` always increments the value. Sometimes the store has to be **conditional**:
"write if the value is still the one I read". `compare_exchange_strong(expected, desired)`
does this as a single indivisible operation. If the atomic value equals `expected`,
`desired` is written and `true` is returned; if it is not equal, nothing is written,
`false` is returned, and `expected` is updated with the atomic's value **at that moment**.
If four threads try to turn the same flag from `0` to `1`, only one wins; the others see the
failure. No lock is needed to choose the winner.

The `weak` form of the operation can fail even when the values are equal; for this reason it
is always used inside a loop. In return, it is cheaper on some hardware. The typical pattern
is to read the value, compute a candidate and try to write with `compare_exchange_weak`; on
failure `expected` has already been refreshed with the new value, so the loop does not read
again. The example below finds the largest value seen by four threads without a lock: if the
candidate is larger than the current value it tries to write, and if not it leaves the loop
at once.

```cpp
// rmw.hpp — a single winner and the largest value with compare_exchange
#pragma once
#include <atomic>
#include <thread>
#include <vector>

inline int single_winner(int thread_count) {
    std::atomic<int> flag{0};
    std::atomic<int> winner{0};
    std::vector<std::thread> workers;
    for (int t = 0; t < thread_count; ++t) {
        workers.emplace_back([&] {
            int expected = 0;
            if (flag.compare_exchange_strong(expected, 1)) winner.fetch_add(1);
        });
    }
    for (auto& worker : workers) worker.join();
    return winner.load();
}

inline int largest(int thread_count, int per_thread) {
    std::atomic<int> biggest{0};
    std::vector<std::thread> workers;
    for (int t = 0; t < thread_count; ++t) {
        workers.emplace_back([&, t] {
            for (int k = 0; k < per_thread; ++k) {
                int candidate = k * thread_count + t;
                int current = biggest.load(std::memory_order_relaxed);
                while (candidate > current && !biggest.compare_exchange_weak(current, candidate)) {
                }
            }
        });
    }
    for (auto& worker : workers) worker.join();
    return biggest.load();
}
```

How many times the loop turns depends on the schedule, so it is not printed. The result,
however, does not depend on the schedule: the largest candidate is written under every
condition.

#### Reading the Happens-Before Chain Step by Step

The happens-before relation is **transitive**. Suppose there are three threads: A writes a
plain value and writes to `flag1` with release; B sees `flag1` with acquire, writes its own
plain value and writes to `flag2` with release; C sees `flag2` with acquire. What C sees
comes through a flag that A never touched; even so, it sees A's write as well. We read the
chain as follows.

1. A's plain write happens before A's release store to `flag1` (order within one thread).
2. The release store to `flag1` happens before B's acquire load that sees it (a
   release/acquire pair).
3. B's acquire load happens before B's plain write and B's release store to `flag2` (order
   within one thread).
4. The release store to `flag2` happens before C's acquire load (the second pair).
5. Transitivity: A's write happens before C's read, and so does B's.

Every link in the chain is either the order within one thread or a release/acquire pair. If
a link breaks, for example if B loads the flag with relaxed, step 2 is not established and
there is no guarantee left that C sees A's write.

```cpp
// chain.hpp — a happens-before chain across three threads
#pragma once
#include <atomic>
#include <thread>

struct Chain {
    int a = 0;
    int b = 0;
    std::atomic<int> flag1{0};
    std::atomic<int> flag2{0};
    int seen_a = 0;
    int seen_b = 0;
};

inline void chain_a(Chain& c) {
    c.a = 10;
    c.flag1.store(1, std::memory_order_release);
}

inline void chain_b(Chain& c) {
    while (c.flag1.load(std::memory_order_acquire) == 0) std::this_thread::yield();
    c.b = c.a + 5;
    c.flag2.store(1, std::memory_order_release);
}

inline void chain_c(Chain& c) {
    while (c.flag2.load(std::memory_order_acquire) == 0) std::this_thread::yield();
    c.seen_a = c.a;
    c.seen_b = c.b;
}
```

#### Measurement: How Many Synchronization Points

```cpp
// publish_measurement.cpp — two publish forms and a relaxed counter
#include <atomic>
#include <functional>
#include <iostream>
#include <thread>
#include <vector>

#include "chain.hpp"
#include "ordering.hpp"
#include "publish.hpp"
#include "rmw.hpp"

int main() {
    SingleFlag single;
    {
        std::thread producer(produce_single, std::ref(single));
        std::thread consumer(consume_single, std::ref(single));
        producer.join();
        consumer.join();
    }
    std::cout << "release/acquire publish wait sync=" << single.sync_points
              << " total=" << single.total << "\n";

    EveryElement every;
    {
        std::thread producer(produce_all, std::ref(every));
        std::thread consumer(consume_all, std::ref(every));
        producer.join();
        consumer.join();
    }
    std::cout << "every element atomic wait sync=" << every.sync_points
              << " total=" << every.total << "\n";

    std::atomic<long> counter{0};
    std::vector<std::thread> workers;
    for (int i = 0; i < 4; ++i) {
        workers.emplace_back([&counter] {
            for (int k = 0; k < 10000; ++k) counter.fetch_add(1, std::memory_order_relaxed);
        });
    }
    for (auto& worker : workers) worker.join();
    std::cout << "relaxed counter wait value=" << counter.load() << "\n";

    DefaultPublish plain;
    {
        std::thread producer(produce_default, std::ref(plain));
        std::thread consumer(consume_default, std::ref(plain));
        producer.join();
        consumer.join();
    }
    std::cout << "seq_cst publish wait sync=" << plain.sync_points
              << " total=" << plain.total << "\n";

    std::cout << "compare exchange wait winner=" << single_winner(4) << "\n";
    std::cout << "cas loop wait largest=" << largest(4, 1000) << "\n";

    Chain chain;
    {
        std::thread c(chain_c, std::ref(chain));
        std::thread b(chain_b, std::ref(chain));
        std::thread a(chain_a, std::ref(chain));
        a.join();
        b.join();
        c.join();
    }
    std::cout << "happens-before chain wait a=" << chain.seen_a
              << " b=" << chain.seen_b << "\n";
    return 0;
}
```

```text
release/acquire publish wait sync=1 total=499500
every element atomic wait sync=1000 total=499500
relaxed counter wait value=40000
seq_cst publish wait sync=1 total=499500
compare exchange wait winner=1
cas loop wait largest=3999
happens-before chain wait a=10 b=15
```

**CP7.** The first line shows that a thousand plain values were published with a single
release store: `sync=1`. When the consumer saw the flag with its acquire load, it read all
thousand elements and the total came out as `499500`, which is the sum of the numbers from
zero to nine hundred ninety-nine. How many times the consumer turned before seeing the flag
is not printed, because that number depends on the schedule; what is measured is not the
loop count but the number of release stores written.

**CP8.** The third line shows that the relaxed `fetch_add` counter still gives `40000`.
Although the order is relaxed, the result is correct; because indivisibility is not
ordering, and no increment breaks into another. A relaxed counter is correct use only where
just the final value is read and no other data is published.

**CP9.** The fourth line shows that the same publish with the default `seq_cst` order also
consists of one store and one load: `sync=1`, `total=499500`. The number of synchronization
points did not change when the order changed; the `seq_cst` difference cannot be read from
this line, because the difference appears only in how observers order two mutually
independent publishes.

**CP10.** With `compare_exchange_strong`, four threads tried to turn the same flag from `0`
to `1` and `winner=1` came out. Had it been possible for all four to succeed at once, the
number would have come out greater than one; the indivisible compare and write prevented
this. Which thread won was not printed, because it depends on the schedule.

**CP11.** The value `largest=3999` is the largest of the candidates produced by the four
threads: `999 * 4 + 3` for the last step `k=999` and the last thread `t=3`. When another
thread slipped in and changed the value, `compare_exchange_weak` failed and updated
`current`; the loop compared the candidate with the new value again. No larger value was
written after a smaller one and lost.

**CP12.** On the last line, thread C saw both `a=10` and `b=15`. The `a` that came through
`flag1`, which C never read, became visible thanks to the transitivity of the chain. Even
though the threads were started out of order (C was started first), the result did not
change, because C stayed in its loop until it saw the flag.

#### The Bounding Measurement

The mechanism this lesson measured is that the memory order determines the number of
synchronization points. The second line publishes the same thousand values, this time making
each element a separate atomic. Every store is a release, every load an acquire; correctness
was not broken, `total=499500`. But `sync=1000`: a thousand times more synchronization
points.

This difference comes not from the data itself but from **how finely the publish is
divided**. While one flag protects a thousand values, a thousand atomics protect each value
one by one. The happens-before relation is cheap for a single release-acquire pair and
covers all the writes before the pair; for this, the data to be published must first be
collected and then opened from a single point. The limit is this: if the consumer has to use
the data without waiting for the other half, a single flag is not enough and a piecewise
publish becomes unavoidable. Relaxing the order is not enough to reduce the cost; the number
of points the publish is divided into must be reduced.

#### Summary

- The mechanism this lesson measured moves the cost to the kind **wait**: the memory order
  determines how many synchronization points a data publish asks for; the measure is the
  number of these points, not actual waiting.
- `std::atomic` gives indivisibility; read-modify-write operations such as `fetch_add`
  turn three steps into one operation. Indivisibility is not ordering.
- A release store and an acquire load establish the happens-before relation: when the
  acquire reads the value the release wrote, all writes before the release become visible to
  all reads after the acquire.
- `seq_cst` is the default and makes all `seq_cst` operations visible in a single common
  order; `relaxed` gives only indivisibility, and using it as a publish flag is a data race.
- `release/acquire publish` published a thousand values at one point, and the
  `every element atomic` mechanism at a thousand points; both gave the same total.

#### Next Step

Reducing synchronization points is half the work; the other half is how the data is laid
out in memory. The next lesson opens the cache line and locality: with the question of how
many jumps a data layout skips, we will compare an array of structures with a structure of
arrays.

### Cache-Friendly Data Layout

Source: https://academia.sh/en/courses/cpp-templates/cache-friendly-data-layout

The cache line, spatial and temporal locality, array of structures versus structure of arrays, row order and column order, false sharing, and counting how many non-contiguous jumps a data layout leaves.

The previous two lessons measured the cost of concurrency: how many times a lock is
acquired, how many synchronization points a publish asks for. This lesson returns to a
single thread, because how data is laid out in memory changes the cost even without
concurrency. The processor does not move memory byte by byte; it moves it in fixed-size
blocks called **cache lines**. When you touch one value, the neighboring bytes around it
come into near memory along with it. If you will soon touch some of those neighbors, this is
a good trade; if you will not, most of the moved bytes were wasted. The question the course
measures is the same again: where does a mechanism move the cost? The answer in this lesson
is the kind **memory**. We do not print the line size or addresses, because both depend on
the machine; the measure counts whether two values that a loop touches one after the other
sit side by side in memory.

#### Locality

There are two kinds of locality. **Spatial locality** is the expectation that a program that
touches a value will soon touch its neighbor too; walking the elements of an array in order
is an example. **Temporal locality** is the expectation that a program that touches a value
will soon touch the same value again; a loop variable or a running total is an example. The
cache line rewards spatial locality: values that sit side by side in the line arrive in a
single transfer.

In multidimensional arrays the same idea appears as row order and column order. In C++,
`int table[rows][columns]` is in row order: the elements of the same row are contiguous. An
inner loop that walks along rows obeys spatial locality; an inner loop that walks along
columns skips a whole row length at every step. We show this difference below with a jump
count.

#### Array of Structures and Structure of Arrays

A set of points is stored with three fields, `x`, `y` and `z`. The first layout is the
**array of structures (AoS)**: each point is a structure and all the points sit in one
array. In memory the order is `x0 y0 z0 x1 y1 z1 ...`. The second layout is the **structure
of arrays (SoA)**: each of the three fields sits in its own array. In memory the order is
`x0 x1 x2 ... y0 y1 y2 ... z0 z1 z2 ...`.

A loop that walks only the `x` field skips the other two fields at every step in the array
of structures; the `x` values that follow one another are not contiguous, with `y` and `z`
between them. In the structure of arrays the `x` values are side by side. The header below
builds the two layouts and the measure. The measure records, in order, the addresses a loop
touches and checks whether the distance between two consecutive touches is exactly one
`int`. No address is printed; only the count comes out.

```cpp
// data_layout.hpp — two data layouts and a measure that records the touches
#pragma once
#include <array>
#include <cstddef>
#include <cstdint>
#include <vector>

constexpr int POINT_COUNT = 4;

struct Point {
    int x, y, z;
};

struct PointArray {
    std::array<Point, POINT_COUNT> points;
};

struct FieldArrays {
    std::array<int, POINT_COUNT> x, y, z;
};

inline PointArray build_array_of_structures() {
    PointArray d;
    for (int i = 0; i < POINT_COUNT; ++i) d.points[i] = Point{i, 10 + i, 20 + i};
    return d;
}

inline FieldArrays build_structure_of_arrays() {
    FieldArrays d;
    for (int i = 0; i < POINT_COUNT; ++i) {
        d.x[i] = i;
        d.y[i] = 10 + i;
        d.z[i] = 20 + i;
    }
    return d;
}

inline bool is_contiguous(const int* before, const int* after) {
    auto a = reinterpret_cast<std::uintptr_t>(before);
    auto b = reinterpret_cast<std::uintptr_t>(after);
    return b - a == sizeof(int);
}

struct Jumps {
    int skipped = 0;
    int total = 0;
};

inline Jumps tally(const std::vector<const int*>& touches) {
    Jumps j;
    for (std::size_t i = 0; i + 1 < touches.size(); ++i) {
        ++j.total;
        if (!is_contiguous(touches[i], touches[i + 1])) ++j.skipped;
    }
    return j;
}
```

The contiguity test converts the pointers to integers and compares the difference with
`sizeof(int)`. Subtracting pointers of two separate arrays would be undefined; converting to
integers is necessary for this reason. `skipped` counts the non-contiguous jumps and `total`
counts all jumps.

#### Row Order and Column Order: Counting Jumps

Put the same idea into numbers on a single flat array. A table of four rows and four
columns sits in row order in a single array of sixteen elements: the expression
`m[r * 4 + c]` is element `c` of row `r`. Consider two nested loops. In the first, the outer
loop runs over rows and the inner loop over columns; consecutive touches are side by side in
the array. In the second, the outer loop runs over columns and the inner loop over rows;
consecutive touches skip one row length, that is four `int`s, at every step, and go back
when the column changes.

The point to notice is that sixteen touches produce fifteen **jumps**: a jump is the step
between two consecutive touches. In row order none of the fifteen jumps skips. In column
order all fifteen skip, because two consecutive touches are either four `int`s ahead or
behind. A jump that goes backward is not counted as contiguous either: the contiguity test
requires the difference to be exactly one `int`.

```cpp
// matrix.hpp — two traversal orders over a flat array of four rows and four columns
#pragma once
#include <array>

#include "data_layout.hpp"

constexpr int ROWS = 4;
constexpr int COLUMNS = 4;

inline Jumps row_order_tally(const std::array<int, ROWS * COLUMNS>& m) {
    std::vector<const int*> touches;
    for (int r = 0; r < ROWS; ++r)
        for (int c = 0; c < COLUMNS; ++c) touches.push_back(&m[r * COLUMNS + c]);
    return tally(touches);
}

inline Jumps column_order_tally(const std::array<int, ROWS * COLUMNS>& m) {
    std::vector<const int*> touches;
    for (int c = 0; c < COLUMNS; ++c)
        for (int r = 0; r < ROWS; ++r) touches.push_back(&m[r * COLUMNS + c]);
    return tally(touches);
}
```

This is the same `tally` function as in the previous section; there is no new measure, only
two new access patterns. In a real table this difference turns into the chance that every
skipping jump brings in a different cache line. If a row of the table is longer than a cache
line, every skipping jump lands on a different cache line, so for large tables fitting the
loop order to the layout of the data is the first place to look.

#### False Sharing and alignas

Data layout does not concern only a single thread. If two threads write to two independent
variables but the two variables land on the same cache line, one thread's write invalidates
the other's line, and the two threads keep emptying each other's cache. This is called
**false sharing**: the variables are not shared, but the line is. The code is correct and
there is no data race; each write only forces the ownership of the line to change hands.
This is a different cost from the waiting points in the lesson on locks or atomics: no
synchronization is visible in the code, and the cost comes from the layout.

The fix is to separate the fields the threads write onto different lines. In C++ the
`alignas` specifier does this: if a type is given `alignas(N)`, the objects of that type are
placed at addresses that are multiples of `N`, and the size of the type is rounded up to a
multiple of `N`. Two consecutive `Aligned` elements are therefore at least `N` bytes apart.

Here the number `64` is an **assumption**: on common processors the cache line is this
size, but it is not a constant the language states and it may not be right on every
hardware. For this reason we name the number and keep it in one place, and the measurement
uses that assumption, not the real line. The `static_assert` below also checks at compile
time that the alignment really is the requested value. The count looks at whether the
difference between the addresses of two consecutive elements is smaller than the assumed
line size; if it is smaller, the two are **candidates** to land on the same line.

```cpp
// sharing.hpp — packed and aligned counters, counting same-line candidates
#pragma once
#include <array>
#include <cstddef>
#include <cstdint>
#include <thread>
#include <vector>

constexpr std::size_t LINE_ASSUMPTION = 64;  // assumption: common processor cache line

struct Packed {
    long value = 0;
};

struct alignas(LINE_ASSUMPTION) Aligned {
    long value = 0;
};

static_assert(alignof(Aligned) == LINE_ASSUMPTION, "alignment is not the requested value");
static_assert(sizeof(Aligned) % LINE_ASSUMPTION == 0, "size was not rounded to the line");

template <typename T>
int same_line_candidates(const std::array<T, 4>& items) {
    int candidates = 0;
    for (std::size_t i = 0; i + 1 < items.size(); ++i) {
        auto a = reinterpret_cast<std::uintptr_t>(&items[i]);
        auto b = reinterpret_cast<std::uintptr_t>(&items[i + 1]);
        if (b - a < LINE_ASSUMPTION) ++candidates;
    }
    return candidates;
}

template <typename T>
long four_writers(std::array<T, 4>& items) {
    std::vector<std::thread> workers;
    for (int t = 0; t < 4; ++t) {
        workers.emplace_back([&items, t] {
            for (int k = 0; k < 10000; ++k) ++items[t].value;
        });
    }
    for (auto& worker : workers) worker.join();
    long total = 0;
    for (const auto& e : items) total += e.value;
    return total;
}
```

Each thread writes only to its own element; both versions are therefore correct and give the
same total. For `long` elements, which are eight bytes on this platform, `same_line_candidates`
counts three of the three pairs, and for the sixty-four-byte aligned elements it counts none
of the three. What is counted here is not a real transfer but the situation the layout
**may cause**.

#### Measurement: x Field Only, Table and Counters

The program below runs three measurements together and prints the counter of each.

```cpp
// layout_measurement.cpp — x field only and three fields together
#include <array>
#include <iostream>
#include <vector>

#include "data_layout.hpp"
#include "matrix.hpp"
#include "sharing.hpp"

int main() {
    PointArray aos = build_array_of_structures();
    FieldArrays soa = build_structure_of_arrays();

    std::vector<const int*> aos_x;
    std::vector<const int*> soa_x;
    int aos_total = 0;
    int soa_total = 0;
    for (int i = 0; i < POINT_COUNT; ++i) {
        aos_x.push_back(&aos.points[i].x);
        aos_total += aos.points[i].x;
        soa_x.push_back(&soa.x[i]);
        soa_total += soa.x[i];
    }
    Jumps a = tally(aos_x);
    Jumps s = tally(soa_x);
    std::cout << "x field only memory aos=" << a.skipped << "/" << a.total
              << " soa=" << s.skipped << "/" << s.total << "\n";
    std::cout << "sum x aos=" << aos_total << " soa=" << soa_total << "\n";

    std::array<int, ROWS * COLUMNS> table{};
    for (int i = 0; i < ROWS * COLUMNS; ++i) table[i] = i;
    Jumps row = row_order_tally(table);
    Jumps column = column_order_tally(table);
    std::cout << "row and column order memory row=" << row.skipped << "/"
              << row.total << " column=" << column.skipped << "/" << column.total << "\n";

    std::array<Packed, 4> packed{};
    std::array<Aligned, 4> aligned{};
    std::cout << "false sharing memory packed=" << same_line_candidates(packed) << "/3"
              << " aligned=" << same_line_candidates(aligned) << "/3\n";
    long packed_total = four_writers(packed);
    long aligned_total = four_writers(aligned);
    std::cout << "false sharing result packed=" << packed_total
              << " aligned=" << aligned_total << "\n";

    std::vector<const int*> aos_three;
    std::vector<const int*> soa_three;
    for (int i = 0; i < POINT_COUNT; ++i) {
        aos_three.push_back(&aos.points[i].x);
        aos_three.push_back(&aos.points[i].y);
        aos_three.push_back(&aos.points[i].z);
        soa_three.push_back(&soa.x[i]);
        soa_three.push_back(&soa.y[i]);
        soa_three.push_back(&soa.z[i]);
    }
    Jumps au = tally(aos_three);
    Jumps su = tally(soa_three);
    std::cout << "three fields together memory aos=" << au.skipped << "/" << au.total
              << " soa=" << su.skipped << "/" << su.total << "\n";
    return 0;
}
```

```text
x field only memory aos=3/3 soa=0/3
sum x aos=6 soa=6
row and column order memory row=0/15 column=15/15
false sharing memory packed=3/3 aligned=0/3
false sharing result packed=40000 aligned=40000
three fields together memory aos=0/11 soa=11/11
```

**CP13.** The first line shows that the loop walking only the `x` field made three jumps over
four elements in both layouts, that in the array of structures all three are non-contiguous,
and that in the structure of arrays none skips: `aos=3/3`, `soa=0/3`. The second line
confirms that the two layouts give the same total, so the difference is not in the result
but in the position of the touches in memory.

**CP14.** The count gives only the non-contiguous jumps, not the line size: a small set of
four points may fit in a single cache line, and every skipped jump may not cause a new line
transfer. For this reason `3/3` is not a transfer count but the **direction** in which the
layout breaks contiguity; the real transfer count gains meaning as the set grows and depends
on the machine.

**CP15.** The third line shows that in the table of four rows and four columns, walking in
row order makes none of the fifteen jumps skip (`row=0/15`), while walking in column order
makes all of them skip (`column=15/15`). The two loops touched the same sixteen elements;
only the order was different. The jumps that go backward in column order also entered the
count, because the contiguity test accepts only a forward step of exactly one `int`.

**CP16.** In the fourth line, the packed array, made of `long` elements that are eight bytes
on this platform, made all three consecutive pairs same-line candidates (`packed=3/3`); the
array given `alignas` made none of them (`aligned=0/3`). This number is not a real cache
line measurement; it rests on the `LINE_ASSUMPTION` assumption. If the assumption is wrong,
the count is wrong too; for this reason we named the value and checked with `static_assert`
that the alignment is the requested value.

**CP17.** In the fifth line both versions gave `40000`. Because each thread wrote only to its
own element there was no data race, and the layout did not change the result. `alignas` does
not change correctness; it changes where the cost is paid, and this change is not visible in
the output and is the part this lesson deliberately does not measure.

#### The Bounding Measurement

The layout this lesson measured, the advantage of the structure of arrays, holds in a loop
that touches only one field. The last line measures the same two layouts this time with a
loop that reads three fields together: for each point `x`, `y`, `z` are read in order. Here
the table turns around: in the array of structures the three fields of a point are side by
side, and so are the fields of the next point, so none of the eleven jumps skips:
`aos=0/11`. In the structure of arrays every read jumps to a different array: `soa=11/11`.

What decides contiguity is not the data but the **access pattern**. The same data can sit in
the best layout for one pattern and the worst for another. For this reason there is no rule
such as "the structure of arrays is faster" or "the array of structures is more natural".
The question is which fields the loop touches together; if the fields are read together, the
array of structures keeps contiguity, and if they are read separately, the structure of
arrays does.

#### Summary

- The mechanism this lesson measured moves the cost to the kind **memory**: a data layout
  determines how much of what a loop touches one after another it leaves contiguous; the
  measure is not time but the number of non-contiguous jumps.
- The cache line moves memory in blocks; spatial locality rewards the neighbor, and temporal
  locality rewards touching the same value again.
- The array of structures keeps the fields contiguous together, and the structure of arrays
  keeps them contiguous separately; the access pattern decides which one suits.
- `x field only` left `aos=3/3` in the array of structures and `soa=0/3` in the structure of
  arrays; `three fields together` left `aos=0/11` and `soa=11/11` in the same two layouts.
- Walking in row order left `row=0/15` skips and walking in column order left `column=15/15`;
  the order must fit the layout of the data.
- False sharing is independent variables landing on the same line; the fix is to give each
  thread its own line, with `alignas`; the line size here is an assumption.

#### Next Step

In this lesson we assumed we knew which layout suits which pattern, but in a real program we
cannot know which layout to touch without knowing which loop is hot. The next lesson opens
profiling: with the question of where a counter finds the hot spot, we will build an
instrumented profiler.

### Profiling and Benchmarking

Source: https://academia.sh/en/courses/cpp-templates/profiling-and-benchmarking

Instrumentation versus sampling, finding the hot spot by placing counters, the warm-up, repetition and dead code rules of benchmarking, and how the place where a measurement starts changes the result.

The previous lesson showed how a data layout changes the memory cost of a loop, but the
lesson assumed one thing: we knew in advance which loop mattered. In a real program this
knowledge does not exist. Choosing the place to optimize by guessing is the shortest way to
spend effort on a place that does not matter. This lesson explains finding which place is hot
by **measuring**. The question the course measures is the same again: where does a mechanism
move the cost? The answer in this lesson is the kind **run**: profiling is a mechanism paid
while the program runs, and the program that runs gives its result. In M10/K03, for the
question "how many times did it run", the count was the measure itself; here the count is a
tool of evidence and the lesson is answered with the name of the kind. No time is printed:
time depends on the machine and the load, while the hot spot is found from a counter.

#### Two Methods: Instrumentation and Sampling

A profiler collects data in two ways. **Instrumentation** is placing counters in the program
itself: a counter is incremented at every function entry or at every loop step, and the
counters are read when the program ends. The count is exact, because every event is counted;
but the counters touch the code, and the measured program is now different from the
unmeasured one.

**Sampling** does not change the code of the program. The profiler stops the program at
certain intervals and looks at which function is running at that moment; over enough looks,
the function seen most often is the hot spot. The overhead of sampling is smaller, but its
result is approximate and depends on timing; the same program gives a slightly different
distribution in two runs. In this lesson we do not run sampling, because its output depends
on the run; we work with instrumentation, because its output is a count and is the same in
every run.

#### Sampling on a Trace

We can build the model of sampling without tying it to a run. Think of which function
is running at each step of the program as a **trace**: the trace is the sequence of function
identifiers in step order. The sampler looks at every `period`-th step of this trace and
counts the identifier it finds. A real sampler does not see the trace; at the moment it
stops the program it sees only the current function. Here the trace is known in advance, so
we can compute what sampling will find. The trace corresponds to a program that runs one
hundred steps of `prepare` and then 4950 steps of `search`: 5050 steps in total.

Sampling does two things. It finds the hot spot, because the function that takes longer
meets more looks. But it does not give the count exactly: the looks fall on certain points
of the trace, and these points depend on the **offset**. If we sample the same trace starting
from step zero or starting from step thirty-five, we get different counts. The hot spot does
not change, but the share of the short-running function moves.

```cpp
// sampling.hpp — a periodic sampling model over a trace
#pragma once
#include <array>
#include <cstddef>
#include <vector>

constexpr int FUNCTION_PREPARE = 0;
constexpr int FUNCTION_SEARCH = 1;

struct SampleCount {
    std::array<int, 2> hits{};
};

inline std::vector<int> build_trace() {
    std::vector<int> trace;
    for (int i = 0; i < 100; ++i) trace.push_back(FUNCTION_PREPARE);
    for (int i = 0; i < 4950; ++i) trace.push_back(FUNCTION_SEARCH);
    return trace;
}

inline SampleCount sample(const std::vector<int>& trace, std::size_t period, std::size_t offset) {
    SampleCount counts;
    for (std::size_t i = offset; i < trace.size(); i += period) ++counts.hits[trace[i]];
    return counts;
}
```

The period was chosen as seventy. This number is a model parameter; the interval of a real
sampler is measured in time and has no counterpart here. When the offset is zero, the looks
fall on steps 0, 70, 140, and so on; two looks enter the hundred-step `prepare` region. When
the offset is thirty-five, the looks fall on steps 35, 105, and so on, and only one enters the
region. The program that prints the count runs only this computation; the result of the
computation is the same in every run, because the trace is fixed and the model has none of
the timing noise of real sampling.

#### Placing Counters

The program below finds the equal pairs among one hundred values. Three operations are
counted: `prepare`, the production of a value; `search`, the comparison of two values; and
`dupes`, the finding of an equal pair. The counters sit in a `Profile` structure and are
passed to the functions as a parameter; the result is read only when the program ends.

```cpp
// profile.hpp — counters and the profiled operations
#pragma once
#include <cstddef>
#include <vector>

struct Profile {
    long prepare = 0;
    long search = 0;
    long dupes = 0;
};

inline int prepare_value(Profile& p, int i) {
    ++p.prepare;
    return i % 50;
}

inline int count_dupes(const std::vector<int>& v, Profile& p) {
    int found = 0;
    for (std::size_t i = 0; i < v.size(); ++i) {
        for (std::size_t j = i + 1; j < v.size(); ++j) {
            ++p.search;
            if (v[i] == v[j]) {
                ++p.dupes;
                ++found;
            }
        }
    }
    return found;
}
```

`prepare_value` returns `i % 50`; when one hundred values are produced, each value is found
twice. For this reason fifty pairs are expected. `count_dupes` compares every pair once with
two nested loops; for one hundred values the number of pairs is `100 * 99 / 2 = 4950`.

#### Optimizing the Hot Spot: Before and After

The counter pointed at the `search` operation, but this is only a diagnosis. The value of a
diagnosis is that the change made after it can be measured. Finding equal pairs does not
require comparing every pair: counting how many times each value occurs in a frequency table
and computing `c * (c - 1) / 2` for each value gives the same number. Walking one hundred
values once is one hundred steps; walking fifty buckets once adds fifty more steps.

To keep the comparison fair, the two versions have the same counter, the same input and the
same result type. Here `search` means "a step of the main loop": a comparison in the old
version, a value read or a bucket sum in the new one. The steps of the two versions are not
the same kind of work; for this reason the number compares the **operation count** of the two
versions, not their time.

```cpp
// optimized.hpp — a second version that gives the same result with a frequency table
#pragma once
#include <algorithm>
#include <vector>

#include "profile.hpp"

inline int count_dupes_table(const std::vector<int>& v, Profile& p) {
    int largest = *std::max_element(v.begin(), v.end());
    std::vector<int> tally(static_cast<std::size_t>(largest) + 1, 0);
    for (int x : v) {
        ++tally[static_cast<std::size_t>(x)];
        ++p.search;
    }
    int found = 0;
    for (int c : tally) {
        found += c * (c - 1) / 2;
        ++p.search;
    }
    return found;
}
```

The new version walks one hundred values once and fifty buckets once: `150` steps. The old
version took `4950` steps. Both versions find fifty pairs; the optimization did not change
the result, it only reduced the size of the hot spot. The number compares the operation
count of the two versions. Whether the time dropped is another question and is not answered
in this lesson.

#### The Rules of Benchmarking

Profiling says which place inside a program is hot. **Benchmarking** races two versions
against the same question. When done with time, four rules are needed, and none of them is
met on its own. The first is **warm-up**: the first run differs from later runs because it
fills the caches and the lazily built structures; the first run should be dropped or
reported separately. The second is **repetition**: a single run depends on the load at that
moment; the distribution of many runs should be examined. The third is **the same input**: if
two versions are measured with different inputs, the difference may come from the input too.
The fourth is **dead code elimination**: the standard allows the compiler to delete a
computation that does not change observable behavior; a computation whose result is used
nowhere may not have run at all while being measured. The fix is to use the result: write it
somewhere or print it.

In this lesson we do not print time, but the four rules also apply when measuring with
counters. The first three are applied below in a separate measurement program. For the
fourth: the result of the `count_dupes` function above is returned as `found` and printed, so
the computation cannot be deleted.

#### Where the Measurement Starts

The warm-up rule says that **where the measurement starts** can change the result. We can
show this with a counter too. A table is built at the first query and found ready at later
queries. The setup is one hundred steps and each query is ten steps; including the first
query in the measurement or not changes the result.

```cpp
// table.hpp — a table built at the first call and the query steps
#pragma once
#include <vector>

struct LazyTable {
    std::vector<int> values;
    bool ready = false;
};

inline long query(LazyTable& t, int start) {
    long steps = 0;
    if (!t.ready) {
        for (int i = 0; i < 100; ++i) {
            t.values.push_back(i * i);
            ++steps;
        }
        t.ready = true;
    }
    long total = 0;
    for (int k = 0; k < 10; ++k) {
        total += t.values[start + k];
        ++steps;
    }
    (void)total;
    return steps;
}
```

`steps` is a local counter: it counts the function's own steps and starts again from zero at
every call. The table is built at the first call with the `ready` flag; at the second call the
flag is set and the setup is skipped.

#### Applying the Warm-Up Rule with a Counter

Of the four rules, the first three look like this in a measurement program. The same input:
in every run `query` is called with the same `start=0` value. Repetition: five runs are made.
Warm-up: the first run is reported separately or removed from the average. In every run the
table stays in the same object, so the first call does the setup and the later ones do not.

```cpp
// measure.hpp — repetition, warm-up and the average steps
#pragma once
#include <vector>

#include "table.hpp"

struct WarmupResult {
    long unwarmed = 0;
    long warmed = 0;
    int iterations = 0;
};

inline WarmupResult measure_warmup(int iterations) {
    LazyTable table;
    std::vector<long> steps;
    for (int i = 0; i < iterations; ++i) steps.push_back(query(table, 0));
    long all = 0;
    long without_first = 0;
    for (int i = 0; i < iterations; ++i) {
        all += steps[i];
        if (i > 0) without_first += steps[i];
    }
    WarmupResult result;
    result.iterations = iterations;
    result.unwarmed = all / iterations;
    result.warmed = without_first / (iterations - 1);
    return result;
}
```

The unwarmed average includes all five runs: `(110 + 10 + 10 + 10 + 10) / 5 = 30`. The warmed
average drops the first run: `(10 + 10 + 10 + 10) / 4 = 10`. Both numbers are correct, but they
measure different things: the first is "what does a program that calls this function five
times from scratch pay", the second is "what is the cost of a query on a ready table".
Giving a number without writing which question it answers is misleading.

#### Measurement: Which Is the Hot Spot

The program below reads three counters, picks the highest as the hot spot, and queries the
table twice.

```cpp
// profile_measurement.cpp — instrumented profile and a lazily built table
#include <iostream>
#include <vector>

#include "measure.hpp"
#include "optimized.hpp"
#include "profile.hpp"
#include "sampling.hpp"
#include "table.hpp"

int main() {
    Profile p;
    std::vector<int> v;
    for (int i = 0; i < 100; ++i) v.push_back(prepare_value(p, i));
    int found = count_dupes(v, p);
    std::cout << "instrumented profile run prepare=" << p.prepare << " search=" << p.search
              << " dupes=" << p.dupes << "\n";

    const char* hot = "prepare";
    long highest = p.prepare;
    if (p.search > highest) { hot = "search"; highest = p.search; }
    if (p.dupes > highest) { hot = "dupes"; highest = p.dupes; }
    std::cout << "hot spot " << hot << " found=" << found << "\n";

    long increments = p.prepare + p.search + p.dupes;
    std::cout << "instrumentation run increments=" << increments << "\n";

    std::vector<int> trace = build_trace();
    SampleCount zero = sample(trace, 70, 0);
    SampleCount thirty_five = sample(trace, 70, 35);
    std::cout << "sampling run offset=0 prepare=" << zero.hits[FUNCTION_PREPARE]
              << " search=" << zero.hits[FUNCTION_SEARCH] << "\n";
    std::cout << "sampling run offset=35 prepare=" << thirty_five.hits[FUNCTION_PREPARE]
              << " search=" << thirty_five.hits[FUNCTION_SEARCH] << "\n";

    Profile p2;
    int found_table = count_dupes_table(v, p2);
    std::cout << "optimization run before=" << p.search << " after=" << p2.search
              << " found=" << found << "/" << found_table << "\n";

    LazyTable table;
    long first = query(table, 0);
    long second = query(table, 10);
    std::cout << "lazy table run first=" << first << " second=" << second << "\n";

    WarmupResult warmup = measure_warmup(5);
    std::cout << "warm-up run unwarmed=" << warmup.unwarmed
              << " warmed=" << warmup.warmed << " iterations=" << warmup.iterations << "\n";
    return 0;
}
```

```text
instrumented profile run prepare=100 search=4950 dupes=50
hot spot search found=50
instrumentation run increments=5100
sampling run offset=0 prepare=2 search=71
sampling run offset=35 prepare=1 search=71
optimization run before=4950 after=150 found=50/50
lazy table run first=110 second=10
warm-up run unwarmed=30 warmed=10 iterations=5
```

**CP18.** The first line gives the three counters: one hundred values were prepared, `4950`
comparisons were made, and `50` equal pairs were found. The hot spot is read from the
counter: `search` is the largest counter and is more than forty-nine times `prepare`. The
place to optimize is the nested loop inside `count_dupes`; not `prepare_value`, and not
counting the equal pairs. What made this choice is not a guess but the counter.

**CP19.** The second line prints the number of equal pairs with `found=50`. Printing the
result is also a safeguard against dead code elimination: since the computation is used,
the compiler deleting it would have changed observable behavior.

**CP20.** Sampling with offset zero gave `prepare=2 search=71`, and with offset thirty-five
`prepare=1 search=71`. In reality one hundred steps are about two percent of 5050 steps, and
both runs saw `prepare` around this share, but a different number of times. In both runs the
hot spot is `search`. What sampling says is the answer to "which is hot"; for the share of
small functions it carries a rounding error that depends on the offset.

**CP21.** The sixth line shows the operation count of the optimization: `before=4950`,
`after=150`. Both gave `found=50`; the result did not change. Because before and after depend
on the same input and the same counter, the comparison is valid. The number is not time: the
two versions take different kinds of steps, and this number is not enough to pass a verdict
about time.

**CP22.** The unwarmed average is `30`, the warmed average is `10`; both were computed with
the same input and five iterations. The source of the difference is a single run: the first
run, which did the setup. Five iterations diluted the share of this one run in the average
but did not erase it. Repetition does not replace warm-up; the run that does the setup must be
named separately.

**CP23.** The instrumentation itself also did work: the `prepare` counter was incremented one
hundred times, the `search` counter 4950 times and the `dupes` counter fifty times; the total
is `increments=5100`. The measured program differs from the unmeasured program by 5100
increments. Since sampling does not change the code, it avoids most of this difference; its
price is giving up the exact count.

#### The Bounding Measurement

The mechanism this lesson measured is finding the hot spot with counters; the `lazy table`
line shows its limit. The same `query` function counted `first=110` steps at the first call
and `second=10` steps at the second: the setup entered the first measurement and did not
enter the second. Comparing the two queries and saying "the second query does eleven times
less work" would be wrong; the setup is paid once and then waits ready.

This shows that the result depends on **where the measurement starts**. If the measurement
starts from the first call, the setup of the table is included; if it starts from the second
call, it is not. Both results are correct, but they answer different questions. The limit of a
profile is this: a counter says whatever it counts; which run you take into the measurement
is decided by your own choices. For this reason the starting point is written next to every
measurement.

#### Summary

- The mechanism this lesson measured moves the cost to the kind **run**: profiling is paid
  while the program runs and the program that runs gives the result; the measure is a
  counter, not time.
- Instrumentation places counters in the code and counts exactly but touches the code;
  sampling does not change the code and has a smaller overhead but its result is approximate.
- The hot spot is found from a counter, not from a guess: `instrumented profile` found the
  `search` counter highest, with `4950`, among the three counters.
- Benchmarking asks for the warm-up, repetition, same input and dead code rules; using the
  result is the safeguard against the last rule.
- `lazy table` counted the same function at `110` steps at the first call and `10` at the
  second: where the measurement starts changes the result, so the starting point is written
  with the measurement.

#### Next Step

After the profile finds the hot spot, another cost remains: how often the code is rebuilt.
The next lesson opens managing compile times: with the question of where the hiding idiom
moves what it gains in compiling, we will reduce header dependency.

### Managing Compile Times

Source: https://academia.sh/en/courses/cpp-templates/managing-compile-times

Forward declaration, trimming unnecessary includes, the pimpl idiom, opaque types, explicit instantiation and extern template, and how the cost gained at compile time moves to run time per object.

The previous lesson showed that the profile finds the hot spot and that where the
measurement starts changes the result. But there is one more cost that no counter can catch:
the compile cost paid before the program runs. When a header file changes, every translation
unit that includes that header, directly or indirectly, is rebuilt. The more units a header
is visible to, the more expensive a change is. This lesson examines ways to reduce that
visibility and measures where one of the ways, the **pimpl idiom**, makes the compile cost it
gained be paid at run time. The answer is the kind **run**. A distinction from M11/K05: there,
the state of a moved object was not the measure; here too we do not look at the state of a
moved object, we only count whether the move makes an allocation. Compile time is not
printed; the dependency is described as "how many units see this header", and the number
measured is the allocation per object.

#### Reducing the Visibility of a Header

The first tool is the **forward declaration**. If a header uses another type only as a
pointer or a reference, it does not need the full definition of that type; writing
`class Window;` is enough. Including the header that holds the full definition with
`#include` makes this header rebuild too every time that header changes. A forward
declaration cuts this chain: the full definition is included only in the `.cpp` file that
really uses it.

The second tool is deleting unnecessary `#include` lines. A line added to a header is a cost
paid by all the units that include that header; an unused line makes them pay the same cost.
The third tool is specific to templates: if a frequently used template specialization is
instantiated again in every unit, **explicit instantiation** and the `extern template`
declaration gather it into one unit. `extern template class Box<int>;` is written in the
header, and the instantiation is done with `template class Box<int>;` in a single `.cpp`
file; the other units link to the definition in that unit instead of regenerating the
non-inline members. There is a small example of this tool below; its effect does not show in
the run output, so it is not measured.

#### Why a Forward Declaration Lightens a Header

The work of a forward declaration shows in an example. A drawing function takes the
`Window` type as a parameter. The full definition of the type is not needed for the
**declaration** of the function: an incomplete type can be a parameter in a function
declaration, whether as a reference or by value. The full definition is needed only in the
**definition** of the function and at the place where the function is **called**. For this
reason the drawing header writes only `class Window;` and does not include `window.hpp` at
all; `window.hpp` is visible only inside `drawing.cpp`.

A unit that includes `drawing.hpp` does not see the inside of `Window`; even if the members
of `Window` change, that unit is not rebuilt. A unit includes the full definition itself only
if it creates a `Window` object or calls one of its members.

```cpp
// drawing.hpp — Window is visible only through a forward declaration
#pragma once

class Window;

int draw(const Window& w);
int draw_copy(Window w);
```

```cpp
// drawing.cpp — the full definition is included only here
#include "drawing.hpp"
#include "window.hpp"

int draw(const Window& w) { return w.width(); }
int draw_copy(Window w) { return w.width(); }
```

The two functions return the same width, but the way the parameter is passed is different.
`draw` takes a reference and does not build a new `Window`. `draw_copy` takes a value: a copy
is built during the call, and the copy of a class with the pimpl idiom makes a heap
allocation. The header shows both functions with the same forward declaration; the cost
depends on the form of the parameter, not on the header.

#### Explicit Instantiation and extern template

For templates a forward declaration is not enough: the body of the template has to sit in the
header, because the compiler substitutes the type at every place of use. If a template is
used with the same type in many units, each unit generates the same instantiation inside
itself and the linker picks one of the copies. The running program is correct, but this
generation is written into the compile time of every unit.

`extern template` cuts this repetition. If `extern template class Box<int>;` is written in
the header, the units do not instantiate the non-inline members of `Box<int>` inside
themselves; the definition waits in another unit. Members defined in the class body are
implicitly inline and the declaration does not cover them: the compiler may still generate
them to inline them. The gain grows in members whose bodies are defined outside; because the
members of the `Box` below are defined in the class body, the example shows the syntax, not
the gain. **Explicit instantiation** is done with `template class Box<int>;` in a single
`.cpp` file, and the single copy of the definition is generated there. The effect shows in
compile time; it does not show in the output. The program below only verifies that the pair
of declarations compiles and links.

```cpp
// box.hpp — the template body is in the header, the int specialization comes from outside
#pragma once

template <typename T>
class Box {
public:
    explicit Box(T value) : value_(value) {}
    T get() const { return value_; }

private:
    T value_;
};

extern template class Box<int>;
```

```cpp
// box.cpp — the single definition of the Box<int> instantiation
#include "box.hpp"

template class Box<int>;
```

#### The Pimpl Idiom

The fourth tool also takes the **private members** of a class out of the header. The private
fields of a class are visible in the header, because the compiler has to know the size of the
object. If the type of a private field changes, every unit that includes the class is
rebuilt. The **pimpl idiom** moves these fields into an inner structure named `Impl` and
keeps in the header only its forward declaration and a `std::unique_ptr<Impl>`. At this point
`Impl` is an **opaque type**: the unit that sees the header knows it exists but not what is
inside.

The header below carries only the forward declaration and the pointer. Notice that the
destructor and the move operations are only **declared** here; their definitions are in the
`.cpp` file.

```cpp
// window.hpp — only a forward declaration and a unique_ptr
#pragma once
#include <memory>

class Window {
public:
    Window();
    ~Window();
    Window(Window&&) noexcept;
    Window& operator=(Window&&) noexcept;
    Window(const Window&);
    Window& operator=(const Window&);

    int width() const;
    void set_width(int value);

    static int object_count();
    static int alloc_count();

private:
    struct Impl;
    std::unique_ptr<Impl> impl_;
};
```

When a `std::unique_ptr<Impl>` is destroyed it calls the destructor of `Impl`; for this it
has to see the full definition of `Impl`. Since `Impl` stands in the header only with a
forward declaration, leaving the destructor implicit in the header or writing `= default`
makes the compiler try to generate the destructor while `Impl` is an incomplete type, and
the build fails. For this reason the destructor and the move operations are only declared,
and defined with `= default` in the `.cpp` file where `Impl` is defined.

```cpp
// window.cpp — the Window implementation, Impl is defined here
#include "window.hpp"

namespace {
int objects = 0;
int allocs = 0;
}  // namespace

struct Window::Impl {
    int width = 0;
};

Window::Window() : impl_(std::make_unique<Impl>()) {
    ++objects;
    ++allocs;
}

Window::~Window() = default;
Window::Window(Window&&) noexcept = default;
Window& Window::operator=(Window&&) noexcept = default;

Window::Window(const Window& other) : impl_(std::make_unique<Impl>(*other.impl_)) {
    ++allocs;
}

Window& Window::operator=(const Window& other) {
    if (this != &other) *impl_ = *other.impl_;
    return *this;
}

int Window::width() const { return impl_->width; }
void Window::set_width(int value) { impl_->width = value; }
int Window::object_count() { return objects; }
int Window::alloc_count() { return allocs; }
```

If a field is added to `Impl`, or the type of `width` changes, only `window.cpp` is rebuilt.
`window.hpp` stays as it is, and no unit that includes it is rebuilt. Being able to change the
implementation without changing the header is the compile cost the pimpl idiom gains.

#### Why the Destructor Is in the .cpp File

The most common mistake in this design is leaving the destructor in the header. The rule is
simple: when a `std::unique_ptr<T>` is destroyed, `delete` is called, and `delete` needs the
full definition of `T`. If the destructor of `Window` is not written in the header or is
written as `= default`, the compiler tries to generate it in **every unit that destroys a
`Window` object**. In those units `Impl` is still an incomplete type and the `delete` is
invalid. The fix is to only declare the destructor in the header and define it with
`= default` in the `.cpp` file where `Impl` is fully visible. The same reason applies to the
move assignment: the assignment has to destroy the old `unique_ptr`. The move constructor is
also defined in the `.cpp` file, because if construction is cut halfway, the code that
destroys the constructed members is generated in it too.

We do not quote the error message here and we do not run it; it varies from compiler to
compiler. What matters is that the error appears in the **user unit**: not where the
destructor is written, but where it is called. This makes the error harder to find.

The difference shows when compared with `std::shared_ptr`. A `shared_ptr` captures its
deleter when the object is **constructed**; the destructor can be written in the header even
for an incomplete type, because the deleter is formed in the unit where the construction is
done, while the type is fully visible. In a `unique_ptr` the deleter is part of the type and
is generated at the place where it is destroyed. A `shared_ptr` is thereby freed from the
destructor-in-the-header rule, but in return it carries a control block: `std::make_shared`
builds it together with the object in a single allocation, while a separately constructed
`shared_ptr` pays a second allocation for it. A `unique_ptr` with the default deleter is, in
common implementations, the size of a single pointer. In this lesson `unique_ptr` was chosen
and the allocation count is read through it.

#### How Many Units See This Header

Compile cost is measured by how many translation units a header is visible to. We cannot read
this from the output; we read it from the setup of the project, so we give the number as a
**counting example**, not as a measurement. Consider a hypothetical project with five
translation units; all the units include `window.hpp`. When the type of a field inside `Impl`
changes, which units are rebuilt?

| Layout | Units that include `window.hpp` | Units rebuilt when `Impl` changes |
|---|---|---|
| Private fields in the header | 5 | 5 |
| Pimpl idiom, `Impl` in the `.cpp` | 5 | 1 |

The numbers in the table come from the setup of this hypothetical project. The only unit
rebuilt in the second row is `window.cpp`, which defines `Impl`. By the same logic, if
`drawing.hpp` included `window.hpp`, every unit that includes `drawing.hpp` would be tied to
`window.hpp` as well; the forward declaration cuts this indirect connection. Indirect
includes quietly grow this number: a header also brings in everything that the headers
including it include.

For this reason two things are checked before adding an `#include` to a header. Is the added
type really needed in the header with its full definition, or is a forward declaration
enough? And how many headers include this header, and how many units do they in turn
include? The length of the chain comes from the answers to these questions; the compiler does
not do this count for us and warn us, because the program compiles correctly and only more
work is done.

#### Measurement: Allocation per Object

```cpp
// window_measurement.cpp — the allocation per object of the pimpl idiom
#include <iostream>
#include <utility>

#include "box.hpp"
#include "drawing.hpp"
#include "window.hpp"

int main() {
    Window a;
    Window b;
    Window c;
    a.set_width(640);
    b.set_width(480);
    std::cout << "pimpl idiom run objects=" << Window::object_count()
              << " allocs=" << Window::alloc_count() << "\n";

    int before = Window::alloc_count();
    Window moved(std::move(a));
    int move_allocs = Window::alloc_count() - before;

    before = Window::alloc_count();
    Window copied(b);
    int copy_allocs = Window::alloc_count() - before;

    std::cout << "pimpl object run move=" << move_allocs
              << " copy=" << copy_allocs << "\n";
    std::cout << "width moved=" << moved.width()
              << " copy=" << copied.width() << "\n";

    int start = Window::alloc_count();
    int w1 = draw(b);
    int by_reference = Window::alloc_count() - start;
    start = Window::alloc_count();
    int w2 = draw_copy(b);
    int by_value = Window::alloc_count() - start;
    std::cout << "forward declaration run reference=" << by_reference
              << " value=" << by_value << " width=" << w1 + w2 << "\n";

    Box<int> box(7);
    std::cout << "explicit instantiation run box=" << box.get() << "\n";
    return 0;
}
```

```text
pimpl idiom run objects=3 allocs=3
pimpl object run move=0 copy=1
width moved=640 copy=480
forward declaration run reference=0 value=1 width=960
explicit instantiation run box=7
```

**CP24.** The first line shows that each of the three `Window` objects allocated one `Impl`
at construction: `objects=3`, `allocs=3`. The pimpl idiom makes you pay the cost of reducing
the visibility of the header as a heap allocation on every object; the inner structure is no
longer inside the object but in a separate block of memory.

**CP25.** The third line confirms that the two objects carry the right values: the moved
object got the width `640` and the copy got `480`. The state of the moved-from `a` was not
looked at; this lesson measures not its state but whether the move makes an allocation.

**CP26.** The fourth line shows that a `Window` shown through a forward declaration made no
allocation when passed by reference (`reference=0`) and made one allocation when passed by
value (`value=1`). The width total `960` confirms that both calls read the value `480`. The
header carried both functions with the same forward declaration; the cost came not from the
header but from the form of the call.

**CP27.** The fifth line prints `box=7`. The `extern template` declaration and the
`template class` definition were compiled and linked together; the output does not show that
there is a single instantiation, it only shows that the pair of declarations is valid. The
effect on compile time cannot be read from this output.

**CP28.** Nothing in the output verifies the five against one in the table; it is a counting
example that comes from the setup of the project. Its correctness depends on the assumption:
that all five units include `window.hpp` and that only one defines `Impl`. In a real project
indirect includes change this number.

**CP29.** The `move=0` in the second line depends on the move constructor being defined with
`= default` in the `.cpp` file: while `Impl` is fully defined, the move only takes over the
`unique_ptr`. If the same constructor were defined with `= default` in the header, a problem
could appear because `Impl` is incomplete. For this reason the measurement is meaningful only
in a layout that applies the rule.

#### The Bounding Measurement

The mechanism this lesson measured is moving the cost gained at compile time to run time per
object. The second line shows when this cost is paid again. **Moving** an object with the pimpl
idiom makes no new allocation: `move=0`, because the move only takes over the pointer of the
`unique_ptr` and `Impl` stays in place. **Copying** the same object duplicates `Impl` and
makes one allocation: `copy=1`.

That is, the compile cost gained turns into a run cost at every place an object is produced:
producing and copying pay an allocation, moving does not. The forward declaration shows the
same limit: `reference=0` and `value=1`. The call that passes by reference does not pay the
cost of the pimpl idiom; the call that passes by value is the one that pays. The limit is
this: if the class is copied a hundred thousand times in a hot loop, the time gained in
compiling corresponds to a hundred thousand allocations at run time. For this reason the
pimpl idiom is justified for classes whose objects are produced rarely, whose header is
visible to many units, and whose implementation changes often.

#### Summary

- The mechanism this lesson measured moves the cost to the kind **run**: the pimpl idiom
  reduces the visibility of the header and in return every object has to pay a heap
  allocation.
- When a header changes, every unit that includes it is rebuilt; forward declaration,
  deleting unnecessary `#include` lines and `extern template` shorten this chain.
- The pimpl idiom hides the private members behind `Impl`; the implementation can change
  without the header changing. The destructor and the move operations are defined in the
  `.cpp` file while `Impl` is fully defined.
- `pimpl idiom` measured `objects=3 allocs=3` on three objects: each object pays one
  allocation.
- A forward declaration lightens the header; with `reference=0` and `value=1` the cost
  depends on the form of the call. `extern template` gathers the template instantiation into
  one unit.
- Moving made `move=0` allocations and copying made `copy=1`: the compile cost gained is paid
  again at run time in copying.

#### Next Step

This lesson showed reducing the visibility of a header, but we still described the effect of
the reduction by guessing. The next lesson is the close of the course: with the question of
how many units a changing header rebuilds, we will evaluate together all the mechanisms we
measured in this course.

### Package Management and Build Tools

Source: https://academia.sh/en/courses/cpp-templates/package-management-and-build-tools

Reproducible installation with a dependency table, version pinning and a lock file; how a header-only template library rebuilds every unit.

The previous lesson showed that reducing the visibility of a header moves its cost to an
allocation per object, but it described the compile time gained by estimate. This lesson
turns that estimate into a number: how many units does a changing header rebuild? The same
question is asked of the libraries a project brings in from outside, because a library is in
the end a few headers. Time is not printed. The number measured is the count of **translation
units** that a change rebuilds. A distinction from M10/K03: the number is not the measure
itself, it is the instrument of evidence. Here too the number is the evidence for a
classification; the answer to the measure question is a kind name, and the answer of this
lesson is **compile**.

#### The Dependency Table

A **build system** rests its work on a single table: which headers does each unit include?
When a file changes, the units that include that file are stale; the others are left alone.
The name of the system and its configuration language are not the subject of this lesson; the
table itself is. We can build the table in plain C++: a unit name and the list of headers it
includes.

```cpp
// dependency.hpp — a table of units and the headers they include
#pragma once
#include <string>
#include <vector>

struct Unit {
    std::string name;
    std::vector<std::string> headers;
};

inline int rebuilt(const std::vector<Unit>& units, const std::string& changed) {
    int count = 0;
    for (const auto& u : units) {
        if (u.name == changed) {
            ++count;
            continue;
        }
        for (const auto& h : u.headers) {
            if (h == changed) {
                ++count;
                break;
            }
        }
    }
    return count;
}
```

`rebuilt` looks at every unit. If the unit's own source changed, it counts the unit;
otherwise it searches the header list for the changed file and stops at the first match. Even
if the same header appears twice in one unit, the unit is counted once, because a unit is
built once. Indirect includes enter this count too, as long as they are written into the
table; a header brought in by another header is no different from a header written in the
list.

#### Version Pinning and the Lock File

A library from outside is brought in by a **package manager**. The project's dependency on it
is written as a version range: "1.0.0 included, 2.0.0 excluded". The range makes a promise; it
does not point to a single version. When the registry publishes a new version, the same range
resolves to a different version. **Version pinning** cuts this drift: the resolved version is
written to a **lock file**, and later installations use the version in the lock instead of
resolving the range again.

A distinction is needed. The lock file shares only its name with the mutual-exclusion lock in
the concurrency part of this course. A mutex puts running threads in line; a lock file is a
record that sits on disk and blocks nothing, it only remembers which version was installed.

```cpp
// version.hpp — a model of the version range and the lock file
#pragma once
#include <map>
#include <string>
#include <vector>

// Version 130 is encoded as 1.3.0; the registry is the list of published versions.
inline int resolve(const std::vector<int>& registry, int low, int high) {
    int chosen = -1;
    for (int v : registry) {
        if (v >= low && v < high && v > chosen) chosen = v;
    }
    return chosen;
}

using LockFile = std::map<std::string, int>;

inline int install(const LockFile& lock, const std::string& package,
                   const std::vector<int>& registry, int low, int high) {
    auto it = lock.find(package);
    if (it != lock.end()) return it->second;
    return resolve(registry, low, high);
}
```

`resolve` picks the highest version in the range. `install` looks at the lock first; if the
package is in the lock, it never resolves the range. If the lock is empty, the installation
trusts the range and ties the result to the current state of the registry. A **reproducible
build** rests on this difference: as long as the version in the lock stands in the registry,
the same lock file gives the same version even if the registry changes.

#### The Header-Only Library

A template library is very often a **header-only library**. The reason was seen in the first
lesson of the course: the compiler produces a template by substituting the type at every
place of use, so the body has to be visible in every unit that uses it. A separate body is
produced for each type, and this production is written into the compile time of every unit
that includes that header. Because the body stands in the header, a change inside the library
makes all the units that include the header stale.

A compiled library sets up another layout. The header only declares the interface; the body
stands in a single `.cpp` file. A change in the body rebuilds a single unit. But this layout,
as with the explicit instantiation in the previous lesson, works only for types chosen in
advance. A library open to every type stops being a template.

```cpp
// build_measurement.cpp — how many units does a changing header rebuild
#include <iostream>

#include "dependency.hpp"
#include "version.hpp"

int main() {
    std::vector<Unit> units = {
        {"input.cpp", {"common.hpp"}},
        {"calc.cpp", {"common.hpp"}},
        {"report.cpp", {"common.hpp", "local.hpp"}},
    };
    std::cout << "changed header compile common=" << rebuilt(units, "common.hpp")
              << " local=" << rebuilt(units, "local.hpp") << "\n";

    std::vector<int> registry = {100, 110, 130};
    LockFile lock;
    int first = install(lock, "counter", registry, 100, 200);
    lock["counter"] = first;
    registry.push_back(140);
    registry.push_back(210);
    int unlocked = install(LockFile{}, "counter", registry, 100, 200);
    int locked = install(lock, "counter", registry, 100, 200);
    std::cout << "version pinning first=" << first << " unlocked=" << unlocked
              << " locked=" << locked << "\n";

    std::vector<Unit> header_only = {
        {"input.cpp", {"common.hpp", "library.hpp"}},
        {"calc.cpp", {"common.hpp", "library.hpp"}},
        {"report.cpp", {"common.hpp", "local.hpp", "library.hpp"}},
        {"draw.cpp", {"library.hpp"}},
    };
    std::vector<Unit> compiled = {
        {"input.cpp", {"common.hpp", "interface.hpp"}},
        {"calc.cpp", {"common.hpp", "interface.hpp"}},
        {"report.cpp", {"common.hpp", "local.hpp", "interface.hpp"}},
        {"draw.cpp", {"interface.hpp"}},
        {"library.cpp", {"interface.hpp"}},
    };
    std::cout << "header-only body=" << rebuilt(header_only, "library.hpp")
              << " compiled body=" << rebuilt(compiled, "library.cpp")
              << " interface=" << rebuilt(compiled, "interface.hpp") << "\n";
    return 0;
}
```

```text
changed header compile common=3 local=1
version pinning first=130 unlocked=140 locked=130
header-only body=4 compiled body=1 interface=5
```

**CP30.** The first line is the result of the dependency table: when `common.hpp` changes,
all three of the three units are rebuilt (`common=3`); when `local.hpp` changes, only
`report.cpp` is (`local=1`). In the same code base the cost of two headers differs by three
to one; the difference comes not from the size of the header but from how many units include
it.

**CP31.** In the second line, `first=130`: while the registry still carried the versions
`100`, `110` and `130`, the range resolved to `130` and the result was written to the lock.
Then `140` and `210`, which falls outside the range, were added to the registry. The unlocked
installation chose `140` (`unlocked=140`), because `210` is not in the range; the locked
installation still gave `130` (`locked=130`).

**CP32.** The two installations above are two runs of the same project, and the only
difference between them is that the registry changed. The locked one did not change, the
unlocked one followed the registry. This output shows not the version number itself but the
drift of the range; `130` and `140` are only the encoding of the model.

**CP33.** In the third line, when the body of the header-only library changes, all four of
the four units are rebuilt (`body=4`). In the compiled library the same body change makes a
single unit stale, `library.cpp` (`body=1`).

**CP34.** `interface=5`: if the header of the compiled library, which carries only the
declarations, changes, `library.cpp` is rebuilt together with the four units that include it.
The compiled layout brings a body change down to a single unit; it does not bring an
interface change down.

**CP35.** The tables of four and five units come from the setup, not from a measured build.
The number depends on the includes we wrote into the table; in a real project, if indirect
includes are written incompletely, the number comes out smaller than it is. The model is
therefore a counting example; it says nothing about compile time.

#### The Bounding Measurement

The mechanism this lesson measured is the count of units that a changing header rebuilds. The
limit lies in the header-only template library. When a library carries a template, its body
has to stand in the header, and **every** unit that includes it produces the body again
inside itself. The smallest change in the body of the library therefore makes all four of the
four units stale: `body=4`. In the compiled library the same change gives `body=1`.

That is, the cost of the template, the body being visible in every unit as seen at the start
of the course, comes back to compiling. The template gives the user the freedom to work for
every type; in return the body stays in the header, and every change is multiplied by the
number of units that include it. Turning every library into a compiled one is not a general
solution, because the compiled layout limits the type independence of a template to the types
that are explicitly instantiated. The choice is a trade-off: if the body changes often and
the header is visible to many units, the compiled layout gains; if the body rarely changes,
the simplicity of the header-only layout is enough.

The place of the number matters too. `body=4` is not the answer to a measure; the answer is
that the mechanism falls in the kind **compile**. The number is the evidence for this
classification: the cost is paid not in the running program but before building the program.
The mechanisms of this lesson produce no line in the kinds run, memory or wait; all of them
are in the kind compile.

#### Summary

- The mechanism this lesson measured moves the cost to the kind **compile**: a changing
  header rebuilds every unit that includes it.
- The dependency table gave `common=3 local=1`: in the same project the cost of two headers
  differs by how many units include them.
- A version range makes a promise, a lock file remembers a version: `unlocked=140` while
  `locked=130`, that is, a reproducible build depends on the lock. The lock file is separate
  from a mutex.
- A header-only library makes `body=4` units stale when its body changes; a compiled library
  makes `body=1` stale, but when the interface changes it gives `interface=5`.
- The cost of the template, the body being visible in every unit, comes back to compiling; the
  compiled layout can reduce it only with types chosen in advance.

#### Course Wrap-Up

Throughout this course we measured twelve mechanisms with the same question: where is the
cost paid? The table below summarizes, for each lesson, the mechanism it measured, where the
cost went, and the bounding measurement of that lesson.

| Lesson | Mechanism measured | Where the cost went | Bounding measurement |
| --- | --- | --- | --- |
| Function and Class Templates | Template instantiation | **compile** | A `const int` argument does not produce a new body |
| Template Specialization | `bool` specialization | **memory** | Two steps per read: the cost returns to run time |
| Variadic Templates | Recursive pack expansion | **compile** | A new type list produces a new body |
| Type Traits | Selection with `if constexpr` | **compile** | With a `volatile` argument the computation moves to run time: `steps=10` |
| Overload Resolution and SFINAE | Detection with `void_t` | **compile** | An error in the body is not eliminated, it stops the compilation |
| Static Polymorphism | Dispatch with CRTP | **compile** | A mixed collection asks for `std::variant` |
| Threads and Locks | Locked counter | **wait** | A local total brings lock acquisitions down to 4 |
| The Memory Model | `release`/`acquire` publication | **wait** | If every element is atomic, synchronization points become 1000 |
| Cache-Friendly Data Layout | The `x` field only | **memory** | When three fields are read together the table turns over: `aos=0/11` |
| Profiling and Benchmarking | Instrumented profile | **run** | In the lazy table the first call takes 110 steps, the second 10 |
| Managing Compile Times | Pimpl idiom | **run** | Move 0, copy 1 allocation |
| Package Management and Build Tools | Changed header | **compile** | A header-only library makes every unit stale |

**6 compile · 2 run · 2 memory · 2 wait; paid at compile time 6, paid at run time 6.** This
distribution is exactly the same as the distribution of the core set up at the start of the
course: six mechanisms write the cost to compiling, and six collect it while the program
runs. The body being visible in every unit was the cost of the template in the first lesson
of the course; in this lesson the same cost came back as a count of units per changed header.

This lesson is the last lesson of M11; M11 closes here.