Skip to content

(OPT) Replay identity-certified shared PLAN prefixes without repeated comparison payloads #899

Open

Description

@wsdt

The retained PLAN heapsort repeatedly compares observations inside the same immutable segment shared by sibling histories. Existing #875 shares physical backing; this follow-up would exploit that exact identity during comparison. It does not replace lexical order with hash order or change the sort schedule.

Discovery source: b8f2295. src/cleanup_plan/replay/ordinary_plan_history/producer.rs:246–318 creates shared arena segments. Existing Cursor::prepare in ordinary_plan_history.rs:245–285 validates links, ordering, depth and backing. comparison_owner.rs:318–501 and comparison_owner/paired_value.rs:36–104 contain the left-before-right preparation and work/cursor sequence.

After both existing preparations, recognize aligned identical segment indices within the same immutable arena. Execute a funded scalar replay state for that segment, preserving EVERY original observation/left-step/left-segment/right-step/right-segment work call individually and in order. Physically avoid observation references, slice-head/rest payloads and content comparisons for certified equal observations. Divergent segments and tails use the complete ordinary path. Final PLAN/HIR validation, heapsort states, terminal ordering and swaps stay independent and unchanged.

Acceptance:

  • Freeze and independently compile the complete immediate comparator/cursor/macros/invoices; preserve every older oracle and source control. Register actual new children in all owning source unions.
  • Invoice the complete new owner, identity detector, retained range/offset/length state, receivers, publication, control, fallback and drop costs before formation. Remove only physically absent payloads; keep all surviving conservative legacy invoices explicit. No fee/cap relaxation, baseline inflation, credit, work batching or crosscheck discount.
  • Preserve exact malformed-link/depth discovery, left/right failure order, sticky byte/work refusal, Oracle/Selected authority and same-invocation borrowing. Do not prescan all paths or let a certificate survive mutation/swap invalidating its referent.
  • Compare complete six-field diagnostics, work remaining/spent, swaps and full Drop on bounded every-work-cut fixtures. Cover long shared prefixes, distinct segments with equal contents, empty/deep segments, tails, first/last divergence, duplicates/strict prefixes, terminal differences, invalid links and both HIR representations.
  • Exercise every new acquisition at exact/short/zero/floor, post-swap and sticky failure. Census actual identity hits/certified observations/fallback observations/replayed work and full new bytes; distinguish eliminated physical cursor operations from executed ones.
  • Run unchanged whole 32-row caller and actual external codec/native/catalog owners at 67,108,864 bytes, plus only relevant focused checks and production Clippy. Never full suites/gates. A later refusal is progress, not admission.

The failed 6a839 unit prefix observed 598 prepared pairs and 51,870 rounds, but neither is a count of shared-segment observations. The existing heapsort is already O(P log P); this targets repeated long prefixes, not alleged quadratic pair enumeration. Opportunity is removed actual comparison/cursor payloads on identity-certified observations minus ALL new costs. No numeric saving, application-fit or token advantage is established. Astra performed read-only discovery; no tests/builds ran for this proposal.

Activity

  1. wsdt commented on Oct 18, 2026

    @wsdt
    MemberAuthor

    Read-only follow-up discovery for the next receiving measurement (no gain claim): the current source candidate replays only already-loaded, same-ID segment remainders (shared_prefix.rs). Its first observation and singleton segments still take the ordinary path. The existing whole-caller dump omitted already-collected K/hits/detectors/captures; source-only commit 96731eeca now exposes them per invocation and with checked totals, typed coefficients, and incomplete-prefix labels. It is not runtime-qualified yet.

    The frozen whole32 caller prefix recorded738pairs,62,710rounds and107,695LOADs before refusal. These are not K, do not establish a singleton distribution, and do not prove a completed saving. First rank current K against ALL new setup/detector/capture/replay costs, with main28 reachable-bank funding kept separate.

    Potential next structural extension: after both unchanged Cursor::prepare calls, recognize aligned same-arena next-link identities and scalar-replay the first item of a nonempty segment. Measure J: eligible entry encounters, same-ID singleton encounters, empty boundaries and asymmetric offsets. Preserve each original left/right work event individually, preparation/link/depth/terminal diagnostics, fallback, sticky failure and full Drop. Any invoice must subtract every new ID/length/pop/receiver/owner/header cost and credit only physically removed MATCH/STEP/LOAD/capture packets, with no double-counting of K. Equal-content/different-ID and malformed/foreign cases remain negative controls.

    No application admission, shipping K/J count, speedup, token advantage or billed-cost reduction is established. Astra performed read-only discovery; no new issue or independent completion claim is needed while this ticket remains open.

  2. wsdt commented on Oct 18, 2026

    @wsdt
    MemberAuthor

    New actual execution at pushed 3522497d7db05f6531dd11fb2bcd209f36638fce: all seven default shared-prefix owners pass, including repaired cold/hot allocation observation and real unwind. The whole-32 caller still refuses under its unchanged ordinary cap. Its reached rows.main prefix reports M=1, K=8,493, hits=8,493, detectors D=62,710, captures C=107,694, extent captures E=53,620, replayed work=42,465; complete=false, ended=true, unwound=false, overflow=false, truncated=false, lost=0.

    Actual typed coefficients: current owner240, immediate-before owner216, additive fields/headers2489, removed per K314, replay per K85, detector56, capture-link8, capture-extent40. Applying the identity-component equation to this reached prefix gives old-minus-new = -4,575,728 reservation bytes. This is an unfavorable partial-prefix component, not a completed caller invoice, RSS, whole-shipping result, or live-agent token/cost comparison. Reachable primitive-site funding is accounted separately; no LOAD/tail credit inferred.

    Next optimization discovery is driven by this detector/capture overhead: investigate genuine segment-entry and retained span replay, preserving each original left/right work call, exact failure selection, all physical operations and fully funded replacement controls. Existing caps, original old oracles and application requirements remain unchanged. Issue stays open; separate opt-in capture owner is still pending.

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

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions