第15.9章 模板膨胀、lambda，以及 fast_io 如何对 vector 去模板化

English

1. 膨胀到底是什么

模板是一台生产代码的机器。每个不同的实参都会把模板里的一切完整复制一份 —— 不只是用到实参的那部分。如果四十行的函数只有一行用到 T，另外三十行从没提到它， 那么那三十行会为每个 T 重新编译一遍。

账单有三种货币：二进制体积、指令缓存压力、编译时间。而且很容易在毫无察觉的情况下付账， 因为单看某个实例化都还算合理。

有两条路，而且不是二选一 —— 写得好的库两条都用：

2. 数一数实例化

膨胀是可测量的，而测量只需一条命令。写出那个显然的模板，用两种元素类型，然后数符号： 


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

两种元素类型，两个函数。那个函数体里真正与类型有关的只有 sizeof(T)、alignof(T) 和移动构造 —— 而包住它们的循环被原样复制了一份。

3. 每个 lambda 都是新类型

现代 C++ 里最昂贵的实例化来源是 lambda，因为 lambda 的类型不是“一个函数”， 而是编译器在源码那一点发明出来的独一无二的类。两个函数体一模一样的 lambda 是两个不同类型， 所以接收比较器的模板会被实例化两次： 


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)

三次调用，三份排序的实例化。反解器显示出眼睛看不出的差别：#1 与 #2。

由此得到的规则不是“永不用 lambda”，而是：算法是模板、而比较器不是重点时， 用具名函数对象。::std::ranges::greater、 ::std::ranges::less、::std::plus<>、 ::std::identity 之类都是普通类型，所以每个传 ::std::ranges::greater 的调用点共用一份实例化。这就是本书所有比较器都具名的原因 （第8.1章）。

lambda 真的是重点时 —— 某处一次性的谓词 —— 就写 lambda。一次实例化不叫膨胀； 一千个调用点各写一份才叫。

4. 去模板化：那条规则

fast_io 自己的贡献者指南用三行写下了这条规则：

模板参数必须为它自己付账。模板里不碰模板参数的代码会按实例化生成 —— N 个模板实参就是 N 份一模一样的机器码。

应用它，就是对模板函数体里的每一行问：这一行需要那个类型，还是只需要它的大小？ 一段扩容循环需要 sizeof(T)、alignof(T) 和一个元素的移动， 它并不需要 T。所以这段循环可以用字节写一次： 


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

三个细节让它成立，也正是这套技术的全部：

元素类型仍然要构造与销毁元素，所以那部分仍然是模板 —— 但它现在只是一层薄包装： 


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

一个函数，不管有多少元素类型。本页的两个程序做的是同一件事：第一个产生两份循环， 第二个只产生一份。

5. 真家伙：fast_io 的 vector

::fast_io::vector 就是这么造的。数据布局里没有元素类型 （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;
};

扩容算法住在 ::fast_io::containers::details::vector::detemplate 里， 只按分配器参数化。下面是最内层；注意 ::std::byte * 指针、运行期的 size 与 alignment，以及来自 第15.8章的条件错误契约。 会就地重新分配的 #if 0 块在此省略，其余与头文件中一致： 


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;
}

它上面是一层五行包装，按 size 与 alignment 参数化 —— 但只是为了决定对齐策略，从不用来干活： 


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);
	}
}

而用户可见的类是知道 T 的那层薄模板 —— 元素构造、析构，以及容量用尽时调用 去模板化的扩容： 


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>

同样的形状在 deque、sized_vector、string、 list 里反复出现：一个与元素无关的模型结构体、一个按分配器参数化的 detemplate 算法命名空间、一个薄模板外壳。这就是为什么你增加元素类型时， fast_io 的编译时间与代码体积保持平坦 —— 增加 vector<my_struct> 的代价是 my_struct 的构造函数调用， 而不是再来一份缓冲区机械。

6. 什么时候不要去模板化

7. 经验法则

← 第15.8章 if constexpr ↑ 主页 第15.10章 类型擦除 →