Perfect—here’s a deeper treatment of the five starter projects. For each one I expand the Idea (what to build) and Why TMP (why templates change the game vs a runtime/naïve design). I close with the same three 10-point ratings you asked for.
Build a header-only FFT “compiler” that, given N, emits a fully specialized transform:
- Factor
Nat compile time into radices (2/3/4/5/8/16…); generate the butterfly graph and stride schedule as a type-level structure. - Select algorithmic family per factorization (decimation-in-time, Stockham, split-radix) as policies.
- Emit specialized micro-kernels for the small radices (e.g.,
radix_4<TwiddlePolicy, LayoutPolicy>), compose them into a loop-free pipeline, and fold permutations when possible. - Precompute twiddle tables via
constexprtrig (with Estrin/Horner polynomial approx for speed) and pin alignment/SoA layout in types so vectorization is deterministic.
Sketch:
template<size_t N, class AlgoPolicy, class LayoutPolicy, class TwiddlePolicy>
struct fft_plan; // materializes compile-time factorization and kernels- Dead-path erasure: The decomposition (e.g.,
N=2^a·3^b·5^c) is a compile-time fact. With partial specializations/if constexpr, only the required butterflies and permutations exist in the final binary—no runtime planner/dispatch. - Instruction-cache friendly: Fully unrolled small-radix kernels + constant strides enable aggressive inlining and register reuse. A runtime “generic” FFT must carry stride/twiddle arithmetic in hot loops.
- Vectorization on rails: Types encode layout (
SoA<2>,Interleaved, alignment) and radix shapes, so the compiler can unroll and emitFMA/SIMD without guessing. Runtime code must branch, blocking vectorizer heuristics. constexprtwiddles: Precompute tables and encode access patterns (bit-reversal, split-radix sign flips) in types; loads become indexed by compile-time constants → constant-folding/strength reduction.- Specialize by target: Policy types pick
AVX2vsAVX-512vs scalar kernels at compile time; no virtual indirection or flag checks in the inner loop.
Ratings: Math 6 • Impl 8 • Real 9
A family of FIR filters where tap count, symmetry, coefficient domain, and scheduling strategy are template parameters:
- If taps are symmetric/antisymmetric, generate half-accumulation kernels automatically.
- Choose accumulator type and quantization (float, Q1.31, mixed precision) via policy.
- Emit unrolled loops with compile-time chunking that matches SIMD width and cacheline size; optional circular buffer with compile-time power-of-two mask.
Sketch:
template<size_t Taps,
class CoefT,
class SymmetryPolicy, // symmetric, antisymmetric, none
class SchedulePolicy, // unroll<VW>, block<B>, circular<Pow2>
class RoundingPolicy> // toward_zero, nearest_even, stochastic
struct fir;- Exploit structure → fewer ops: Symmetry halves MACs; half-band zeros skip work. A runtime kernel must branch per sample; templates erase those branches.
- Zero-overhead specialization:
Taps, unroll factor, and alignment become constants → exact unroll, prefetch distance, and FMA grouping are compiled in, not guessed. - Compile-time safety:
concepts/requiresenforce valid combinations (e.g., half-band requires oddTaps, linear phase constraints). Catch design errors at compile time. - No heap/virtuals: Small filters fit on stack or in
staticstorage; codegen is identical to hand-rolled kernels but parameterized. - Deterministic SIMD: A
SchedulePolicy<SimdWidth<8>>yields one inner kernel per ISA; nothing in the hot path checks mode flags.
Ratings: Math 5 • Impl 7 • Real 10
A convolve front end that chooses the optimal algorithm at compile time, based on signal and kernel sizes, streaming vs offline, and latency budgets:
- For small
M, choose direct or Winograd; for largeM, choose FFT; for streaming, pick overlap-save/overlap-add with block size computed from L2/cache and FFT radix preferences. - Compose the chosen pipeline (windowing → FFT → pointwise → IFFT → overlap fixup) as a single, fused expression template to minimize temporaries and copies.
- Allow external backends (your FFT from #1, or cuFFT/FFTW) via a policy.
Sketch:
template<size_t N, size_t M, class ModePolicy, class FFTPolicy, class LayoutPolicy>
auto convolve(View<N> x, View<M> h);- Thresholds are constants: For fixed-shape systems, the
N,M, and mode are often known at compile time. Specialization lets you delete non-viable strategies; no runtime “if (M < 32) … else …”. - Fused pipelines: Expression templates build the multi-stage DAG so copies/normalizations can be hoisted or eliminated (e.g., apply scaling only once at the end).
- Cache-aware by construction: Block size and overlap are type parameters selected from cache/ISA traits; runtime systems can only approximate with heuristics.
- Backend without cost: Policy types choose the FFT backend with static polymorphism; hot loops have no virtual calls.
- Latency control: In streaming mode, the block scheduler is generated with the minimal state footprint and no dynamic maps/allocations.
Ratings: Math 6 • Impl 7 • Real 9
A Kalman family where state dimension n, measurement dimension m, and numeric/storage choices are template parameters:
- Provide
KF<n,m, UpdatePolicy, FactorPolicy, ScalarT>with compile-time fixed matrices (Vec<n>,Mat<n,n>). - Choose update flavor (standard KF, EKF with Jacobian policy, UKF with sigma-point policy) and factorization (Cholesky, LDLᵀ) via policies.
- Enforce SPD, symmetry, and dimension compatibility at compile time; optional
noexceptpath for real-time.
Sketch:
template<size_t n, size_t m,
class UpdatePolicy, // KF, EKF<J>, UKF<SigmaPoints>
class FactorPolicy, // Cholesky, LDLT
class ScalarT> // float, double, fixed
struct kalman;- Static linear algebra = speed: With
nandmas non-type template params, loops unroll and stack storage replaces heap. For small/medium filters (common in control/SLAM), this beats generic dynamic-size BLAS. - Policy-selected numerics:
if constexprchooses Cholesky vs LDLᵀ (or Joseph form for covariance) with no runtime flag checks; the compiler removes unused code. - Compile-time contracts:
requires SPD<ProcessNoise>orrequires Symmetric<Cov>guard against misuse. You get readable, early diagnostics instead of runtime asserts. - Deterministic latency: No dynamic allocation, no virtuals, no size checks in the hot path → stable timing for embedded/real-time contexts.
- Backend freedom: You can still delegate heavy ops to a static-size backend (e.g., a tiny fixed-matrix library or intrinsics) chosen via policy, with zero runtime cost.
Ratings: Math 8 • Impl 8 • Real 9
Design a tiny embedded DSL using expression templates to describe multi-stage stencil updates on structured grids:
- Encode grid extents, halo width, dimensionality, and memory layout (AoS/SoA/tiled) as types.
- Users write formulas like
u_next = a*laplace(u) + b*grad_dot(u,v); the DSL builds an AST and emits a single fused kernel per time step. - Boundary conditions (Dirichlet/Neumann/periodic/Sommerfeld) are policies; codegen injects the right prologue/epilogue without branching in the interior.
- Optional schedule policy selects blocking/tiling to match cache and SIMD width.
Sketch:
template<class Shape, class Layout, class BC, class Schedule>
struct field;
template<class Expr> void step(field<...>& out, const Expr& e); // fuses expression- Loop fusion by construction: Expression templates combine multiple operators (e.g., Laplacian + nonlinear terms) into a single pass, eliminating temporaries and cache-thrashing copies.
- Index math as constants: Stencil radii and neighbor offsets are known at compile time; pointer arithmetic becomes constant-folded, SIMD-friendly code.
- BC/layout without branches: With BC/layout encoded in types, the interior kernel is branchless; separate specialized kernels handle boundaries (or predicated loads), selected at compile time.
- Predictable memory traffic: Tiling/unrolling are compile-time schedule parameters; the compiler can see exact strides and emit wide loads/stores.
- Extensible algebra: Adding a new stencil or nonlinear term adds a node type; the fusion machinery and policies remain unchanged.
Ratings: Math 8 • Impl 9 • Real 8
- Runtime flags/branches in hot loops block vectorization and inhibit inlining. TMP removes them entirely.
- Dynamic sizes force heap allocation and generic kernels. Static non-type params unlock stack storage and unrolling.
- Virtual dispatch adds overhead and prevents interprocedural optimization across “black-box” calls. Static polymorphism (policy types) composes cleanly.
- Generic index math repeats work per element. Compile-time schedules make strides/offsets constants.
If you want next steps, say which one you’d like me to scaffold first (FFT or FIR are the most “immediately measurable”), and I’ll draft the template interfaces plus a tiny -O3 -march=native benchmark harness.