Package Management and Build Tools

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.

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

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

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

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.