镜像站点 · 本页由第三方 GitHub 只读镜像提供,非 GitHub 官方站点,不接受任何登录或凭据输入。前往 github.com
Skip to content

Array: bound numeric keys in generic indexed traversal #529

Closed

Description

@chrisbbreuer

Parent: #480
Related: #460, #472, #478, #493

Problem

Generic Array methods route array-like, sparse, inherited, accessor, typed-array, and Proxy indices through arrIndexPresent, arrIndexGet, arrIndexSetOrThrow, arrIndexDeleteOrThrow, and related result/set helpers. These helpers currently format ToString(index) with allocPrint(self.arena, ...). The key is consumed synchronously by [[HasProperty]], [[Get]], [[Set]], [[Delete]], or CreateDataProperty, but its temporary bytes remain in Context backing. Repeated generic forEach/map/filter/search/shift-style traversal therefore retains O(iterations × logical length) decimal-key storage and adds allocator work to every observed index.

Scope

  • Format numeric property keys in bounded native storage wherever the callee consumes or copies the key synchronously.
  • Preserve exact ECMA-262 ordering for length, per-index HasProperty, Get, callback, Set, Delete, and result definition.
  • Keep dense-array and typed-array fast paths unchanged unless exact evidence supports a retained improvement.
  • Cover plain array-likes, holes with inherited properties, accessors, Proxies, mutation during callbacks, exotic result species, and throwing traps.
  • Audit every converted sink to prove borrowed bytes cannot escape; storage sites must establish owned key lifetime before return.

No-workaround rules

  • No dense-only shortcut presented as generic support, skipped holes/traps/callbacks, snapshotted input, capped ordinary length, cached user-visible keys, unbounded realm/process cache, or bypass of property attributes/prototype setters.
  • OOM from a property operation or owned-key publication must propagate without partial extra mutation or leaks.

Acceptance

  • Deterministic 1K/2K/4K generic array-like rows, a sparse Proxy row, and a dense-array control preserve frozen checksums.
  • Exact-parent wall/instruction/allocation/RSS evidence attributes numeric-key retention and rejects dense-control regression.
  • Proxy/accessor/inherited-hole ordering and callback-time mutation match the specification.
  • Set/Delete/result-definition paths copy borrowed keys before they escape; OOM is rollback-safe and leak-free.
  • Moving GC, bounded heap, no-GIL, focused TSan, full units, and affected test/built-ins/Array/prototype subtrees pass with nonzero denominators.

Security boundary

Logical length and Proxy behavior are attacker-controlled. Work must remain proportional to the specified traversal while temporary native storage stays bounded independently of the number of visited indices.

Activity

  1. added
    enhancementNew feature or request
    performanceMeasured runtime, memory, scaling, or build performance
    runtimeJavaScript runtime and builtin implementation
    on Aug 11, 2026
  2. chrisbbreuer commented on Aug 11, 2026

    @chrisbbreuer
    MemberAuthor

    Scope split: the benchmark-only parent exposes a second, independent bottleneck. Ordinary 1K/2K/4K array-like rows measured about 4.15/25.71/153.66 ms in the parent diagnostic and 4.02/27.43/148.83 ms after bounding temporary index-key storage, while the dense 4K control remains about 3.65 ms. Shape.lookupState is linear in shape depth, so computed Has/Get across thousands of numeric named properties becomes O(N²). I opened #530 to own a collision-safe, no-GIL-safe shape lookup index. #529 remains scoped to temporary key lifetime and allocator/retained-memory removal; it will not hide the separate curve with a numeric-key shortcut.

  3. chrisbbreuer commented on Aug 11, 2026

    @chrisbbreuer
    MemberAuthor

    Implementation landed directly on main: perf(array): bound generic traversal index keys (#529), following the benchmark-only parent bench(array): add generic traversal scaling rows (#529).

    Measured semantic gates before landing:

    • focused generic Array units: 6/6 pass, 0 leaks;
    • deterministic borrowed-key allocation-failure sweep: pass;
    • four-lane no-GIL witness under TSan: pass;
    • test/built-ins/Array/prototype: parent 2810 pass / 0 fail -> candidate 2810 pass / 0 fail (0 flips, nonzero denominator).

    Exact parent-vs-child timing, instruction, allocation, and RSS publication plus the full unit gate remain before closure.

  4. chrisbbreuer commented on Aug 11, 2026

    @chrisbbreuer
    MemberAuthor

    Completed on main.

    Commits:

    Acceptance evidence:

    • frozen 1K/2K/4K plain array-like, sparse Proxy, and dense control checksums all matched in order-balanced exact-parent artifacts;
    • live Proxy Has/Get order, inherited holes, callback mutation, Set/Delete, and species defineProperty order pass;
    • ordinary publication copies borrowed key bytes before return and rolls back every injected allocation failure;
    • re-entrant GC plus actual moving compaction pass;
    • the 32 MiB bounded-heap witness traverses 786,432 logical indices without unreclaimable key residue;
    • four-lane no-GIL passes under focused TSan;
    • full units: 1,580 pass, 1 skip, 0 fail, 0 leak;
    • test/built-ins/Array/prototype: 2,810 pass / 0 fail in parent and candidate, flips 0;
    • docs build and exact-evidence schema/identity checks pass.

    Causal allocation delta for 100 x 1K traversal: requested backing bytes 59,423,930 -> 38,534,342; backing growths 215 -> 28; retained backing increase 35,070,438 -> 14,164,680; GC-cell work remains exactly equal. The 15-pair dense refinement is neutral at 1.001x wall, 1.008x instructions, and 1.000x peak RSS.

    Evidence report: exact-parent-array-index-keys-2026-08-10.md.

    The separate O(depth) Shape lookup curve remains explicitly owned by #530; no numeric-key workaround was folded into this issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or requestperformanceMeasured runtime, memory, scaling, or build performanceruntimeJavaScript runtime and builtin implementation

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions