Cython optimization of OOP Code

Currently I am working on a optimized dataflow for zooming functionality of the e-profile portal.

A key component of this optimization is a server side pre classification of datapoints that assigns them a certain zoom level.

This is should be done with a modified QuadTree algorithm in Python. 

The Python implementation of the QuadTree algorithm that I used for my "proof-of--concept" implementation is from Scipy Author Christian. Many thanks for this easy to understand piece of software.

The Python algorithm is working and has no obvious Python bottlenecks, but it is too slow (0.1 sec for 5000 datapoints) for our purpose. Our target is 0.1 sec for 100000 datapoints.

The algorithm is OOP and pure python so no shame to the author. I have at least 3 ideas how to optimize the algorithm and make it more memory and time effizient.

But I am also right in the middle of creating stuff for our Cython course for the Inqbus programming academy. 

My goal for today was to check what a naive Cython optimization will gain in speed:

• Just switching on Cython instead of Python
• Then ctype all variables
• Then change more complex semantics to Cython like functions and classes utilizing "enhancement types"

Now to the gain:

• Just switching on Cython instead of Python : Gain 30%
• Then ctype some variables : Gain 33%
• Then change other semantics to Cython like functions and classes utilizing "enhancement types": Gain 50%

Some naive measurements (Timing whole programm via the profiler, including data preparation) in seconds runtime.

Conclusion:

1. Changing to Cython semenatics will give you a performance factor of two for your python code. This is OK if you need just this factor. But usually you are in search of a magnitude before you start optimizing.
2. Cython shows an impressive potential for optimization even on complex OOP codes utilizing "enhancement types". But here I have to dig a lot deeper to find the corner cases.
3. A real Cython optimization is a complete different thing.
   
   • Choose the optimal datastructures that interface smoothly between the Python and the Cython world (in both directions). Numpy-Structures are a good start for that.
   • The internal data structures of your Cython code should be optimized to Cython not Python.
   • Cleanly dividing the Cython from the Python world via effective Interfaces is the goal to Cython performance.

I will come up with two new implementations of the QuadTree algorithm in Python as well as in Cython. My objective for this reimplementation is to change the classes Point/Rect/QuadTree from representing the data structure to just manage the data structure. This is in pattern terms a classical MVC optimization.