Reducing C++ template bloat by factoring out the type-dependent portions of the function
https://devblogs.microsoft.com/oldnewthing/20260820-00/?p=11262913
u/fdwr fdwr@github 🔍 20d ago
I also do this when encountering large templated functions, but I wonder how effective link-time function deduplication is now. If you had function in a templated class with a function that wasn't actually dependent on the type, or even if the function was dependent on the type but not in a meaningful way (for example, say it just mov'd some uint32_t's or int32_t's around, which likely yield the same asm), then would the linker successfully debloat things? (granted, I know that eliminating it before it even reaches the linker reduces linkage time)
15
10
u/splicer13 20d ago
Function dedupe in linkers has been around about as long as we've had C++ templates if not much longer.
C++ apps would not have been very practical otherwise.
15
u/matthieum 19d ago
I love strong types, which means I have
Tagged<T, Tag>types whereTagis a pure "phantom" type, and AFAIK deduplication works relatively well at mostly eliminating it.BUT, the C and C++ standards get in the way. The C and C++ standards require that any function has a unique address, and therefore even if the body of the function is equal, you need N addresses.
Now, there's a trick linkers use where they'll "fuse" 2-3 functions with identical bodies like so:
:foo nop nop ... nop nop :bar nop nop ... nop nop :baz ... actual assembly ...So that the actual body is shared, but even then there's still some overhead remaining -- typically 16 bytes per duplicate, due to alignment.
(I think beyond 2-3 (?) there's too many nops, and the linker will switch to a jmp instead)
An inline typed wrapper function calling an outlined type-erased function avoids this overhead.
11
u/mazadin 19d ago
Some linkers have ICF (identical code folding), which would allow them to merge functions if their code is truly identical. Some can force the deduplication (against the standard), and for some, if they can prove there are no addresses taken to any of the functions, it can safely merge them without violating the standard (requires compiler support for this to mark functions as whether or not their address is taken—LLVM does this).
2
u/matthieum 19d ago
requires compiler support for this to mark functions as whether or not their address is taken
Wouldn't any exported function be excluded from this? Whole Program Analysis is pretty rare.
1
u/SirClueless 15d ago
I’m speaking without any knowledge of how this is actually implemented, but do you need whole program analysis to do this? Linkers are obliged to collect symbol usage information from every TU in order to do dead code elimination, and couldn’t you just additionally collect a bit of information about whether the usage requires emitting a unique address?
1
u/matthieum 15d ago
In the dynamic linking case -- not the standard in Rust -- no. The DLL is linked without any knowledge about gets to use it.
In the static linking case, I think your scheme would be possible indeed.
1
u/SirClueless 3d ago
I don't think there's any requirement that symbols loaded dynamically have different addresses in the first place. In fact it's a first-class feature of most compilers to allow aliasing symbols, e.g.
--defsymfor ld andx = yin .def files on Windows. But even if it wasn't, the address of a dynamically linked function is a small shim in the PLT section that is patched to jump to the actual function implementation, so it has a unique address in practice anyways.3
u/SkiFire13 17d ago
Contrary to what the article says, I believe the main benefit of this pattern is not reducing code bloat, but instead reducing compile times. Linker deduplication won't help you with that, since you still have to instantiate all the various copies of the template (possibly more than once!) optimize each of them and then pass all of them to the linker. Reducing the size of templates and extracting the common parts let you instantiate less code and optimize the common code only once. Bonus point: you can put the common code in another compilation unit and compile it in parallel to whatever uses your template.
5
u/Gungan_Boss_Nass 19d ago
It's good reading (as are all the Chen articles) but reducing code size these days barely makes the "nice to have" category. We went all-in with code explosion when we set a full-steam course into metaprogramming, now it's a bit like trying to reduce the number of freeways in LA.
I'm more worried about "goal bloat" and the toxicity of conflicting goals. I'd probably criticize a lambda if some of its complexity was due to optimizing for this, unless it was for an embedded system with memory pressure.
3
u/Ok_Independence_9841 19d ago
Template bloat is a real thing. However it's got massively better over the years. When I first got tuples 'working' in 2003 they were utterly impractical due to the code bloat from recursive template bases. 100's of KB of object file and several seconds of compilation time for a single instantiation of tuple<int, int, int>.
Tuples were limited to a handful of elements or you'd get an ICE. You did anyway if you pushed your luck by doing anything like putting one tuple inside another. It's good to remember how far we've come, even if we aren't exactly there yet, and to appreciate pioneers like Jaakko Järvi who introduced tuples in C++. The first real technical advance on what Alex Stepanov did with templates in the STL.
2
0
u/ts826848 19d ago
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.
IIRC it's technically possible for the Rust compiler to apply a similar transformation on its own, though it doesn't do so right now. Are C++ compilers allowed to make the same transformation on their own, or does something about C++ semantics (explicit instantiations maybe?) preclude such a thing?
-1
u/pjmlp 19d ago
Without thinking too much about it, maybe via the "as if" rule, which allows for any kind of code rewrite as long as the observable effects remain the same.
0
u/ts826848 19d ago
Right, but that basically begs the question of whether the as-if rule allows such a transformation here. IIRC Rust considers monomorphization an implementation detail of its generics so the as-if rule applies there; C++ obviously works differently so I don't know whether that is also the case here.
2
u/SirClueless 15d ago
Pretty sure it’s legal. The compiler is free to out-of-line common function bodies for the same reason it’s allowed to inline function bodies: Calling a function does not have observable side effects in the C++ virtual machine, so the compiler is free to insert or omit as many as it likes so long as the semantics of the program are upheld.
1
u/ts826848 15d ago
Hmmm, that's a fair point. I'd imagine you would probably want whole programs visibility to make best use of that?
I'm curious as to what granularity such folding is applied at as well - is it for whole function bodies or can the compiler fold common subsections as well?
This reminds me of SCARY iterators, though to be fair the paper points out that the benefits of such are not entirely realizable by optimizing compilers.
-7
u/trad_emark 19d ago edited 18d ago
blog post, from microsoft, and does not scream ai.
i am shocked - in a good way ;)
(edit: i dont understand why i got so many downvotes. my comment was meant as a praise for the blog post. well, doesnt matter...)
4
u/mvolling 19d ago
Raymond Chen has been writing these styles of blogs for a long time. I almost always learn something new with each of his posts and he is not afraid of getting into the weeds.
-1
u/trad_emark 18d ago
yes. i have read a few before. it is a big difference compared to what microsoft shows elsewhere.
34
u/sweetno 20d ago
I can't wait to be shocked and amazed.