Neighbour list performance

[V-Francois]

Summary
In the current implementation, neighbour lists are updated every time a Displacement action is performed (Swap moves do not do that).
As Displacements are usually the moves that are attempted the most frequently, this neighbour list update must contribute significantly to the overall run time, as suggested by #48.

The neighbour lists implementation could be updated to do the following:

• We set a parameter dr at the beginning of the simulation
• Neighbour lists are built, not using the interaction cutoff as the cutoff, but rather using cutoff + dr
• As long as no particle moves a distance greater than dr/2, we do not need to update the neighbour lists
• During the simulation, we record the position of the particles each time the neighbour lists are updated. Each time a displacement action is performed, we check if the moving particle ends up at a distance greater than dr/2 from its recorded position. If not, we compute the energy without recomputing the neighbour lists. Otherwise, we recompute neighbour lists and reset the recorded positions.

The proposed implementation would yield larger neighbour lists, so iterating over them would be slower. However, their updates become less frequent, which results in a performance gain.
Depending on the system density, acceptance rate, and value of dr, there could exist a regime where this implementation is faster.

Proposed implementation
The perform_action! methods already handle too much neighbour list logic in my opinion, which would be aggravated if we handled the proposed implementation there.

I would therefore first do a refactor PR, that streamlines the neighbour list update API. These lines:

c, c2 = old_new_cell(system, action.i, neighbour_list)
if c != c2
    update_neighbour_list!(action.i, c, c2, neighbour_list)
end

could be be refactored into

update_neighbour_list!(system, action.i, neighbour_list)

where this new method would be straightforward to implement (just a copy/paste of the removed lines). This way, we remove the cell logic from the actions (I think it should be fully within the neighbours.jl file), and remove the number of methods that NeighbourLists must implement (EmptyList will no longer have a old_new_cell method).

In a second PR, we extend CellList and LinkedList to contain a new array: a record of the positions at the last update.
The new API, which passes the system, allows the update! methods to query positions and handle the logic required for the steps described above.

Implementation discussion
It's possible that the proposed implementation would be faster for some systems, but slower for others. If this is the case, we will need a way to switch it off. A clever way to handle the dr=0 case without overhead will be needed.
Finding this solution is only required if we are in the situation described above, which is unknown. So I skip this part for now.

Test set
We will need a set of relevant systems to try this.

Timeline
I do not plan to implement this right now, so there's ample time to discuss.

[romainljsimon]

Yes, I think it is a great idea (it's the Verlet neighbour list I believe).
I'm not sure about one point, do you mean to have an independent VerletList struct, or to build a verlet list from the already existing cell neighbours of CellList or LinkedList?
In the former case, I believe that the implementation will be quite slow for large systems, as the update step loops on all the particules. In the latter, the implementation is faster because the update loops on all the particules of the neighbouring cells.
Also I'm not sure I agree with The proposed implementation would yield larger neighbour list.
If

$$r_c + dr < 2r_c; dr < r_c$$

Shouldn't the verlet neighbour list be smaller ?

[V-Francois]

I forgot it had a specific name…

So basically the proposition would be to implement a new type of NeighbourList, that would be some sort of "CellVerlet".

I only realize now that linked lists don't include any cutoff on $r_{ij}$, so yes a Verlet list would have fewer particles.
For a dense system, where diffusion is low, a Verlet list (built using cell indices to be of O(N) instead of O(N²)) could be way more efficient.

[romainljsimon]

Yep I totally agree !