Ch15.9: Template Bloat, Lambdas, and How fast_io Detemplatizes `vector`

1. What Bloat Actually Is

A template is a machine for producing code. Every distinct argument produces a complete copy of everything inside the template — not just the parts that mention the argument. If a forty-line function uses T on one line and runs a loop of thirty lines that never mentions it, the thirty lines are compiled again for every T.

The bill arrives in three currencies: binary size, instruction-cache pressure, and compile time. It is easy to pay without noticing, because each individual instantiation looks reasonable.

There are two ways out, and they are not alternatives — a well-written library uses both:

Stop instantiating per type. Each lambda you pass to a template is a new type, so every lambda is a new instantiation (§2, §3).
Detemplatize. Move the part that does not depend on the argument out of the template, so it is compiled once (§4–§6).

2. Counting Instantiations

Bloat is measurable, and measuring it takes one command. Write the obvious template, use it with two element types, and count the symbols:


namespace naive
{
template <typename T>
[[nodiscard]] inline T *grow(T *old, ::std::size_t oldn, ::std::size_t newn) throws
{
	auto const res{::fast_io::native_global_allocator::allocate_aligned_at_least(alignof(T), newn * sizeof(T))};
	auto *const p{static_cast<T *>(res.ptr)};
	for (::std::size_t i{}; i != oldn; ++i)
	{
		::new (p + i) T(::std::move(old[i]));
	}
	::fast_io::native_global_allocator::deallocate_aligned_n(old, alignof(T), oldn * sizeof(T));
	return p;
}
} // namespace naive


$ nm -C prog | grep -c 'naive::grow<'
2

Two element types, two functions. Nothing in that body is type-specific except sizeof(T), alignof(T), and the move constructor — and the loop around them is duplicated verbatim.

3. Every Lambda Is a New Type

The most expensive source of instantiations in modern C++ is the lambda, because a lambda's type is not “a function”; it is a unique class the compiler invents at that exact point in the source. Two lambdas with identical bodies are two different types, so a template taking a comparator is instantiated twice:


int data[4]{3, 1, 4, 2};
my_sort(data, 4, [](int x, int y) noexcept { return x < y; });
my_sort(data, 4, [](int x, int y) noexcept { return x > y; });
my_sort(data, 4, ::std::ranges::greater{});


$ nm -C prog | grep 'my_sort<' | sed 's/.*\(my_sort<\)/\1/' | sort | uniq -c
   1 my_sort<main::{lambda(int, int)#1}>(int*, unsigned long, main::{lambda(int, int)#1})
   1 my_sort<main::{lambda(int, int)#2}>(int*, unsigned long, main::{lambda(int, int)#2})
   1 my_sort<std::ranges::greater>(int*, unsigned long, std::ranges::greater)

Three calls, three instantiations of the sort. The demangler shows the difference the eye cannot: #1 and #2.

The rule that follows is not “never use lambdas” — it is use a named function object when the algorithm is a template and the comparator is not the point. ::std::ranges::greater, ::std::ranges::less, ::std::plus<>, ::std::identity and friends are ordinary types, so every call site that passes ::std::ranges::greater shares one instantiation. That is why every comparator in this book is named (Ch8.1).

When the lambda really is the point — a one-off predicate in one place — write the lambda. One instantiation is not bloat. A thousand call sites each with its own copy is.

4. Detemplatization: the Rule

fast_io's own contributor guide states the rule in three lines:

Template parameters must pay for themselves. Code inside a template that does not touch the template parameter is generated per instantiation — N template arguments means N copies of identical machine code.

Applying it means asking, for every line in a template body: does this line need the type, or does it only need its size? A grow loop needs sizeof(T), alignof(T) and a move of one element. It does not need T. So the loop can be written once, taking bytes:


namespace erased
{
struct model
{
	::std::byte *begin_ptr{};
	::std::byte *curr_ptr{};
	::std::byte *end_ptr{};
};

namespace detemplate
{
template <typename allocator>
inline void *grow_to_byte_size(model &m, ::std::size_t newbytes, ::std::size_t size, ::std::size_t align) throws
{
	auto const oldbytes{static_cast<::std::size_t>(m.curr_ptr - m.begin_ptr)};
	auto const res{allocator::allocate_aligned_at_least(align, newbytes)};
	auto *const p{static_cast<::std::byte *>(res.ptr)};
	(void)::fast_io::freestanding::nonoverlapped_bytes_copy(m.begin_ptr, m.curr_ptr, p);
	allocator::deallocate_aligned_n(m.begin_ptr, align, oldbytes);
	m.end_ptr = p + (res.count / size * size);
	m.curr_ptr = m.begin_ptr = p;
	return p;
}
} // namespace detemplate

Three details make this work, and they are the whole technique:

The model is element-free. model is three ::std::byte *; no T appears in the layout, so one function can take it by reference.
Size and alignment became numbers. They are ordinary ::std::size_t parameters, passed at run time (and folded away by the optimiser at the call site).
The template parameter is the allocator, not the element type. Allocation policy is the only thing the loop genuinely depends on, and there are very few allocators.

The element type still has to construct and destroy elements, so that part stays in a template — but it is now a thin wrapper:


template <typename T>
class buffer
{
	using allocator = ::fast_io::native_global_allocator;
	model m_{};

public:
	void reserve_bytes(::std::size_t n) throws
	{
		detemplate::grow_to_byte_size<allocator>(m_, n * sizeof(T), sizeof(T), alignof(T));
	}
};


$ nm -C prog | grep -c 'grow_to_byte_size<'
1

One function, no matter how many element types. The two programs in this page are the same operation; the first produces two copies of the loop, the second produces one.

5. The Real Thing: fast_io's `vector`

This is exactly how ::fast_io::vector is built. The data layout has no element type in it (include/fast_io_dsal/impl/vector.h):


struct
#if __has_cpp_attribute(__gnu__::__may_alias__)
	[[__gnu__::__may_alias__]]
#endif
	vector_model
{
	::std::byte *begin_ptr;
	::std::byte *curr_ptr;
	::std::byte *end_ptr;
};

template <typename allochandle>
struct
#if __has_cpp_attribute(__gnu__::__may_alias__)
	[[__gnu__::__may_alias__]]
#endif
	vector_alloc_handle_model
{
	::std::byte *begin_ptr;
	::std::byte *curr_ptr;
	::std::byte *end_ptr;
#if __has_cpp_attribute(msvc::no_unique_address)
	[[msvc::no_unique_address]]
#else
	[[no_unique_address]]
#endif
	allochandle alloc;
};

The growth algorithm lives in ::fast_io::containers::details::vector::detemplate and is parameterised on the allocator only. Here is its innermost layer; note the ::std::byte * pointers, the runtime size and alignment, and the conditional error contract from Ch15.8. The #if 0 block that would reallocate in place is elided here; everything else is as it appears in the header:


template <typename allocator>
inline void *grow_to_byte_size_iter_impl(vector_model &imp, void *iter, ::std::size_t newcap, ::std::size_t gap, ::std::size_t size, ::std::size_t alignment)
	FAST_IO_HERBCEPTIONS_THROWS_IF(allocator::throws_on_allocation_failure)
{
	::std::byte *old_begin_ptr{imp.begin_ptr};
	::std::byte *old_curr_ptr{imp.curr_ptr};
	::std::size_t const old_size{static_cast<::std::size_t>(old_curr_ptr - old_begin_ptr)};
	::std::size_t const old_capacity{static_cast<::std::size_t>(imp.end_ptr - old_begin_ptr)};

	auto const newres{allocator::allocate_aligned_at_least(alignment, newcap)};
	auto *const begin_ptr{static_cast<::std::byte *>(newres.ptr)};
	auto *const newiter{::fast_io::freestanding::nonoverlapped_bytes_copy(old_begin_ptr, static_cast<::std::byte const *>(iter), begin_ptr)};
	static_cast<void>(::fast_io::freestanding::nonoverlapped_bytes_copy(static_cast<::std::byte const *>(iter), old_curr_ptr, newiter + gap));
	allocator::deallocate_aligned_n(old_begin_ptr, alignment, old_capacity);

	imp.begin_ptr = begin_ptr;
	imp.curr_ptr = begin_ptr + old_size;
	imp.end_ptr = begin_ptr + (newres.count / size * size);
	return newiter;
}

Above it sits a five-line wrapper that is templated on size and alignment — but only to decide an alignment policy, never to do work:


template <typename allocator, ::std::size_t size, ::std::size_t alignment>
inline constexpr void *grow_to_size_iter_impl(vector_model &imp, void *iter, ::std::size_t newcap)
	FAST_IO_HERBCEPTIONS_THROWS_IF(allocator::throws_on_allocation_failure || allocator::throws_on_violations)
{
	if constexpr (alignment < allocator::default_alignment)
	{
		return ::fast_io::containers::details::vector::grow_to_size_iter_impl<allocator, size, allocator::default_alignment>(imp, iter, newcap);
	}
	else
	{
		return ::fast_io::containers::details::vector::detemplate::grow_to_size_iter_impl<allocator>(imp, iter, newcap, size, alignment);
	}
}

And the user-visible class is the thin, templated layer that knows about T — element construction, destruction, and calling the detemplated growth when capacity runs out:


template <typename T, typename Alloc = ::fast_io::native_global_allocator>
using vector = ::fast_io::containers::vector<T, Alloc>;

// CTAD guides, so the allocator is never written at a call site
template <::std::input_iterator InputIt>
vector(InputIt, InputIt) -> vector<typename ::std::iterator_traits<InputIt>::value_type, ::fast_io::native_global_allocator>

The same shape repeats in deque, sized_vector, string and list: an element-free model struct, a detemplate namespace of algorithms parameterised on the allocator, and a thin templated shell. That is why fast_io's compile times and code size stay flat as you add element types — adding vector<my_struct> costs you one my_struct's constructor calls, not another copy of the buffer machinery.

6. When Not to Detemplatize

When the type is needed for speed. A detemplated loop over bytes cannot inline T's move constructor. For trivial types the optimiser recovers it; for a move constructor that does real work per element, the templated version is faster. fast_io keeps uninitialized_move templated for that reason and detemplatizes only the allocation-and-copy-of-raw-bytes part.
When there is only one instantiation. A template used with one type is not bloated; it is just a function.
When the extraction makes the code unreadable. Three void * parameters and two runtime sizes are worse than a duplicate if the function is ten lines and used twice.

7. Rules of Thumb

Measure before you refactor: nm -C binary | grep -c 'name<' is the whole toolchain you need.
Pass named function objects (::std::ranges::greater) to templates; keep lambdas for one-off use.
Split a template at the point where the type is used: everything before and after that point belongs in a non-template function.
Replace “the type” with sizeof, alignof, ::std::byte * and void * wherever the code does not construct, destroy or call something on an element.
Parameterise on what changes rarely (the allocator), not on what changes often (the element type).
Bloat compounds: a templated algorithm that calls a templated helper that calls a templated logger is one instantiation tree per call site.

Ch15.9: Template Bloat, Lambdas, and How fast_io Detemplatizes vector