Swallowing the elephant (postscript: reader emails)
Thus, “writing an email” is the activation energy required to comment on things posted here. Even with that friction, a number of people sent me insightful emails after I posted the “Swallowing the Elephant” series on rendering the Moana island scene with pbrt; many thanks to everyone who took the time to write. Today, we’ll dig into a few of those emails, enjoy another parsing speedup, and learn a few things along the way.
Parsing floats, revisited
When we ended before, roughly 20% of scene parsing time was spent turning floats-as-text into floats-in-memory. That felt like a lot, but it wasn’t clear to me what do to about it.
Fortunately, both Jon Harper and Алексей Аверченко pointed me at a nice
Google has released. Both of them told me that it was state-of-the-art for
efficiently and accurately printing floats and both suggested that it would
also likely be good at parsing them. I did a few benchmarks and found that
they were right: it was between 1.5x and 2x faster than
strtof() on the
system I was using. Nice!
It was easy enough to use that for the float parsing code in pbrt-next, the branch I use for hacking on new ideas. With fingers crossed, I ran some benchmarks. Previously, pbrt-next spent 11m 24s parsing the Moana island scene. When using double-conversion, parsing time dropped to 9m 18s, a 1.2x speedup.
That’s delightful, though it doesn’t quite fit with the earlier measurements,
which had 20% of startup time spent in
strtof(). If 20% of time is spent
parsing floats, doubling the performance of float parsing should give
roughly a 1.1x speedup, so something’s off somewhere. Forgive me, but I’m
going to be lazy here and not chase down exactly what happened; when you
get a greater than expected speedup, it can be hard to muster the
motivation to chase down where your earlier measurements were off. tl;dr,
double-conversion is fast.
Allow me to distract you from my lack of benchmarking rigor with another rendering:
Moana island, closer in, rendered with pbrt at 2048x858 resolution with 256 samples per pixel. Rendering time with a 96 vCPU Google Compute Engine instance at 2 GHz was just 34m 32s.
Printing floats, revisited
Ever since I read Bruce Dawson’s nice blog post about accurately printing
I’ve been nuts about using
printf when printing
floating-point values. The idea of printing out a truncated number that
doesn’t capture the full precision of a floating-point value drives me
bananas; in what world does it make sense for default behavior for
be to throw away precision?
%.9g works well enough, but it has one shortcoming: it gives a
sufficiently precise value to be able to accurately reconstruct the
original floating-point value, but not necessarily the shortest value that
will do that. Consider the real number 0.2: it can’t be exactly
represented in base-2 floating-point. With 32-bit floats, the closest
representable value to 0.2 is
turn, if you print that using
%.9g, you get
0.200000003. That is
indeed enough precision so that parsing it gets you back to the exact
value as before, but it’s a little messy—all those zeros and then a bit
of schmutz, more characters than you started out with.
I thought that discrepancy might cause some trouble when converting the
Moana island scene to use PLY
When pbrt is run with the
--toply option, it parses the scene
description, writes out PLY files for big meshes, and then prints the
remainder of the scene description to standard output. I made sure to use
%.9g for all of that printing in order to be sure that the new scene
description was completely unchanged by the conversion process (every bit
is sacred and all that).
Aesthetic issues of numbers like
0.200000003 in the output aside, I
wondered whether the files were significantly larger than they needed to be
due to carrying along more digits than were actually needed. I didn’t know
what to do about that until I checked out
routines for printing floats and doubles; they include
which prints a
float with just enough precision to reconstruct its
floating point value. In turn, that prints the rounded
float value of
I changed pbrt to use
ToShortestSingle() rather than
re-converted the scene to PLY format, with high hopes that the residual
pbrt files would be significantly smaller and that in turn, parsing time
would be further reduced thanks to having less stuff to get through.
Unfortunately, the scene files were only 2.5% smaller; a nice little
something, but not enough to materially affect startup time.
Tagged pointers and friends
Last time, when discussing additional ways to further reduce memory use, I suggested using unused bits in pointers for type identification and then manually performing virtual function calls using those type indexes as a way to save all the storage of vtable pointers. Many people wrote with information about prior applications of this idea; it’s definitely a thing, especially in modern dynamically-typed languages.
Juho Snellman pointed me to a blog post he wrote about the history of the representation of numbers in Lisp, which is full of great history on this topic. He also noted:
Alternatively, since you’re already considering arena allocation for these objects, it seems like some form of range-based pointer tagging (e.g. BIBOP) could work well for. The core idea is that you reserve each X byte block (e.g. 1MB) in the arena for just one datatype. The block->(vtable for all objects in the block) mapping is kept on the side. With properly aligned blocks, going from a pointer to an index in the vtable vector can be just a couple of bit operations.
Steele’s Data Representations in PDP-10 MacLISP seems to be the origin of the range-based pointer tagging idea. This idea seems particularly appealing in a world of massive 64-bit address spaces: map a single huge range of virtual memory for triangles, say, let the virtual memory system allocate physical pages only when needed, and then do a quick check to see if a given pointer is in that range to know if it’s a pointer to a triangle.
Going back to the original idea, number of libraries make it easy to encode type information directly in pointers and even offer a measure of type safety when doing so. Bart Schuurmans pointed me at LLVM’s PointerSumType, which uses the low bits of a pointer for type identification. The caller must provide sufficiently aligned pointers to leave enough bits for type identification, which is arguably a more portable approach than stealing currently-unused high bits from 64-bit pointers. (Juho also noted that using the low bits is likely to lead to more efficient code on x86 than using the high bits.) Bryan Catanzaro pointed me at DiscriminatedPtr in Facebook’s folly library, which uses the high bits, which is preferable if the number of distinct types to be represented is more than a small handful.
My earlier assumption had been that given a type index, the best way to
dynamic dispatch would be to do an indirect function call through a table
of function pointers. Sebastian Sylvan
wrote a nice email arguing that using a
switch statement or explicit
ifs based on the type could actually be a better approach, especially if
there are not too many different types (as is the case here).
Consider something like:
int type = /* extract the bits from the pointer */; if (type == TRIANGLE) return RayTriangleIntersect(...); else if (type == CURVE) return RayCurveIntersect(...); else return shapeVTables[type]->Intersect(...);
The common cases—triangles and curves—are checked first and those
tests would turn into direct branches that likely be very well-predicted
(by which I mean “it’s probably a triangle”). Further, the code for those
cases could even be inlined if we wanted; that gives us now two things that
might give better performance than a virtual function call. For a
situation like this, where there are a very small number of commonly-used
cases and then a long-ish tail of more rare ones, this implementation
approach is potentially appealing from a performance perspective—it’s not
necessarily just about saving memory by getting rid of vtable pointers.
Having two good reasons for adopting this approach (memory use and performance) now has me conflicted about how to proceed with respect to pbrt. pbrt’s two main reasons for existence are to teach people how physically based rendering works through code and to show the implementation of a reasonably well-written ray tracer.
Is this a technique that’s important enough for renderer implementation that we should include it in the book in the interests of pedagogical completeness, or is it too much added complexity for the student trying to get a handle on the basics of ray tracing in the first place? I can’t decide, but at least there’s some time to figure it out before a new version of the book is due. Onward to hacking up an implementation and seeing how it feels.