Repository navigation
Description
Parent: #493
Related: #460, #471, #478, #480, #529
Problem
Shape.lookupState and Shape.lookup walk the immutable parent chain linearly. That is compact and effective for ordinary shallow objects, while inline caches remove repeated lookup at stable source sites. Generic or computed access to an object with N attacker-controlled named properties cannot use one stable inline-cache key, however: each HasProperty or Get walks O(N) shape operations. A length-N Array generic over a plain array-like with N numeric named properties therefore performs O(N²) shape-name comparisons.
The deterministic #529 diagnostic rows expose the independent curve: 1K, 2K, and 4K generic array-like traversal grows far faster than linearly even after temporary decimal-key allocation is removed. This issue owns the lookup complexity; #529 remains the separate temporary-key lifetime fix.
Scope
- Add an immutable or versioned exact name-to-latest-operation index for deep Shapes, preserving transition sharing, stable slots, deletion tombstones, re-add semantics, and prepared literal shapes.
- Keep shallow objects compact and fast; activate or consult indexed state only when exact attribution justifies it.
- Make every lookup collision-safe and deterministic in semantics under attacker-controlled property names.
- Prove publication ordering and lifetime for no-GIL readers, concurrent transitions, deletion compaction, moving GC, and Context teardown.
- Bound index construction, rebuild, and retained memory in terms of live/historical shape state.
No-workaround rules
- No cap on object property count or Array logical length, numeric-key special case presented as a general shape fix, semantic key cache, linear fallback on hash collisions, globally shared mutable cache, predictable collision-vulnerable table, GIL, or bypass of attributes/prototypes/Proxy behavior.
- Do not replace the shape chain with per-object maps or sacrifice transition convergence without exact evidence proving the full object-model tradeoff.
Acceptance
- Exact-parent 1K/2K/4K computed Has/Get and generic array-like rows demonstrate approximately linear work using instruction and shape-lookup counters, with frozen results.
- Shallow literal, monomorphic property, transition-hit/miss, deletion/re-add, sparse numeric, and dense Array controls do not regress materially.
- Collision corpus, adversarial names, deep delete/re-add history, deterministic OOM/fault injection, and bounded-heap/RSS tests pass.
- Shared transition publication scales monotonically at 1/2/4/8 lanes; no-GIL, threadfuzz, moving/parallel GC, lifecycle, and suppression-free TSan pass.
- Full units and affected test262 Object/Array/Proxy subtrees pass with nonzero denominators.
Security boundary
Property names and shape depth are attacker-controlled. Lookup must remain exact under collision and concurrent publication while CPU and retained memory stay bounded by documented shape state.
Activity
perf(shape): index deep property lookup (#530)
chrisbbreuer commentedon Aug 11, 2026
Implementation landed on
mainas7666c5f1:perf(shape): index deep property lookup (#530).What changed:
Validation completed:
The intentionally oversized lifecycle run (400 seeds × 56 subcases) is still progressing; exact-parent timing/allocation evidence will follow in a separate evidence commit before this issue is closed.
docs(performance): publish deep Shape index evidence (#530)
chrisbbreuer commentedon Aug 11, 2026
Exact-parent evidence landed on
mainas21a33f13:docs(performance): publish deep Shape index evidence (#530).Direct implementation edge:
8592a7dc→7666c5f1.Stable work result (candidate / parent instructions):
Candidate median instructions per traversed property/job stay nearly flat: 24,494.5 at 1K, 24,532.5 at 2K, and 25,086.8 at 4K (only 1.024x growth), while the parent rises from 85,040.9 to 273,604.1. Wall medians improve strongly too, but the report labels them diagnostic where this host exceeded the wall-dispersion threshold; no samples were discarded.
Controls:
Memory is explicit: 4K post-invocation retained RSS rises from 38,322,176 to 40,501,248 bytes, +2,179,072 bytes (1.057x). The 32 MiB heap/moving-compaction witness passes, and the index is Context-arena-owned.
Correctness:
asyncHoldscore oracle; exact parent reproduces the same failure class (559/560), so it is not a Shape regression;Evidence:
exact-parent-deep-shape-index-2026-08-10.md.I am keeping #530 open for its remaining declared acceptance item: a real 1/2/4/8-lane shared transition-throughput publication. The four-lane functional/TSan witness is not being presented as that missing scaling result.
chrisbbreuer commentedon Aug 11, 2026
#530 is complete on its deep-lookup/security scope:
7666c5f121a33f13exact-parent-deep-shape-index-2026-08-10.mdThe remaining 1/2/4/8 shared publication requirement exposed a distinct shared arena/object-model bottleneck and is now explicitly owned by #531. Its benchmark was committed first in
d9d54b5b, with partitioned, anti-specialization, and contended rows and no runtime fix mixed in.Closing this issue does not claim #531 scaling is solved; it records the completed collision-free logarithmic lookup implementation and preserves the independent concurrency defect in its own acceptance contract.