Skip to content

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 switch into 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.py on the probes in tests/codegen/, compiled at -O2 through 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 the v0.9.5 tag's headers.
  • Apple Clang timings: Google Benchmark, min_time 0.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-publish workflow's logs for the last pushes to main before 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.