Add documentation for python package!

[mushroomfire]

I wanted to find a library that was fast for neighbourhood search and supported periodic boundary conditions and stumbled across this library. I gave it a quick try and I found it really powerful, but I'm not sure if the library is still being updated. I have two questions.

1. update the documentation of the python library, otherwise it will be difficult to use and promote it back.
2. I found that there is no parallelisation when building the Tree, which led to a speed similar to that of the KDTree in scipy when I tested it. The code is as follows.

   
   import pyfnntw
   from scipy.spatial import KDTree
   import numpy as np

N = 500000 pos = np.random.random((N, 3))

kdt = KDTree(pos, leafsize=32, boxsize=[1.0, 1.0, 1.0]) _, ind = kdt.query(pos, 5, workers=-1)

rkdt = pyfnntw.Tree(pos, 32, np.array([1.0, 1.0, 1.0])) _, rind = rkdt.query(pos, 5)

By the way, many thanks to the author for developing this library.

[cavemanloverboy]

Thank you for the kind words. This library is still under active development. I just made it 20-30% faster last week, and added support for single precision, although it hasn't reached the python package yet. I have plans to update the python package this week and while doing so I will add docs.

To take advantage of the parallelism, you need to specify par_split_level (optional third argument). I will say that the parallelism is only beneficial in larger trees (>=100,000 items), and I have found that only 2 or 4 threads are helpful (unless the tree is very big). If you use it in smaller trees it will slow you down.

[mushroomfire]

I have tried par_split_level parameter and I found it has a certain improvement on building tree using 2 or 4 threads. More threads are not helpful even my tree includes more than 1,000,000 items. The test code is as below:

import pyfnntw
import numpy as np
from time import time
from scipy.spatial import KDTree

N = 10000000
pos = np.random.random((N, 3))
start = time()
kdt = KDTree(pos, leafsize=32, boxsize=[1, 1, 1])  
end = time()
print(f"build kdtree Time cost: {end-start} s.")
start = time()
_, ind = kdt.query(pos, 5, workers=-1)
end = time()
print(f"query kdtree Time cost: {end-start} s.")
print("index is:")
print(ind[:2])

start = time()
rkdt = pyfnntw.Tree(
    pos, 32, np.array([1.0, 1.0, 1.0]), par_split_level=4
)  
end = time()
print(f"build rkdtree Time cost: {end-start} s.")
start = time()
_, ind = rkdt.query(pos, 5)
end = time()
print(f"query rkdtree Time cost: {end-start} s.")
print("index is:")
print(ind[:2])

The output is:

build kdtree Time cost: 13.246489763259888 s.
query kdtree Time cost: 6.715745449066162 s.
index is:
[[      0 1767474 6692552 8329806 5636645]
 [      1 2019263 5924125 2235534 1263112]]
Parallelism activated: 40 threads
build rkdtree Time cost: 11.521869897842407 s.
query rkdtree Time cost: 6.766228199005127 s.
index is:
[[      0 1767474 6692552 8329806 5636645]
 [      1 2019263 5924125 2235534 1263112]]

pyfnntw is two seconds faster than KDtree in scipy.

I am not familier with Rust so I am not sure whether you can optimize the Algorithms to make it very fast to build and query tree at the case of low dimensional data, such as a points of (N, 3). I need a library faster than kDtree in scipy to find nearest neighbor in particle simulation and I think pyfnntw has great potential.

Finally, as a python user, I would like to suggest pyfnntw can distribute the pre-compiled pypi wheel when pyfnntw is stable. It helps user to install pyfnntw without the reqirement of compiler of the Rust.

[cavemanloverboy]

I have tried par_split_level parameter and I found it has a certain improvement on building tree using 2 or 4 threads. More threads are not helpful even my tree includes more than 1,000,000 items. The test code is as below:

import pyfnntw

import numpy as np

from time import time

from scipy.spatial import KDTree

N = 10000000

pos = np.random.random((N, 3))

start = time()

kdt = KDTree(pos, leafsize=32, boxsize=[1, 1, 1])  

end = time()

print(f"build kdtree Time cost: {end-start} s.")

start = time()

_, ind = kdt.query(pos, 5, workers=-1)

end = time()

print(f"query kdtree Time cost: {end-start} s.")

print("index is:")

print(ind[:2])

start = time()

rkdt = pyfnntw.Tree(

    pos, 32, np.array([1.0, 1.0, 1.0]), par_split_level=4

)  

end = time()

print(f"build rkdtree Time cost: {end-start} s.")

start = time()

_, ind = rkdt.query(pos, 5)

end = time()

print(f"query rkdtree Time cost: {end-start} s.")

print("index is:")

print(ind[:2])

The output is:

build kdtree Time cost: 13.246489763259888 s.

query kdtree Time cost: 6.715745449066162 s.

index is:

[[      0 1767474 6692552 8329806 5636645]

 [      1 2019263 5924125 2235534 1263112]]

Parallelism activated: 40 threads

build rkdtree Time cost: 11.521869897842407 s.

query rkdtree Time cost: 6.766228199005127 s.

index is:

[[      0 1767474 6692552 8329806 5636645]

 [      1 2019263 5924125 2235534 1263112]]

pyfnntw is two seconds faster than KDtree in scipy.

I am not familier with Rust so I am not sure whether you can optimize the Algorithms to make it very fast to build and query tree at the case of low dimensional data, such as a points of (N, 3). I need a library faster than kDtree in scipy to find nearest neighbor in particle simulation and I think pyfnntw has great potential.

Finally, as a python user, I would like to suggest pyfnntw can distribute the pre-compiled pypi wheel when pyfnntw is stable. It helps user to install pyfnntw without the reqirement of compiler of the Rust.

I recently found a bug with the parallelization strategy. It wasn't doing what I thought I was. Was not a correctness issue. I fixed it. 4.0 will have more documentation and should be out this week.

[mushroomfire]

I have tried _par_splitlevel parameter and I found it has a certain improvement on building tree using 2 or 4 threads. More threads are not helpful even my tree includes more than 1,000,000 items. The test code is as below:

import pyfnntw

import numpy as np

from time import time

from scipy.spatial import KDTree

N = 10000000

pos = np.random.random((N, 3))

start = time()

kdt = KDTree(pos, leafsize=32, boxsize=[1, 1, 1])  

end = time()

print(f"build kdtree Time cost: {end-start} s.")

start = time()

_, ind = kdt.query(pos, 5, workers=-1)

end = time()

print(f"query kdtree Time cost: {end-start} s.")

print("index is:")

print(ind[:2])

start = time()

rkdt = pyfnntw.Tree(

    pos, 32, np.array([1.0, 1.0, 1.0]), par_split_level=4

)  

end = time()

print(f"build rkdtree Time cost: {end-start} s.")

start = time()

_, ind = rkdt.query(pos, 5)

end = time()

print(f"query rkdtree Time cost: {end-start} s.")

print("index is:")

print(ind[:2])

The output is:

build kdtree Time cost: 13.246489763259888 s.

query kdtree Time cost: 6.715745449066162 s.

index is:

[[      0 1767474 6692552 8329806 5636645]

 [      1 2019263 5924125 2235534 1263112]]

Parallelism activated: 40 threads

build rkdtree Time cost: 11.521869897842407 s.

query rkdtree Time cost: 6.766228199005127 s.

index is:

[[      0 1767474 6692552 8329806 5636645]

 [      1 2019263 5924125 2235534 1263112]]

pyfnntw is two seconds faster than KDtree in scipy. I am not familier with Rust so I am not sure whether you can optimize the Algorithms to make it very fast to build and query tree at the case of low dimensional data, such as a points of (N, 3). I need a library faster than kDtree in scipy to find nearest neighbor in particle simulation and I think pyfnntw has great potential. Finally, as a python user, I would like to suggest pyfnntw can distribute the pre-compiled pypi wheel when pyfnntw is stable. It helps user to install pyfnntw without the reqirement of compiler of the Rust.

I recently found a bug with the parallelization strategy. It wasn't doing what I thought I was. Was not a correctness issue. I fixed it. 4.0 will have more documentation and should be out this week.

That would be great, looking forward to new version!