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

[Glavo]

On Fri, 26 Jul 2024 12:44:31 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 four additional commits since the last revision:
> 
>  - Fix
>  - Apparently this(!)
>  - This?
>  - Use COMMA

src/hotspot/share/classfile/classFileParser.hpp line 46:

> 44: class ConstMethod;
> 45: class FieldInfo;
> 46: template<typename E, typename Index>

Suggestion:

template<typename E, typename Index = int>


Is it possible to reduce the changes by providing default parameters?

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

PR Review Comment: https://git.openjdk.org/jdk/pull/20031#discussion_r1666447498