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