Iteration/callback perf: JSLN key-reconstruction hypothesis refuted; the addressable cost is the per-element second lookup in *_HASH / *_ADAPTIVE #85

Investigation of the standing roadmap item "C-level forEach()/filter()/map() performance tuning (vtable dispatch)". Measurement only — no code changed.

Short version: the hypothesis that JSLN's caller-supplied key buffer makes ordered string iteration expensive is refuted. JSLN's cost is flat in key length and flat in working-set size; the expensive part is JudySL's stateless per-call root descend plus successor search, and libJudy exposes no cheaper primitive. The one large addressable cost the decomposition did find is elsewhere: the four *_HASH / *_ADAPTIVE types perform a second full lookup (JHSG/JLG) per element during ordered traversal, worth 22 ns/elem at 16-byte keys and 98 ns/elem at 40-byte keys — up to 46% of forEach() on those types. The "vtable dispatch" framing in the roadmap line targets a few ns and should be dropped.

Method

Host honeycomb, 24-core x86_64, Ubuntu 22.04, idle. /proc/loadavg snapshotted before and after every run: 0.07–0.47 across all runs (contention threshold for this box is cores/2 = 12.0). PHP runs inside the existing php-judy-bench image: Debian 13, PHP 8.4.24, ext-judy 2.4.2. C benchmarks gcc -O2, same image, same libJudy.

Keys are user:%08d:f%d padded to a target length — 10 keys share each user: prefix, matching the shape the backend-evaluation POC used. All numbers are median of 5 runs, [min .. max] shown. Every PHP figure below was reproduced independently at n=500K and n=1M (deltas <3%). All numbers (measured) unless tagged otherwise.

C level: which part of JSLN is expensive

n=1M, median ns/key:

This reproduces the POC's ~67 ns/key for JudySL ordered iteration (70.2 here).

Three discriminators, all pointing the same way:

1. Key length. 16 → 64 bytes is 4× the bytes to materialize; JSLN moves 70.5 → 77.8 (+10%). A cost dominated by writing the key into the caller buffer would scale with the key.
2. Working set. n=100K → 1M is 10× the tree; JSLN moves 66.4 → 70.2 (+6%). Not cache-miss-bound on tree size either.
3. Direct subtraction. JSLG replayed in iteration order does the same descend with the same locality and does not write a key back. JSLN − JSLG = 33.1 / 30.7 / 31.1 / 32.9 ns at keylen 16 / 24 / 40 / 64 — constant in key length. What "next" adds over a plain lookup is successor search (backtracking to the next populated branch), not key materialization.

So the 70 ns decomposes roughly as 37 ns descend (itself 3.5× a complete JudyL JLN step) + 32 ns successor search + ~1 ns key bytes.

This is not addressable from php-judy. The entire JudySL surface in Judy.h is JSLI JSLG JSLD JSLF JSLN JSLL JSLP JSLFA — there is no cursor/stateful-iteration primitive. The gap against libart's art_iter (2.7 ns/key in the POC) is stateful-DFS-with-a-path-stack vs stateless-successor-API; closing it means replacing the backend, not tuning the extension. That belongs to the backend-evaluation thread, not here.

PHP level: per-layer decomposition

n=500K, keylen 16 and 40, median ns/element:

Spreads were tight throughout (worst case ±1.5% around the median; the few keys() maxima are single first-run allocator warmups).

Attributing the layers:

forEach(noop) on STRING_TO_INT, keylen 16 = 95.2 ns/elem

• JSLF/JSLN traversal ≈ 70 (74%) — not addressable
• userland dispatch ≈ 10 (11%) — at the PHP floor, not addressable
• extension glue (per-element ZVAL_STRING for the key, fci setup, arg + retval dtor, type branches) ≈ 15 (16%)

forEach(noop) on INT_TO_INT = 26.4 ns/elem

• JLF/JLN ≈ 10.6 (40%)
• dispatch ≈ 10 (38%)
• glue ≈ 6 (22%)

Dispatch is isolated two ways and both agree on ~10 ns: INT_TO_INT forEach(noop) 26.4 − values() 15.1 (same traversal, same zval build, no callback) = 11.3; and the pure-PHP floor of calling an empty closure in a for loop = 11.0 − 1.8 = 9.2. Judy::forEach() on INT_TO_INT (26.4) is already faster than array_map() over a native PHP array (29.0). There is nothing to win in dispatch.

The one large addressable cost. For *_HASH and *_ADAPTIVE, ordered traversal walks the JudySL key_index and then does a second, independent lookup (JHSG, or JLG on the SSO path) to fetch the value — in judy_iterator_move_forward, judy_iterator_rewind, judy_populate_array, and judy_callback_iterator. Measured directly as values() − keys() (identical traversal, one with the value fetch, one without):

Matching the C-level JHSG sorted-order figures (31.4 → 106.8 as keylen goes 16 → 40). At keylen 40 this is 46% of forEach() on those types and the reason STRING_TO_*_HASH iteration costs 2× STRING_TO_INT iteration despite walking the same JudySL.

filter() re-fetch. action_filter (php_judy.c:4149) calls judy_object_read_dimension_helper_zv() to recover the value, but judy_callback_iterator still has it in args[0] — it just isn't passed to the action. Isolated as filter(true) − map(identity) (the extra read filter does that map does not): +36.5 ns on STRING_TO_INT kl16, +12.2 ns on INT_TO_INT. Consistent with JSLG sorted (37.1) and JLG.

Ceiling

Addressable fraction, i.e. what is left after subtracting Judy traversal and userland dispatch:

Nobody should start this work expecting more than that. In particular, on the flagship STRING_TO_INT type, three quarters of forEach() is JSLN and another tenth is zend_call_function — the whole extension layer is ~16% and it will not all come out.

Plan

Step 1 — remove the per-element second lookup for *_HASH and *_ADAPTIVE.
Mechanism: the JudySL key_index value word is allocated but never written. Every JSLI(..., key_index, ...) site (php_judy.c:752, 795, 831, 848, 879, 903, 3057, 3107, 3185, 4732; judy_handlers.c:148, 181, 253) only checks the return for PJERR and stores nothing through it. Put the payload there — Word_t for the _INT variants, zval* for the _MIXED variants — so ordered traversal reads the value from the cursor it already holds and never calls JHSG/JLG.
Targets: 22 ns/elem at keylen 16, 98 ns/elem at keylen 40 (measured), across foreach, forEach(), filter(), map(), keys()/values()/toArray()/getAll(), clone, and the set ops, for 4 of the 10 types. Memory cost is zero — the word is already allocated.
Gating dependency (this is the real work, not the traversal edit): audit every path that mutates a value in place so the two stores cannot diverge — offsetSet on an existing key, increment(), putAll, mergeWith, map() writing into a result, __unserialize — and every delete path so a zval* is freed exactly once.
Rejected alternative: caching the PWord_t slot returned by JHSI instead of the value. libJudy can relocate JudyHS leaves on insert, so a cached slot pointer can dangle.
Gate: ≥15% improvement on foreach and values() at keylen 16 and ≥35% at keylen 40 for all four types; no regression on point-lookup benchmarks; .phpt covering mutation before/during/after iteration for both _INT and _MIXED; clean USE_ZEND_ALLOC=0 valgrind on the iteration and mutation tests.

Step 2 — drop the value re-fetch in filter(). Independent of Step 1, either order. Widen the judy_callback_action signature to pass args[0] so action_filter stops re-reading a value the iterator already has. Targets 36.5 ns per surviving element on STRING_TO_INT (13% of filter(true)), 12.2 ns on INT_TO_INT (19%). Small, isolated, no data-structure change.
Semantics: today, a predicate that mutates $this[$k] changes what filter() copies; after the change filter() copies the pre-callback value. Snapshot semantics are the more defensible contract, but this is a behavior change and needs a .phpt pinning whichever is chosen.

Step 3 (optional, lowest value, do last or not at all) — reuse one zend_string for the key across callback iterations. judy_callback_iterator does ZVAL_STRING(&args[1], key) + zval_ptr_dtor per element; judy_iterator_move_forward (judy_iterator.c:214-221) already implements the non-interned / refcount==1 / length-fits reuse. Projected ~8-12 ns/elem on string-keyed forEach/filter/map, ~10% (projected, not measured — measuring it requires building the change**)**. Hazard: a callback may retain the key ($keys[] = $k;), so the refcount guard is mandatory and getting it wrong corrupts a userland string. Bounded above by the whole 15 ns glue bucket. Weak supporting evidence that it is marginal: foreach (which already reuses) measures 95.1 vs forEach() (which does not) at 95.2.

Non-goals

• Callback dispatch optimization. Measured at ~10 ns/elem, equal to the pure-PHP closure-call floor. forEach() already beats array_map() over a native array.
• "vtable dispatch" as the roadmap line describes it. The per-element type branches live inside a glue bucket that is ~6 ns total on INT_TO_INT and ~15 ns on STRING_TO_INT; the branches themselves are a few ns of well-predicted work. Not worth a refactor.
• Faster JudySL ordered traversal. JSLN is 70 ns/key and libJudy exposes no cursor API. Any real improvement here is a backend change, not extension tuning.
• INT_TO_* traversal. JLN is 10.6 ns/key.
• Chasing the libart art_iter 2.7 ns/key figure from inside php-judy. Different problem, different thread.

Roadmap

Replace C-level forEach()/filter()/map() performance tuning (vtable dispatch) in README.md:497 with the Step 1 item, which is the only part of that line the data supports.