/
Possible changes to HGrid

Possible changes to HGrid

The idea:

Most time is now spent with finding contacts using the HGrid. We have a custom hash-set implementation with a fixed number of buckets and a linked list of all particles in each bucket. What we want, is a "list" of all coordinates (x,y,z,level) which have a particle and the particles at that coordinate. For this, there exists the datastructure unordered_multimap, which is a hash-map from coordinate to particle with the possibility to have multiple particles at a coordinate. This makes our code much simpler to read, and removes HGrid information from BaseParticle.

Branch HGridHack, important commits:

  • 1918: findContactsWithinTargetCell now takes an object and only looks for contacts with that object
  • 1924: it is not necessary anymore to have bucketIsChecked_ in HGrid (clean version in commit 1927)
  • 1942: the structure with the unordered_multimap is complete

Performance:


Ubuntu 16.04, gcc 5.4.0, Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz processor

 SilbertPeriodicSelfTest, endTime = 1
Trunk72.785673.18173.7959
ummap complete version81.325282.29880.724
commit 192771.558371.572

71.7695

 USER/Kit/DrumCodes/Drum, endTime = 0.3
Trunk99.889798.423799.8312
ummap complete version177.437--
commit 1927104.434104.334

103.57

Conclusion:

The implementation with the unordered_multimap is significantly slower than the current implementation. More than half the time in SilbertPeriodicSelfTest is spent in the equal_range method of unordered_multimap, so I think we can not win much performance there. It might be nice to keep the branch alive to see if future compilers are better optimised for this data-structure. It might be worth it to remove bucketIsChecked_ and change findContactsWithinTargetCell to look only at the object itself instead of all contacts in the cell at the same time, but this should be tested with more applications/compilers/computers.