The programming before programming

I usually hear compile-time execution sold as a way to make the finished program faster. Calculate the table now. Remove the branch now. Generate the specialized function now. Fair enough, but the compiler is the program I am waiting for right now.

In Gotta go fast, I looked at simple compilers that avoid unnecessary representations and passes. That leaves an awkward question for comptime: why would running another program inside the compiler help? Surely that is adding work.

I wanted to test the less obvious possibility. A small compile-time program might tell the compiler to never construct some expensive work, or that several apparently different jobs are actually the same job. I built two C++ experiments around those ideas. Both helped on the tested workloads. A third configuration, where the supposed sharing disappeared, was considerably less exciting. That one belongs in the article too.

First, which kind of constant?#

There are several promises hiding behind similar spelling. An immutable value can still come from the network. A function that is allowed during compilation can also be called with runtime inputs. An expression required during compilation must produce its answer before the compiler can continue.

In C++, constexpr and consteval make different promises. A constexpr function is eligible for constant evaluation; marking the function does not force every call to happen then. A constexpr object requires a constant initializer. A normal call to a consteval function must satisfy the immediate-function rules. Here is a small C++20 example:

int read_number();constexpr int twice(int x) { return x * 2; }consteval int checked_size(int n) {  if (n < 1 || n > 64) throw "invalid size";  return n;}const int input = read_number(); // immutable; obtained at runtimeconstexpr int lanes = twice(4);  // initializer must be constantconstexpr int size = checked_size(8);// checked_size(input);          // cannot use that runtime input

Rust's const fn similarly permits calls from const contexts, such as a constant initializer. Outside such a context, it behaves like an ordinary function. That does not turn every constant-looking Rust branch into C++'s template-discarding if constexpr.

Zig's 0.16.0 reference describes another arrangement: comptime parameters are known during compilation, types are compile-time values, and a comptime expression requires compile-time execution. A local const binding alone does not make its initializer compile-time known. These distinctions matter more than the keyword count. The compiler needs a fact at a particular stage, not just a promise that the eventual value will never change.

Make the evaluator cheap enough to be useful#

Before asking compile-time execution to save anything, it needs a sensible implementation. Repeatedly walking a rich syntax tree, resolving the same operations, and allocating short-lived objects can be an expensive way to run a loop.

Clang's constant-interpreter design makes a useful distinction. Its bytecode emitter prepares function bodies for repeated execution on a typed stack machine. Its separate evaluation emitter handles one-off top-level expressions directly, avoiding the cost of constructing bytecode that will never be reused. The documentation presents this as the newer interpreter design, rather than a guarantee that every installed Clang uses it by default.

I like that split because it gives the setup cost somewhere to go. A frequently called helper can repay decoding once. A single addition cannot repay much infrastructure. A native JIT for compile-time programs would face the same question: does enough evaluation remain to recover the cost of compiling the evaluator's input?

The evaluator also has a language to implement. Rust explicitly specifies target-side interpretation: a target with 32-bit usize still has 32-bit usize when compiled on a 64-bit host. Pointer validity, initialization, overflow, and object lifetimes may need checking too. Running arbitrary host code and copying the answer back would skip precisely the rules that make compile-time evaluation trustworthy.

There are less glamorous improvements available before that. Use a linear loop instead of repeatedly solving overlapping subproblems. Keep temporary arrays in storage with a clear lifetime. Memoize genuinely repeated pure calls, but account for the table and its keys. GCC exposes a constexpr cache-depth option whose documented purpose is balancing compilation speed against memory consumption. More caching has a bill.

Then count the output. A fast generator can still leave a million syntax nodes for everyone else to process. To make the whole build faster, the evaluation, validation, and materialization costs must be smaller than the later work they prevent. That is the comparison I care about here.

Experiment one: do not instantiate the thing#

Imagine an optional feature with a complicated implementation. An ordinary branch with a constant false condition can disappear from the finished code, after the frontend has already done work to make the branch meaningful. I wanted to isolate that earlier cost.

The companion generator emits 256 wrappers. Each calls the following template with a different tag and Enabled = false. Meta is a deliberately boring chain of template classes that calculates an unsigned integer through 64 recurrence steps. Including its base case, that means 65 class specializations per tag.

template<unsigned Tag, bool Enabled>unsigned pick(unsigned x) {  if constexpr (Enabled)    return Meta<Tag, 64>::value;  else    return x + Tag;}// The experiment emits 256 wrappers with different tags.// Changing only "if constexpr" to "if" is the baseline.unsigned example(unsigned x) { return pick<17, false>(x); }

I compiled one version with an ordinary if, and another with if constexpr. The source differs by ten bytes. The workload intentionally amplifies dead template work; it is not a model of an average application. In real code I would also question doing this arithmetic through template recursion at all.

The C++ rule for a discarded constexpr-if arm allows the unselected dependent branch to remain uninstantiated once the template condition is resolved. Both arms must still be parsed, and nondependent errors do not become legal. The test suite checks that distinction with an invalid dependent specialization and, separately, an undeclared nondependent name.

The interesting number is zero. The faster version never creates those Meta specializations. The output objects have the same size within each compiler: 32,672 bytes for Clang and 32,280 for GCC. Looking only at final file size would have missed the avoided work. These values and the individual samples are in the raw results.

Zig offers a related early boundary: its documented compile-time-known branches skip analysis of the arm not taken. The important design choice is deciding before expensive dependent analysis. Constant folding at the end of optimization cannot reimburse work already done by the frontend.

Experiment two: calculate what makes a specialization different#

The second case is where I had more fun. Suppose a small arithmetic kernel accepts configuration with a round count, an optional salt, and a label. The label must be valid, but it does not affect the arithmetic. A salt matters only when salting is enabled.

If the complete configuration becomes the template argument, different labels and disabled salts create different template identities. We could hope that a later optimizer notices equivalent code. I wanted to give the frontend a smaller identity before it creates those bodies.

The following is the actual kernel and planner from the experiment. All arithmetic uses 32-bit unsigned values. The planner checks the configuration and returns only the two values the kernel needs. The identity overload lets the same kernel accept either a full configuration or an already-computed plan.

using U = unsigned;static_assert(sizeof(U) == 4);struct Config { U rounds, salt; bool salted; U label; };struct Plan { U rounds, salt; };consteval Plan plan(Config c) {  if (c.rounds < 1 || c.rounds > 64 || c.label > 1000000)    throw "invalid configuration";  return {c.rounds, c.salted ? c.salt : 0u};}consteval Plan plan(Plan p) { return p; }template<auto Key>__attribute__((noinline)) static U mix(U x) {  constexpr Plan p = plan(Key);  for (U j = 0; j < p.rounds; ++j) {    x ^= x << 13; x ^= x >> 17; x ^= x << 5;    x += p.salt + j;  }  return x;}

The noinline attribute, supported by both tested compilers, keeps the kernel separate from its wrappers. Both variants use it. There is no runtime interpreter replacing the kernel, and no runtime configuration table replacing its constants. The experiment changes where the static identity is chosen.

// Different template identities, despite the same effective work.mix<Config{12, 99, false, 1}>(x);mix<Config{12, 77, false, 2}>(x);// Evaluate the configuration BEFORE choosing the template identity.mix<plan(Config{12, 99, false, 1})>(x);mix<plan(Config{12, 77, false, 2})>(x);// Both instantiate mix<Plan{12, 0}>.

The baseline also computes plan(Key) inside the kernel. By then, the full configuration has already selected a specialization. Moving the normalization into the template argument lets equal plans name the same specialization from the start. It adds an explicit compile-time call at the call site and removes a much larger amount of repeated work later.

I generated 256 distinct configurations with eight round counts and salting disabled. Every label differs, and every supplied salt differs, but there are only eight effective plans. Invalid labels still cause compilation to fail. Dropping a field from the code-generation key does not grant permission to skip checking it.

This was the result I was looking for: doing a little programming before specialization made the rest of compilation smaller. Clang's trace makes the avoided function instantiations visible. GCC's object sizes were much closer, 33,560 versus 33,456 bytes, yet its measured compilation also improved. A nearly unchanged output size does not tell us that constructing the output cost the same amount.

There is a strict semantic boundary here. The kernel's result depends only on rounds and effective salt. The example has no per-specialization static state, no exposed kernel addresses, and no type reflection observing the original key. Removing a nominal type, a visible function identity, or a field that affects layout would require a different argument. Similar-looking machine code is not enough to justify sharing arbitrary language entities.

Now remove the opportunity to share#

A normalization benchmark that only contains duplicates is a little too convenient. I repeated the experiment with 256 genuinely distinct effective plans, using active salts to distinguish them. The same planner still runs, but it no longer reduces the number of kernel identities.

The large gain is gone. The small difference between medians is not a result I would build a design around. Normalization helps when it collapses distinctions the later stage does not need. Running a function named plan has no special performance property.

These are synthetic, single-translation-unit experiments on an Intel Xeon Platinum 8272CL, Linux x86-64, using the installed Clang 17.0.0 and GCC 14.2.0 with -std=c++20 -O2. Each variant gets one unrecorded warm-up, followed by five measurements with alternating pair order. Compiler processes are fresh; filesystem caches are warm. The machine is shared, with no core pinning or isolation. These are within-compiler comparisons, not a compiler ranking.

The timed region ends at an object file. Source generation is recorded separately; linking, checking results, and Clang tracing happen outside it. For every full-size variant, a separate runtime reference checks 17,408 outputs across all wrappers, including edge values and deterministic random inputs. The smaller ten-test suite also exercises enabled branches, active salts, rejected configurations, and exact source hashes. I did not measure runtime throughput, an application's end-to-end build, or an incremental edit loop.

The generators, harness, tests, compiler versions, source hashes, CPU times, peak-memory samples, and wall-time samples are all in the companion. It needs Node.js and a C++20 compiler; the Linux timing harness also uses /usr/bin/time. No package installation is required for these experiments.

node --test examples/the-programming-before-programming/experiment.test.mjsnode examples/the-programming-before-programming/bench.mjs clang++ clang-results.jsonnode examples/the-programming-before-programming/bench.mjs g++ gcc-results.json

Repository validation runs the smaller correctness suite, rather than turning noisy timing thresholds into CI requirements. The recorded numbers are observations from this machine. Running the harness elsewhere should produce new observations, not a promise to reproduce the same milliseconds.

Let the result be smaller than the program that produced it#

The plan is the part I would carry into a language implementation. A generator can return a small description of what must happen: selected operations, field offsets, a validated layout, a table, or a set of required functions. The next stage can use that result without replaying the entire reasoning process.

For a schema-driven serializer, I would try computing layout and field-operation descriptors once, then specializing only where the descriptor changes useful runtime behavior. A field's documentation might belong in a diagnostic record rather than in every code-generation identity. This is a proposed application of the experiment, not a serializer benchmark I have run.

There are two different forms of reuse to distinguish. During one compilation, equal plans can share work, as the C++ experiment demonstrates. Across edits, a changed input can produce an unchanged plan. Exploiting that second case requires dependency tracking and a persistent cache; the companion does not implement either.

Rust's incremental-compilation guide describes the relevant idea: recomputing a query does not have to invalidate its consumers if its result stayed the same. It also explains the cost of stable identities and fingerprinting. A plan gives a compiler designer a candidate result to compare, not a way around those costs.

My next implementation would keep validation dependencies, code dependencies, and diagnostic origins distinguishable. Editing a label should still update an error message or debug view. It should not necessarily rebuild an arithmetic kernel. Editing the planner must cause its result to be reconsidered, while an unchanged result may still allow the kernel to survive.

// A compiler design sketch, not a language API.fullInput = readTrackedInputs()validated = checkConfiguration(fullInput)plan = evaluatePlanner(validated, evaluationBudget)checkOutputSize(plan, outputBudget)codeKey = (kernelVersion, target, buildOptions, canonical(plan))body = compileOrReuse(codeKey)attachCurrentDiagnosticsAndDebugOrigins(body, fullInput)

The cache key needs the kernel implementation, target, relevant build options, and a stable representation of the plan. Inputs read by the planner must be tracked too. A hash match needs the project's chosen collision-handling policy. These obligations are easiest to meet with deterministic, bounded inputs; unrestricted filesystem, clock, or environment access makes the dependency story harder.

The compiler can have a preparation stage too#

This belongs to a longer line of research on partial evaluation: run the parts whose inputs are already known and leave a residual program for the unknown inputs. The timing of that preparation can itself be chosen.

The 2002 LOGEN paper on offline specialization describes generating a specialized specializer from a program and annotations about how to specialize it. Concrete static inputs then go through that prepared specializer. Some decisions about performing specialization have already been made before each specialization request arrives.

That gives another angle on compiler speed. A schema generator, parser generator, or DSL compiler may repeatedly process different inputs using the same generating logic. Preparing that logic once could remove repeated dispatch and analysis from subsequent requests. It has a setup cost, and changing the generator invalidates the preparation. I would measure preparation plus all uses, not start the stopwatch after the expensive part.

The local plan experiment makes that decision at a much smaller scale: it changes the key presented to an existing compiler. A prepared specializer instead changes how later specialization itself runs. Both make me look for information available before the expensive stage starts.

Do not let the generator decide the budget#

A loop that computes a table and a loop that emits one function per element can have similar-looking generator source. Their residual programs can be wildly different sizes. I would budget evaluation steps, temporary memory, generated nodes or bytes, and distinct specializations separately. Fast evaluation alone protects none of the other three.

Unrolling is an obvious place to get carried away. A runtime loop with a known bound may be entirely adequate. Repeating its body in generated code spends compilation time and code size to pursue a possible runtime improvement. That trade needs a workload, not an assumption that anything known early should be expanded.

A budget also cannot silently change language semantics. If a constant is required for a type, layout, or immediate call, exceeding the evaluation budget needs a useful diagnostic or an explicit resource-setting decision. Falling back to runtime is only available when the operation was an optional optimization and the language still permits the residual computation.

For the compiler I would want to use, the profiler would show both sides: time spent running each compile-time program, and the specializations or residual nodes it causes downstream. A generator taking 20 milliseconds might be doing excellent work if it prevents seconds of repeated lowering. A generator taking one millisecond might be the reason a build produces ten thousand functions.

That is the version of compile-time programming I find interesting. Give the compiler a small, checked answer early enough to change its workload. Then verify that the workload actually got smaller. In one experiment the answer was a discarded branch. In the other it was an eight-element set of plans where I had initially handed the compiler 256 different jobs.