RFR 8200696 : Optimal initial capacity of java.lang.Class.enumConstantDirectory

[David Holmes]

On 4/04/2018 1:06 PM, Ivan Gerasimov wrote:
> Hi David!
> 
> 
> On 4/3/18 6:41 PM, David Holmes wrote:
>> Hi Ivan,
>>
>> On 4/04/2018 10:01 AM, Ivan Gerasimov wrote:
>>> Hi David!
>>>
>>>
>>> On 4/3/18 4:49 PM, David Holmes wrote:
>>>> Hi Ivan,
>>>>
>>>> On 4/04/2018 9:22 AM, Ivan Gerasimov wrote:
>>>>> Hello!
>>>>>
>>>>> Yet another occurrence of not-optimally pre-sized HashMap.
>>>>>
>>>>> When java.lang.Class.enumConstantDirectory is created, the initial 
>>>>> capacity is set to be (2 * universe.length), which is more than 
>>>>> necessary in some cases.
>>>>>
>>>>> Choosing the capacity optimally will allow us to save a few bytes 
>>>>> with some enum classes.
>>>>
>>>> How are you defining optimal? 
>>> By optimal I meant the minimum value that will not make the internal 
>>> storage to be reallocated during insertion.
>>>
>>> Here's a quotation from the documentation [1]:
>>> "If the initial capacity is greater than the maximum number of 
>>> entries divided by the load factor, no rehash operations will ever 
>>> occur."
>>>
>>> Given the default load factor 0.75, the formula (expectedSize / 0.75 
>>> + 1) gives us the optimal initial capacity.
>>
>> Isn't it simpler to just do:
>>
>> new HashMap(universe.length, 1.0f);
>>
>> and change the load factor? Otherwise you have to allow for an extra 
>> 25% of space, and that is before it expands to be a power of 2 IIUC.
>>
> Yes, it would be simpler of course.
> However, the chance of a collision will also increase then.
> Especially in cases when the number of entries is close (but not greater 
> than) to a power of 2.
> 
> Not sure if it matters in this particular case, as the number of enum 
> values is likely to be relatively small, so the lookup will be fast anyway.
> But I thought it would be better to keep the default load factor and 
> just set the initial capacity to the optimal value: minimum while not 
> causing reallocations during insertion.

Okay. Thanks for explaining. The code could do with a comment explaining 
this, and the bug report certainly should explain it.

Thanks,
David

> With kind regards,
> Ivan
> 
>> David
>>
>>> The testlibrary class testlibrary/OptimalCapacity.java is used to 
>>> make sure that the chosen initial capacity is neither too low (so 
>>> that no reallocations happen) nor too high (no memory is wasted).
>>>
>>> With kind regards,
>>> Ivan
>>>
>>> [1] https://docs.oracle.com/javase/10/docs/api/java/util/HashMap.html
>>>
>>>
>>>> The bug report only gives one example where the current calculation 
>>>> produces a too large value. If the HashMap itself rounds up the 
>>>> initial capacity to a power of 2, how much extra space do we need 
>>>> compared to universe.length? Do we just need to pass 
>>>> (universe.length+1) to get the smallest power of 2 greater than 
>>>> universe.length?
>>>>
>>>> Thanks,
>>>> David
>>>>
>>>>> Would you please help review this trivial fix?
>>>>>
>>>>> BUGURL: https://bugs.openjdk.java.net/browse/JDK-8200696
>>>>> WEBREV: http://cr.openjdk.java.net/~igerasim/8200696/00/webrev/
>>>>>
>>>>
>>>
>>
>