Code health: evaluateRetention re-sorts each revision group per artifact — O(n² log n) where one sort per revision (O(n log n)) suffices

[qwen-code-dev-bot]

sourceType

source:self-discovery — undirected maintainer review pass over the repository itself (no diff trigger). Code-health / performance category.

sourceLinkOrEvidence

Concrete evidence on main @ 01f4bef. evaluateRetention (src/artifact-retention.ts) re-sorts the same revision group inside the per-artifact loop and then linearly scans it:

// src/artifact-retention.ts
for (const artifact of artifacts) {                       // line 85
  ...
  const revisionGroup = byRevision.get(artifact.goalRevision)!;      // line 90
  const sorted = [...revisionGroup].sort((a, b) => b.createdAt - a.createdAt);  // line 91
  const indexInRevision = sorted.indexOf(artifact);                   // line 92
  const isExcess = indexInRevision >= policy.maxCountPerRevision;     // line 93
  ...
}

The revision groups are built once up front (src/artifact-retention.ts:78-83), but for every artifact the code copies its whole revision group with [...revisionGroup], sorts it, and then does an indexOf linear scan. For a revision holding k artifacts that is k copies + k sorts of k elements + k linear scans → O(k² log k) per revision (O(n² log n) across n artifacts), where a single sort per revision plus an index lookup is O(n log n).

Minimal scenario: one revision with 200 artifacts → the group is copied and sorted 200 times (≈ 200 × 200·log 200 comparisons) instead of once; the retention verdict for each artifact is identical either way, so this is pure redundant work.

problemStatement

evaluateRetention computes each artifact's position within its revision by re-copying and re-sorting the entire revision group for every artifact, then locating the artifact with a linear indexOf. The retention decision only needs each artifact's rank in a newest-first ordering of its revision, which a single sort per revision (plus an index map) provides. The current shape does quadratically more work than necessary as artifacts per revision grow.

userValue

Artifact-retention evaluation scales linearly with artifact count instead of quadratically with per-revision count, keeping cleanup fast for long-running Goals that accumulate many artifacts per revision, and the function becomes simpler (one sort per revision instead of one per artifact).

scope

• In evaluateRetention (src/artifact-retention.ts), sort each revision group once (newest-first) and derive each artifact's rank via an index map (e.g. Map<ArtifactRecord, number> built while iterating the sorted group) instead of re-sorting + indexOf inside the per-artifact loop.
• Preserve the retention semantics exactly: same retained / eligibleForCleanup partition, same cleanupReasons strings (including the indexInRevision + 1 count), same ordering where observable.
• Keep the behavior covered by the existing tests/unit/artifact-retention.test.ts cases unchanged.

nonGoals

• Not changing the retention policy semantics (maxAgeDays, maxCountPerRevision), the age-based path, the report formatting, or the ArtifactRecord/RetentionPolicy shapes.
• Not introducing a different data structure for byRevision beyond what the single-sort refactor needs.
• Not touching other modules that call evaluateRetention.
• Desktop, Dynamic Workflow, or governance surfaces.

acceptanceCriteria

• Each revision group is sorted at most once per evaluateRetention call (no per-artifact copy+sort of the group).
• Retention output is identical to the current implementation for the same input: same retained/eligibleForCleanup sets and same cleanupReasons strings (age and count reasons, including the 1-based count).
• All existing tests/unit/artifact-retention.test.ts cases pass unchanged, plus a regression test asserting the rank/excess behavior for a revision with more than maxCountPerRevision artifacts.
• No change to formatRetentionReport output for a given evaluation.

testPlan

Unit tests in tests/unit/artifact-retention.test.ts: (1) keep/extend the existing age- and count-based cases to lock behavior; (2) add a case with maxCountPerRevision + N artifacts in one revision asserting exactly the oldest N are eligible with correct 1-based count reasons; (3) a mixed-revision case asserting per-revision independence. Deterministic assertions on the retained/eligible sets and reason strings.

dogfoodPlan

Build from the merged branch and run the retention unit suite to confirm identical behavior; optionally exercise a retention report path (the function is pure, so the unit suite plus npm test is the meaningful check) and confirm no other suite regresses.

riskAndSecurityNotes

Low risk: behavior-preserving refactor of a pure function. The primary risk is an accidental change to the retention partition or reason strings, guarded by the existing + new tests. No state mutation, no privilege change, no secret handling, and no public-API signature change to evaluateRetention.

duplicateSearchEvidence

• gh search issues for evaluateRetention, retention performance, artifact retention sort, O(n^2), retention O(n → no Issue/PR about the algorithmic efficiency.
• The only related Issues, Goal: add retention and cleanup rules for completed execution artifacts #430/feat(goal): add retention and cleanup rules for completed execution artifacts #431, are the original retention/cleanup feature (behavior), not the evaluation's complexity; Robustness: formatBytes lacks GB/TB tiers — multi-GB session-store footprints render as thousands/millions of MB #850/fix(cli): add GB/TB tiers to formatBytes so multi-GB footprints scale instead of rendering as millions of MB (Issue #850) #851 (formatBytes) is the same file but a different function/concern.
• tests/unit/artifact-retention.test.ts covers retention behavior, not the sort/index efficiency.
  Conclusion: distinct, unfixed algorithmic inefficiency — not a duplicate.

parentChildRelationship

Standalone source:self-discovery Issue (not a child of any roadmap parent). Refines the retention feature (#430/#431) without changing its behavior.

dependencyOrder

No blocking dependencies; executable immediately (evaluateRetention already exists on main @ 01f4bef). Single vertical slice: refactor one function to sort once per revision plus regression tests.

[github-actions]

Automated intake triage

• Type: enhancement
• Priority: priority:p3
• Confidence: 0.95

Refactor artifact retention evaluation to sort each revision group once instead of re-sorting it for every artifact to avoid quadratic redundant work.

Reported evidence (unverified)

• evaluateRetention re-sorts the same revision group inside the per-artifact loop
• The issue reports O(n squared log n) work where one sort per revision would suffice
• Requested change preserves existing retention output and reason strings

Repository verification

Pending. Repository verification is still required before this Issue can become agent-ready.

This bounded pass classifies intake only. It cannot execute code, close the Issue, or grant governance authority.

[qwen-code-dev-bot]

🤖 Leased by qwen-code-dev-bot (autonomous loop, priority 4 — highest-priority dependency-ready agent-ready; the higher-priority Desktop/Dynamic-Workflow subtasks are blocked by open governance blockers #74/#106/#133/#142). Branch: issue/852-retention-single-sort. Starting the train: refactor evaluateRetention to sort each revision group once (O(n log n)) instead of re-sorting per artifact (O(n² log n)), behavior-preserving with regression tests, gates, PR, merge, dogfood.

[qwen-code-dev-bot]

Evidence (append-only) — implementation complete, PR #853 open

• evaluateRetention (src/artifact-retention.ts:78-101) now sorts each revision group once (stable, newest-first) and builds a rank map; the per-artifact loop reads the rank in O(1) instead of re-copying + re-sorting + indexOf. O(n² log n) → O(n log n), behavior-preserving.
• Behavior preserved: all 16 retention tests pass on both the old and new implementations (15 existing + 1 new regression pinning newest-first ranking + 1-based count reasons).
• Performance (3000 artifacts in one revision, 5-run avg): old ~219.5 ms/run → new ~2.28 ms/run (~96× faster).
• Gate: typecheck ✓, build ✓ (desktop bundle), unit 271 files/4119 passed (+1), integration 158 files/956 passed, smoke ✓, npm audit --omit=dev 0 vulns. Desktop E2E leg runs only in CI (no xvfb locally); change is a pure behavior-preserving refactor.

PR: #853

[qwen-code-dev-bot]

Evidence (append-only) — merged & dogfooded; releasing lease

Merged to main via PR #853 (commit efdddff); CI verify (incl. desktop E2E leg, 3m52s) + protected-paths both green.

Post-merge dogfood against the rebuilt artifact (dist evaluateRetention):

• Retention unit tests: 16 passed (behavior preserved on merged code).
• Perf (3000 artifacts in one revision, 5-run avg): 2.24 ms/run (previously ~219 ms, ~96× faster); retained=50 / eligible=2950 as expected for maxCountPerRevision=50.

Issue closed by the merge (Closes #852). Releasing the agent-active lease; deleting the feature branch.