Skippable Context: I have a simulation loop (using fixed update but variable rendering pattern), which instantiates entities of classes that are generated on the fly according to user-input and/or file configurations from a database of millions of components (of the container state modifying pattern).
I have implemented a system that automagically...deduces(some kind of logic cell/math I don't know the name to) and applies needed components whenever the user-input/config ignores the fact that one of their options requires additional components.
How so? Many of the components are complex formulae or fuzzy logic (gates?) or other complex scientific reasoning, coded in a way that can operate my simulation's structure, its objects, its environment, thus sometimes one component relies on the other and I need the 'deduction algorithm/system' to be able to pass that reliance to the class constructor.
I've used maximum granularity in the way I decided to store these 'knowledge pieces' because I really can't waste any memory given the sizes and compute intensity of the simulations and number of individual instances but now I'm running the issue of a single instance needing thousands, sometimes tens of thousands of components, and I need the instance's "creation-map" both saved and still bound as a private member so I can: 1st - know where my deductions are leading the constructor of instances and maybe be able to use memoization to reduce build times; 2nd - implement injection of changes to a live instance during the simulation¹.
What I think I need: I need a possibly infinite or at least very long bit-mask, so I can iterate the creation faster and let the final component-tree of my dynamically-constructed objects logged for future use.
Possible approaches, which I have no idea will work: 1st - Manually and sequentially store values for the bit flags in each RAM cell, using the RAM wafer as my bit-mask. 2nd - Breakdown the map into smaller bit-masks of known size(hard because the final number of components is unknown until the creation is done and decoupling the deduction is something which might even be impossible without refactoring the entire system). 3rd - Figure out a way to make an infinite bit-mask, or use some library that has implemented a really long integer(5.12e+11 or bigger).
My code is written in C++, my rendering and compute kernels are Vulkan.
My objective question: How do I implement an arbitrarily long bit-mask that is memory and compute efficient?
If I am allowed a bonus question, what is the most efficient way to implement such a bit-mask, assuming I have no architecture (software and hardware) constraints?
¹ I cannot browse an object's tree during the simulation and I also cannot afford to pause the simulation and wait for the browsing to be done before injecting the modification, I need to know and be able to make an arbitrary change on an arbitrary frame of simulation in both a pre-scheduled manner and a real-time manner.
what is the most efficient way to implement such a bit-mask
Put std::vector<bool> there and profile. If/when you’ll discover you’re spending significant time working with that vector, read further.
There’s no most efficient way, it all depends on what exactly does your code do with these bits.
One standard approach is keep continuous vector of integers, and treat them as a vector of bits. For example, std::vector<bool> on Windows uses 32-bit values, keeping 32 bools in each one.
However, the API of std::vector is too general. If your vector has majority of 0-s, or majority of 1-s, you’ll be able to implement many operations (get value, find first/next/previous 0/1) much faster than std::vector<bool> does.
Also depending on your access patterns, you may want either smaller or larger elements. If you’ll decide to use large SIMD types i.e. __m128i or __m256i don’t forget about alignment for them.