nearest particle search

Nearest neighbour particle search (NNPS) is  a common requirement of (meshfreee) particle methods, such as SPH. The requirement is to locate all particles within a fixed distance (the kernel support) of a specified particle, and the trick is to avoid doing brute-force distance comparison of every particle with every other particle (O(N^2)). There are many techniques available to implement this. One of the simplest for a fixed kernel support of all particles is to bin the particles and then search for the particles only in the neighbouring bins. Such a technique is implemented here: http://code.google.com/p/pysph/source/browse/source/pysph/base/nnps.pyx?repo=kunalp-alternate.
Here i'm gonna present some timings for the nnps. Note that the timings are old and also include some constant extra times for other operations (calling of rand() numpy function which i've now converted to the c rand() function).

Here are the timings result (Click on image to view the raw data sheet) :

As you can see, it shows that the bin size should be atleast thrice the kernel support size to get good performance.