<div dir="ltr"><div style="color:rgb(33,33,33);font-size:13px">Hi,</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">TLDR: Is there any work going on to drastically improve constexpr evaluation</div><div style="color:rgb(33,33,33);font-size:13px">      speed?</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">after watching "constexpr ALL the things!"</div><div style="color:rgb(33,33,33);font-size:13px">(<a href="https://www.youtube.com/watch?v=HMB9oXFobJc" target="_blank">https://www.youtube.com/watch?v=HMB9oXFobJc</a>) I started making my hobby</div><div style="color:rgb(33,33,33);font-size:13px">lexer/parser generator library constexpr as well, which turned out to be just as</div><div style="color:rgb(33,33,33);font-size:13px">easy as advertised. There where two problems I could deal with relativly easily:</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">a) gcc exhausts any available memory. So switch to clang.</div><div style="color:rgb(33,33,33);font-size:13px">b) clang 5.0.0 has the constexpr constructor bug </div><div style="color:rgb(33,33,33);font-size:13px">   (<a href="https://bugs.llvm.org/show_bug.cgi?id=19741" target="_blank">https://bugs.llvm.org/show_bug.cgi?id=19741</a>), so build clang from source.</div><div style="color:rgb(33,33,33);font-size:13px">c) -fconstexpr-steps=-1</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">The only obstacle left (except for missing placement new and having to</div><div style="color:rgb(33,33,33);font-size:13px">initialize all memory) are the slow, slow slow compile times. I'm talking about</div><div style="color:rgb(33,33,33);font-size:13px">"I don't even know if it will ever end", before I started optimizing for </div><div style="color:rgb(33,33,33);font-size:13px">constexpr evaluation. I have been able to decrease the compile time to 20</div><div style="color:rgb(33,33,33);font-size:13px">minutes, then 15 minutes, then 10 minutes, ... etc. There was no "Oh, I</div><div style="color:rgb(33,33,33);font-size:13px">accidentally used a bad algorithm." or "Oh, the compiler doesn't handle X very</div><div style="color:rgb(33,33,33);font-size:13px">well.". Just incrementally optimizing the code for compile time evaluation.</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">By now I am down to 3 minutes for my "test case" of constructing a minimal DFA </div><div style="color:rgb(33,33,33);font-size:13px">for a json Lexer including</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">a) parsing the Regexes for json terminals and constructing an NFA,</div><div style="color:rgb(33,33,33);font-size:13px">b) constructing the corresponding DFA based on the NFA,</div><div style="color:rgb(33,33,33);font-size:13px">c) minimizing the DFA (Hopcroft's algorithm).</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">I'm basically using algorithms described in the Dragon Book.</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">With -O0 and disabling constexpr, this runs in 0.275 seconds. I have</div><div style="color:rgb(33,33,33);font-size:13px">continuously improved the compilation time by profiling and optimizing the -O0 </div><div style="color:rgb(33,33,33);font-size:13px">build first with perf tools and then with callgrind. Here is what I learned:</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">a) Just reduce the number of operations necessary to compute the result.</div><div style="color:rgb(33,33,33);font-size:13px">b) Ignore cache locality.</div><div style="color:rgb(33,33,33);font-size:13px">c) Abstraction is too expensive. Inline everything manually.</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">While this is a fascinating experience that goes against everything I learned</div><div style="color:rgb(33,33,33);font-size:13px">about optimization in the past few years, it obviously hinders the idea of being</div><div style="color:rgb(33,33,33);font-size:13px">able to use constexpr functions both at compile time AND at run time.</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">So of course I would prefer it if compile time evaluation speed would be</div><div style="color:rgb(33,33,33);font-size:13px">comparable to, say, an interpreted language. Maybe one using just-in-time</div><div style="color:rgb(33,33,33);font-size:13px">compilation like LLVM (hint, hint). Of course you can't just compile and run the </div><div style="color:rgb(33,33,33);font-size:13px">constexpr code because undefined behavior must be "trapped". But running a</div><div style="color:rgb(33,33,33);font-size:13px">no-undefined-behavior version of C++ would be cool, I think. Even if it</div><div style="color:rgb(33,33,33);font-size:13px">certainly would be a lot of work ... </div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">Is there any work going on in that direction? Am I missing something?</div><div style="color:rgb(33,33,33);font-size:13px"><br></div><div style="color:rgb(33,33,33);font-size:13px">Regards,</div><div style="color:rgb(33,33,33);font-size:13px">Tim Rakowski</div></div>