Build1 publisher3 min readPublished
Perturbed probing cut a miss-heavy map benchmark from 32.7 seconds to 44.9 milliseconds
Codename One packed small integer keys into adjacent slots in ParparVM, so a lookup for an absent key walked thousands of entries before finding an empty one. The team swapped in CPython's probe recurrence.
The Engineer · Build desk
What happened
- Three million containsKey calls on absent keys took 32.7 seconds in Codename One's ParparVM, while the benchmark the team usually watched looked healthy because it mostly asked for keys that existed.
- Scrambling the hash harder did remove the miss penalty, and it made dense-key construction and scans 1.8 to 2.2 times slower in the measured shapes.
- With the perturbed probe sequence shipped, the miss-heavy workload came in at 44.9 ms, random hits in the large table got slower, and the broad suite's geometric mean barely moved.
Compiled by The EngineerSomething wrong?How this is made
Why it matters
- constraint The probe recurrence now exists in both the native and the Java implementation, and the two must emit the same sequence during growth and deletion, so future tuning cannot land in one side alone.
- cost Applications whose maps mostly hit present keys in large tables get the cost of the miss fix and none of the benefit, since that shape regressed and the overall suite average held flat.
- decision Hashtable's leftover gap is in synchronization, so the next round of work is in the address-keyed monitor table.
- precedent A map benchmark that only queries keys it inserted will keep reporting a one-probe lookup. Claiming a map is fast takes controlled runs for misses, tombstones, growth, string keys and identity keys.
Each of those three million absent-key lookups cost about 10.9 microseconds [1]. After the change the same workload runs at roughly 15 nanoseconds a call, a ratio of about 728 to 1 [2][3]. The win is probe count: hits already resolved in one probe, so no per-comparison saving was available to find [7].
The map is ParparVM's HashMap, inside a framework that compiles one Java or Kotlin codebase to native iOS, Android, desktop and web apps [20]. It keeps entries in arrays and resolves collisions by probing other slots [2]. Integer hashes preserve the value, and the familiar `h ^= h >>> 16` spread leaves small dense integer keys close to their original positions [3]. Insert 0 through 99,999 and the occupied slots form an uninterrupted run [6][4]. A present key usually lands on its home slot; `containsKey(-1)` enters the run and linear probing walks until it finds an empty slot [4]. Deleting entries does not shorten that walk, because tombstones cannot terminate a search either [5].
The chosen fix keeps the first probe at `marker & mask` and then steps with the recurrence associated with CPython's dictionary probing [10]. The Java helper is one line: `((i << 2) + i + 1 + perturb) & mask` [10]. The caller shifts the unsigned perturbation right five bits between probes, and once it decays to zero the recurrence still traverses the power-of-two table [11].
Go's Swiss maps compare compact control metadata before loading full keys, so more of the search is in a small amount of contiguous memory [13]. ParparVM's layout already separated metadata from keys and values, so the urgent problem was the route through that layout after a collision, and the team kept scalar perturbed probing [14]. The measured gain comes from a new probe sequence over the old layout. Group probing over metadata was not part of it [14].
String keys got a separate change. Cached unequal hashes now reject a match immediately, and compatible UTF-16 arrays go through native `memcmp`, which hands the byte work to the platform's optimized vector comparison [15]. The numbers come from alternating old and new builds on one development Mac, confirming the two builds agreed, and comparing best runs [16]. For the improvement to appear in an application, its map traffic has to contain absent-key lookups or tombstone walks over dense integer keys; on random hits in a large table, the new build is the slower one [17].
Hashtable now avoids an `Entry` allocation per mapping and uses the compact layout, and its lookup is still more expensive than HashMap on the same probe code because synchronization goes through ParparVM's address-keyed monitor table [18]. IdentityHashMap gave a different warning: HotSpot's identity hash is already scrambled, ParparVM's is derived from an aligned address, and copying the JDK's indexing expression preserved zero low bits and worsened collisions [19].
What to watch
- Whether the rework of ParparVM's address-keyed monitor table lands, and how much of Hashtable's remaining lookup cost it removes.
- Whether the slower random-hit path in large tables gets revisited once the pathological miss case is gone.
- Whether IdentityHashMap's index expression ends up with an indexing scheme fitted to an address-derived hash.