Sunday, 4 August 2013

C++ Virtual Function Overhead

I have recently been trying to change Imagine's Acceleration Structure infrastructure to be more dynamic, allowing different objects and geometry instances to have different acceleration structures either automatically based on heuristics, or based on user-specification within the interface.

Imagine's acceleration structures have for the past two years been implemented with the "Curiously Recurring Template" design pattern, which allows virtual function-like ability to some extent while enabling the compiler to inline the functions. I chose this way of doing things as I had assumed that Virtual Functions would have some overhead, despite previously doing some experimentation with Virtual Functions and surprisingly finding they don't seem to have any overhead compared to fully-inline-able functions.

The "Curiously Recurring Template" pattern doesn't easily allow a templated base class (for Triangles, Shapes or Objects in Imagine's case) to be specified as a pointer and then the actual implementation to be instantiated as a derived templated acceleration structure, which is what I needed for this dynamic flexibility.

So I decided to do some more benchmarks to investigate any overhead again.

First of all, I tried a synthetic benchmark of just a simple for loop of 1,073,741,824 iterations, calling getHitObject() on the acceleration structure pointer. For the "Curiously Recurring Template" implementation, the pointer type was of KDTreeVolume<T>, the actual derived class and the object allocated for that pointer was of the same type.
In the Virtual Function implementation, the pointer type was to AccelerationStructure<T>, the base class and the actual object allocated for the pointer was KDTree<T>, a duplicate of the KDTreeVolume<T> class but which used standard C++ virtual inheritance from the abstract AccelerationStructure<T> base class.
The code was run in a single thread.

Eight pairs of runs were done, alternating each implementation, and I tried to make sure the CPU core temperatures were under 55 degC before starting each test to ensure that there was no disadvantage to be had by a core not being able to Turbo Boost overclock.

TestCRTVirtual Function
1138.73941137.11993
2141.10697137.10513
3136.96121137.07798
4136.67388139.22481
5136.91679138.22481
6137.20460138.49725
7138.77106139.43341
8136.85819137.13652
Mean Average137.90402137.97748

Other than the second result for the "Curiously Recurring Template" implementation, the Virtual Function method seems very slightly slower, but this difference is within the margin of error. This surprised me, but given the simple test case, it's possible that the processor's branch-predictor was negating the overhead of the v-table lookup, and thus might not be showing the difference.

So I decided to do some more realistic general purpose rendering benchmarks with the two different implementations, to see if any difference could be spotted there.

I created a scene with a fully-enclosed room, with 32 cubes inside and 2 area lights, and all surfaces fully diffuse. All geometry objects had less than or equal to 12 triangles, so the acceleration structures would be very shallow and thus any Virtual Function overhead would not be dwarfed by the work each function was doing on the acceleration structure.

The first test was at 1024x768, with 256 samples per pixel, and 10 ray bounces.
With this test, the getHitObject() function would be called 2,013,265,920 times (for each camera ray and each diffuse bounce ray) and the doesOcclude() function would be called 4,026,531,840 times, once for each light (no light importance sampling was used) for each surface evaluation. All threads were being used for rendering.

TestCRTVirtual Functions
105:52.72005:41.340
205:53.42005:40.790
305:51.87005:41.620
405:49.58005:42.200
505:46.38005:41.790
605:49.15005:44.380
Average05:50.52005:42.020

The above results are in minutes, and show that the Virtual Function implementation was consistently slightly faster. I decided to do these tests again with double the number of samples per pixel (to double the above numbers), and again the results were pretty much the same:

TestCRTVirtual Functions
111:41.97011:40.880
211:41.38011:37.710
311:47.79011:31.560
411:37.53011:26.680
511:45.27011:31.530
Average11:42.78811:33.672

I'm still surprised by this, but I'm putting it down to either compilers being a lot more clever than they used to, or the inlined "Curiously Recurring Template" implementation creating bloated instruction size. Or more likely, the fact that things like cache misses, load dependencies and branch miss-predictions within triangle and boundary box ray intersection code hide any overhead there may be.

Regardless, it appears that to all intents and purposes in my use-case, Virtual Function overhead is practically non-existent. I'm sure things would change with deeper inheritance hierarchies and multiple inheritance, but at least in my use-case it seems safe to move back to Virtual Functions. What's more, Intel's Embree high-performance ray tracing kernels use Virtual Functions, and they're pretty-much state-of-the-art.

No comments:

Post a Comment