On Mon Mar 18 06:39:16 2024 +0000, Jinoh Kang wrote:
@rbernon has pointed out that the capacity is always derived from the mapping size, which means that we can assume that the capacity is the greatest that can fill the given mapping. Rewriting above in terms of old capacity so that truncated capacity (i.e. does not fill the mapping) is ruled out, the inequality (for non-growth) becomes:
k > \tfrac12\cdot\mathsf{OldCapacity} + \mathsf{PageSize}/\mathsf{EltSize}In general, for growth rate (1 + *g*), the equation is:
k > g\cdot\mathsf{OldCapacity} + \mathsf{PageSize}/\mathsf{EltSize}In the particular case of "*g* = ½" (in this MR), "capacity ≥ 2" is enough to guarantee that the mapping size increases. However, if it's reduced to a more modest growth rate, the minimum bar for capacity increases. In short, the following two conditions are required for non-growth (the problem of interest):
- **The element size is greater than the page size.** This might happen if we end up needing larger chunks of data that
contains e.g. key state array. 2. **The old capacity is less than *g*<sup>-1</sup> (the inverse of the growth rate minus 1).** This might happen if we decide that the current growth rate is too fast and slow it down. For example, if "*g* = 1/32", then just "capacity = 31" satisfies the condition.[^c] Although it might sound unlikely, I wouldn't completely rule out either possibility. I'd argue that it's always a good idea to insert explicit assertions[^1] locally rather than relying on the implicit environment (invariant conditions upheld by surrounding code or distant functions), especially since we'll probably end up putting more things into the shared mapping as new performance bottlenecks are discovered. Assertions also improve clarity IMHO. [^c]: We can of course blame the incorrect initial capacity, but I don't see this kind of mistake as outlandish. [^1]: One `assert()` statement in this case
As a concrete example, if the growth expression becomes `* 33 / 32` but initial capacity = 31, we won't be able to notice it because of page-unit roundup. After a while, someone enlarges the object size and/or make changes to allocation strategy, which will be blamed for regression until the initial faulty capacity is revealed as the root cause.