You wrote one pool by hand last week, and priced the virtual call. Write it once instead, and let the compiler
stamp out a version for every type you need. A template is not a runtime abstraction that happens to
be fast — it is code generation, finished before main starts, and the
machine code it emits is the code you would have written by hand.
concept instead of an enable_if, and read the error message it produces.if constexpr so the dead arm is never instantiated — and know when a plain if would not have compiled at all.if constexpr codec
HW5: class template + variadic utility, with tests
Project Phase 1: one templated codec, no per-type copy-paste
There are two ways to write one algorithm that works for many types. A virtual function decides which code to run while the program is running, from a pointer it has to load. A template decides while the program is being compiled, and then there is nothing left to decide. Both are polymorphism. Only one of them is free.
Virtual dispatch itself — inheritance, the vptr and vtable, virtual destructors, final —
was covered in week 4, Runtime polymorphism
(the cost simulator). Here it is the baseline you are comparing against.
A template is a recipe, not code. Nothing is emitted until you use it with a concrete type; at that point the compiler instantiates it — generates one real function or class for that type — and from then on the call is an ordinary direct call to an ordinary function whose body it can see, inline and fold.
The price is that the type set has to be known at compile time, and every distinct instantiation is separate machine code. That is the whole trade, and Part 3 makes you put a number on it.
The same enc() called 12 times per tick, two ways. Move the call-count slider to see the cost
scale linearly, and the type-mix slider to watch the branch predictor stop helping. Press
Race to run it.
ICodec&hot_template<C>sizeof and drop to
0.75 ns. Directional, not a benchmark — measure your own.// runtime polymorphism: one vtable, one indirect call struct ICodec { virtual std::size_t enc(Buf&, std::int64_t) const = 0; virtual ~ICodec() = default; }; std::size_t hot_virtual(const ICodec& c, Buf& b, std::int64_t v) { return c.enc(b, v); // load vtable, load slot, jump } // compile-time polymorphism: no base class, no vtable struct FastTickCodec { std::size_t enc(Buf& b, std::int64_t v) const { std::memcpy(b.p, &v, sizeof v); return sizeof v; } }; template <class C> std::size_t hot_template(const C& c, Buf& b, std::int64_t v) { return c.enc(b, v); // direct, inlined, folded }
Templates are code generation, so you should be able to answer “how many functions did I just create, and how big are they?” Pick the types your codec is used with and read the answer.
put<T> withThree mechanisms carry almost every generic thing you will write this term.
Deduction means you rarely spell out the type. Concepts say which
types are allowed, in one word, with an error message a human can read. if
constexpr lets one function body contain several mutually incompatible
implementations, because the compiler throws away the ones it did not pick.
max_of(3, 4) deduces T = int; you never write
<int>. When one type deserves bespoke treatment you specialise:
a full specialization for exactly that type, or a partial one for a family
(Ptr<T*>). Overload the hot type when the generic body is a cycle too slow —
but measure first.
std::is_integral_v<T>,
std::is_trivially_copyable_v<T>, std::is_same_v<A,B> resolve
to true/false before the program runs.
std::remove_reference_t, std::decay_t,
std::conditional_t compute new types. Write your own: a trait is
just a template with a static constexpr bool value.
template <class... Ts> binds a whole list;
sizeof...(Ts) is its length at compile time. A C++17 fold collapses the pack over an
operator in one line — (xs + ...), or (encode(b, fs), ...) to write a
whole message. No recursion, no base case, and it unrolls completely.
Concepts are the C++20 replacement for
enable_if: a named, readable constraint that fails at the constraint
instead of two hundred lines deep inside your codec. Click a cell to see the requirement and the
verdict.
if constexpr — which arm survives?One body, three implementations, and only one of them is
ever compiled for a given T. The greyed lines are not dead code the optimiser removes
later — they are never instantiated, which is why they are allowed to be
nonsense for this type. Compare with the plain-if column.
if constexpr — compilesif — ?Here is the payoff, and here is the price. One Ladder template gives you a
fixed-depth book side for equities in integer ticks, for futures in a different tick size, and for
anything else, with inline storage and no heap traffic — and each instantiation is
a separate copy of the machine code. Both of those are true at once, and you are expected to say so.
Parameterise on the price type, the depth and the side, then
read what the compiler produced: the layout, the sizeof, the cache lines it occupies and
which arm of the comparator survived.
Every instantiation is its own machine code. Usually irrelevant; occasionally it is your p99, because the hot path stops fitting in the 32 KB level-one instruction cache and every tick starts with a fetch miss.
T belongs in an ordinary non-template function the instantiations call. One copy instead of twenty.std::string, const char* and char[8] are three different Ts and three copies of the same algorithm. Take a std::string_view and you have one.Your C++ bot speaks a JSON tagged union to the Python exchange — Handshake,
PlaceOrder, OrderAck, BookSnapshot, CancelOrder,
each selected by a type field. This week that becomes one templated
put<T> / encode<T> path with an if constexpr
per field kind and a fold to write a whole message, instead of one hand-written serialiser per
message and a runtime switch on the tag.
Next week that same union becomes a std::variant with a compile-time
visitor, and the switch disappears from the receive path too. Everything in Week 6 —
traits, tag dispatch, CRTP, policies — is built on what you write today.
These are the five that cost marks on HW5, every time. Open them.
.cppYou declare template <class T> std::size_t put(Buf&, const T&); in the
header and define it in codec.cpp. It compiles. Then the link fails with
undefined reference to put<long>(...) and the message looks
like a build-system problem, which it is not.
A template is not code — the compiler can only emit put<long> at the point
where it can see both the use and the definition. Your translation unit saw the
declaration, so it emitted a call; the one that had the definition never saw a use, so it emitted
nothing.
Fix: define templates in the header (that is why the STL is header-only), or, if you
genuinely want to hide the body and you know the complete type set, use
explicit instantiation: template std::size_t
put<std::int64_t>(Buf&, const std::int64_t&); in the .cpp, one line
per type. That also caps the bloat — at the cost of the type set no longer being open.
if where you needed if constexprif (std::is_integral_v<T>) memcpy(out, &v, sizeof v); else return
encode(v.data(), v.size()); reads fine and fails to build for T = int, because
both arms of a runtime if must compile for every instantiation —
and int has no .data(). The condition being a compile-time constant does
not save you; it is still an if.
The same mistake in reverse is subtler: with if constexpr the discarded arm is not
instantiated, so a genuine bug living in a branch no type ever selects will sit there silently for
the rest of the term until someone adds the type that reaches it.
Fix: if constexpr whenever the condition is a property of
T. Terminate the chain with else static_assert(always_false<T>,
"unhandled type") — a dependent-false helper, because a bare
static_assert(false) fires even in a discarded arm — so a type you forgot is a
readable build error instead of a silent fall-through.
T&& is not always an rvalue referenceIn template <class T> void submit(T&& o), T&& is a
forwarding reference: it binds to lvalues and rvalues alike, and T
is deduced as Order& in the first case. So std::move(o) inside that
function will happily gut a caller's live object — you moved from something the caller still owns
and still uses.
The tell is that it works in every test, because your tests pass temporaries. It breaks the first time the call site passes a named variable, which is the first time it matters.
Fix: in a pass-through, always std::forward<T>(o), never
std::move. std::move is for when you own the object and are done with
it. And remember the asymmetry: in template <class T> class Pool { void
push(T&&); }, T is already fixed by the class, so that
T&& really is an rvalue reference.
send("AAPL"), send(sym_string) and send(sym_view) look
like one function used three ways. They are send<char[5]>,
send<std::string> and send<std::string_view> — three
complete copies of your serialiser in .text, doing identical work. Multiply by the
number of call sites and templates and you can add tens of kilobytes to a hot path that has
32 KB of L1i to live in.
The cost does not show up as a slower call. It shows up as instruction-fetch misses at the start of a tick, which is a p99 problem with no line of code to blame.
Fix: normalise at the boundary — take std::string_view and
std::span<const std::byte> so there is one T. Hoist every line that
does not mention T into a non-template helper. Then check: nm -C --size-sort
your_bot | tail -40 lists your largest symbols, and duplicated instantiations are obvious
in that list.
typename, and shipping the error walltypename Container::value_type x; needs the typename keyword because
at definition time the compiler cannot know whether Container::value_type names a
type or a member — the name is dependent on T, and the default
assumption is “not a type”. The sibling case is obj.template get<0>(), where
without template the < parses as less-than.
The larger version of this pitfall is what you hand to whoever reads your error: an unconstrained template that a wrong type reaches will fail deep inside your codec and print the whole instantiation stack. The bug is one line at the call site; the message is two screens from somewhere else.
Fix: typename for dependent types, .template for dependent
member templates. Then constrain the entry point — template <Encodable T>, or
void send(Encodable auto& m) — so a wrong type fails at
your constraint with your name on it. That is the real reason concepts beat
enable_if: not brevity, error quality.
Three questions, instant feedback, nothing recorded.
Q1At a call site that only ever sees one concrete type, which part of a virtual call costs the most?
Q2You write if (std::is_integral_v<T>) memcpy(out, &v, sizeof v); else write(v.data(), v.size()); — a plain if, not if constexpr — and instantiate it with T = int. What happens?
Q3You templatise the hot path and end up with 20 instantiations of a 700-byte inlined body. Every individual call gets faster. What is the risk you now have to check?
max_of<T>, then check with
-O2 -S that the call vanishes into a cmov.std::vector,
std::sort, std::accumulate, and T{} for the right zero.sum(...) with a fold, then avg(...) on top of it using
sizeof...(xs).if constexpr codec with an integer path and a quantised floating path, plus an
enable_if version of the same constraint so you have seen both.if constexpr or SFINAE that selects a
different path per type, and evidence it inlines (diff -O2 -S for two
instantiations).encode<T> / decode<T> — no per-type copy-paste on the send path.nm -C --size-sort on your binary. If one algorithm appears
three times, normalise the type.make test confirms nothing else regressed.Pool<T,N>, once, for everything.