Runtime: string-key arrays are still super-linear after the DJB index — 5k keys 0.13 s, 20k keys 2.4 s, 100k keys > 120 s (Zend 0.03–0.09 s); the `isset`/read path or the index growth is not O(1) (lib/JIT/Builtin/Type/HashTable.php) (re-#36191)

[PurHur]

Category

Foundation: · closed-but-not-done · child of #36379

Problem

#36191 was closed by "HashTable: DJB hash index for string-key lookup" + "O(1) string-key append via strKeysTail (#36191 partial)". Re-verified on master 1edb103c34 with the issue's own probe ($a["k$i"] = $i then isset+read for all keys):

n	2026-09-01	2026-09-02	Zend
5,000	171 s	0.133 s	0.028 s
20,000	> 300 s	2.40 s	0.037 s
100,000	> 300 s	> 120 s (timeout)	0.086 s

4x more keys → 18x the time: still ~n^2. The 5k case improved 1,300x (the {main} copy-per-store, #36252, was the first-order term), but the structure is not a hash table yet on at least one of: the index is not consulted on isset/read (only on insert), the index never grows (fixed bucket count → chains of n/buckets), or strKeysTail append still walks. The issue's Done-when required "within 2x of Zend at 100k" — not met.

PHP implementation target

• Instrument: count key comparisons per lookup at n = 5k/20k/100k (a PHPC_HT_STATS=1 counter in the helper) — if comparisons grow with n, the index is not used or not resized.
• Zend layout as specified in Runtime: __hashtable__ string keys are a singly linked list with no hash function — O(n) lookup, O(n²) build for every associative array (lib/JIT/Builtin/Type/HashTable.php) #36191: arData + arHash with power-of-two resize at load factor, hash cached on the string, used by every string-key entry point (setStringKey*, readStringKey*, offsetIsSetStringKey, unsetStringKey, peek), and the iteration order kept by the ordered array (not by the linked list).

Done when

• Probe at 100k within 2x of Zend; comparisons per lookup O(1) in the stats counter
• foreach order, ksort/asort, unset+re-add, numeric-string normalisation differential cases green; --aot --repeat 3 unchanged

[PurHur]

claim: implementer-worker-lane-a — starting this run

[PurHur]

Merged #36420.

Fix: ensureStrHashIndex doubles DJB buckets at load factor ≥1; all setStringKey* writes use hash lookup instead of list walks.

Verify (merged tip):

make dev-verify-fast → OK
./script/aot-smoke.sh → 9/9
/tmp/ht.bin 100000 → 100000 in 0.078s (Zend 0.019s)
/tmp/ht.bin 20000 → 20000 in 0.016s (Zend 0.009s)

Full differential-sweep --aot --repeat 3 not run this session (CI lock); tier-0 VM differential green.

[PurHur]

claim: implementer-worker-lane-a — starting this run (lane A tie-break #36408 % 3 == 0; lane overflow: #36143–#36148 closed; closed-but-partial per #36449 — Done-when 100k within 2x Zend still open)

[PurHur]

claim: implementer-worker-lane-a — continuing this run (Done-when: 100k within 2x Zend; prior merge #36420 left ~4x). Measuring probe on current master then tightening lookup/insert path.

[PurHur]

claim: implementer-worker-lane-a — starting this run (lane A tie-break #36408 % 3 == 0; lane overflow: #36143–#36148 closed; closed-but-partial per #36449 — Done-when 100k within 2x Zend)

[PurHur]

Merged #36498

100k test/repro/hashtable_hash_index_assoc.php (insert + isset), same-container median 11 runs: Zend 0.0168s, master 2.57×, branch 1.84×. aot-smoke 9/9.