Removing/replacing the PolyVox::Array class

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

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 :-)

kklouzal · **Posted:** Fri Aug 22, 2014 3:00 pm

Awesome! The faster the better! I'm curious as to what profiler you use?

petersvp · **Joined:** Tue Apr 08, 2014 5:10 pm **Posts:** 124

Do NOT use Private for something useful. Mark it as Advanced / Undocumented, else, you are risking us hacking it

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

kklouzal wrote:

Awesome! The faster the better!

Yep! I also said that the 'best case' scenario (with the biggest improvements) occurs when a processed region is empty, and actually I think this is probably the most common scenario as well. The amount of voxels which actually generate mesh data is quite a small proportion of the whole volume, so I hope it will give real speed-ups.

kklouzal wrote:

I'm curious as to what profiler you use?

The one which comes with Visual Studio. I actually have Visual Studio Ultimate (one of the perks of being in academia) and I think it might not be included in the Express edition.

petersvp wrote:

Do NOT use Private for something useful. Mark it as Advanced / Undocumented, else, you are risking us hacking it

By 'private' I actually meant I have put it in the 'Impl' (implementation) subfolder, so you just have to include 'PolyVoxCore/Impl' to get it. It's pretty simple anyway (the old version was spread over seven files!).

petersvp · **Joined:** Tue Apr 08, 2014 5:10 pm **Posts:** 124

Nice. I feel like I will integrate this into my local copy of PolyVox 0.2.1 and will add clone() method

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

Ok, so I've actually left the new Array class in the public API as it does indeed seem generally useful. It might change further though. I've also templatized it so that it is again multidimensional (up to three dimensions), but it does not support '[]' chaining as this is the part that was slow.

So, in summary, the Array class still exists but instead of:

Code:

myArray[xPos][yPos][zPos] = value;

You now have to call:

Code:

myArray(xPos, yPos, zPos) = value;

Amazing that it can make such a difference to the speed, really.

petersvp · **Joined:** Tue Apr 08, 2014 5:10 pm **Posts:** 124

Today I am debugging similar Array class with no evidence why my operator()(x,y,z) crashes as hell

https://github.com/spytheman/piGameCrea ... cArray3D.h

mordentral · **Joined:** Mon Feb 17, 2014 2:27 pm **Posts:** 6

So this thread was interesting enough that I went ahead and transitioned my UE4 plugin over to the Polyvox Development branch today.

Holy crap, it is like a 75% speed decrease on my test landscape extraction time. Not only that you provide samples for GPU mesh decoding that I should be able to fit into the UE4 FRHIComputeShader and the unclassified functions should work into my threading model better.

Great work guys.

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

mordentral wrote:

Holy crap, it is like a 75% speed decrease on my test landscape extraction time..

That's good to hear, the tests were performed on best-case and worst-case scenarios so I'm glad they map to real-world performance gains. And hopefully there are more improvements to come :-)

Removing/replacing the PolyVox::Array class

Who is online