Performance improvements replacing std::pow( float, 2 ) with explicit squaring, std::array<uint32_t,8> in createOctant about octree HOT 3 CLOSED

Thanks for your sharing your observations under Windows and glad to hear that my implementation also works there. Did you encounter any other issues when porting the code to windows?

I only tested my implementation under Linux Ubuntu 14.04, but did not spend sooo much time on squeezing out every bit of performance. I generally often decided to stay with a more readable version instead of trying to optimize every statement. For me the optimization from using -O3 -DNDEBUG from gcc were enough. But if you need the fastest possible version, there are certainly plenty of opportunities and tricks to further speed up the tree.

As far as I remember, the std::pow had no significant drawback with ggc under Ubuntu 14.04. Therefore, I decided to stay with std::pow for readibility.

The replacement of the std::vector with an std::array is definitely more readable and makes totally sense, but needs C++11 compatible compiler, which I currently don't require. As almost all common compilers now support C++11, it might be a good addition.

from octree.

Jess,

You could replace the arrays with simple uint32_t childStarts[8] = { .... } and it would be almost as legible, with the dowside of not having bounds checking in debug. But I don't think you need to really worry about that in this use case since the number of elements is well known.

Regarding the std::pow, it may we ll be that gcc's implementation handles an explicit exponent of 2 and unrolls it, but visual studio does not. That would explain it not showing up in your use case.

The only other porting issue I had required that I cast one value from size_t to uint32_t - on line 393:

const uint32_t N = pts.size();

becomes

const uint32_t N = (uint32_t)pts.size();

I am running 64 bit so the size_t is a uint64_t - I decided to cast it to a uint32_t because I couldn't imagine having any more points than uint32_t could handle, but really some sort of range test should probably be included, or the N should be a size_t, and everything else dependent on it follow suit.

As for speed optimizations, if I had the time I would investigate changing the node pointers to 32 bit indices, an allocating the nodes out of a pool - this is always a performance win, but complicates legibility.

Thanks again for the implementation - I was going to roll my own but yours is superior.

from octree.

Thanks again for your comment. I put the changes on my TODO list and hopefully can return to this issue soon.

Good luck with your project and glad to hear that my implementation helped someone.

from octree.