Re: RFR: JDK-8277520: Implement JDK-8 default methods for IdentityHashMap [v4]

[ExE Boss]

On Mon, 21 Feb 2022 23:36:19 GMT, liach  wrote:

>> Might need a CSR as now `computeIfAbsent` `computeIfPresent` `compute` 
>> `merge` would throw CME if the functions modified the map itself, and there 
>> are corresponding specification changes.
>
> liach has updated the pull request incrementally with two additional commits 
> since the last revision:
> 
>  - merge branch 'identityhashmap-bench' of https://github.com/liachmodded/jdk 
> into identityhashmap-default
>  - fix whitespace

There should probably be something like 
[test/jdk/java/util/Collections/Wrappers.java](https://github.com/openjdk/jdk/blob/master/test/jdk/java/util/Collections/Wrappers.java)
 to check that `IdentityHashMap` overrides all `default` methods from 
`java.util.Map` (with `remove(K, V)` and `replace(K, V, V)` depending on 
).

-

PR: https://git.openjdk.java.net/jdk/pull/6532

Re: RFR: JDK-8277520: Implement JDK-8 default methods for IdentityHashMap [v4]

[ExE Boss]

On Sat, 19 Mar 2022 19:46:19 GMT, ExE Boss  wrote:

>> liach has updated the pull request incrementally with two additional commits 
>> since the last revision:
>> 
>>  - merge branch 'identityhashmap-bench' of 
>> https://github.com/liachmodded/jdk into identityhashmap-default
>>  - fix whitespace
>
> src/java.base/share/classes/java/util/IdentityHashMap.java line 523:
> 
>> 521:  *  mapping was in the map
>> 522:  */
>> 523: private boolean removeMapping(Object key, Object value) {
> 
> Note that `IdentityHashMap.remove(Object, Object)` needs to call this method, 
> as the default implementation calls `Objects.equals(…)`: 
> 

This is being addressed in .

-

PR: https://git.openjdk.java.net/jdk/pull/6532

Re: RFR: JDK-8277520: Implement JDK-8 default methods for IdentityHashMap [v4]

[liach]

On Mon, 21 Feb 2022 23:36:19 GMT, liach  wrote:

>> Might need a CSR as now `computeIfAbsent` `computeIfPresent` `compute` 
>> `merge` would throw CME if the functions modified the map itself, and there 
>> are corresponding specification changes.
>
> liach has updated the pull request incrementally with two additional commits 
> since the last revision:
> 
>  - merge branch 'identityhashmap-bench' of https://github.com/liachmodded/jdk 
> into identityhashmap-default
>  - fix whitespace

Also re stuart: The relative performance of `putIfAbsent` versus `put` has 
always improved with this patch, now being 1.01 times of `put` call time while 
previously it was 1.2 times of it, regardless of jvm instance noise.

My main concern is the performance hit brought by my move of the while loops in 
every method into a consolidated `findInterestingIndex`. This part is somehow 
harder to get consistent results, or should I make a clean copy of 
`IdentityHashMap` on new implementation and test (works only if there is no 
existing hotspot optimizations on `IdentityHashMap`)

-

PR: https://git.openjdk.java.net/jdk/pull/6532

Re: RFR: JDK-8277520: Implement JDK-8 default methods for IdentityHashMap [v4]

[ExE Boss]

On Mon, 21 Feb 2022 23:36:19 GMT, liach  wrote:

>> Might need a CSR as now `computeIfAbsent` `computeIfPresent` `compute` 
>> `merge` would throw CME if the functions modified the map itself, and there 
>> are corresponding specification changes.
>
> liach has updated the pull request incrementally with two additional commits 
> since the last revision:
> 
>  - merge branch 'identityhashmap-bench' of https://github.com/liachmodded/jdk 
> into identityhashmap-default
>  - fix whitespace

src/java.base/share/classes/java/util/IdentityHashMap.java line 523:

> 521:  *  mapping was in the map
> 522:  */
> 523: private boolean removeMapping(Object key, Object value) {

Note that `IdentityHashMap.remove(Object, Object)` needs to call this method, 
as the default implementation calls `Objects.equals(…)`: 


-

PR: https://git.openjdk.java.net/jdk/pull/6532

Re: RFR: JDK-8277520: Implement JDK-8 default methods for IdentityHashMap [v4]

[liach]

On Sat, 19 Mar 2022 00:45:14 GMT, Stuart Marks  wrote:

>> @stuart-marks Could you help me with this?
>> 
>> In my JMH benchmark runs, I often find that ambient differences (from the 
>> jdk processes, the random test data generated, etc.) hide the actual 
>> performance difference caused by the patches.
>> 
>> Hence, I need help in these two area:
>> 1. I probably need to make a baseline benchmark that can discount the 
>> fundamental differences between jdk processes. What should it be?
>> 2. How do I generate consistent data set for all test runs to avoid 
>> contributing to errors?
>
> @liach I don't have much time to spend on this. Several comments.
> 
> JMH benchmarking is more than a bit of an art. There's a lot of information 
> in the JMH samples, so I'd recommend going through them in detail if you 
> haven't already. There are a couple of obvious things to look at, such as to 
> make sure to return values produced by the computation (or use black holes); 
> to fork multiple JVMs during the benchmark run; to reduce or eliminate 
> garbage generation during the test, or account for it if it can't be 
> eliminated; and so forth.
> 
> In this particular case it's not clear to me how much performance there is to 
> be gained from overriding the default methods. Suppose an entry exists and 
> `compute(k, bifunc)` is called. The default method calls `get` to obtain the 
> value, calls the bifunction, then calls `put(k, newVal)`. An optimized 
> implementation would remember the location of the mapping so that the new 
> value could be stored without probing again. But probing in an 
> IdentityHashMap is likely pretty inexpensive: the identity hashcode is 
> cached, finding the table index is integer arithmetic, and searching for the 
> right mapping is reference comparisons on table entries that are probably 
> already cached. It doesn't seem likely to me that there is much to be gained 
> here in the first place.
> 
> Then again, one's intuition about performance, including mine, is easily 
> wrong! But: if you're having trouble writing a benchmark that demonstrates a 
> performance improvement, maybe that means there isn't much performance to be 
> gained.
> 
> As a general comment I'd suggest pursuing performance improvements only when 
> there's a demonstrated performance issue. This kind of looks to me like a 
> case of starting with "I bet I can speed this up by changing this code" and 
> then trying to justify that with benchmarks. If so, that's kind of backwards, 
> and it can easily lead to a lot of time being wasted.

> @stuart-marks Note that the default implementation of those methods assume 
> that the map uses `Object.equals(…)` and `Object.hashCode()`, which doesn’t 
> apply to `IdentityHashMap`.
> 
> This means that the performance argument is secondary to implementation 
> correctness.

That was tracked in a separate ticket 
[JDK-8178355](https://bugs.openjdk.java.net/browse/JDK-8178355). My current 
implementations utilize the newly added `findInterestingIndex`, which I plan to 
use in a fix for that bug in addition, as opposed to writing a while loop in 
virtually every method in the class.

-

PR: https://git.openjdk.java.net/jdk/pull/6532

Re: RFR: JDK-8277520: Implement JDK-8 default methods for IdentityHashMap [v4]

[ExE Boss]

On Sat, 19 Mar 2022 00:45:14 GMT, Stuart Marks  wrote:

>> @stuart-marks Could you help me with this?
>> 
>> In my JMH benchmark runs, I often find that ambient differences (from the 
>> jdk processes, the random test data generated, etc.) hide the actual 
>> performance difference caused by the patches.
>> 
>> Hence, I need help in these two area:
>> 1. I probably need to make a baseline benchmark that can discount the 
>> fundamental differences between jdk processes. What should it be?
>> 2. How do I generate consistent data set for all test runs to avoid 
>> contributing to errors?
>
> @liach I don't have much time to spend on this. Several comments.
> 
> JMH benchmarking is more than a bit of an art. There's a lot of information 
> in the JMH samples, so I'd recommend going through them in detail if you 
> haven't already. There are a couple of obvious things to look at, such as to 
> make sure to return values produced by the computation (or use black holes); 
> to fork multiple JVMs during the benchmark run; to reduce or eliminate 
> garbage generation during the test, or account for it if it can't be 
> eliminated; and so forth.
> 
> In this particular case it's not clear to me how much performance there is to 
> be gained from overriding the default methods. Suppose an entry exists and 
> `compute(k, bifunc)` is called. The default method calls `get` to obtain the 
> value, calls the bifunction, then calls `put(k, newVal)`. An optimized 
> implementation would remember the location of the mapping so that the new 
> value could be stored without probing again. But probing in an 
> IdentityHashMap is likely pretty inexpensive: the identity hashcode is 
> cached, finding the table index is integer arithmetic, and searching for the 
> right mapping is reference comparisons on table entries that are probably 
> already cached. It doesn't seem likely to me that there is much to be gained 
> here in the first place.
> 
> Then again, one's intuition about performance, including mine, is easily 
> wrong! But: if you're having trouble writing a benchmark that demonstrates a 
> performance improvement, maybe that means there isn't much performance to be 
> gained.
> 
> As a general comment I'd suggest pursuing performance improvements only when 
> there's a demonstrated performance issue. This kind of looks to me like a 
> case of starting with "I bet I can speed this up by changing this code" and 
> then trying to justify that with benchmarks. If so, that's kind of backwards, 
> and it can easily lead to a lot of time being wasted.

@stuart-marks
Note that the default implementation of those methods assume that the map uses 
`Object.equals(…)` and `Object.hashCode()`, which doesn’t apply to 
`IdentityHashMap`.

This means that the performance argument is secondary to implementation 
correctness.

-

PR: https://git.openjdk.java.net/jdk/pull/6532

Re: RFR: JDK-8277520: Implement JDK-8 default methods for IdentityHashMap [v4]

[Stuart Marks]

On Wed, 16 Mar 2022 17:16:06 GMT, liach  wrote:

>> liach has updated the pull request incrementally with two additional commits 
>> since the last revision:
>> 
>>  - merge branch 'identityhashmap-bench' of 
>> https://github.com/liachmodded/jdk into identityhashmap-default
>>  - fix whitespace
>
> @stuart-marks Could you help me with this?
> 
> In my JMH benchmark runs, I often find that ambient differences (from the jdk 
> processes, the random test data generated, etc.) hide the actual performance 
> difference caused by the patches.
> 
> Hence, I need help in these two area:
> 1. I probably need to make a baseline benchmark that can discount the 
> fundamental differences between jdk processes. What should it be?
> 2. How do I generate consistent data set for all test runs to avoid 
> contributing to errors?

@liach I don't have much time to spend on this. Several comments.

JMH benchmarking is more than a bit of an art. There's a lot of information in 
the JMH samples, so I'd recommend going through them in detail if you haven't 
already. There are a couple of obvious things to look at, such as to make sure 
to return values produced by the computation (or use black holes); to fork 
multiple JVMs during the benchmark run; to reduce or eliminate garbage 
generation during the test, or account for it if it can't be eliminated; and so 
forth.

In this particular case it's not clear to me how much performance there is to 
be gained from overriding the default methods. Suppose an entry exists and 
`compute(k, bifunc)` is called. The default method calls `get` to obtain the 
value, calls the bifunction, then calls `put(k, newVal)`. An optimized 
implementation would remember the location of the mapping so that the new value 
could be stored without probing again. But probing in an IdentityHashMap is 
likely pretty inexpensive: the identity hashcode is cached, finding the table 
index is integer arithmetic, and searching for the right mapping is reference 
comparisons on table entries that are probably already cached. It doesn't seem 
likely to me that there is much to be gained here in the first place.

Then again, one's intuition about performance, including mine, is easily wrong! 
But: if you're having trouble writing a benchmark that demonstrates a 
performance improvement, maybe that means there isn't much performance to be 
gained.

As a general comment I'd suggest pursuing performance improvements only when 
there's a demonstrated performance issue. This kind of looks to me like a case 
of starting with "I bet I can speed this up by changing this code" and then 
trying to justify that with benchmarks. If so, that's kind of backwards, and it 
can easily lead to a lot of time being wasted.

-

PR: https://git.openjdk.java.net/jdk/pull/6532

Re: RFR: JDK-8277520: Implement JDK-8 default methods for IdentityHashMap [v4]

[liach]

On Mon, 21 Feb 2022 23:36:19 GMT, liach  wrote:

>> Might need a CSR as now `computeIfAbsent` `computeIfPresent` `compute` 
>> `merge` would throw CME if the functions modified the map itself, and there 
>> are corresponding specification changes.
>
> liach has updated the pull request incrementally with two additional commits 
> since the last revision:
> 
>  - merge branch 'identityhashmap-bench' of https://github.com/liachmodded/jdk 
> into identityhashmap-default
>  - fix whitespace

@stuart-marks Could you help me with this?

In my JMH benchmark runs, I often find that ambient differences (from the jdk 
processes, the random test data generated, etc.) hide the actual performance 
difference caused by the patches.

Hence, I need help in these two area:
1. I probably need to make a baseline benchmark that can discount the 
fundamental differences between jdk processes. What should it be?
2. How do I generate consistent data set for all test runs to avoid 
contributing to errors?

-

PR: https://git.openjdk.java.net/jdk/pull/6532

Re: RFR: JDK-8277520: Implement JDK-8 default methods for IdentityHashMap [v4]

[liach]

> Might need a CSR as now `computeIfAbsent` `computeIfPresent` `compute` 
> `merge` would throw CME if the functions modified the map itself, and there 
> are corresponding specification changes.

liach has updated the pull request incrementally with two additional commits 
since the last revision:

 - merge branch 'identityhashmap-bench' of https://github.com/liachmodded/jdk 
into identityhashmap-default
 - fix whitespace

-

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/6532/files
  - new: https://git.openjdk.java.net/jdk/pull/6532/files/f6ee4fab..9fe578be

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk=6532=03
 - incr: https://webrevs.openjdk.java.net/?repo=jdk=6532=02-03

  Stats: 105 lines in 1 file changed: 0 ins; 0 del; 105 mod
  Patch: https://git.openjdk.java.net/jdk/pull/6532.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/6532/head:pull/6532

PR: https://git.openjdk.java.net/jdk/pull/6532