{"id":298,"date":"2023-01-15T23:22:40","date_gmt":"2023-01-16T04:22:40","guid":{"rendered":"https:\/\/www.schveiguy.com\/blog\/?p=298"},"modified":"2023-02-04T21:28:53","modified_gmt":"2023-02-05T02:28:53","slug":"the-cost-of-compile-time-in-d","status":"publish","type":"post","link":"https:\/\/www.schveiguy.com\/blog\/2023\/01\/the-cost-of-compile-time-in-d\/","title":{"rendered":"The Cost of Compile Time in D"},"content":{"rendered":"\n

When I was creating my presentation for dconf online 2022<\/a>, I was looking at alternatives to building constraints. If you watched my talk, you can see the fruit of that experiment in my strawman library<\/a> (which is very much a proof-of-concept, and not ready for real use).<\/p>\n\n\n\n

But it got me thinking — how much more expensive are these strawman constraints than the current Phobos range constraints? But even before I went that far, I started looking at some of the phobos constraints, and realized even there, we can achieve some savings.<\/p>\n\n\n\n

Consider the constraint for isInputRange:<\/p>\n\n\n\n

enum bool isInputRange(R) =\n    is(typeof(R.init) == R)\n    && is(ReturnType!((R r) => r.empty) == bool)\n    && (is(typeof((return ref R r) => r.front)) ||\n        is(typeof(ref (return ref R r) => r.front)))\n    && !is(ReturnType!((R r) => r.front) == void)\n    && is(typeof((R r) => r.popFront));<\/code><\/pre>\n\n\n\n
Let’s focus on one aspect of this, the use of the ReturnType<\/code> template<\/a>. What does that do? Essentially, it takes the parameter (in this case a lambda function) and evaluates to the return type of the callable.<\/p>\n\n\n\n
But…. we have that as part of the language, don’t we? Yeah, it’s called typeof<\/code><\/a>. typeof<\/code> gives you the “type of” an expression. And it’s a direct link into the compiler’s semantic analysis — no additional semantic computation is needed.<\/p>\n\n\n\n
To see what we are comparing against, let’s take a look at the ReturnType<\/code> template (and its dependencies):<\/p>\n\n\n\n
template ReturnType(alias func)\nif (isCallable!func)\n{\n    static if (is(FunctionTypeOf!func R == return))\n        alias ReturnType = R;\n    else\n        static assert(0, "argument has no return type");\n}\n\ntemplate FunctionTypeOf(alias func)\nif (isCallable!func)\n{\n    static if ( (is(typeof(& func) Fsym : Fsym*) && is(Fsym == function)) || is(typeof(& func) Fsym == delegate))\n    {\n        alias FunctionTypeOf = Fsym; \/\/ HIT: (nested) function symbol\n    }\n    else static if (is(typeof(& func.opCall) Fobj == delegate) || is(typeof(& func.opCall!()) Fobj == delegate))\n    {\n        alias FunctionTypeOf = Fobj; \/\/ HIT: callable object\n    }\n    else static if (\n            (is(typeof(& func.opCall) Ftyp : Ftyp*) && is(Ftyp == function)) ||\n            (is(typeof(& func.opCall!()) Ftyp : Ftyp*) && is(Ftyp == function))\n        )\n    {\n        alias FunctionTypeOf = Ftyp; \/\/ HIT: callable type\n    }\n    else static if (is(func T) || is(typeof(func) T))\n    {\n        static if (is(T == function))\n            alias FunctionTypeOf = T;    \/\/ HIT: function\n        else static if (is(T Fptr : Fptr*) && is(Fptr == function))\n            alias FunctionTypeOf = Fptr; \/\/ HIT: function pointer\n        else static if (is(T Fdlg == delegate))\n            alias FunctionTypeOf = Fdlg; \/\/ HIT: delegate\n        else\n            static assert(0);\n    }\n    else\n        static assert(0);\n}\n\ntemplate isCallable(alias callable)\n{\n    \/\/ 20 lines of code\n}\n\ntemplate isSomeFunction(alias T)\n{\n    \/\/ 15 lines of code\n}<\/code><\/pre>\n\n\n\n
Whoa, that’s a lot of code to tell me what the type of something is! Why is it so complex? The reason is because in order to determine the return type of something, we have to use the typeof<\/code> primitive, but this needs a valid expression. For a callable, that means we need a valid set of parameters. All of that needs to be introspected by the library, which is simply given a symbol and doesn’t know anything about that symbol without context.<\/p>\n\n\n\n
However we have context! We know exactly how to call the lambda function we have constructed, with an R<\/code>! Why do we need this complexity for something that should be a simple call? As most well-versed in writing generic library code know, this is not an easy thing to do (sometimes generic types can’t be easily constructed, or you might have issues with disabled copying, etc.). In addition, ReturnType<\/code> is built to handle all sorts of callable things, not just lambda functions.<\/p>\n\n\n\n
But isInputRange<\/code> doesn’t actually need to construct, or even have a valid R<\/code> for generating the expression, all it needs is an already existing R<\/code> to call methods on it. We can do this using a reinterpret cast of null<\/code> to an R*<\/code> and now we have an “already made” R<\/code>. Yes, this would crash if actually run, but we don’t ever need to run it, we just need to get its type! And so, here is an equivalent isInputRange<\/code> template that does not use ReturnType<\/code>:<\/p>\n\n\n\n
enum isInputRange(R) =\n    is(typeof(R.init) == R)\n    && is(typeof(() { return (*cast(R*)null).empty; }()) == bool)\n    && (is(typeof((return ref R r) => r.front)) ||\n        is(typeof(ref (return ref R r) => r.front)))\n    && !is(typeof(() { return (*cast(R*)null).front; }()) == void)\n    && is(typeof((R r) => r.popFront));\n<\/code><\/pre>\n\n\n\n
The difference here is we have a no-argument lambda, and so we don’t have to rely on library tricks or introspection to know how to call it (and as you can see, we call it with no parameters as expected).<\/p>\n\n\n\n
Measuring the results<\/h2>\n\n\n\n
Given an isInputRange<\/code> template that is completely independent of std.traits<\/code>, what is the result? How much does it save?<\/p>\n\n\n\n
To test this, I wrote a program generator that created 10000 identical but independently named input ranges, that are tested like this:<\/p>\n\n\n\n
struct S0 { int front; void popFront() {}; bool empty = false; }\nstatic assert(isInputRange!S0);\nstruct S1 { int front; void popFront() {}; bool empty = false; }\nstatic assert(isInputRange!S1);\n...\nstruct S9999 { int front; void popFront() {}; bool empty = false; }\nstatic assert(isInputRange!S9999);<\/code><\/pre>\n\n\n\n
Running on my Linux system, using DMD 2.101.2, I get the following results:<\/p>\n\n\n\n
COMMAND<\/strong><\/td>TIME<\/strong><\/td>MEMORY USAGE<\/strong><\/td><\/tr>
dmd -version=usePhobos<\/td>2.75s<\/td>1.755G<\/td><\/tr>
dmd -version=useTypeof<\/td>1.47s<\/td>621M<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Looking at the savings, it’s quite significant — almost 50% time savings, and over 65% memory savings. Note that each call to ReturnType<\/code> is unique, and so it will execute its own semantic analysis. Using the compiler’s -vtemplates<\/a> switch, we can see that using the current Phobos adds quite a few dependent templates. For each usage of isInputRange<\/code>, we see:<\/p>\n\n\n\n