Hi guys,
As noted in our
last blog post, one of the next aims for Cubiquity is to improve the performance and naturally this involves some optimizations to PolyVox. I've recently been going over the marching cubes surface extractor with a profiler and noticed that the PolyVox::Array class was one of the bottlenecks. I created a separate test for it, and found that in terms of raw read-write performance the PolyVox::Array was roughly 50(!) times slower than a raw C array.
The main aim of the Array class was to provide a multidimensional fixed-size array where the size can be specified at runtime. It is this runtime-size property which separates it from C arrays, which can only have their size set at compile time. The reason that this Array class is complicated is that we usually like to index multidimensional arrays with a myArray[...][...][...] notation, but C++ only lets us overload [] a single level deep.
The solution presented
in this article solves this problem by defining the operator[] of an N-dimensional Array to return an N-1 dimensional Array, so that the [] operators can be chained. The resulting template code is rather complex but does work, and is what we used in PolyVox.
However, we now find it is very slow! I suspect the reason is the construction of the intermediate lower-dimensional array objects, which we would have hoped were optimized away by the compiler. Perhaps they are not, or perhaps there is some other issue. At any rate, I can say that we do not need the flexibility which this class provides (certainly not at this cost) as we are only using 2D arrays anyway.
I am therefore removing the Array class from PolyVox, and have replaced it with a much faster Array2D which does not use any fancy template magic and which is as fast as a native C array. The marching cubes extractor is now more than twice as fast in the best case (when processing an empty region) and about 25% faster in the worst case (processing a region full of noise).
I think this probably does not affect any users as I doubt anyone was actually using the PolyVox::Array class? I'll probably keep the Array2D class private as it doesn't feel like it needs to be part of the PolyVox public API.
Anyway, you can all look forward to faster surface extraction now