Performance of array of non-nullable value objects

[Sergey Kuksenko]

HashMaps on Valhalla were analyzed some time ago:
https://cr.openjdk.org/~skuksenko/valhalla/hashmaps/hash.html

________________________________________
From: valhalla-dev <valhalla-dev-retn at openjdk.org> on behalf of David Witten <vadavidsw at gmail.com>
Sent: Tuesday, February 13, 2024 1:01 PM
To: valhalla-dev at openjdk.org
Subject: Performance of array of non-nullable value objects

First I'd like to thank everyone working on valhalla, it is very exciting!

I was playing around with different hash Map implementations using Build 20-valhalla+20-75<https://download.java.net/java/early_access/valhalla/20/openjdk-20-valhalla+20-75_linux-x64_bin.tar.gz>.  I was surprised that get() performance when bins were arrays of primitive classes containing (int hash, K key, V value) performed worse than the normal non-primitive linked-list bins of (int hash, K key, V value, Node next) even when bins were rather large.

Is this expected to be the case for this old early release?
Is this expected to be the case when non-nullable, not-atomicly-updated value objects are officially released?
Is there any guess about when another early release will be available?

The initial size and load factor of the Maps guaranteed that the bins were largish.  The random seed was the same for array-bin vs list-bin so that the bins sizes are always same for both.  Here is a typical histogram for bin sizes (again same for list vs array bins):

histogram: max: 16, [589, 2436, 4805, 6396, 6342, 5173, 3413, 1889, 1017, 437, 187, 55, 21, 6, 1, 0, 1]
So, for example, there were 2436 bins of size 1.

Here are some results (I started with the jmh tests in https://hg.openjdk.org/valhalla/valhalla/rev/71ba79398dd9 ) but the Map implementations and random seed approach are different.

Benchmark                              (mapType)  (size)  Mode  Cnt     Score     Error  Units
GetX.getHit  mapprotos.ArrayBinHashMapJustPutGet  131072  avgt   10  4784.596 ± 649.247  us/op
GetX.getHit          mapprotos.HashMapJustPutGet  131072  avgt   10  3053.680 ± 427.430  us/op
GetX.getMix  mapprotos.ArrayBinHashMapJustPutGet  131072  avgt   10  4991.512 ± 292.345  us/op
GetX.getMix          mapprotos.HashMapJustPutGet  131072  avgt   10  4291.636 ± 543.059  us/op

If this sort of behavior is not expected, and someone would like to look into it, I can clean up and supply my test.


-thanks, David