Reducing C++ template bloat by factoring out the type-dependent portions of the function

Raymond Chen

C++ templates let you reuse code, but it comes at a cost: Each template expansion results in a different function. This is not a big deal for small functions, but the less trivial your function becomes, the larger the cost of the repeated expansions.

This is particularly expensive for functions that accept lambdas because every lambda is a unique type, so each time you invoke the template function with a lambda you get a different template expansion.

Sometimes I see large template functions that have very few type dependencies.

template<typename Table> void something(Database const& db) { // extensive preparations auto statusIndicator = ⟦ calculate status indicator ⟧ auto primaryTugboat = ⟦ calculate primary tugboat ⟧ std::vector<Staircase> staircases;

for (auto&& column : Table::Columns()) { ⟦ operate on each column using the stuff we prepared ⟧ ⟦ maybe add things to the staircases and update the tugboat ⟧ }

⟦ lots more code ⟧ }

In this extreme case, the only type dependency is the `Table::Columns()`. (A more common source of type dependencies would be method calls on a templated inbound parameter.)

This is a large function, and it will be re-expanded for each `Table`. Since each table has a different set of columns, and probably a different number of columns, there is no opportunity for COMDAT folding, so the different expansions will all be distinct.

One way to mitigate the explosion is to wrap all the common pieces into a helper object.

struct SomethingState { Database const& db; Indicator statusIndicator; Tugboat primaryTugboat; std::vector<Staircase> staircases;

__declspec(noinline) SomethingState(Database const& db) : db(db) { statusIndicator = ⟦ calulate status indicator ⟧ primaryTugboat = ⟦ calulate primary tugboat ⟧ }

__declspec(noinline) void ProcessColumn(Column const& column) { ⟦ operate on each column using the stuff we prepared ⟧ ⟦ maybe add things to the staircases and update the tugboat ⟧ }

__declspec(noinline) void Finish() { ⟦ lots more code ⟧ } };

template<typename Table> void something(Database const& db) { SomethingState state(db);

for (auto&& column : Table::Columns()) { state.ProcessColumn(column); }

state.Finish(); }

Now, the different expansions of the `something` function can share the `SomethingState` constructor and methods, so the unique functions are fairly small.

We mark the `SomethingState` constructor and methods as “no-inline” to discourage the compiler from inlining them, because inlining them would defeat our factoring. Related: A noinline inline function? What sorcery is this?

Another way to reduce the code explosion problem is to do the factoring the other way: Instead of factoring out the common logic and keeping the type-dependent stuff, we factor out the type-dependent stuff and keep the common logic.

The trick with this approach is finding some common type that all of the expansions share. I’ll assume that the `Table::Colums()` is a C-style array of `Column` objects, or a `std::vector` of `Column` objects, or a `std::array` of `Column` objects, or otherwise something that can produce a `std::span` of `Column` objects.

void somethingWorker(Database const& db, std::span<Column> columns) { // extensive preparations auto statusIndicator = ⟦ calculate status indicator ⟧ auto primaryTugboat = ⟦ calculate primary tugboat ⟧ std::vector<Staircase> staircases;

for (auto&& column : columns) { ⟦ operate on each column using the stuff we prepared ⟧ ⟦ maybe add things to the staircases and update the tugboat ⟧ }

⟦ lots more code ⟧ }

template<typename Table> void something(Database const& db) { somethingWorker(db, Table::Columns()); }

We capture the columns ahead of time and then use the captured values to perform the enumeration inside a non-templated worker function. Since the worker function is non-templated, there is no template explosion when it is called by each `something<Table>`.

One thing to watch out for is that we are changing the order of evaluation, The old code didn’t call `Table::Columns()` until after the preparations were complete. You can look at the code to confirm, but I suspect that `Table::Columns()` just returns a reference to some pre-existing source of column information, so it doesn’t matter when you call it. Even if it returned the columns by value (say, by cloning an internal vector), retrieving the columns early does change the point at which that vector is generated, but generating it even if the preparatory steps fail is probably not a problem because (1) generating it has no interesting side effects, (2) the order of evaluation is not important, and (3) the failure case is probably rare, so the extra cost of generating a vector that is not used is inconsequential.

We’ll apply these principles to our previous example and make a surprising discovery that will shock and amaze you.

Topics

Code

Author

Raymond Chen

Raymond has been involved in the evolution of Windows for more than 30 years. In 2003, he began a Web site known as The Old New Thing which has grown in popularity far beyond his wildest imagination, a development which still gives him the heebie-jeebies. The Web site spawned a book, coincidentally also titled The Old New Thing (Addison Wesley 2007). He occasionally appears on the Windows Dev Docs Twitter account to tell stories which convey no useful information.

Reducing C++ template bloat by factoring out the type-dependent portions of the function

Reducing C++ template bloat by factoring out the type-dependent portions of the function

Category

Topics

Share

Author

0 comments

Leave a commentCancel reply

Read next

On wrapping a callable in a lambda that just calls it with the same parameters

How do functions like alloca allocate memory from the stack?

Stay informed

Comments (0)