On Thu, 4 Jul 2024 11:34:23 GMT, Johan Sjölen <jsjo...@openjdk.org> wrote:
> Hi, > > Today the GrowableArray has a set index type of `int`, this PR makes it so > that you can set your own index type through a template parameter. > > This opens up for a few new design choices: > > - Do you know that you have a very small array? Use an `uint8_t` for len and > cap, each. > - Do you have a very large one? Use an `uint64_t`. > > The code has opted for `int` being default, as to keep identical semantics > for all existing code and to let users not have to worry about the index if > they don't care. > > One "major" change that I don't want to get lost in the review: I've changed > the mid-point calculation to be overflow insensitive without casting. > > > > // Old > mid = ((max + min) / 2); > // New > mid = min + ((max - min) / 2); > > Some semi-rigorous thinking: > min \in [0, len) > max \in [0, len) > min <= max > max - min / 2 \in [0, len/2) > Maximizing min and max => len + 0 > Maximizing max, minimizing min => len/2 > Minimizing max, maximizing min => max = min => min > > > // Proof that they're identical when m, h, l \in N > (1) m = l + (h - l) / 2 <=> > 2m = 2l + h - l = h + l > > (2) m = (h + l) / 2 <=> > 2m = h + l > (1) = (2) > QED This pull request has been closed without being integrated. ------------- PR: https://git.openjdk.org/jdk/pull/20031
