Patternia Performance - v0.9.6¶
Published: November 2026
Focus: One switch for every keyed match, on GCC as well as Clang,
for borrowed and owned subjects, with less debug information.
Overview¶
Before v0.9.6, each kind of keyed match had its own lowering. Dense
val<N> literals used a table of function pointers or a recursive
comparison tree, lit(...) literals used a chain of comparisons, and
variant alternatives used a comparison chain or a function-pointer
table depending on the number of alternatives. Clang usually folded
these into good code. GCC often did not: whether it inlined the
dispatch depended on its size estimates and on the order of functions
in the translation unit, and when it did not, the case pack was written
to the stack and every comparison stayed a branch.
v0.9.6 lowers every keyed plan to the same shape. The plan computes a
small integer (the literal's offset, the index of the first matching
lit, or the variant's index()), and one index_visit switch over
that integer runs the selected case. Every function on that path is
always inlined. On x86-64 the result is the code of a hand-written
switch with GCC 11 and 13 and Clang 14 and 18, and the codegen gate in
CTest keeps it that way.
The release also introduces owned subjects (match(std::move(x))).
They use the same plans as borrowed subjects, so moving a subject into
a match does not cost a slower dispatch.
Changes¶
| Pull request | Change | Effect |
|---|---|---|
| #93 | Store the case pack in a type whose accessors are always inlined | GCC no longer writes the case pack to the stack when a function's position in the file changes its inlining budget |
| #94 | Owned subjects use the dense-literal plan | An owned val<N> match compiles like a borrowed one |
| #97 | Variant alternatives dispatch through a switch on index() |
Replaces the comparison chain (few alternatives) and the function-pointer table (many) |
| #98 | PTN_ON and static_on cache stateless case packs as const |
GCC builds a lookup table instead of a jump table through a mutable static |
| #99 | Inline the lit(...) comparison chain for owned subjects |
Owned literal matches lose their remaining call |
| #100 | Inside a variant arm, cases that only test the alternative are not tested again | One switch, then the handler |
| #102 | lit(...) lists compute the first matching index with comparisons that each yield a constant, then switch on it |
GCC turns 15 sparse literals from 14 branches into a table lookup |
| #103 | Dense val<N> literals go through the same index_visit switch |
Replaces the comparison tree that GCC left as branches |
| #104 | Owned variants with five or more alternatives switch on the active alternative | Owned variant matches stop testing alternatives one by one |
| #105 | Always inline the owned evaluation path | Owned matches on Apple Clang reach hand-written speed |
| #106 | Keep the case pack's type out of the names of per-case templates | GCC debug information shrinks about 8× |
The plans and their thresholds are described in Performance Tuning.
Generated code¶
Instructions in the probe function at -O2 on x86-64, from Compiler
Explorer, v0.9.5 → v0.9.6. "b" counts conditional branches. The
reference is the same logic written by hand in the same file
(switch, if chain or std::visit).
| Probe | GCC 13.3 | Clang 18.1 | Reference (GCC / Clang) |
|---|---|---|---|
16 dense val<N> |
38/1b → 6/0b | 46/1b → 6/0b | — |
64 dense val<N> |
134/1b → 7/1b | 144/1b → 6/0b | 6 / 6 |
64 dense val<N>, cached pack |
134/1b → 7/1b | 15/1b → 6/0b | 7 / 6 |
8 lit(...) |
26/7b → 7/1b | 10/0b → 7/0b | — |
15 sparse lit(...) |
47/14b → 6/1b | 40/1b → 39/1b | 7 / 39 |
16-alternative variant, is<T> |
59/8b → 8/1b | 80/4b → 7/1b | — |
| 16-alternative variant, cached | 52/8b → 7/1b | 47/4b → 7/1b | 8 / 7 |
16-alternative variant, $(is<T>) bindings |
61/8b → 55/1b | 99/22b → 8/1b | — |
| 2-alternative variant with a guard | 18/2b → 17/2b | 18/2b → 18/2b | 17 / 17 |
GCC 11.4 and Clang 14 give the same picture, except that GCC 11 keeps two branches for the 8-literal and sparse cases (11/2b and 10/2b). Clang already compiled the sparse list to a table in v0.9.5, so it does not change. The probes that use v0.9.6 features (owned subjects, expression guards) have no v0.9.5 counterpart; they are all within a few instructions of their reference.
Run time¶
Apple Clang¶
Apple M5 Pro, Apple clang 17.0.0, -std=c++17 -O2 -DNDEBUG. The same
benchmark sources (bench/bench_suite.cpp, bench/bench_scale.cpp)
were built against the v0.9.5 headers and the v0.9.6 headers. Each
benchmark is the median of 20 repetitions; the table gives the median
of three process runs, alternating versions. Times are ns per match.
| Benchmark | v0.9.5 | v0.9.6 | Hand-written |
|---|---|---|---|
16 dense val<N> |
1.92 | 0.92 | 0.92 (switch) |
32 dense val<N> |
3.01 | 0.91 | 0.92 |
64 dense val<N> |
5.21 | 0.92 | 0.92 |
128 dense val<N>, on(...) |
8.92 | 0.94 | 0.92 |
128 dense val<N>, PTN_ON |
0.97 | 0.94 | 0.92 |
lit(...) list |
0.93 | 0.92 | 0.92 |
| 32-alternative variant | 3.38 | 0.90 | 0.91 (switch on index()) |
| 32-alternative variant, cached pack | 2.60 | 0.93 | 0.91 |
| Scale, 4 alternatives | 1.53 | 1.32 | 1.31 |
| Scale, 8 alternatives | 1.20 | 0.95 | 0.96 |
| Scale, 16 alternatives | 2.69 | 1.31 | 1.32 |
| Scale, 32 alternatives | 3.17 | 1.32 | 1.32 |
| 2-alternative variant, guarded | 1.82 | 0.95 | 0.96 |
| Protocol router | 1.20 | 0.89 | 0.83 (if chain) |
| Command parser | 1.14 | 1.00 | 0.97 |
| Packet mixed | 1.13 | 1.15 | 1.56 |
| 2-alternative variant | 0.92 | 1.31 | 1.31 |
| 2-alternative variant, one hot alternative | 0.55 | 0.87 | 0.66 |
Run-to-run spread was under 3% for most rows and up to 13% for the
scale benchmarks. Before this release, a dense literal match without
PTN_ON grew linearly with the number of cases; it is now flat.
The last two rows got slower. v0.9.6 compiles the two-alternative
match to exactly the instructions of the hand-written
switch (v.index()): two compares and three conditional selects.
v0.9.5 produced a different sequence with one never-taken branch,
which this core runs faster in a tight loop. Code layout matters at
this scale: in the same pair of binaries, the hand-written 32-case
switch with one hot alternative, whose source did not change, went
from 0.52 to 0.87 ns. We have not found a way to make Clang choose the
v0.9.5 sequence without diverging from the hand-written code
elsewhere.
GCC in CI¶
The bench-publish job runs the suite with GCC 13 on a GitHub-hosted
x86-64 runner after every push to main. Shared runners vary from run
to run, so the table below divides each Patternia time by the fastest
hand-written implementation in the same run, and gives the median of
8 runs on v0.9.5 code and 3 runs on v0.9.6 code. 1.00 means as fast
as the best hand-written version.
| Benchmark | v0.9.5 | v0.9.6 |
|---|---|---|
| Variant, mixed alternatives | 1.99 | 1.02 |
| Variant, mixed, guarded | 1.72 | 1.02 |
| Scale, 4 alternatives | 1.45 | 1.15 |
| Scale, 8 alternatives | 1.87 | 1.12 |
| Scale, 16 alternatives | 1.78 | 1.00 |
| Scale, 32 alternatives | 2.27 | 1.05 |
| Command parser | 1.27 | 1.05 |
| Variant, one hot alternative | 0.98 | 1.09 |
| Variant, one hot alternative, guarded | 0.97 | 1.16 |
| Protocol router | 1.07 | 1.15 |
| Packet mixed | 1.17 | 1.27 |
| Packet mixed, heavy bindings | 1.12 | 1.13 |
The first seven rows are the intended improvement. The last five are within the spread between runs on the same code (up to about 15% on these runners). The benchmark harness itself changed in #93, which force-inlines the per-benchmark runner, so the two columns are not a strict same-binary comparison.
Owned subjects¶
bench/bench_ownership.cpp runs the same cases on a borrowed subject
(match(x)), an owned subject (match(std::move(copy))) and
hand-written code. Same machine and settings as above, median of three
process runs of 10 repetitions, ns per match:
| Scenario | Borrowed | Owned | Hand-written |
|---|---|---|---|
lit(...) on an int |
0.97 | 0.97 | 0.97 |
64 dense val<N> |
0.97 | 0.97 | 0.98 |
| 4-alternative variant with bindings | 1.51 | 1.44 | 1.77 |
| Rejected guards, then a later case | 1.21 | 1.21 | 1.21 |
| Structural bindings with a guard | 1.22 | 1.06 | 1.23 |
| Handler takes over a heap string | 16.89 | 1.48 | 2.24 |
| Two rejected guards, then a consuming fallback | 16.50 | 1.88 | 1.77 |
Owned matches cost the same as borrowed ones, or less. The two consuming scenarios show what ownership is for: a borrowed subject has to be copied to hand it to a by-value handler, which allocates; an owned subject is moved. Guards before the consuming case observe the string without moving it, and adding one, two or four rejected guards does not change the time (1.05 ns in each case).
Debug information¶
GCC writes the name of every template instantiation, with all its template arguments, into the debug information. Before v0.9.6, the type of the whole case pack appeared in the arguments of every per-case template, so a match with N cases wrote N names that were each as long as the case list. v0.9.6 passes a case's index instead of the pack type where the pack type is not needed.
bench/bench_suite.cpp, -O2 -g, object file size and compile time
on the same machine:
| Compiler | v0.9.5 | v0.9.6 |
|---|---|---|
GCC 13 (macOS, with pubnames) |
686 MB, 18.4 s | 92 MB, 5.8 s |
GCC 13, -gno-pubnames (as on Linux) |
206 MB, 10.1 s | 25 MB, 4.2 s |
| Apple Clang 17 | 4.7 MB, 2.6 s | 3.9 MB, 1.7 s |
Single probes from tests/codegen/ (GCC 13, -gno-pubnames, object
file size):
| Probe | v0.9.5 | v0.9.6 |
|---|---|---|
16 dense val<N> |
7.6 MB | 0.3 MB |
64 dense val<N> |
31.7 MB | 1.3 MB |
16-alternative variant, $(is<T>) bindings |
21.4 MB | 2.7 MB |
16-alternative variant, is<T> |
2.0 MB | 1.9 MB |
Clang's object files were small to begin with and shrank less.
Limits¶
- Owned variants with four or fewer alternatives are evaluated in
source order. The compilers already make tight code of so few index
tests, and Apple Clang 17 turned the
switchinto a tree of compares that was slower. - With
$(is<T>)bindings on a 16-alternative variant, GCC now has one conditional branch but still emits 55 instructions, where Clang emits 8. - A 16-alternative variant match without bindings still produces about 1.9 MB of GCC debug information; that probe did not shrink.
- MSVC was not measured. The dispatch functions are
__forceinline, but MSVC has no portable way to force a lambda inline. - Two-alternative variant matches on Apple Clang are slower than in v0.9.5, as described above. Workloads dominated by one hot alternative are within noise on GCC.
Methods¶
- Instruction counts:
scripts/check_codegen.pyon the probes intests/codegen/, compiled at-O2through the Compiler Explorer API for GCC 11.4 and 13.3 and Clang 14 and 18.1 on x86-64. The probes at v0.9.5 were compiled against thev0.9.5tag's headers. - Apple Clang timings: Google Benchmark,
min_time0.5 s and 20 repetitions per benchmark (bench_ownership: 0.2 s and 10), three process runs per version in the order v0.9.5, v0.9.6, ownership. The binaries were built from the v0.9.6 benchmark sources against each version's headers. - GCC timings: the
bench-publishworkflow's logs for the last pushes tomainbefore and after the dispatch changes. - Debug sizes: object file size after
-c -O2 -g, wall-clock compile time of a single run, GCC 13.3 from Homebrew and Apple clang 17.
Outcome¶
Keyed matches in v0.9.6 compile to a hand-written switch on both
major compilers, independent of the number of cases and of where the
function sits in the file. Dense literal matches that grew linearly
with the case count are now constant time, variant matches on GCC went
from about twice the hand-written time to parity, owned subjects cost
nothing over borrowed ones, and GCC debug builds are about 8 times
smaller. The one measured regression is the two-alternative variant on
Apple Clang, where Patternia now matches the hand-written switch
instead of beating it.