Repository navigation
IntMap is 2.3x slower than stock hxcpp 4.3.53 (map_int benchmark) #231
Description
The benchmark suite (#151) measures IntMap at 0.44x the speed of stock hxcpp 4.3.53: 54.8M map operations/s against 124M. The gap is the same in all three processes, and well outside the run-to-run spread (±1.2% and ±0.7%).
What the benchmark does (bench/src/MapBenchmarks.hx, MapInt): a fresh IntMap<Int> per cycle, 200,000 keys; 200,000 sets, 200,000 hits, 200,000 misses, 100,000 removes, then iterates the 100,000 values left. 6 cycles per sample. Keys are distinct non-sequential ints computed in setup(), so only map work is timed. Checksums match stock, so both runtimes do the same work.
Not known yet: which of the operations is slower. The first step is to time set, get, exists, remove and iteration separately against stock.
Possibly related, unconfirmed: #189 (initial reservation ignored during storage conversion, repeated rehashing) and #225 (resize hysteresis). Both concern libhxcpp's hash code, which differs from stock's.
Measured on perf/benchmark-suite at bf583e5, which includes the #230 heap fix: Windows, Ryzen 9 9950X, MSVC 19.44, 64-bit, Haxe 4.3.7, 3 processes x 10 samples. The full table is in that branch's README.
Reproduce (on perf/benchmark-suite until the suite reaches main):
cd bench
haxe --run Run --only map_int
Done when map_int is at least level with stock on Windows and Linux.
Activity
Keep the heap on Gc.run(true); only Gc.compact releases it all
dimensionscape commentedon Oct 20, 2026
Progress on
perf/benchmark-suite(not onmainyet).map_intis now 0.5x stock (was 0.44x). What's known:Fixed
Gc.run(true)released every empty block group, likeGc.compact, so each sample started with a cold heap. Map lookups and iteration after a major collection were up to 2x slower. OnlyGc.compactreleases everything now (also Small allocations are 2-10% slower than stock hxcpp 4.3.53 (alloc_small, alloc_arrays, string_substr) #233).Most of the remaining gap is the benchmark's key pattern, not a defect. The keys are
(i*2579)^0x2b5f3c1d. With stock's identity hash those land in distinct buckets, and misses land in empty buckets: a perfect hash. libhxcpp mixes the bits (to avoid the collisions fixed in rc.1), which scatters them. Per phase, ms per cycle, 200,000 keys:i<<10, stock / libWith random keys libhxcpp is level or faster on every phase except iteration. With strided keys stock is up to 680x slower. Going back to an identity hash would trade that away to win this one benchmark, so I'm not doing that.
Iteration (3.0 vs 1.8 ms on scattered keys) is a GC threshold effect, not iterator or marking cost. With the map dropped before the walk, libhxcpp walks faster than stock (1.65 vs 1.8). GC event logs show that per rep libhxcpp's heap ends one 1 MB group over the 20 MB minimum target (21.3 MB) and collects once during the walk, while stock sits just under it (19.4 MB) and adds a group instead. The allocator and sizing code are identical; the difference is about 1 MB more allocated per rep, landing right at the edge. I'm leaving the GC tuning alone for this.
Next: add
map_int_randomandmap_int_stridedbenchmarks so the README shows both sides of the hash trade-off, rather than changingmap_int's keys.Start int maps on the identity hash, switch to the mix on collisions
dimensionscape commentedon Oct 20, 2026
The remaining gap is closed on
perf/benchmark-suite(b245698):map_intis now 1.04x stock hxcpp 4.3.53, up from 0.5x.Cause. Every Int key went through
HashMixInt. The mix protects strided keys (i << 10and similar), but it scatters arithmetic keys (ids, offsets,i * odd), which stock's identity hash spreads with no collisions at all. The benchmark's keys are arithmetic, and so are many keys in real programs.Fix. Int maps start on the identity hash, like stock. A map switches to the mix for good, rehashing in place once, when either:
Int64 and object keys are unchanged.
Per-phase probe (ms per cycle, 200,000 keys, after
Gc.run(true)), stock / before / now:(i*2579)^ci<<10Random keys still beat stock on set, get and miss (4.0 / 3.3 / 2.1 against 6.4 / 4.0 / 2.6).
Tests. The new
test/regression/IntMapHashSwitchcovers keys that never switch, keys that switch on a long chain, and keys that switch at growth. Each pattern runs at 10 to 100,000 keys with updates, removes, misses, iteration, emptying and refilling. It also fails if strided keys take more than 10 s, which is what happens if the switch breaks.MapShrinkRegrowand thetest/haxesuite (667 assertions, generational GC build) pass.Left: walk is still about 0.4 ms slower, which is the 20 MB working-target edge effect described above. I'll leave this open until the branch reaches
mainand Linux numbers confirm it.Keep the heap on Gc.run(true); only Gc.compact releases it all
Start int maps on the identity hash, switch to the mix on collisions
Keep the heap on Gc.run(true); only Gc.compact releases it all
Start int maps on the identity hash, switch to the mix on collisions
dimensionscape commentedon Oct 20, 2026
Fixed in e97f84c: int maps start on the identity hash and switch to the mix on collisions. map_int is now 1.04x of hxcpp 4.3.53 (see BENCHMARKS.md).