trixi-framework / PointNeighbors.jl

PointNeighbors.jl: Neighborhood search with fixed search radius in Julia
https://trixi-framework.github.io/PointNeighbors.jl/
MIT License
10 stars 1 forks source link

Store coordinates together with the points in a cell list #52

Open efaulhaber opened 4 days ago

efaulhaber commented 4 days ago

I realized that the FullGridCellList (at least with the Vector{Vector} backend) is algorithmically almost identical to the method of CellListMap.jl. But CellListMap.jl is slightly faster on a single thread or on multiple threads when modified to use Polyester.jl for threading.

The main difference is that @lmiq is storing the coordinates together with the point indices in the cell lists. This avoids unordered access of the big coordinate array to get the coordinates of the neighbor. I implemented a similar data structure and made it configurable, as our goal is to have a playground to try out methods.

We now get very similar performance to CellListMap.jl. Here is a plot showing the speedup against CellListMap.jl on a single thread (Threadripper 3990X):

grafik

On 128 threads, we're still slightly slower:

grafik

Here is a plot showing the speedup from using PointWithCoordinates on different architectures.

grafik

We see the largest speedups (14-15% for a WCSPH interaction on 128 threads!) on the CPU. The Nvidia H100 is also benefiting from this data structure. The RTX 3090 is only getting 0.5-1% faster. For some reason, the AMD Instinct MI210 doesn't like this data structure at all and is performing 2x slower.

svchb commented 4 days ago

Great work! But the conclusion is very unsatisfactory as that basically means we would need both...