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 | ||
|---|---|---|---|
Trunk | 72.7856 | 73.181 | 73.7959 |
ummap complete version | 81.3252 | 82.298 | 80.724 |
commit 1927 | 71.5583 | 71.572 | 71.7695 |
| USER/Kit/DrumCodes/Drum, endTime = 0.3 | ||
|---|---|---|---|
Trunk | 99.8897 | 98.4237 | 99.8312 |
ummap complete version | 177.437 | - | - |
commit 1927 | 104.434 | 104.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.