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:
| SilbertPeriodicSelfTest, endTime = 1 | |||
|---|---|---|---|
| Trunk | 72.7856 | 73.181 | 73.7959 |
| ummap compelte version | 81.3252 | 82.298 | 80.724 |
| commit 1927 | 71.5583 | 71.572 | 71.7695 |
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.