![\"\"](\"https:\/\/dlang.org\/blog\/wp-content\/uploads\/2019\/08\/cropped-rocket-200x200.png\")
<\/p>\n<\/p>\n
Templates have been enormously profitable for the D programming language. They allow the programmer to generate efficient and correct code at compile time. Long gone are the days of preprocessor macros or handwritten, per-type data structures. D templates, though designed in the shadow of C++ templates, were not made in their image. D makes templates cleaner and more expressive, and also enables patterns like “Design by Introspection<\/a>”.<\/p>\n Here is a simple example of a template that would require the use of preprocessor macros in C or C++:<\/p>\n D’s templates are powerful tools but should not be used unthinkingly. Carelessness could result in long compile times or excessive code generation.<\/p>\n In this blog post, I introduce some simple concepts that can help in writing templates that minimize resource usage. Deeper intuition can also lead to the discovery of new abstractions or increased confidence in existing ones.<\/p>\n The D compiler memoizes template instantiations: if I instantiate As a demonstration, let’s write a generic addition function and use Now let’s compile the code and look at what our This yields the following output during compilation:<\/p>\n We can see The benefit of this feature should be obvious, but what may not be obvious is how it can be employed in writing templates. Within the bounds of our desire for ergonomics, we should design the interfaces<\/em> of our templates to maximize the number of identical instantiations.<\/p>\n The following example, adapted from a real-world change to a large D project, yielded a reduction in compile time of a few percent for unit-test builds.<\/p>\n Let’s say we have an expensive template whose behavior we want to test over a simple type. Our type might be:<\/p>\n To demonstrate the phenomenon, we don’t have to do anything fancy, so we’ll just declare a stub called A note on syntax:<\/strong> Given a variable Our test might then be something like:<\/p>\n This is reasonable so far. However, an issue arises when we start to write more than one test. Should we want to test different behaviors of a fancy template, but instantiate it with the same type, then we end up spending more time in compilation than we would have expected. A lot more time. And we see large growth in the number of symbols emitted in the resulting binary, resulting in a larger file size than one would expect. Why is that?<\/p>\n Despite our intuition that the compiler should consider multiple declarations of a type like This results in the following output from the compiler:<\/p>\n Huh? Doesn’t this violate our “you can’t pay twice” rule? If you were to take this output from the compiler as gospel, then yes, but there’s a more subtle truth here.<\/p>\n The name of a type as you would write it in your editor is not the complete name of a type. Let’s amend the implementation of Assuming the module is named This explains our previous conundrum. By declaring the type locally<\/em> in each test, we have actually declared a new type per test, each of which results in a new instantiation.<\/p>\n A type’s fully qualified name includes the name of its enclosing scope ( We want to ensure that one instantiation is reused across The Much better.<\/p>\n To collect some anecdata about the usefulness of these changes, we’ll look at compilation times and the size of compiled binaries. Since this template is very<\/em> trivial, let’s generate a hundred copies of the same On my system, timing the compilation of our programs shows the locally declared types took 243ms<\/strong> to compile, but the version with a single global type declaration took 159ms<\/strong> to compile. A difference of 84ms<\/strong> is not all that much, sure, but in a large codebase, there may be a lot<\/em> of these speedups waiting to be found. Any reduction in compile times is to be embraced, especially when it’s cumulative.<\/p>\n As for binary size, I saw a savings of The following example demonstrates a very simple but fundamental change to a template that yields an enormous improvement in compile times and other metrics.<\/p>\n Let’s say we have a fairly simple interpreter, and we want to expose functions in our D code to the scripts executed by our interpreter. We can do that with some sort of registration function, which we’ll call To prove the point I’m discussing, we don’t need to implement this function—its interface<\/em> is what can cause a big slow down.<\/p>\n Let’s say our It’s pretty reasonable, right? It takes a template alias parameter that specifies the function to call (a common idiom in D) and a template value parameter of type The scripts can call the Phobos The interface for Although we will pull the functions out of a hat, the thing that will drive our intuition is to realize that a small number of interfaces will likely be reused many times. We could start with a basket of interface stubs like this:<\/p>\n More broadly, with a bunch of functions that have identical signatures and a bunch of functions with random parameter lists and return types, we can get a rough baseline. With the set of stubs I used, compile times ended up at roughly 5<\/strong> seconds.<\/p>\n So what happens if we move the compile-time parameters to run time? Since With this signature, the compile time drops to roughly 1<\/strong> second.<\/p>\n D is a fairly fast language to compile. Good decisions have been made over the lifetime of the language to make that possible. It is also the case that one can happily write slow-to-compile D code. Although we are choosing to ignore the compilation speeds of the non-infrastructure code to simplify the point being made, this can actually (in a certain sense) be the case in real projects, too. As such it is worthwhile to pay attention not to the quantity of metaprogramming being done semantically<\/em> but rather the quantity of metaprogramming being performed by the compiler<\/em>.<\/p>\n In this case, with the first interface used for To be clear, this is not an indictment of template alias parameters. There are good use cases for them (the Phobos algorithms API is an example). The point of this example is to show how the compile-time costs of unique template instantiations can be hidden. A decision about the trade-offs between compile-time and run-time performance can only be made if the programmer is aware there is a decision to make. So when implementing a template, consider how it will be used. If it’s going to end up creating many unique instantiations, then you can weigh the benefits of keeping that interface versus redesigning it to maximize reuse.<\/p>\ntemplate sizeOfTypeByName(string name)\n{\n enum sizeOfTypeByName = mixin(name, \".sizeof\");\n}\nunittest\n{\n assert(sizeOfTypeByName!\"int\" == 4);\n}<\/pre>\nRead the memo<\/h2>\n
MyTemplate!int<\/code> once, the compiler produces an AST for that instantiation; if I instantiate that exact template again, the previous computation is reused.<\/p>\npragma(msg, ...)<\/code> to print the number of instantiations at compile time. I’m going to use it twice with integers and twice with floating point numbers.<\/p>\nauto genericAdd(T)(const T x, const T y)\n{\n pragma(msg, \"genericAdd instantiated with \", T);\n return x + y;\n}\n\n\/\/ Instantiate with int\nwriteln(genericAdd!int(4, 5));\nwriteln(genericAdd!int(6, 1));\n\n\/\/ Now for the float type\nwriteln(genericAdd!float(24.0, 32.0));\nwriteln(genericAdd!float(0.0, float.nan));<\/pre>\npragma(msg, )<\/code> says about template instantiations in the compiler.<\/p>\ndmd -c generic_add.d<\/pre>\n
genericAdd instantiated with int\ngenericAdd instantiated with float<\/pre>\n
int<\/code> and float<\/code> as we expected, but notice that each is only mentioned once. Newcomers to languages with templates or generics can sometimes mistakenly think that using a template requires a potentially expensive instantiation on every use in the source code. For the benefit of those new users of D, the above is categoric proof that this is not the case; you cannot<\/em> pay twice for templates you have already asked the compiler to instantiate. (You can, however, convince yourself that you are<\/em> asking the compiler to do something it’s already done when you in fact are not. We’ll go over contrived and real-world examples of this later in this article.)<\/p>\nWhat’s in a name?<\/h2>\n
struct Vector3\n{\n float x;\n float y;\n float z;\n}<\/pre>\nsend<\/code>.<\/p>\n\/\/ Let's say this sends a value of type T to a database.\nvoid send(T)(T x);<\/pre>\n
val<\/code> of type int<\/code>, this template could be explicitly instantiated as send!(int)(val)<\/code>. However, the compiler can infer the type T<\/code>, so we can instantiate it as if it were a normal function call as send(val)<\/code>. Using D’s Uniform Function Call Syntax<\/a>, we could alternatively call it like a property or member, as val.send()<\/code> (the approach used in the following example), or even val.send<\/code>, since parentheses are optional in function calls when there are no arguments.<\/p>\nstruct Vector3\n{\n float x;\n float y;\n float z;\n}\n\nunittest\n{\n Vector3 value;\n value.send();\n}<\/pre>\nVector3<\/code> in multiple unittest<\/code> blocks as identical, it actually does not. We can demonstrate this effect with an extremely simple example. We’ll provide an implementation of send<\/code> that prints at compile time the type of each instantiation. Then we’ll use static foreach<\/code><\/a> to generate five distinct implementations of a single unit test.<\/p>\nvoid send(T)(T x)\n{\n pragma(msg, T); \n}\n\n\/\/ Generate 5 unittest blocks\nstatic foreach(_; 0..5)\n{\n unittest\n {\n struct JustInt\n {\n int x;\n }\n JustInt value;\n value.send;\n }\n}<\/pre>\nJustInt\nJustInt\nJustInt\nJustInt\nJustInt<\/pre>\n
Fully qualified names<\/h2>\n
send<\/code> to print the return value of a template called fullyQualifiedName<\/code> rather than printing T<\/code> directly. The rest of the example remains the same.<\/p>\nvoid send(T)(T x)\n{\n import std.traits : fullyQualifiedName;\n pragma(msg, fullyQualifiedName!T); \n}<\/pre>\nexample<\/code>, this yields something like:<\/p>\nexample.__unittest_L13_C3_1.JustInt\nexample.__unittest_L13_C3_2.JustInt\nexample.__unittest_L13_C3_3.JustInt\nexample.__unittest_L13_C3_4.JustInt\nexample.__unittest_L13_C3_5.JustInt<\/pre>\n
{package-name.}module-name.{scope-name(s).}TypeName<\/code>). The compiler rewrites each unittest<\/code> as a unique function with a generated name. We have five unique functions, each with its own local, distinct declaration of a JustInt<\/code> type. And so we end up with five distinct types.<\/p>\nunittest<\/code> blocks. We do that by moving the declaration of JustInt<\/code> to module scope, outside of the unit tests.<\/p>\nstruct JustInt\n{\n int x;\n}\n\nstatic foreach(_; 0..5)\n{\n unittest\n {\n JustInt value;\n value.send;\n }\n}<\/pre>\nsend<\/code> template now prints:<\/p>\nexample.JustInt<\/pre>\n
Some hard data<\/h3>\n
unittest<\/code> rather than five so we can see a trend.<\/p>\n69K<\/code> on disk. The quantity of machine code generated by the compiler is worth keeping a close eye on. Larger binaries mean more work for the linker, which in turn means more time waiting for builds to complete. The easiest job is the one you don’t have to do.<\/p>\nA more complex example<\/h2>\n
register<\/code>.<\/p>\nThe signature of the register function<\/h3>\n
register<\/code> function looks like this:<\/p>\n\/\/ Context is something our hypothetical interpreter works with\nvoid register(alias func, string registeredName)(Context x); <\/pre>\n
string<\/code> that represents the name of the function as it is exposed to scripts. The implementation of register<\/code> will presumably map the value of registeredName<\/code> to the func<\/code> alias, and then scripts can call the function using that value. Functions can be registered with, e.g., the following:<\/p>\n\ncontext = createAContext();\ncontext.register!(writeln!string, \"writeln\")();<\/pre>\n
writeln<\/code> function template using the name writeln<\/code>.<\/p>\nThe compile-time performance of the register template<\/h3>\n
register<\/code> looks harmless, but it turns out that it has a significant impact on compile time. We can test this by registering some random functions. The actual contents of the functions don’t matter—this article is about template compile times, so we just want a baseline figure for roughly how much time the infrastructure templates take to compile rather than the code they are hooking together.<\/p>\nint stub1(string) { return 1; }\n\nint stub2(string) { return 2; }\n\nint stub3(string) { return 3; }\n\n\/\/ etc.<\/pre>\nregisteredName<\/code> is a template value parameter, we can just move it into the function parameter list with no change. We have to handle the func<\/code> parameter differently. Almost any symbol can bind at compile time to a template alias parameter, but symbols can’t bind at run time to function parameters. We have to use a function pointer instead. In that case, we can use the type of the referenced function as a template parameter.<\/p>\nvoid register(FuncType)(Context x, FuncType ptr, string registeredName);<\/pre>\n
What’s going on?<\/h3>\n
register<\/code>, the compiler had no opportunity to reuse any instantiations. Because it accepted the registered functions as symbols, each instantiation was unique. By shifting instead to take the type<\/em> of the registered function as a template parameter and a pointer to the function as a function parameter, the compiler could reuse instantiations. stub1<\/code>, stub2<\/code>, and stub3<\/code> are distinct symbols, but they each have the same type of (int function(string)<\/code>).<\/p>\nA false friend<\/h2>\n