{"id":246,"date":"2009-09-22T15:01:54","date_gmt":"2009-09-22T22:01:54","guid":{"rendered":"http:\/\/gameangst.com\/?p=246"},"modified":"2009-09-22T15:02:59","modified_gmt":"2009-09-22T22:02:59","slug":"minimizing-code-bloat-redundant-template-instantiation","status":"publish","type":"post","link":"http:\/\/gameangst.com\/?p=246","title":{"rendered":"Minimizing Code Bloat: Redundant Template Instantiation"},"content":{"rendered":"

This article is a continuation of Minimizing Code Bloat for Faster Builds and Smaller Executables<\/a>.<\/em><\/p>\n

The last item on my list of code bloat causes is redundant template instantiation. \u00a0Template functions have a lot in common with inline functions. \u00a0Like inline functions, template functions are instantiated into the object file of every translation unit in which they are used. \u00a0Also like inline functions, template functions generate weak symbols which are merged silently by the linker. \u00a0Redundant template instantiations won’t increase your executable size, but they can contribute significantly to your build times.<\/p>\n

Consider a commonly used class like std::string<\/em>. \u00a0The std::string class is actually a template class defined as:<\/p>\n

typedef<\/span> basic_string<char, char_traits<char>, allocator<char> > string;<\/div>\n<\/p>\n

In an engine that uses std::strings, some members like std::string::assign may be referenced in nearly every translation unit. \u00a0Even engines that eschew the use of std::string may unknowingly be instantiating a lot of std::string code because it is so pervasive in the standard library. \u00a0Looking at a symbol dump from one version of Despair Engine, I see over 1600 instances of dozens of functions from std::string. \u00a0That’s right, in every full build we compile most of std::string 1600 times, optimize the code 1600 times, write it into .obj files 1600 times, copy it into .lib files 1600 times, read it into the linker 1600 times, and then throw 1599 identical copies away! \u00a0All told I think it is less than 10 megabytes of code and accounts for only a couple percent of our build times, but still, it’s a lot to pay for a wrapper around a char*.<\/p>\n

Don’t think that these sorts of problems are confined to the standard library. \u00a0Any template class that is widely used can produce a lot of code bloat from redundant instantiations. \u00a0The question is, what do you do about it?<\/p>\n

One option is to convert template code into non template code. \u00a0If you never instantiate basic_string with anything other than a single set of parameters, is it really worth being a template class? \u00a0The same question could be asked of a templatized math library. \u00a0Does matrix<T> need to be a template class when all you ever use is matrix<float>?<\/p>\n

Although removing template code is always an option, it isn’t always a good one. \u00a0Template code may be expensive, but it is also really handy. \u00a0If you have a templatized math library, chances are that while 99% of the instantiations are matrix<float>, somewhere in your engine or tools you have an instantiation of matrix<double>. \u00a0Similarly, amid all those instantiations of basic_string<char>, maybe there’s a basic_string<wchar_t> or two hanging out.<\/p>\n

Luckily there is a way to prevent redundant template instantiations without changing the code. \u00a0That is through the use of explicit template instantiation declarations. \u00a0Explicit instantiation declarations aren’t technically part of the C++ standard, but they’re supported by MSVC<\/a> and gcc<\/a> and they’re included in the C++09 draft standard, so they’re a safe bet to use. \u00a0What explicit instantiation declarations do is allow you to prevent the compiler from instantiating a particular template in the current translation unit. \u00a0They look just like explicit instantiation definitions, but they’re preceded by the extern keyword. \u00a0For example, the explicit instantiation declaration of basic_string<char> looks like this:<\/p>\n

extern<\/span> template<\/span> class<\/span> basic_string<char>;<\/div>\n<\/p>\n

You can add this declaration to a root header in your application and rebuild, and, unless you’ve missed a translation unit, you’ll encounter linker errors for missing basic_string<char> symbols. \u00a0Once you’ve removed all the basic_string<char> instantiations from your engine, the next thing to do is to add one back so the linker has all the code it needs to put together a complete executable. \u00a0That’s where\u00a0explicit instantiation definitions come in.<\/p>\n

Explicit instantiation definitions are the counterpart to explicit instantiation declarations. \u00a0They tell the compiler to fully instantiate a particular template even if it is otherwise unused in the current translation unit. \u00a0Here’s an example of how you can use the two concepts together to prevent redundant instantiations of basic_string.<\/p>\n

\n
\/\/ in string_instantiation.h<\/span>
\n#ifdef DS_EXTERN_TEMPLATE_INSTANTIATION<\/span>
\nnamespace<\/span> std
\n{<\/span>
\n    extern<\/span> template<\/span> class<\/span> basic_string<char>;
\n}<\/span>
\n#endif<\/span><\/p>\n

\/\/ in string_instantiation.cpp<\/span>
\n#ifdef DS_EXTERN_TEMPLATE_INSTANTIATION<\/span>
\n#undef DS_EXTERN_TEMPLATE_INSTANTIATION<\/span><\/p>\n

#include "string_instantiation.h"<\/span><\/p>\n

namespace<\/span> std
\n{<\/span>
\n    template<\/span> class<\/span> basic_string<char>
\n}<\/span>
\n#endif \/\/ DS_EXTERN_TEMPLATE_INSTANTIATION<\/span><\/div>\n<\/blockquote>\n

The DS_EXTERN_TEMPLATE_INSTANTIATION #define<\/em> in the above code serves two purposes. \u00a0First it allows us to disable explicit template instantiation for compilers that don’t support it, and second it allows us to work around a common bug in compilers that do support it. \u00a0Although the standard states that an explicit instantiation definition may follow an explicit instantiation declaration within a translation unit, many compilers don’t like it and won’t allow an explicit instantiation definition to override a preceding explicit instantiation declaration.<\/p>\n

There is one dark fact about explicit template instantiation that you should know before applying it in your own codebase. \u00a0Although explicit template instantiation effectively turns template code into non template code from the perspective of code bloat, it doesn’t really help much with classes like std::string. \u00a0The syntax for out-of-line template class function definitions is so cumbersome that many programmers prefer to implement all their template class members entirely within the class declaration. \u00a0That’s what has happened with Microsoft’s STL implementation. \u00a0Unfortunately what that does is implicitly make every member function in a template class an inline function. \u00a0Of course most of the member functions are so large that they’ll never be inlined, but it doesn’t matter from the perspective of the compiler.<\/p>\n

The explicit template declaration of basic_string<char> prevents the compiler from instantiating its members as template functions, but it doesn’t prevent it from instantiating them as inline functions! \u00a0The basic_string class goes from a classic example of code bloat due to redundant template instantiation to a classic example of code bloat due to incorrect inlining<\/a>! \u00a0You can’t win!<\/p>\n

In your own code, at least, you can fix the incorrect inlining problem right after you fix the redundant instantiation problem. \u00a0Just move the template class member functions out of line and they’ll disappear from your symbol dumps.<\/p>\n

And that’s everything I know about code bloat in a voluminous 6 part series. \u00a0Perhaps what I should be writing about is blog bloat. \u00a0All that’s left is to post some code<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

This article is a continuation of Minimizing Code Bloat for Faster Builds and Smaller Executables. The last item on my list of code bloat causes is redundant template instantiation. \u00a0Template functions have a lot in common with inline functions. \u00a0Like inline functions, template functions are instantiated into the object file of every translation unit in […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[8,14,7],"_links":{"self":[{"href":"http:\/\/gameangst.com\/index.php?rest_route=\/wp\/v2\/posts\/246"}],"collection":[{"href":"http:\/\/gameangst.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/gameangst.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/gameangst.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/gameangst.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=246"}],"version-history":[{"count":12,"href":"http:\/\/gameangst.com\/index.php?rest_route=\/wp\/v2\/posts\/246\/revisions"}],"predecessor-version":[{"id":309,"href":"http:\/\/gameangst.com\/index.php?rest_route=\/wp\/v2\/posts\/246\/revisions\/309"}],"wp:attachment":[{"href":"http:\/\/gameangst.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=246"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/gameangst.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=246"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/gameangst.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=246"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}