metatrace, a C++ compile time ray tracer

(L) [2010/01/07] [phresnel] [ metatrace, a C++ compile time ray tracer] Wayback!

Background
Three years ago ... Upon trying to increase wisdom and earning some geek points, I conclude that writing a C++ compile time ray tracer might be a valid idea.
Three or so months ago ... I consider the point of time back then to be a good one to start development.
Two or so months ago ...
precprec5.png
>> me: just some more man-hours * and i have a whitted-style cornell box
lycium: hehehe, you're crazy
... who could know that fractionals, even when using 64 bits for both the numerator and denominator, get out of control so madly ... I implement precision reduction (i.e. inexact cancelling), but it was not enough for real scenes. Arbitrary large integers at compile time was no option. I conclude that having a fixed denominator in every case might yield the most robust and consistent results: fixed point math.
... distractions and backlogged stuff and an act of relocation keep me off. I know I have it quasi ready, except for some more debugging. Then, the christian holydays before the gregorian new year kick me back in. I hack fixed point math and can reuse most of the cruft.
... and it is good ...

Less boring stuff
I know most of us are male and thus not interested in all the emotional background crap, hence:
example-0.png

Info
Metatrace is a C++ compile time ray tracer (as of the initial release, it is a whitted style one).
It is mostly inane stuff. Except, maybe, that it’s a nice gadget to test compiler performance and conformance, especially but not exclusively in the Template and Metaprogramming corner of C++.
It requires basic C++0x support; with g++, make sure to have at least 4.4 installed. Other compilers are untested.
Features (graphics viewpoint):
  linear object list
  recursive ray tracing (whitted style)
  mirror reflections
  spheres, axis aligned planes
  quite easily extensible (considering the circumstances)
  rgb colors
  scalar type is fixed point
  not fastFeatures (c++ viewpoint):
  uses variadic templates in some contexts (e.g. scene, some math-operations)
  fairly heavy compile time number crunching (brings back the “slow” in “ray tracing”)
  strongly typed enums, to avoid ugly enum hacks like “FORCE_DWORD=0xEFFFFFFF” and the like
Features (bash viewpoint):
  contains an ugly bash script to compile on multiple cores
… more to come.
This is a first release. I have to work through the code to ensure compliance before The Supreme Committee. I also got to set up some benchmarks and make some cosmetical changes. But now, I am happy to release this crap.
Btw, here is how to invoke metatrace at the sourcecode level: [LINK http://gitorious.org/metatrace/metatrace/blobs/master/src/main.cc#line199] [SMILEY :D]

Get and view
get: [LINK http://code.google.com/p/metatrace/downloads/list]
view: [LINK http://gitorious.org/metatrace] or [LINK http://savannah.nongnu.org/projects/metatrace]

Other Compile Time Ray Tracers
At the forefront, there is ctrace [0] by codeinsane, h3r3t1c, or simply Tomasz Stachowiak [1]. But is in D, where template metaprogramming is not a challenge anymore (Tomasz, lurker, please don't take me serious, I am not kidding [SMILEY ;)] ).
Then, our benevolent dictator tbp, Master of C++ Templates [2], Expert of Floating Point [2], and Silent Wizard of Optimization [3] has written a little toy ray tracer (sic) based on his metafloat [3] meta float library. Upon inspecting the source code, I see it renders a single sphere in pseudo-phong (read: dot product) which is hardcoded into scene. An awesome proof of concept of compile time, handcoded (!) ieee math.
Finally, and I (read: google) found no other results on the first 10 pages of search results, there is the Meta-Programming Raytracer [5]. It is based on fractional math, and renders a single sphere of unshaded green (basically, it visualizes whether the sphere has been intersected or not). It is also based on boost::mpl [6].
I think metatrace is the first recursive ray tracer at compile time in C++  [SMILEY :P]
[0]: ctrace, [LINK http://h3.team0xf.com/ctrace/]
[1]: [LINK http://codeinsane.deviantart.com/] , [LINK http://h3.gd/]
[2]: [LINK http://ompf.org/forum/viewtopic.php?f=8&t=737 viewtopic.php?f=8&t=737]
[3]: [LINK http://ompf.org/forum/viewtopic.php?f=11&t=499&start=50 viewtopic.php?f=11&t=499&start=50]
[4]: metafloat, [LINK http://ompf.org/forum/viewtopic.php?p=6525#p6525 viewtopic.php?p=6525#p6525]
[5]: meta-programming raytracer, [LINK http://www.ambient-occlusion.com/2009/09/meta-programming-raytracer-13/]
[6]: [LINK http://www.boost.org/doc/libs/1_41_0/libs/mpl/doc/index.html]
---

Again: Creepy sourcecode here!
get: [LINK http://code.google.com/p/metatrace/downloads/list]
view: [LINK http://gitorious.org/metatrace] or [LINK http://savannah.nongnu.org/projects/metatrace]

(L) [2010/01/08] [phresnel] [ metatrace, a C++ compile time ray tracer] Wayback!

>> lycium
anyway, i maintain that you're completely crazy
What does not kill you makes you stronger [SMILEY :)]
>> h3r3tic
Any stats on that sample image? I'm curious about the overall time and memory consumption of the compiler.
I think the render time was 14 hours, with a tile-size of 5x1 ([LINK http://gitorious.org/metatrace/metatrace/blobs/master/render.sh]), then after everything is done, I invoke image magick to catenate the ppm's. But ...
>> h3r3tic/phresnel-correlation
I had to split the rendering into tiles for ctrace/metatrace [...] because the compiler would run out of memory
... and performance slows down exponentially with the number of template instantiations, which made it difficult to choose a good tile-size. But [LINK http://gcc.gnu.org/gcc-4.5/changes.html g++ 4.5] should fix this, as
>> [LINK http://gcc.gnu.org/gcc-4.5/changes.html gcc 4.5]
Compilation time for code that uses templates should now scale linearly with the number of instantiations rather than quadratically, as template instantiations are now looked up using hash tables.
Here are my results from a first test run for g++ 4.4 (test script and script to create an amalgam file are in git-repo):
Code: [LINK # Select all]running 2x1 (2 pixels)
real 0m1.429s
user 0m1.380s
sys 0m0.048s

running 2x2 (4 pixels)
real 0m1.154s
user 0m1.048s
sys 0m0.104s

running 4x2 (8 pixels)
real 0m3.396s
user 0m3.256s
sys 0m0.140s

running 4x4 (16 pixels)
real 0m4.364s
user 0m4.216s
sys 0m0.140s

running 8x4 (32 pixels)
real 0m36.969s
user 0m36.782s
sys 0m0.176s

running 8x8 (64 pixels)
real 0m36.948s
user 0m36.774s
sys 0m0.172s

running 16x8 (128 pixels)
real 10m37.773s
user 10m37.132s
sys 0m0.676s
So, up until now, I have only found out that at least g++-4.4 has exponential runtime in that respect, so may I beg gcc haters for there convenience until I tested the other compilers, please.
edit: About memory consumption, can't tell (but benchmarks are in the make), but I remember having frozen up my 4GiB box several times in the first days.
>> Perhaps g++ is smarter here and can discard unreferenced template instances?
I am slightly confused; in C++, templates are only instantiated when actually used or instantiated explicitly (which is why it is possible to instantiate a template X upon some type T, even if type T does not support all operations of template X; in .net, the contrary is the case, and you have to write ugly workarounds, even if you know what you do: [LINK http://www.gamedev.net/community/forums/viewreply.asp?ID=3504784 [0]] , [LINK http://www.gamedev.net/community/forums/viewreply.asp?ID=3438892 [1]]).
But I guess you mean something like
template <bool cond, typename if_T, typename else_T> struct ift : if_T {};
template <typename if_T, typename else_T> struct ift<false, if_T, else_T> : else_T {};
and then
typedef ift<
        flipflop,
        foomplate<sqrt<666>>,
        barmplate<sqrt<999>>
> frobmplate;
both foomplate and barmplate will be instantiated, as they are part of the type id of frobmplate. So, here comes a lesson from the "C++ Metaprogramming Perfomance Optimization Guide":

template <bool cond> struct foombarm : sqrt<666> {};
template <> struct foombarm<false> : sqrt<999> {};
...
typedef foombarm<flipflop> frobmplate;

Now, only sqrt<666> xor sqrt<999> will be instantiated all the route down.

>> Anyway, looks like I have some work to do on ctrace because your stuff looks better
Heh, until we end up with a compile time monte carlo terrain renderer [SMILEY :D] (I seriously thought about implementing a preetham sky)

(L) [2010/01/09] [h3r3tic] [ metatrace, a C++ compile time ray tracer] Wayback!

>> phresnel wrote:I think the render time was 14 hours
Oh, that's not bad at all, I thought it would be worse [SMILEY :D] Looking forward to gcc 4.5 now.

>> phresnel wrote:Here are my results from a first test run for g++ 4.4 (...)
Interesting numbers, thanks! Is the almost free scaling in the vertical direction an artifact of the test scene (or its fragment) used in this simple test?
As for freezing the box, yea I've done that as well, thought only had 512 rams so it was easier [SMILEY :D]

>> phresnel wrote:I am slightly confused; in C++, templates are only instantiated when actually used or instantiated explicitly (...)
I should have specified it more clearly, sorry. What I had on mind was garbage collection of already instantiated unreferenced templates. For instance, take a template that multiplies two numbers ( pardon if my C++is broken ):
Code: [LINK # Select all]template <int a, int b>
struct Mult {
enum { value = a * b; }
}

now let's use it to implement a factorial:
Code: [LINK # Select all]template <int n>
struct Fact {
enum { value = Mult<n, Fact<n-1>::value>::value; };
}
template <>
struct Fact<0> {
enum { value = 1 }
};

Even though the Mult template is instantiated explicitly, the only entity ever referenced from it is a 'manifest constant', one that doesn't create any symbol. In this case the compiler might be able to figure it out and remove all Mult instances via garbage collection ( well, or any other management scheme ). Same would also be case for Fact if only its ::value field was used.

>> phresnel wrote:eh, until we end up with a compile time monte carlo terrain renderer
Sounds like a plan!

(L) [2010/01/11] [phresnel] [ metatrace, a C++ compile time ray tracer] Wayback!

>> playmesumch00ns wrote:Haha this is one of the most ridiculous things I have ever seen! I love it! Kudos for actually making it work
Danke sehr [SMILEY :)]

>> h3r3tic wrote:phresnel wrote:Here are my results from a first test run for g++ 4.4 (...)Interesting numbers, thanks! Is the almost free scaling in the vertical direction an artifact of the test scene (or its fragment) used in this simple test?
I guess it's just an artifact combined with running the benchmark on a busy box.[/quote]

>> phresnel wrote:I am slightly confused; in C++, templates are only instantiated when actually used or instantiated explicitly (...)
I should have specified it more clearly, sorry. What I had on mind was garbage collection of already instantiated unreferenced templates. For instance, take a template that multiplies two numbers ( pardon if my C++is broken ):
[...]
Even though the Mult template is instantiated explicitly, the only entity ever referenced from it is a 'manifest constant', one that doesn't create any symbol. In this case the compiler might be able to figure it out and remove all Mult instances via garbage collection ( well, or any other management scheme ). Same would also be case for Fact if only its ::value field was used.
Ah, I see. Sorry, I can't give you an answer, but regarding the non-linear memory usage w.r.t. instantiated-template-count in gcc, I guess they are not collected.
Then, there is the one-definition-rule (ODR), stating that each template-id shall only be instantiated once.
In combination with different points of instantiations (where the point of instantiation in itself can be deciding about program semantics as it has a direct effect on symbol lookup (i.e. a symbol X can have different meanings depending on where the template is used)), and assuming that already garbaged template-id can have different points of instantiation upon re-instancing them somewhere else, I guess there can be very very subtle issues, or otherwise, the full context of the first instantiation must somehow be preserved, and hence a GC might not be wortwhile.
So my guess is "no", because of sensible ODR/point-of-instantiation/lookup issues, there is no GC.
I don't know about how points-of-instantiation are defined in D, but if you want to get a glimpse, I am sure you can find something on googlebooks in Josuttis/Vandevoorde "C++ Templates: The Complete Guide".
>> phresnel wrote:eh, until we end up with a compile time monte carlo terrain renderer
Sounds like a plan!
Ausgezeichnet.

(L) [2010/01/12] [h3r3tic] [ metatrace, a C++ compile time ray tracer] Wayback!

>> phresnel wrote:In combination with different points of instantiations (where the point of instantiation in itself can be deciding about program semantics as it has a direct effect on symbol lookup (i.e. a symbol X can have different meanings depending on where the template is used)), and assuming that already garbaged template-id can have different points of instantiation upon re-instancing them somewhere else, I guess there can be very very subtle issues, or otherwise, the full context of the first instantiation must somehow be preserved, and hence a GC might not be wortwhile.
So my guess is "no", because of sensible ODR/point-of-instantiation/lookup issues, there is no GC.
I don't know about how points-of-instantiation are defined in D, but if you want to get a glimpse, I am sure you can find something on googlebooks in Josuttis/Vandevoorde "C++ Templates: The Complete Guide".

I realize that in a general context there are issues with exactly what you're describing. On the other hand, this case is pretty specific. The only entities being accessed from the instantiations are manifest constants. They're not symbols that need to be hashed internally in the compiler and yield the same instance each time, they don't need any mangling either. Any trace of their existence completely disappears after constant folding. That is, unless the compiler is not smart enough to elide them. Wrapping up, I was just wondering whether GCC could do just that. I'm pretty sure DMD-based compilers for D can't and it would seem GCC can't either but I'm not desperate enough for this knowledge as to read its source [SMILEY :P]

(L) [2010/01/15] [phresnel] [ metatrace, a C++ compile time ray tracer] Wayback!

>> h3r3tic wrote:I realize that in a general context there are issues with exactly what you're describing. On the other hand, this case is pretty specific. The only entities being accessed from the instantiations are manifest constants. They're not symbols that need to be hashed internally in the compiler and yield the same instance each time, they don't need any mangling either. Any trace of their existence completely disappears after constant folding. That is, unless the compiler is not smart enough to elide them. Wrapping up, I was just wondering whether GCC could do just that. I'm pretty sure DMD-based compilers for D can't and it would seem GCC can't either but I'm not desperate enough for this knowledge as to read its source
Very subtle. I've looked up the standard, and there:
>> C++ Standard - ANSI ISO IEC 14882 2003-4.pdf :: 14.7.3.6 Explicit Specialization wrote:If a template, a member template or the member of a class template is explicitly specialized then that specialization shall be declared before the first use of that specialization that would cause an implicit instantia-
tion to take place, in every translation unit in which such a use occurs; no diagnostic is required.
In other words: If your program *is* well formed, all template specializations are available at the point where the template is used. And thus some or even all of the things I've mentioned vanish, I think (sidenote: even if no diagnostic is required, gcc will gives me an error when I write an explicit specialization for a template-id that has already been instantiated). I guess it could be possible to write a garbage collector somehow, but that might be hard to accomplish when taking into account the one definition rule. Hmmm. Need more coffee.
>> BlindSideAsGuest wrote:I honestly have no idea why anyone in their right mind would do this
Because what does not kill you makes you hard!
But more seriously, it was primarily an exercise to increase knowledge and fluency when writing meta code.
Anyways, it's not soooo perverse except for the syntax and the lack of a debugger (note to self: write compile time debugger). C++ template metaprogramming means primarily to have
* ... a purely functional language with ...
* ... static duck typing
* ... and lazy evaluation
>> , but knowing you from all your posts on this forum, I know you're completely insane, Phresnal.
[SMILEY :twisted:]

metatrace, a C++ compile time ray tracer back

Board: Board index ‹ Ray tracing ‹ Tools, demos & sources