Optimize (Linked-)HashMap lookup when backing array is null
Christoph Dreis
christoph.dreis at freenet.de
Tue May 19 17:50:13 UTC 2020
Hi Claes,
On 2020-05-19 15:15, Christoph Dreis wrote:
>> Hi Claes,
>>
>>> unlike CHM, HashMap and LinkedHashMap have constant-time size/isEmpty
>>> accessors - could this be used to simplify your patch?
>>
>> I was wondering about that during implementation, but simply took the path I already chose for the CHM.
> I think we should try to keep any changes here as simple as possible.
Please find an alternative solution attached that does isEmpty() checks for get() and containsKey() calls.
With the provided solution and the combined (empty & non-empty maps) benchmarks, I get the following results:
MyBenchmarkNew.test avgt 10 4,479 ± 0,061 ns/op
MyBenchmarkOld.test avgt 10 4,877 ± 0,054 ns/op
I should note that I see a slightly higher average timing with a filled map with the isEmpty() version:
MyBenchmarkNew.test avgt 10 5,465 ± 0,354 ns/op
MyBenchmarkOld.test avgt 10 5,315 ± 0,187 ns/op
Isolated benchmarks on just an empty map show the following results (for completeness reasons):
MyBenchmarkNew.test avgt 10 2,785 ± 0,191 ns/op
MyBenchmarkOld.test avgt 10 3,785 ± 0,436 ns/op
I can somewhat explain the higher average timing on a filled map with this solution:
It actually does "more" work by checking for the size, while the previous solution shifted only existing work to a place where it's actually needed.
I would probably go for the first version although it is a bit more complicated and has the computeIfPresent caveat, because it doesn't slow down the common Map.get() case when the map is actually filled.
Let me know what you think.
Cheers,
Christoph
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: pre-isempty-hashmap.txt
URL: <https://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20200519/0531140f/pre-isempty-hashmap.txt>
More information about the core-libs-dev
mailing list