Roadmap for neighborhood search implementations

[efaulhaber]

• Neighborhood search storing explicit neighbor lists for a >2x speedup of simulations with static NHS (TLSPH). Implement neighborhood search based on static neighbor lists #9
• Contiguous memory layout for neighbor lists for more performance in large simulations and for GPU compatibility. Use contiguous memory layout for neighbor lists #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). Add "full grid" cell list with a separate list for each cell of a rectangular domain #25
• Contiguous memory layout for cell lists for more performance in large simulations and for GPU compatibility. Prototype in [Proof of Concept] GPU-compatible, memory-hungry NHS with scalable update TrixiParticles.jl#483. Data type implemented in Implement dynamic vector of vectors data structure #34.
• GPU-compatible update for full grid GridNeighborhoodSearch with contiguous memory. Prototype in [Proof of Concept] GPU-compatible, memory-hungry NHS with scalable update TrixiParticles.jl#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.