HashMap.putAll can cause redundant space waste
Xeno Amess
xenoamess at gmail.com
Fri Feb 4 13:40:15 UTC 2022
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