Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Wed, 2 Mar 2022 01:44:24 GMT, Stuart Marks wrote: > I'm starting to look at this again. First, a quick note -- I don't think > there should be any IdentityHashMap changes here. That uses a completely > different internal structure and allocation policy, and it's kind of a > distraction from the main point of this change. (As the preceding chain of > comments illustrates.) > > There is a question of whether IdentityHashMap ought to "allow for some > growth" when copying a map, but it's hard to see how much of a problem this > really is. I'd suggest focusing on getting this change done, and then (if you > still have energy) to try to eradicate the `(int) (expected / 0.75) + 1` > idiom that's sprinkled around the JDK. OK, will split this part from this pr. - PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 19:50:01 GMT, liach wrote: >> @liach Hi. please have a look at the latest commit. >> do you think it be better now? > > Oops, didn't notice there was this helpful `init` method. Does look much more > straightforward now. I'm starting to look at this again. First, a quick note -- I don't think there should be any IdentityHashMap changes here. That uses a completely different internal structure and allocation policy, and it's kind of a distraction from the main point of this change. (As the preceding chain of comments illustrates.) There is a question of whether IdentityHashMap ought to "allow for some growth" when copying a map, but it's hard to see how much of a problem this really is. I'd suggest focusing on getting this change done, and then (if you still have energy) to try to eradicate the `(int) (expected / 0.75) + 1` idiom that's sprinkled around the JDK. - PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 19:41:22 GMT, XenoAmess wrote: >> In fact, if we do worry about the performance of adding from maps, calling >> `map.forEach(this::put);` would be a better alternative both in concurrency >> (as the concurrent map itself takes charage) and object allocation-wise (no >> allocation of immutable entry objects), but that belongs to another issue. > > @liach Hi. please have a look at the latest commit. > do you think it be better now? Oops, didn't notice there was this helpful `init` method. Does look much more straightforward now. - PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 19:19:16 GMT, liach wrote: >> Imo you should just remove the `if (expectedSize == 0)` check than using >> this somewhat ugly trick to avoid calling `size()` twice (the second call is >> only used for this relatively useless fast-path, especially for the >> concurrent collections you refer to) > > In fact, if we do worry about the performance of adding from maps, calling > `map.forEach(this::put);` would be a better alternative both in concurrency > (as the concurrent map itself takes charage) and object allocation-wise (no > allocation of immutable entry objects), but that belongs to another issue. @liach Hi. please have a look at the latest commit. do you think it be better now? - PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 19:08:39 GMT, liach wrote: >>> @liach implementations `size()` seems O1, and returns a single int number >>> field, but it actually defers in some Map implementations. >> >> @liach for example, in ConcurrentSkipListMap and ConcurrentHashMap, `size()` >> function is far complicated than reading a field, thus calling it twice >> meaninglessly is not a wise choice. > > Imo you should just remove the `if (expectedSize == 0)` check than using this > somewhat ugly trick to avoid calling `size()` twice (the second call is only > used for this relatively useless fast-path, especially for the concurrent > collections you refer to) In fact, if we do worry about the performance of adding from maps, calling `map.forEach(this::put);` would be a better alternative both in concurrency (as the concurrent map itself takes charage) and object allocation-wise (no allocation of immutable entry objects), but that belongs to another issue. - PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 18:44:09 GMT, XenoAmess wrote:
>> src/java.base/share/classes/java/util/IdentityHashMap.java line 281:
>>
>>> 279: * @throws NullPointerException if the specified map is null
>>> 280: */
>>> 281: private IdentityHashMap(Map map, int
>>> expectedSize) {
>>
>> Why are you writing a new constructor when you can just change the old call
>> to `this(m.size());`?
>
>> @liach implementations `size()` seems O1, and returns a single int number
>> field, but it actually defers in some Map implementations.
>
> @liach for example, in ConcurrentSkipListMap and ConcurrentHashMap, `size()`
> function is far complicated than reading a field, thus calling it twice
> meaninglessly is not a wise choice.
Imo you should just remove the `if (expectedSize == 0)` check than using this
somewhat ugly trick to avoid calling `size()` twice (the second call is only
used for this relatively useless fast-path, especially for the concurrent
collections you refer to)
-
PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 18:08:24 GMT, XenoAmess wrote: > I don't thik it reasonable. or is there eveidence it be? If this map is too dense, there may be a lot of hash collisions, and the lookup performance would decrease because this hashmap is linear probe than red-black tree buckets like the regular hash map is using. This was effectively trading some memory for better performance. You should run benchmarks to see how bad the lookup performance degrades after you saves memory used by the hash table. - PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 18:20:27 GMT, liach wrote:
>> XenoAmess has updated the pull request incrementally with three additional
>> commits since the last revision:
>>
>> - refine test
>> - 1. optimize IdentityHashMap that when calling ::new(Map), do not call
>> map.size() twice but once.
>>2. delete the this((int) ((1 + m.size()) * 1.1)); as it makes the table
>> over-allocate when size = 19.
>> - refine test
>
> src/java.base/share/classes/java/util/IdentityHashMap.java line 281:
>
>> 279: * @throws NullPointerException if the specified map is null
>> 280: */
>> 281: private IdentityHashMap(Map map, int
>> expectedSize) {
>
> Why are you writing a new constructor when you can just change the old call
> to `this(m.size());`?
> @liach implementations `size()` seems O1, and returns a single int number
> field, but it actually defers in some Map implementations.
@liach for example, in ConcurrentSkipListMap and ConcurrentHashMap, `size()`
function is far complicated than reading a field, thus calling it twice
meaninglessly is not a wise choice.
-
PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 18:38:35 GMT, XenoAmess wrote:
>> src/java.base/share/classes/java/util/IdentityHashMap.java line 281:
>>
>>> 279: * @throws NullPointerException if the specified map is null
>>> 280: */
>>> 281: private IdentityHashMap(Map map, int
>>> expectedSize) {
>>
>> Why are you writing a new constructor when you can just change the old call
>> to `this(m.size());`?
>
> @liach because I don't like to call m.size() twice.
> the original codes did so: one call at the `public IdentityHashMap(Map extends K, ? extends V> map)` , and the second inside of `putAll`.
> well in most Map implementations `size()` seems O1, and returns a single int
> number field, but it actually defers in some Map implementations.
> But java grammar do not allow me to make a local variable before calling
> constructor in a constructor.
> In other words, `this()` must be the first line in a constructor.
and adding a private constructor should not cause any trouble I guess?
-
PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 18:20:27 GMT, liach wrote:
>> XenoAmess has updated the pull request incrementally with three additional
>> commits since the last revision:
>>
>> - refine test
>> - 1. optimize IdentityHashMap that when calling ::new(Map), do not call
>> map.size() twice but once.
>>2. delete the this((int) ((1 + m.size()) * 1.1)); as it makes the table
>> over-allocate when size = 19.
>> - refine test
>
> src/java.base/share/classes/java/util/IdentityHashMap.java line 281:
>
>> 279: * @throws NullPointerException if the specified map is null
>> 280: */
>> 281: private IdentityHashMap(Map map, int
>> expectedSize) {
>
> Why are you writing a new constructor when you can just change the old call
> to `this(m.size());`?
@liach because I don't like to call m.size() twice.
the original codes did so: one call at the `public IdentityHashMap(Map map)` , and the second inside of `putAll`.
well in most Map implementations `size()` seems O1, and returns a single int
number field, but it actually defers in some Map implementations.
But java grammar do not allow me to make a local variable before calling
constructor in a constructor.
In other words, `this()` must be the first line in a constructor.
-
PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 18:08:37 GMT, XenoAmess wrote:
>> 8281631: HashMap copy constructor and putAll can over-allocate table
>
> XenoAmess has updated the pull request incrementally with three additional
> commits since the last revision:
>
> - refine test
> - 1. optimize IdentityHashMap that when calling ::new(Map), do not call
> map.size() twice but once.
>2. delete the this((int) ((1 + m.size()) * 1.1)); as it makes the table
> over-allocate when size = 19.
> - refine test
src/java.base/share/classes/java/util/IdentityHashMap.java line 281:
> 279: * @throws NullPointerException if the specified map is null
> 280: */
> 281: private IdentityHashMap(Map map, int
> expectedSize) {
Why are you writing a new constructor when you can just change the old call to
`this(m.size());`?
-
PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 18:03:07 GMT, XenoAmess wrote:
>> XenoAmess has updated the pull request incrementally with three additional
>> commits since the last revision:
>>
>> - refine test
>> - 1. optimize IdentityHashMap that when calling ::new(Map), do not call
>> map.size() twice but once.
>>2. delete the this((int) ((1 + m.size()) * 1.1)); as it makes the table
>> over-allocate when size = 19.
>> - refine test
>
> src/java.base/share/classes/java/util/IdentityHashMap.java line 270:
>
>> 268: */
>> 269: public IdentityHashMap(Map m) {
>> 270: this(m, m.size());
>
> I actually do not know if this change shall be in this pr, or in a new issue.
> But the original codes can cause IdentityHashMap to over-allocate at size ==
> 19.
> @stuart-marks what do you think about this?
I checked this `(int) ((1 + m.size()) * 1.1)`. It is there when the codes
original created there at 2007.
I don't thik it reasonable. or is there eveidence it be?
-
PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
On Sun, 20 Feb 2022 18:04:50 GMT, XenoAmess wrote:
>> 8281631: HashMap copy constructor and putAll can over-allocate table
>
> XenoAmess has updated the pull request incrementally with three additional
> commits since the last revision:
>
> - refine test
> - 1. optimize IdentityHashMap that when calling ::new(Map), do not call
> map.size() twice but once.
>2. delete the this((int) ((1 + m.size()) * 1.1)); as it makes the table
> over-allocate when size = 19.
> - refine test
src/java.base/share/classes/java/util/IdentityHashMap.java line 270:
> 268: */
> 269: public IdentityHashMap(Map m) {
> 270: this(m, m.size());
I actually do not know if this change shall be in this pr, or in a new issue.
But the original codes can cause IdentityHashMap to over-allocate at size == 19.
@stuart-marks what do you think about this?
-
PR: https://git.openjdk.java.net/jdk/pull/7431
Re: RFR: 8281631: HashMap copy constructor and putAll can over-allocate table [v21]
> 8281631: HashMap copy constructor and putAll can over-allocate table XenoAmess has updated the pull request incrementally with three additional commits since the last revision: - refine test - 1. optimize IdentityHashMap that when calling ::new(Map), do not call map.size() twice but once. 2. delete the this((int) ((1 + m.size()) * 1.1)); as it makes the table over-allocate when size = 19. - refine test - Changes: - all: https://git.openjdk.java.net/jdk/pull/7431/files - new: https://git.openjdk.java.net/jdk/pull/7431/files/182c22d7..6d0ab0ef Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=7431=20 - incr: https://webrevs.openjdk.java.net/?repo=jdk=7431=19-20 Stats: 55 lines in 2 files changed: 37 ins; 3 del; 15 mod Patch: https://git.openjdk.java.net/jdk/pull/7431.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/7431/head:pull/7431 PR: https://git.openjdk.java.net/jdk/pull/7431
