CppCon 2019: Matt Godbolt “Path Tracing Three Ways: A Study of C++ Style”

CppCon.org
-
Discussion & Comments: / cpp
-
Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/CppCon/CppCon2019
-
C++ is a multi-paradigm language allowing us as developers to pick and choose among a variety of styles: procedural, functional, object oriented, hybrids, and more. How does the style of programming we choose affect code clarity, testability, ease of changes, compile time and run-time performance?
In this talk Matt will show a toy path tracer project (a form of ray tracer) implemented in three different styles: traditional object oriented, functional, and data-oriented design. He'll then compare and contrast his experiences developing in each case, showing how often the compiler is able to reduce each style to similar performing code. There's certain to be some surprises - and of course some Compiler Explorer usage!
-
Matt Godbolt
Aquatic Capital Management, LLC
Development Engineer
Greater Chicago Area
Matt Godbolt is the creator of the Compiler Explorer website. He is passionate about writing efficient code. He has previously worked at a trading firm, on mobile apps at Google, run his own C++ tools company and spent more than a decade making console games. When he's not hacking on Compiler Explorer, Matt enjoys writing emulators for old 8-bit computer hardware.
-
Videos Filmed & Edited by Bash Films: www.BashFilms.com
*-----*
Register Now For CppCon 2022: cppcon.org/registration/
*-----*

[@narnbrez]

You mean Godbolt isn't a catchy name the dev threw on the tool? lol I had no idea. Great name

[@MattGodbolt]

I know, right?!

[@Evan490BC]

@@MattGodbolt It's like in the old Rowan Atkinson sketch, "The School Master", but in reverse 😉

[@youdonotknowmyname9663]

Wow, this guy ... Just casually writing a path-tracing application in about 100 lines of code .... Awsome!

[@CppCon]

Glad you like it!

[@darkwinter6028]

So YOU’RE the one responsible! I use your website ALL the time; especially when doing embedded stuff. Thanks! 👍😀

[@LogicEu]

Path tracing on its own is already pretty interesting, but this talk is on anther level.

[@ChiliTomatoNoodle]

Great discussion! Rare to see talks like this that don't just devolve into a polemic.

[@dmitriykarbovskiy1790]

Data oriented design is not only more optimal, it's *optimiseable*. It's trivial to add SIMD and run it in multiple threads and gain multiple times the performance. You can't really scale OOP code. Also, this example is really tiny. It's computation-heavy, not memory-heavy, not memory-bound. It does not really show the difference on that tiny scale when everything fits in the cache anyway.

[@DrGeoxion]

I really like Matt! The enthusiasm is contagious 😅

[@parnmatt]

watched the streams as Matt was coding this; fantastic to finally see the talk!

[@michaelthompson7217]

His talks are always solid

[@femloh]

Goodness... Just that change alone! Huge increase! This was a really great talk. Learnt a lot.

[@axelwimmer4601]

Absolutely awesome!

[@aaardvaaark]

Really enjoyed this talk, thanks.

[@Meow_YT]

Really interesting and nice dive into the CPU.

[@nazavode]

One of the most fun and enjoyable talks I've seen recently. Actually using the language to do real stuff is something I was missing in these kind of conference talks. This should have taken twice as much time tho, looking forward to part II!

[@LostieTrekieTechie]

Always a great talk when Goldbolt takes the stage!

[@defense200x]

Very interesting talk!

[@NoNameAtAll2]

Godbolt is always so exciting to listen to I wonder if "likely/unlikely" advice to compiler could be used to make it (and not programmer) think about branch prediction

[@notnullnotvoid]

At the point where you're thinking about likely vs unlikely, you're really already thinking about branch prediction. If you want the compiler to know without having to think about it, that's where profile-guided optimization comes in. Unfortunately the tools for that in practice are pretty scant.

[@ChristianBrugger]

In the original version this wouldn't have helped, as it was a 50/50 chance for each of the branches. Only if as you say it would have made the programmer rethink it.

[@TheBlenderblob]

great talk

[@slipcurve1410]

I love compiler explorer

[@TOMiX1024]

54:00 that is actually what Mitsuba 2 does, i.e. `struct { float x[N], float y[N], float z[N] };`.

[@zvxcvxcz]

38:45 It's simple, test functions instead of objects. This data based approach is definitely the one that comes most naturally to me. Adding other objects, well the difficulty would mainly be in intersection... and actually you should probably break most other shapes into triangles and then do that calculation. I don't think it actually works out to be harder to change if you give a bit of thought to how you would change it before you write it. I don't think difficult adaptability is intrinsic to the approach. 42:50 Hmm, some issue with the triangle intersection code? The spheres were fine. A few minutes later: Lol, branch missing, heh.

[@OskarSigvardsson]

Excellent talk! Is there a link to the github page? On the final thing: I've hit that same || vs. | issue in a couple of hot loops, though never with this spectacular difference. "Avoid branches in hot loops" is very good advice, even short-circuited ones (I might have even replaced the "if (dist < minDist) minDist = dist" with a call to min function). I don't think the "extra work" is a concern here at all. The few extra comparisons will be pipelined and auto-vectorized up the wazoo.

[@SuperLugol]

github.com/mattgodbolt/pt-three-ways

[@MattGodbolt]

The code is on GitHub at github.com/mattgodbolt/pt-three-ways

[@hamesjetfield0]

I thought the OOP version was fairly functional (maybe not aesthetically but from a conceptual point of view). Most functions I saw were pure in terms of this and params. I'd say that's pretty functional). Most mutations seemed to be local. And the virtual inheritance part is just a character of C++ rather than OOP. In a more functional language (with typeclasses or even Rust traits), you'd be able to do the virtual stuff without inheritance so I don't see virtual dispatch as a purely OOP concept.

[@darkengine5931]

It's a path tracer though. A path tracer barely has to deal with mutable state beyond the image it outputs at the end. It spends almost the entire time as well as 99% or so of the code purely reading data in an immutable fashion. So I actually think it's a poor example of highlighting differences in these styles, especially from a code and maintenance perspective. Particularly with a small and simple path tracer like this, you could probably even write it very procedural and just use a dozen global variables and the end result would still be quite easy to maintain (maybe even easiest to maintain). There just isn't much mutable program state at all. Where the code would vary so much more between these while still keeping the project reasonably small would be something like a text editor or CAD software where the user can edit all sorts of stuff, undo/redo operations, save and load, etc. For example, the object-oriented approach to the undo system might use the Command pattern with a whole bunch of command objects that provide virtual undo/redo methods, the functional version immutable/persistent data structures, and the DOD style maybe some very efficient diff/delta system over the data (maybe with hashes and memcmps over memory blocks) to store changesets.

[@statebased]

Fun talk, thanks. Note that technically the data oriented approach can be seen also as a functional approach. For example you could see it as an indexed comonadic container-like structure which contains the intersection “functions” of the scenery, which then can be efficiently “joined” with the ray container (plus recursion for reflections). The difficulty is to capture these complex types. Even in Haskell these indexed types (if we want to allow the scene objects to individual types, eg sphere, cube, ...) are not an easy task.

[@w-mwijnja8919]

Correct, although the same could be said of the 'object-oriented' (class-oriented) approach. That one can also be described by a Hindley-Milner-esque type system. Of course, at the end of the day 'functional programming' first and foremost means 'that functions are used as first-class values', regardless of whether immutability, sum types, monoids, functors etc end up being used.

[@briannoel7398]

I wonder if the reason why the DOD method had so many branch-misses was because he didn't generate data tables with valid information. If I'm thinking about this correctly, you want to check validity when inserting data into a table. That way, when you do your operations on that data, you won't need to check for validity.

[@Jkauppa]

explicit (fixed) sampling is better than random sampling distribution, its more stable, better as single frame, no inter-frame averaging required

[@Jkauppa]

if you are poor, select only the main peak of the distribution, fixed, always, 1 ray per pixel

[@Jkauppa]

wrap the triangle with a sphere collision ray tracing volume, center of mass centered, for ray intersection check boost

[@younghsiang2509]

Does anyone know the tool that was used in this talk to generate the profiling data such as: branch-misses, branches, and instructions?

[@tkava7906]

It comes with Linux kernel. Look up Linux perf tutorial to get started.

[@sideparting6845]

Thanks for saying zed I recognized your BBC owl and Exile on your emulator Yes I am mid 30s and a Brit

[@pavelcelba6976]

Don't believe in splitting X, Y, Z - maybe having one big array of X,Y,Z, X2, Y2, Z2 maybe

[@mikaurtela8047]

The problems with DoD approach being more difficult to change afterwards would be alleviated if we used an actual ecs library instead of a hand written SoA layout.

[@darkengine5931]

Yeah, I felt like the DoD section was the weakest and obviously where Matt had the least experience. But he also missed the single greatest optimization that such a codebase could have with DoD by still keeping his triangle points in interleaved XYZ AoS format (he did mention that, but that's like the biggest and number one optimization afforded with DoD that he neglected) when he's sequentially looping through them. It's often easy enough to get order of magnitude improvements over OO in those cases with a serious DoD mindset, and sometimes 100x or faster without algorithmic improvements, in simple loopy code over data like his path tracer. I also wanted to facepalm a bit when he didn't even bother to profile the code until he had written it all and not only then, but only after he noticed something weird in the benchmarks. Also maybe this is a bit contentious, but from my standpoint, DoD is more top-down design than bottom-up as he described. It's OO that's bottom-up, not the other way around. DoD gets to the heart of the design requirements of the software by looking at it from a data-centric (information-centric, i.e.) standpoint. It organizes the data for efficient access and then builds the minimum layer of functionality and abstractions on top. The code it tends to produce tends to be minimalist and highly-tailored for the problem at hand. It's OO where I tend to find programmers start going really bottom-up and sometimes moving far, far away from the business requirements by building all sorts of monstrous libraries and frameworks before they start actually building the software and writing and using anywhere from tens to thousands of times more code than actually required for the problem at hand.

[@satellite964]

DoD is the most clear. FP was the most opaque.

[@pushqrdx]

15:20

[@danielkrajnik3817]

funny, Compiler Explorer is called the same name

[@perfumedmanatee6235]

Discriminant (not determinant)

[@MattGodbolt]

Oh doops!

[@smrtfasizmu6161]

Yes, determinant is a property of a matrix, how much hypervolume created by unit vectors increases under a given matrix transformation, but it doesn't matter, we all understood what he wanted to say, I would sometimes mix up the two terms as well.

[@spiceEx]

Can someone make a subtitle so the people who English Listening Comprehension not well can follow the talk?

[@sebastiantill8019]

Nice bloke, but his naive implementation of path tracing is a worst case scenario for data coherence and thus an awful example for the comparison he is trying to make.

[@MattGodbolt]

Of course: it's a talk, and it wasn't designed to be anything but a demonstration of techniques and styles. If it was even slightly serious, then some kind of BV-hierarchy would be the first thing to do... but anyway! Hope it was interesting. To get the stats I used Linux `perf`

[@skepticmoderate5790]

Cartesian product? Bro, you C++ programmers are weird. It's called zip.

[@xarcaz]

Lol, no.

[@IsmeGenius]

Zip is inner product. Cartesian product is outer product where you visit all the possible combinations.

[@AntiProtonBoy]

@@IsmeGenius My understanding of zip is you parallel combine pair of input ranges, producing an output range. Whereas inner product parallel combines pair of input ranges, then reduces into a single element for output.

[@zanityplays]

What else should Cartesian product be called even in python it's called product in the itertools library