Expand description
§Memory Reallocation
Looking at the input and the reallocation rules, when there is at most one bank with 15 blocks, it is easy to see that no other bank will exceed 15 after reallocation. However, some input files have early scenarios where there are a couple of banks with 15, which can result in the next round or two needing to process 16 or even 17 blocks. The overflow issue only occurs early; in the long run, the banks settle into a pattern where overflow does not interfere.
With that in mind, it is possible to design a compact layout that stores each bank in one nibble of a u64 in the common case, but with manual iterations managing the overflow as needed.
For all but the few manual overflow cases, it is very fast to find the highest nibble
using bitwise logic. To detect the cycle a FastMap stores each previously seen
memory layout along with the cycle that it first appeared.
Constants§
- REMOVE 🔒
- Reallocate a bank and set to zero by rotating this mask the correct number of bits.
- SPREAD 🔒
- The highest number of banks when overflow is not a concern is 15, so each bank will add at most 1 to each of the banks that come after it.
Functions§
Type Aliases§
- Input 🔒