HashMap.putAll can cause redundant space waste
Xeno Amess
xenoamess at gmail.com
Fri Feb 4 18:48:05 UTC 2022
wait, things get interesting now.
We do have such a test named ConstantDirectoryOptimalCapacity to make sure
this does not happen, but my tests still fill under the idea debugger.
Is there any specialist for help? I would dig in but it is a little
complicated.
[image: image.png]
Xeno Amess <xenoamess at gmail.com> 于2022年2月5日周六 02:39写道：
> Sorry for my mistake.
> After a more throughout dig in, this thing has already fixed several years
> ago, at year 2015.
> Issue close.
>
> Xeno Amess <xenoamess at gmail.com> 于2022年2月4日周五 21:40写道：
>
>> Besides, is it worthy to develop a public float Math.ceil(float) function?
>>
>> Xeno Amess <xenoamess at gmail.com> 于2022年2月4日周五 21:39写道：
>>
>>> patch applied.
>>>
>>> Index: src/java.base/share/classes/java/lang/Module.java
>>> IDEA additional info:
>>> Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
>>> <+>UTF-8
>>> ===================================================================
>>> diff --git a/src/java.base/share/classes/java/lang/Module.java
>>> b/src/java.base/share/classes/java/lang/Module.java
>>> --- a/src/java.base/share/classes/java/lang/Module.java (revision
>>> 3d926dd66ef6551e91a4ebbbc59dcff58f5ede5a)
>>> +++ b/src/java.base/share/classes/java/lang/Module.java (revision
>>> deeba25d15398fea8bc971ac915e348878b2c27a)
>>> @@ -1133,7 +1133,7 @@
>>> boolean isBootLayer = (ModuleLayer.boot() == null);
>>>
>>> int numModules = cf.modules().size();
>>> - int cap = (int)(numModules / 0.75f + 1.0f);
>>> + int cap = (int)Math.ceil(numModules / 0.75f);
>>> Map<String, Module> nameToModule = new HashMap<>(cap);
>>>
>>> // to avoid repeated lookups and reduce iteration overhead, we
>>> create
>>> Index: src/java.base/share/classes/java/util/HashMap.java
>>> IDEA additional info:
>>> Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
>>> <+>UTF-8
>>> ===================================================================
>>> diff --git a/src/java.base/share/classes/java/util/HashMap.java
>>> b/src/java.base/share/classes/java/util/HashMap.java
>>> --- a/src/java.base/share/classes/java/util/HashMap.java (revision
>>> 3d926dd66ef6551e91a4ebbbc59dcff58f5ede5a)
>>> +++ b/src/java.base/share/classes/java/util/HashMap.java (revision
>>> deeba25d15398fea8bc971ac915e348878b2c27a)
>>> @@ -495,9 +495,9 @@
>>> int s = m.size();
>>> if (s > 0) {
>>> if (table == null) { // pre-size
>>> - float ft = ((float)s / loadFactor) + 1.0F;
>>> - int t = ((ft < (float)MAXIMUM_CAPACITY) ?
>>> - (int)ft : MAXIMUM_CAPACITY);
>>> + double dt = Math.ceil(s / loadFactor);
>>> + int t = ((dt < (double)MAXIMUM_CAPACITY) ?
>>> + (int)dt : MAXIMUM_CAPACITY);
>>> if (t > threshold)
>>> threshold = tableSizeFor(t);
>>> } else {
>>> @@ -1527,12 +1527,12 @@
>>> } else if (mappings == 0) {
>>> // use defaults
>>> } else if (mappings > 0) {
>>> - float fc = (float)mappings / lf + 1.0f;
>>> - int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
>>> + double dc = Math.ceil(mappings / lf);
>>> + int cap = ((dc < DEFAULT_INITIAL_CAPACITY) ?
>>> DEFAULT_INITIAL_CAPACITY :
>>> - (fc >= MAXIMUM_CAPACITY) ?
>>> + (dc >= MAXIMUM_CAPACITY) ?
>>> MAXIMUM_CAPACITY :
>>> - tableSizeFor((int)fc));
>>> + tableSizeFor((int)dc));
>>> float ft = (float)cap * lf;
>>> threshold = ((cap < MAXIMUM_CAPACITY && ft <
>>> MAXIMUM_CAPACITY) ?
>>> (int)ft : Integer.MAX_VALUE);
>>> Index: src/java.base/share/classes/java/util/WeakHashMap.java
>>> IDEA additional info:
>>> Subsystem: com.intellij.openapi.diff.impl.patch.CharsetEP
>>> <+>UTF-8
>>> ===================================================================
>>> diff --git a/src/java.base/share/classes/java/util/WeakHashMap.java
>>> b/src/java.base/share/classes/java/util/WeakHashMap.java
>>> --- a/src/java.base/share/classes/java/util/WeakHashMap.java (revision
>>> 3d926dd66ef6551e91a4ebbbc59dcff58f5ede5a)
>>> +++ b/src/java.base/share/classes/java/util/WeakHashMap.java (revision
>>> deeba25d15398fea8bc971ac915e348878b2c27a)
>>> @@ -251,7 +251,7 @@
>>> * @since 1.3
>>> */
>>> public WeakHashMap(Map<? extends K, ? extends V> m) {
>>> - this(Math.max((int) ((float)m.size() / DEFAULT_LOAD_FACTOR +
>>> 1.0F),
>>> + this(Math.max((int) Math.ceil(m.size() / DEFAULT_LOAD_FACTOR),
>>> DEFAULT_INITIAL_CAPACITY),
>>> DEFAULT_LOAD_FACTOR);
>>> putAll(m);
>>>
>>> Xeno Amess <xenoamess at gmail.com> 于2022年2月4日周五 18:45写道：
>>>
>>>> also find some other places have same problem.
>>>> If some of your already-in people aggree, I would create a pr, but
>>>> according to the rules seems I should wait for now.
>>>>
>>>> Xeno Amess <xenoamess at gmail.com> 于2022年2月4日周五 18:42写道：
>>>>
>>>>> import java.lang.reflect.Array;
>>>>> import java.lang.reflect.Field;
>>>>> import java.util.HashMap;
>>>>> import java.util.Map;
>>>>>
>>>>> public class TestMap {
>>>>>
>>>>> public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
>>>>> HashMap<Object, Object> a = new HashMap<>();
>>>>> fill12(a);
>>>>> HashMap<Object, Object> b = new HashMap<>(12);
>>>>> fill12(b);
>>>>> HashMap<Object, Object> c = new HashMap<>(a);
>>>>> HashMap<Object, Object> d = new HashMap<>();
>>>>> d.putAll(a);
>>>>> System.out.println("a : " + getArrayLength(a));
>>>>> System.out.println("b : " + getArrayLength(b));
>>>>> System.out.println("c : " + getArrayLength(c));
>>>>> System.out.println("d : " + getArrayLength(d));
>>>>> }
>>>>>
>>>>> public static void fill12(Map<Object, Object> map) {
>>>>> for (int i = 0; i < 12; i++) {
>>>>> map.put(i, i);
>>>>> }
>>>>> }
>>>>>
>>>>> public static int getArrayLength(Map<Object, Object> map) throws NoSuchFieldException, IllegalAccessException {
>>>>> Field field = HashMap.class.getDeclaredField("table");
>>>>> field.setAccessible(true);
>>>>> Object table = field.get(map);
>>>>> return Array.getLength(table);
>>>>> }
>>>>>
>>>>> }
>>>>>
>>>>> run this and we get the output:
>>>>>
>>>>> a : 16
>>>>> b : 16
>>>>> c : 32
>>>>> d : 32
>>>>>
>>>>> So I go see the codes.
>>>>>
>>>>> /**
>>>>> * Implements Map.putAll and Map constructor.
>>>>> *
>>>>> * @param m the map
>>>>> * @param evict false when initially constructing this map, else
>>>>> * true (relayed to method afterNodeInsertion).
>>>>> */
>>>>> final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
>>>>> int s = m.size();
>>>>> if (s > 0) {
>>>>> if (table == null) { // pre-size
>>>>> float ft = ((float)s / loadFactor) + 1.0F;
>>>>> int t = ((ft < (float)MAXIMUM_CAPACITY) ?
>>>>> (int)ft : MAXIMUM_CAPACITY);
>>>>> if (t > threshold)
>>>>> threshold = tableSizeFor(t);
>>>>> } else {
>>>>> // Because of linked-list bucket constraints, we cannot
>>>>> // expand all at once, but can reduce total resize
>>>>> // effort by repeated doubling now vs later
>>>>> while (s > threshold && table.length < MAXIMUM_CAPACITY)
>>>>> resize();
>>>>> }
>>>>>
>>>>> for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
>>>>> K key = e.getKey();
>>>>> V value = e.getValue();
>>>>> putVal(hash(key), key, value, false, evict);
>>>>> }
>>>>> }
>>>>> }
>>>>>
>>>>> yep I do think *((float)s / loadFactor) + 1.0F* here is wrong.
>>>>>
>>>>> It should be *Math.ceil((float)s / loadFactor)*
>>>>>
>>>>> So I wish to generate a pull request.
>>>>>
>>>>> Anyone interested?
>>>>>
>>>>>
More information about the core-libs-dev
mailing list