Performance optimization of the modified quadtree algorithm

For e-profile we need a really fast algorithm to place a bunch of windbarbs according to a given zoom level.

We discussed this issue here and here and here.

The algorithm for E-Profile is a slightly modified quadtree algorithm, described here in detail. Update: The algorithm failed the goal. So a new algorithm was developed.

To get a decent performance you have to squeeze any ounce of performance out of the code.

So we test all our optimizations against 1 Milllion datapoints and our target is one second runtime.

The base case is the Python OOP Code. It take 21 seconds for 100000 datapoints, far to slow for our need.

An alternative implementation in Numpy utilizing numpy Integers in favour to python Pointers reduces the memory consumption tremendously. Also the runtime is roughly halved or tripeled.

Ich we take the base case code and do just semantic changes in Cython notation via a pxd file we will gain ten times the speed of the numpy solution. Cool!

Then we can optimize the cython code even more. We combine the three classes in the base case into one class and use for this class a Cython cdef class we speed up another factor of five. Really impressive.

But the fastest and most memory efficient solution is the write the algorithm in plain procedural Cython utilizing a Struct to represent the quadtree structure. In addition we use a Cython cdef class to present the cython procedures as member of a Python class. And with this optimization we arrive at our optimization goal: 1 Mio datapoints processed in 1.4 seconds.