salilab / imp

The Integrative Modeling Platform
https://integrativemodeling.org
GNU General Public License v3.0
74 stars 30 forks source link

Add "sparse" Keys #1081

Closed benmwebb closed 1 year ago

benmwebb commented 1 year ago

Regular particle attributes like FloatKey are backed by a std::vector indexed by the particle index. This results in a constant-time lookup to get the attribute, but it can use a lot of memory, since the size of the array must be at least that of the largest particle index that uses that attribute. This is OK for attributes that are used all the time and by a large fraction of particles (such as xyz coordinates or hierarchy pointers) but is very inefficient for attributes used by a small fraction of the particles - for example, those used by Provenance decorators.

Proposal: add a similar family of keys with the same interface that are backed by sparse storage, e.g. SparseFloatKey backed by a std::map<ParticleIndex, Float>. The tradeoff is possibly slower O(logN) lookup (and worse memory usage if a large fraction of particles have that attribute).

benmwebb commented 1 year ago

Rather than using std::map, use boost::container::flat_map as this will pack the keys into a std::vector. This should be an efficient use of memory but, more importantly, will allow us to easily pass the contents of that vector to GPU code. The only drawback is that attribute removal will be comparatively slow, but that's a rare operation.