C++17 constexpr Compile-time Ray Tracer (2017) | Hacker News Reader

C++17 constexpr Compile-time Ray Tracer (2017)

github.com

155 pointszone41158 comments

There's seemingly a lot of negative responses to articles concerning constexpr in modern C++ (you can see some here in this thread). I suspect this is partially because there's a general outsized dislike of C++, and partially because typically these articles focus on toy problems where the capacity to run at compile time isn't actually beneficial, rather than cases where constexpr can provide some real benefit towards production code.

Like any syntactic construct in a turing complete language constexpr presents a convenience - in this case the ability to rectify compile time generated data and runtime code paths/data. There are some practical cases I've seen where it can be a real improvement to hygiene (i.e. you can replace a compile time script/program generating data with one unified code base). e.g.

1. Perfect hash generation. Rather than using a separate gperf run you can generate your hashes during compilation of the relevant TU.

2. Format string lookup tables. For fast formatting you can push an index and positional arguments to a queue, and handle formatted string construction in another thread. Broadly speaking lookup tables in general can be generated at compile time rather than static data imported into code.

3. Complex starting conditions for physics simulations. If you have, say, some initial matrix that doesn't change between simulation runs - you can exercise existing code to generate this matrix at compile time rather than needing a separate process run or script.

These approaches are not without their downsides - particularly if the translation units in question need to be recompiled often, or if you're using whole program optimisation - but the benefit of keeping generated data in lockstep with the code consuming it can be worthwhile.

(That being said, I personally find articles like this incredibly edifying.)

I like to think of constexpr as a better, typesafe preprocessor. There are a lot of places constexpr can replace it.

4. Things you want to not run at runtime. If you can demand of the compiler that foo is run only at compile time, you can eliminate some performance outliers, with good protection against accidental later regressions. (I suppose this could apply to security too — anything run at compile time is definitely not vulnerable to crafty user input from a malicious user.)

5. My compiler is a rackmount somewhere; even if constexpr evaluation is somewhat slower than runtime code in a particular case, I may prefer to use the rackmount's plentiful power rather than the slim, light battery on the device where the final code will run.

6. A constexpr function is guaranteed to have no undefined behaviour (when evaluated at compile time, anyway)

I think the most important benefit is simpler and just the code clarity for your constants. For instance if you have compile time constants for width and height you can sanely write diagonal=Pythagoras(width,height) and be done and know you have that value at compile time.

Before you'd either have to hope the compiler did that for you magically, do something ugly with the preprocessor, or bake in numbers

In a way all your examples are just more extreme version of the same but I guess my point is that it's not something fringe for fancy optimizations, it's daily use.

Author here. I wrote this on a rainy weekend last year and mostly forgot about it, so it was a bit of a surprise to see it pop up on HN this morning!

Happy to answer any questions (including "why on earth would you do this?") :)

Thanks for the article. Seems nobody seems to have asked anything.. i'll start...

Why on earth would you do this?

> Why on earth would you do this?

Good question! :)

It actually started out as a learning exercise -- I didn't (and still don't) know much about ray tracing, and so I thought it would be good to study a simple example by translating it from a language I didn't know (TypeScript) to one I was more familiar with.

This involved writing a simple vec3 class, and it seemed natural to make that constexpr. Then as I went through I realised that many more functions could be made constexpr too. And then if I hacked together some (admittedly very poor) replacement maths functions, even more of it could be constexpr...

At this point, it became a challenge to see whether I could make the whole thing run at compile-time. The only tricky part was avoiding virtual functions -- I'd originally naturally translated TypeScript "interface"s into C++ abstract classes. I ended up using two different approaches: firstly using std::variant and std::visit (the any_thing class in the source code), and secondly using a struct of function pointers (for the surfaces) -- because while virtual calls aren't allowed in constexpr code, calls via a function pointer are just fine.

In the end, I was pretty satisfied that I'd managed to push constexpr as far as I could take it. I had intended to blog about it, but never got round to it ... and now 18 months later someone has saved me the job by posting it to HN anyway :)

Good way to spend the weekend, I totally get it :) I was thinking that constexpr has been around since 11 (17 has if-constexpr, but I didn't see any of those). Were there particular features of 17 that you were able to benefit from?

While constexpr was introduced in C++11, it was initially very limited -- a constexpr function could only consist of a single return statement, for example. It was only in C++14 that things like variable declarations and loops were allowed, and constexpr programming became practical.

> Were there particular features of 17 that you were able to benefit from?

I used std::variant from C++17 for polymorphism, as a workaround for the fact that you can't have constexpr virtual functions (these have since been proposed for C++20). I also used `std::optional` when testing for intersections between a ray and a "thing", but it would have been possible to structure the code in such a way that this wasn't necessary (for example, by using a bool return value and an out parameter).

Lastly, I used constexpr lambdas (new in C++17) though again, it would have been possible to do things differently so these weren't required -- and indeed I did have to work around the fact that Clang (at the time) didn't support evaluating capturing lambdas at compile-time.

Great explanation, thank you!

Regarding using std::variant for polymorphism as a work-around for not having virtual functions: I've often thought there's a bit of a mismatch between how many different derived classes (0 to infinity) an abstract base class can support, versus how many are actually needed in the average user code (anecdotally, 2 or 3 real classes and however many mocks needed for unit tests). Even something like a GUI framework may still have a manageable amount to just compile into something like a std::variant. Theoretically a whole-program analysis could even compile language-level inheritance into something like a std::variant. My point is, this mismatch between how flexible the technique we're using is versus how much flexibility we actually need, maybe indicates that we're not seeing something about how we develop software.

An analogy would be if we used only ball-and-socket joints everywhere in machines, even where a single-axis hinge would work just fine. And then just accepted that machines are inherently wobbly, rather than questioning whether extra degrees of freedom (whether needed or not) are always better than less.

I think sometimes what we really want when we use class inheritance is actually something like a std::variant where we don't have to know all of the constituent types in advance.

> My point is, this mismatch between how flexible the technique we're using is versus how much flexibility we actually need

well, most of the software I use every day have some sort of plug-in interface which is done at some point by loading a .dll at runtime and getting derived instances of a base type defined in the host app.

That's a very good point. It might be question of high versus low level. From a video I watched today (the rest of the video is worth watching, too, but the following stand-alone quote is apropos): "Polymorphism and interfaces have to be kept under control. I don't believe that their role is in a very low level system like interpolating a couple of numbers in the animations, but they have their place in high level systems, in client facing APIs. They are amazing if you do a type of plug in and you really need some type of dynamic polymorphism."

https://youtu.be/yy8jQgmhbAU?list=WL&t=2553

For sure, this is one of the legitimate uses of runtime vtable-based polymorphism. But it's also unnecessary if you assume the user is able to recompile the program.

There also was a talk at CppCon on compile time regular expressions in C++20: https://www.youtube.com/watch?v=QM3W36COnE4

> Believe it or not, this is actually decent performance

The ARE YOU NOT ENTERTAINED of programming.

Impressive! Interesting as a benchmark to test the performance of different compiler implementations.

There is no misuse of anything. Stop being so presumptuous and shortsighted, especially on hacker news.

Is there some theoretical bounds or anything preventing the compilers to be faster or is it just implementation/optimization details?

(GHC tends also to be quite slow.)

C++ compilation is massively slowed down by the sheer existence of the preprocessor. This could be drastically improved by the usage of modules which are coming soon(tm).

Both MSVC and Clang already support them experimentally fwiw.

To be fair, what slows down compilation is not "the sheer existence" but the extensive use of large and complex #include files.

Indeed. IIRC this topic is covered directly in Meyers' "Effective C++" book, including the trick to use pointers + forward declarations in headers to avoid including other headers.

The argument could be made that compile-time processing is highly appropriate for the static inputs of a program, and, at the other extreme, obviously can't be applied to the dynamic inputs. (Terminology from https://en.wikipedia.org/wiki/Partial_evaluation)

Of course, the raytracer source code is the dynamic input of a compiler. The Futamura projection perspective suggests interesting options here for e.g. specializing raytracers in relation to particular scenes.

D did this a long time ago too.

https://news.ycombinator.com/item?id=7530692

https://web.archive.org/web/20151113173822/http://h3.gd/ctra...

It should be noted that this was done in very old D, before a lot of compile-time improvements that modern D has. I guess makes this feat more impressive for the time, while the same exercise today should be more pedestrian.

It's really nice that D was built with this sort of application in mind instead of having it added 30 years later. It makes the language feel far more cohesive and inviting for this sort of thing.

If C++ were able to discard old features, I might not be so scared of going back to it. The way it keeps growing without pruning does not make it feel very inviting.

The annoying thing about C++ is you need a big huge book to tell you which features are safe and how to combine them and stay safe.

Maybe if they started defining a 'modern c++' subset that you could limit it to via compiler flags and/or pragma's it would make life a bit easier when starting new codebases.

Obviously you can always make a personal style choice on what to use, but then you have to find one. Anyone have a favorite set of recommendations for c++ feature usage?

Also, if you start with 'X did this a long time ago.' You always end up in a LISP-hole. :P

> Maybe if they started defining a 'modern c++' subset...

Here it is: https://github.com/isocpp/CppCoreGuidelines/blob/master/CppC...

Great reference, although none of the hyperlinks on the page work for me. I tried Firefox, Chrome, and Edge. I also tried all of the older tagged versions.

For me neither, try this instead:

https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines

Awesome! Thanks for the info.

Apparently it doesn't compile because of how the pow function is implemented. I am not able to figure out what the issue is right now.

Ye gods. And I thought build times were long enough already!

In awe.

So this is basically misusing the compiler as an impractial script interpreter?

I'm not sure if it counts as misuse, compile time evaluation is intended to be used to do computation at compile time. But "an impractical script interpreter" is certainly one way to view it.

It used to be a misuse (when metaprogramming was templates and then after the very first constexpr functions were introduced) since back then metaprogramming was intended to decide simple facts about the program and make inlining easier. But in this standard they actually made it so that pretty much all C++ stdlib can be constexpr and it is encouraged to "constexpr everything". So while this is not an abuse of C++ compiler, it's likely not a fantastic idea since C++ compilers tend to be slow.

> misusing

AKA hacking.

so, c++ becomes greater?

C++ has a whole scripting language embedded into itself. They're trying to reinvent lisp, of course a much less efficient lisp.

> less efficient lisp

But C++'s variety of parentheses is larger!

If LISP can do it with just one kind of parentheses that means it's more efficient. Can't argue with that...

I'm not following you. Lisp can do it with just two sort of syntactic atoms: symbol and parenthesis. To me, it seems like lisp is an order of magnitude more elegant than C++ where you need to hack-in every additional feature by (1) standardizing a syntax after making sure it doesn't break anything (this takes years of committee meeting and convincing tons of angry people with opinions) (2) handling that special syntax in lexer+parser+static analyzer+code generator; whereas in lisp every new feature would be part of the program itself, so essentially you just need to implement some parts of static analyzer and code generator.

Lisp is certainly more elegant than C or C++. The axiomatic nature makes for beautiful programs, and small teams of bright people have had notable successes using Lisp.

But in practical use, being axiomatic can be an enormous weakness. After all those much-derided committee meetings for C++, there is a standard, and having a standard allows people to collaborate without every team having to invent their own conventions and teach those conventions to everyone they work with.

Old style C macros can be seen as an ugly way of providing lisp-like power. One of the problems with macros is people abuse them to do crazy non-standard things, and in doing so make code really opaque to others. So in C, having to invent a custom language to do something is a bug. In Lisp, it's a feature. That distinction has a lot to do with why the world is running so much C and C++ code even though a Lisp is more elegant.

Genuinely curious here, I don't know much Lisp, but dont Lisp macros tend to be powerful in the sense that they expand to more statements for runtime, whereas the purpose of C++ constexpr is to compile it down to one constant at runtime?

Lisp macros expand at compile time. You can also generate code and execute it with eval like in many other languages like python.

Lisp macros expand at compile time, but there's nothing special about the code running in them. Nothing at all stops you from doing arbitrary evaluation in one.

Speed also isn't as much of an issue, because macros (and the functions they call) can be compiled before execution.

Aah, k, thank you!

You can do arbitrary computation with lisp macros. But the magic you do it exactly the same way you do runtime computation.

> They're trying to reinvent lisp, of course a much less efficient lisp.

yes, please show us all those high performance libraries written in lisp

It's OK.

Lispers live in a parallel universe, where performance issues are mere distractions from the higher level thinking.

Not every performance issue needs lower level optimization. Most performance issues can be solved by (1) optimizing algorithms and (2) abstracting lower level code in FFI C functions. C++ helps for 2 but not for 1 because if you don't have a clear high-level understanding of your algorithm, system, pipeline, it's harder to optimize or maintain that optimized code.

> C++ helps for 2 but not for 1 because if you don't have a clear high-level understanding of your algorithm, system, pipeline, it's harder to optimize or maintain that optimized code.

I strongly disagree. C++ has very nice tools for abstraction: higher-kinded types, dependent types (to some extent), lambdas & function objects, overloads, etc. It's a pain to design a data flow in C, but in C++ for instance it can just be something like this : https://github.com/RaftLib/RaftLib/wiki/Linking-Kernels or this : https://ericniebler.github.io/range-v3/.

What's that saying? "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp." Apparently applies to the compilers now, too!

Can you show us some examples of this efficient lisp that's faster than anything already constexpr-ed? :P

I didn't say "faster", I'm not claiming lisp is faster than C++, that's factually wrong. C++ is investing VERY heavily in metaprogramming since they finally figured out metaprogramming is important. Guess what, we knew this since 1960s and had an even better and elegant way of doing metaprogramming. It took ~60 years for us to realize the importance of a key feature of lisp and now we decided to make a hacked-on implementation of it. I'm personally pretty ok with C++, and it's not like this is community's fault given C++ originated from C. I'm just saying that the concept of "doing arbitrary computation in compile time" has been known since the dawn of computer science, and we had an extremely elegant and efficient way of doing it.

Then I misunderstood the original comment, apologies.

I agree with the utility of the approach. Given the narrow space the language can move, they actually placed the feature really well.

Starting with C, we almost achieved what lisp can do in a few thousand lines of code in, what, 20 years. I don't consider this a success, especially since C++ standard is now one of the longest, subtlest technical documents in the industry. We created a monster.

Fun project, but C++ sure is getting more ugly and arcane by the day. I think it's time it went away. I have great love for C but C++ has just always turned me off.

I felt this way too but was using C++ for work and have grown to like it. If you can use only the newer language features it is actually quite pleasant. You can avoid a lot of the pointer arithmetic and off by one errors that occur in C. I didn't realize how productive I was in the language until I found myself writing a small script I would normally have written in python in C++ instead.

Reply on news.ycombinator.com