Re: RFR: 8322149: ConcurrentHashMap copy constructor should not transfer from old table on presizing [v2]
On Fri, 12 Jan 2024 08:51:16 GMT, Volker Simonis wrote: >>> tryPresize(int size) is doing and if its size argument is supposed to >>> contain the additional number of elements which will be inserted into the >>> hash map or if it is a hint for the new total size of the hash map >> >> Argument `size` for `tryPresize()` is a hint for the **new total size** of >> the hash map. If the size is too small compared to the current size of the >> map, there will be no resizing. > > Thanks. In that case, calling `tryPresize()` with `size < this.size()` > doesn't make sense and we should call it with `this.size() + m.size()`. Thanks. Just committed this change. Also added a new benchmark for `putAll()` and the results in the top post. - PR Review Comment: https://git.openjdk.org/jdk/pull/17116#discussion_r1456490539
Re: RFR: 8322149: ConcurrentHashMap copy constructor should not transfer from old table on presizing [v2]
On Thu, 11 Jan 2024 19:21:00 GMT, Joshua Cao wrote: >>> We don't need to compute max() here. >>> [tryPresize()](https://github.com/openjdk/jdk/blob/8a4dc79e1a40e7115e2971af81623b6b0368f41c/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java#L2397) >>> does that already. >> >> The code you reference is only executed if `table == null` but in this case >> we know it is not `null` because we only call `tryPresize()` if `table != >> null`. >> >> In general, it's hard fro me to understand what `tryPresize(int size)` is >> doing and if its `size` argument is supposed to contain the additional >> number of elements which will be inserted into the hash map or if it is a >> hint for the new total size of the hash map. Can you explain? > >> tryPresize(int size) is doing and if its size argument is supposed to >> contain the additional number of elements which will be inserted into the >> hash map or if it is a hint for the new total size of the hash map > > Argument `size` for `tryPresize()` is a hint for the **new total size** of > the hash map. If the size is too small compared to the current size of the > map, there will be no resizing. Thanks. In that case, calling `tryPresize()` with `size < this.size()` doesn't make sense and we should call it with `this.size() + m.size()`. - PR Review Comment: https://git.openjdk.org/jdk/pull/17116#discussion_r1450063503
Re: RFR: 8322149: ConcurrentHashMap copy constructor should not transfer from old table on presizing [v2]
On Thu, 11 Jan 2024 09:40:07 GMT, Volker Simonis wrote: > tryPresize(int size) is doing and if its size argument is supposed to contain > the additional number of elements which will be inserted into the hash map or > if it is a hint for the new total size of the hash map Argument `size` for `tryPresize()` is a hint for the **new total size** of the hash map. If the size is too small compared to the current size of the map, there will be no resizing. - PR Review Comment: https://git.openjdk.org/jdk/pull/17116#discussion_r1449296202
Re: RFR: 8322149: ConcurrentHashMap copy constructor should not transfer from old table on presizing [v2]
On Mon, 8 Jan 2024 20:27:59 GMT, Joshua Cao wrote: > We don't need to compute max() here. > [tryPresize()](https://github.com/openjdk/jdk/blob/8a4dc79e1a40e7115e2971af81623b6b0368f41c/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java#L2397) > does that already. The code you reference is only executed if `table == null` but in this case we know it is not `null` because we only call `tryPresize()` if `table != null`. In general, it's hard fro me to understand what `tryPresize(int size)` is doing and if its `size` argument is supposed to contain the additional number of elements which will be inserted into the hash map or if it is a hint for the new total size of the hash map. Can you explain? - PR Review Comment: https://git.openjdk.org/jdk/pull/17116#discussion_r1448566797
Re: RFR: 8322149: ConcurrentHashMap copy constructor should not transfer from old table on presizing [v2]
On Mon, 8 Jan 2024 15:59:17 GMT, Volker Simonis wrote: > Shouldn't this be something like tryPresize(this.size() + m.size()) to > accommodate for the worst case where there are no common keys in this map and > m? Its a good callout. Not sure if it is a miss, or intentionally conservative. > But then shouldn't we use at least max(this.size(), m.size)? We don't need to compute `max()` here. [tryPresize()](https://github.com/openjdk/jdk/blob/8a4dc79e1a40e7115e2971af81623b6b0368f41c/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java#L2397) does that already. Although this does bring to my attention that maybe there is the same symptom of "extra unnecessary work" when merging in a smaller map. If the new size is smaller, we should just be able to exit out of `tryPresize()` without having to call the expensive `transfer()`. We would need to run a separate experiment for it. - PR Review Comment: https://git.openjdk.org/jdk/pull/17116#discussion_r1445292956
Re: RFR: 8322149: ConcurrentHashMap copy constructor should not transfer from old table on presizing [v2]
On Wed, 3 Jan 2024 21:29:57 GMT, Joshua Cao wrote:
>> ConcurrentHashMap's copy constructor calls `putAll()` -> `tryPresize()` ->
>> `transfer()`. When coming from the copy constructor, the Map is empty, so
>> there is nothing to transfer. But `transfer()` will still copy all the empty
>> nodes from the old table to the new table.
>>
>> This patch avoids this work by only calling `tryPresize()` if the table is
>> already initialized. If `table` is null, the initialization is deferred to
>> `putVal()`, which calls `initTable()`.
>>
>> ---
>>
>> ### JMH results for testCopyConstructor
>>
>> before patch:
>>
>>
>> Result "org.openjdk.bench.java.util.concurrent.Maps.testCopyConstructor":
>> 937395.686 ±(99.9%) 99074.324 ns/op [Average]
>> (min, avg, max) = (825732.550, 937395.686, 1072024.041), stdev = 92674.184
>> CI (99.9%): [838321.362, 1036470.010] (assumes normal distribution)
>>
>>
>> after patch:
>>
>>
>> Result "org.openjdk.bench.java.util.concurrent.Maps.testCopyConstructor":
>> 620871.469 ±(99.9%) 59195.406 ns/op [Average]
>> (min, avg, max) = (545304.633, 620871.469, 689013.573), stdev = 55371.419
>> CI (99.9%): [561676.063, 680066.875] (assumes normal distribution)
>>
>>
>> Average time is decreased by about 33%.
>
> Joshua Cao has updated the pull request incrementally with one additional
> commit since the last revision:
>
> Cleanup benchmark
src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java line
1088:
> 1086: public void putAll(Map m) {
> 1087: if (table != null) {
> 1088: tryPresize(m.size());
Shouldn't this be something like `tryPresize(this.size() + m.size())` to
accommodate for the worst case where there are no common keys in `this` map and
`m`?
Or do we intentionally try to be conservative with memory usage? But then
shouldn't we use at least `max(this.size(), m.size)`?
-
PR Review Comment: https://git.openjdk.org/jdk/pull/17116#discussion_r1444898430
Re: RFR: 8322149: ConcurrentHashMap copy constructor should not transfer from old table on presizing [v2]
On Wed, 3 Jan 2024 21:29:57 GMT, Joshua Cao wrote: >> ConcurrentHashMap's copy constructor calls `putAll()` -> `tryPresize()` -> >> `transfer()`. When coming from the copy constructor, the Map is empty, so >> there is nothing to transfer. But `transfer()` will still copy all the empty >> nodes from the old table to the new table. >> >> This patch avoids this work by only calling `tryPresize()` if the table is >> already initialized. If `table` is null, the initialization is deferred to >> `putVal()`, which calls `initTable()`. >> >> --- >> >> ### JMH results for testCopyConstructor >> >> before patch: >> >> >> Result "org.openjdk.bench.java.util.concurrent.Maps.testCopyConstructor": >> 937395.686 ±(99.9%) 99074.324 ns/op [Average] >> (min, avg, max) = (825732.550, 937395.686, 1072024.041), stdev = 92674.184 >> CI (99.9%): [838321.362, 1036470.010] (assumes normal distribution) >> >> >> after patch: >> >> >> Result "org.openjdk.bench.java.util.concurrent.Maps.testCopyConstructor": >> 620871.469 ±(99.9%) 59195.406 ns/op [Average] >> (min, avg, max) = (545304.633, 620871.469, 689013.573), stdev = 55371.419 >> CI (99.9%): [561676.063, 680066.875] (assumes normal distribution) >> >> >> Average time is decreased by about 33%. > > Joshua Cao has updated the pull request incrementally with one additional > commit since the last revision: > > Cleanup benchmark I am good this this version. I would like a second Reviewer to ack this too. - Marked as reviewed by shade (Reviewer). PR Review: https://git.openjdk.org/jdk/pull/17116#pullrequestreview-1803734314
Re: RFR: 8322149: ConcurrentHashMap copy constructor should not transfer from old table on presizing [v2]
On Wed, 3 Jan 2024 19:52:34 GMT, Joshua Cao wrote:
>> test/micro/org/openjdk/bench/java/util/concurrent/Maps.java line 122:
>>
>>> 120: public void testCopyConstructor() {
>>> 121: ConcurrentHashMap clone = new
>>> ConcurrentHashMap<>(staticMap);
>>> 122: dummy = clone;
>>
>> Is this for preventing dead-code elimination? If so, just do:
>>
>>
>> return new ConcurrentHashMap<>(staticMap);
>
> I tried this. I don't think its working. When I just return the map, we lose
> the improvements in performance, and the benchmark overall just runs much
> faster. I'm guessing the map got DCE'ed
Scratch that. Was my mistake. Was running the wrong test.
I'm renaming `testCopyConstructor` to `testConcurrentHashMapCopyConstructor`,
since the file name + test don't actually explicitly say its for
ConcurrentHashMap.
-
PR Review Comment: https://git.openjdk.org/jdk/pull/17116#discussion_r1440968465
Re: RFR: 8322149: ConcurrentHashMap copy constructor should not transfer from old table on presizing [v2]
> ConcurrentHashMap's copy constructor calls `putAll()` -> `tryPresize()` -> > `transfer()`. When coming from the copy constructor, the Map is empty, so > there is nothing to transfer. But `transfer()` will still copy all the empty > nodes from the old table to the new table. > > This patch avoids this work by only calling `tryPresize()` if the table is > already initialized. If `table` is null, the initialization is deferred to > `putVal()`, which calls `initTable()`. > > --- > > ### JMH results for testCopyConstructor > > before patch: > > > Result "org.openjdk.bench.java.util.concurrent.Maps.testCopyConstructor": > 937395.686 ±(99.9%) 99074.324 ns/op [Average] > (min, avg, max) = (825732.550, 937395.686, 1072024.041), stdev = 92674.184 > CI (99.9%): [838321.362, 1036470.010] (assumes normal distribution) > > > after patch: > > > Result "org.openjdk.bench.java.util.concurrent.Maps.testCopyConstructor": > 620871.469 ±(99.9%) 59195.406 ns/op [Average] > (min, avg, max) = (545304.633, 620871.469, 689013.573), stdev = 55371.419 > CI (99.9%): [561676.063, 680066.875] (assumes normal distribution) > > > Average time is decreased by about 33%. Joshua Cao has updated the pull request incrementally with one additional commit since the last revision: Cleanup benchmark - Changes: - all: https://git.openjdk.org/jdk/pull/17116/files - new: https://git.openjdk.org/jdk/pull/17116/files/93b9072d..3632649c Webrevs: - full: https://webrevs.openjdk.org/?repo=jdk&pr=17116&range=01 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=17116&range=00-01 Stats: 12 lines in 2 files changed: 2 ins; 7 del; 3 mod Patch: https://git.openjdk.org/jdk/pull/17116.diff Fetch: git fetch https://git.openjdk.org/jdk.git pull/17116/head:pull/17116 PR: https://git.openjdk.org/jdk/pull/17116
