RFR: 8335701: Make GrowableArray templated by an Index [v2]

[Johan Sjölen]

On Thu, 4 Jul 2024 13:35:36 GMT, Johan Sjölen <jsjolen at 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
>
> Johan Sjölen has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Attempt at fixing GA VMStruct

Always fun to grapple with vmStructs, moving this back to draft.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/20031#issuecomment-2209022728