Roadmap for neighborhood search implementations

[efaulhaber]

• [x] Neighborhood search storing explicit neighbor lists for a >2x speedup of simulations with static NHS (TLSPH). #9
• [ ] Contiguous memory layout for neighbor lists for more performance in large simulations and for GPU compatibility. #10
• [ ] GPU-compatible version of the above (if it's not GPU-compatible yet).
• [ ] "Full grid" backend for GridNeighborhoodSearch, storing a list of particles for each cell of a rectangular domain. This gives us more control over the backend than using a Dict. We can choose to store cell lists as Vector of Vectors or use a contiguous memory layout (see below). #25
• [ ] Contiguous memory layout for cell lists for more performance in large simulations and for GPU compatibility. Prototype in https://github.com/trixi-framework/TrixiParticles.jl/pull/483. Data type implemented in #34.
• [ ] GPU-compatible update for full grid GridNeighborhoodSearch with contiguous memory. Prototype in https://github.com/trixi-framework/TrixiParticles.jl/pull/483.
• [ ] Implement spatial hashing backend (full grid with hashing) for sparsely filled domains.
• [ ] Implement compact cell lists for full grid and spatial hashing. For full grid and spatial hashing, often only a small percentage of all available cell lists is used, the rest is empty, wasting memory and causing cache misses. A solution for this is to only have one scalar entry for each cell, which, if the cell is not empty, points to the index of the cell list in a much smaller collection of used cell lists.
• [ ] Implement a sorting cell lists, which sorts a vector of particle indices by cell index, so that we only have to store a single number (the first index of the particle vector belonging to that cell) per cell.
• [ ] Distributed-memory neighborhood search.

[sloede]

What about

• [ ] Octree-based neighborhood search (as preparation for distributed memory simulations)

? Is this something for the agenda as well? It could also be independent of the technique (i.e., not necessarily octree-based).

[efaulhaber]

Octrees are only needed when we don't have a fixed search radius anymore. They might perform similarly, but I don't have any plans to implement them for now.

I'll add distributed memory NHS to the list.