Sort parts

[rbooth200]

This pull request (re-)implements particle sorting and the optimizations that are possible once the particles are sorted. Specifically:

• The particles are sorted during the tree-build, such that each cell knows the range of particles contained within it.
• The inext array has been removed, particles are now indexed directly
• The neighbour manager now loads all of the particles from a cell together at once, rather than by individual id, which should help with memory pre-fetching.

Also: The neighbour manager now computes the fast-multipole terms on the fly to avoid an unecessary reloading of the multipole cells.

The only significant side effect of this implementation is that building the tree now invalidates ghosts lists. This means that ghost lists need to be rebuild on a tree-rebuild. Similarly, ghosts-of-ghosts now point back to the real particle, rather than the ghost-of-real particle, because sorting the ghost tree would otherwise break the link. This means the CopyHydroDataToGhosts has changed slightly, too.

[dhubber]

Sounds like an important list of improvements which will hopefully help the scaling and general performance. I'm guessing you'll want to fix the MPI issues (where Travis failed) before merging?

The only significant side effect of this implementation is that building the tree now invalidates ghosts lists. This means that ghost lists need to be rebuild on a tree-rebuild.

Wasn't this always true? I thought ghosts were only built on tree rebuilding steps or did this change at some point?

[rbooth200]

I think in practice we were always doing it, but I'm not sure if it was a necessity.

[rbooth200]

I do need to fix the issues, I thought I had. Currently all the travis problems do not show up on my laptop...

[rbooth200]

I don't know...

[rbooth200]

Running the code through valgrind has come up with a potential solution: there seems to be an empty tree (perhaps the ghost tree), which was leading to empty cells. I hadn't thought this was possible so wasn't checking. Adding the check during tree stocking seems to fix this.

Hopefully the pull request will now pass.

[rbooth200]

Ok, so this is ready to go. Perhaps you might want to merge it into improve_openmp though, rather than directly into master.

[rbooth200]

Closing this, we have the commits elsewhere (improve_openmp2)