{"id":723,"date":"2017-04-10T12:59:16","date_gmt":"2017-04-10T12:59:16","guid":{"rendered":"http:\/\/dlang.org\/blog\/?p=723"},"modified":"2021-10-08T11:11:09","modified_gmt":"2021-10-08T11:11:09","slug":"the-new-ctfe-engine","status":"publish","type":"post","link":"https:\/\/dlang.org\/blog\/2017\/04\/10\/the-new-ctfe-engine\/","title":{"rendered":"The New CTFE Engine"},"content":{"rendered":"

Stefan Koch is the maintainer of sqlite-d<\/a>, a native D sqlite<\/a> reader, and has contributed to projects like SDC<\/a> (the\u00a0Stupid D Compiler) and vibe.d<\/a>. He was also responsible for a 10% performance improvement in D’s current CTFE implementation and is currently writing a new CTFE engine, the subject of this post.<\/em><\/p>\n

\n

For the past nine months, I’ve been working on a project called NewCTFE, a reimplementation of the Compile-Time Function Evaluation (CTFE)<\/a> feature of the D compiler front-end. CTFE is considered one of the game-changing features of D.<\/p>\n

As the name implies, CTFE allows certain functions to be evaluated by the compiler while it is compiling the source code in which the functions are implemented. As long as all arguments to a function are available at compile time and the function is pure (has no side effects), then the function qualifies for CTFE. The compiler will replace the function call with the result.<\/p>\n

Since this is an integral part of the language, pure functions can be evaluated anywhere a compile-time constant may go. A simple example can be found in the standard library<\/a> module, std.uri<\/code><\/a>, where CTFE is used to compute a lookup table. It looks like<\/a> this:<\/p>\n

private immutable ubyte[128] uri_flags = \/\/ indexed by character\r\n({\r\n\r\n    ubyte[128] uflags;\r\n\r\n    \/\/ Compile time initialize\r\n    uflags['#'] |= URI_Hash;\r\n\r\n    foreach (c; 'A' .. 'Z' + 1)\r\n    {\r\n        uflags[c] |= URI_Alpha;\r\n        uflags[c + 0x20] |= URI_Alpha; \/\/ lowercase letters\r\n\r\n    }\r\n\r\n    foreach (c; '0' .. '9' + 1) uflags[c] |= URI_Digit;\r\n\r\n    foreach (c; \";\/?:@&=+$,\") uflags[c] |= URI_Reserved;\r\n\r\n    foreach (c; \"-_.!~*'()\") uflags[c] |= URI_Mark;\r\n\r\n    return uflags;\r\n\r\n})();<\/pre>\n
Instead of populating the table with magic values, a simple expressive function literal<\/a> is used. This is much easier to understand and debug than some opaque static array. The ({<\/code> starts a function-literal, the })<\/code> closes it. The ()<\/code> at the end tells the compiler to immediately evoke that literal such that uri_flags<\/code> becomes the result of the literal.<\/p>\n
Functions are only evaluated at compile time if they need to be. uri_flags<\/code> in the snippet above is declared in module scope. When a module-scope variable is initialized in this manner, the initializer must be available at compile time. In this case, since the initializer is a function literal, an attempt will be made to perform CTFE. This particular literal has no arguments and is pure, so the attempt succeeds.<\/p>\n
For a more in-depth discussion of CTFE, see this article<\/a> by H. S. Teoh at the D Wiki.<\/p>\n
Of course, the same technique can be applied to more complicated problems as well; std.regex<\/code>, for example, can build a specialized automaton for a regex at compile time using CTFE. However, as soon as std.regex<\/code><\/a> is used with CTFE for non-trivial patterns, compile times can become extremely high (in D everything that takes longer than a second to compile is bloat-ware :)). Eventually, as patterns get more complex, the compiler will run out of memory and probably take the whole system down with it.<\/p>\n
The blame for this can be laid at the feet of the current CTFE interpreter’s architecture. It’s an AST interpreter, which means that it interprets the AST while traversing it. To represent the result of interpreted expressions, it uses DMD’s AST node classes. This means that every expression encountered will allocate one or more AST nodes. Within a tight loop, the interpreter can easily generate over 100_000_000<\/code> nodes and eat a few gigabytes of RAM. That can exhaust memory quite quickly.<\/p>\n
Issue 12844<\/a> complains about std.regex<\/code> taking more than 16GB of RAM. For one pattern. Then there’s issue 6498<\/a>, which executes a simple 0<\/code> to 10_000_000<\/code> while loop via CTFE and runs out of memory.<\/p>\n
Simply freeing nodes doesn’t fix the problem; we don\u2019t know which nodes to free and enabling the garbage collector makes the whole compiler brutally slow. Luckily there is another approach which doesn’t allocate for every expression encountered. It involves compiling the function to a virtual ISA (Instruction Set Architecture). This virtual ISA, also known as bytecode, is then given to a dedicated interpreter for that ISA (in the case in which a virtual ISA happens to be the same as the ISA of the host, we call it a JIT (Just in Time) interpreter).<\/p>\n
The NewCTFE project concerns itself with implementing such a bytecode interpreter. Writing the actual interpreter (a CPU emulator for a virtual CPU\/ISA) is reasonably simple. However, compiling code to a virtual ISA is exactly as much work as compiling it to a real ISA (though, a virtual ISA has the added benefit that it can be extended for customized needs, but that makes it harder to do JIT later). That’s why it took a month just to get the first simple examples running on the new CTFE engine, and why slightly more complicated ones still aren’t running even after 9 months of development. At the end of the post, you’ll find an approximate timeline of the work done so far.<\/p>\n
I’ll be giving a presentation<\/a> at DConf 2017<\/a>, where I’ll discuss my experience implementing the engine and explain some of the technical details, particularly regarding the trade-offs and design choices I’ve made. The current estimation is that the 1.0 goals will not be met by then, but I’ll keep coding away until it’s done.<\/p>\n
Those interested in keeping up with my progress can follow my status updates in the D forums<\/a>. At some point in the future, I will write another article on some of the technical details of the implementation. In the meantime, I hope the following listing does shed some light on how much work it is to implement NewCTFE \ud83d\ude42<\/p>\n