[omp major] Tray reads LIST on hot path with O(n²) sort #157

New issue

Closed

opened 2026-09-05 20:39:02 +00:00 by crueber · 3 comments

crueber commented

2026-09-05 20:39:02 +00:00

Owner

[omp major] Tray reads LIST on hot path with O(n²) sort

internal/notify/http.go:354-371, :381-390, :422-432: every GET /notifications LISTs the prefix + GETs up to 1000 overflow objects even when the index suffices, plus up to ~1050 repoAlive HEADs, plus an O(n²) insertion sort.

Fix

Index-first serving (answer from the unread index when it covers the window; LIST only for overflow pages), bound/skip the alive probes on the hot path (lazy or capped), replace the quadratic sort. Regression/benchmark test pinning per-request cost. Coverage gate holds.

Acceptance criteria

Index-covered tray reads cost O(page), no LIST, no quadratic sort; test green -race.

# [omp major] Tray reads LIST on hot path with O(n²) sort `internal/notify/http.go:354-371`, `:381-390`, `:422-432`: every `GET /notifications` LISTs the prefix + GETs up to 1000 overflow objects even when the index suffices, plus up to ~1050 `repoAlive` HEADs, plus an O(n²) insertion sort. ## Fix Index-first serving (answer from the unread index when it covers the window; LIST only for overflow pages), bound/skip the alive probes on the hot path (lazy or capped), replace the quadratic sort. Regression/benchmark test pinning per-request cost. Coverage gate holds. ## Acceptance criteria - [ ] Index-covered tray reads cost O(page), no LIST, no quadratic sort; test green `-race`.

crueber referenced this issue from a pull request that will close it,

2026-09-05 21:43:39 +00:00

Fix #157: index-first tray reads #163

crueber referenced this issue from a commit

2026-09-05 21:43:39 +00:00

Fix #157: index-first tray reads (no LIST on hot path, memoized liveness, sort.Slice)

crueber commented

2026-09-05 21:43:42 +00:00

Author

Owner

Fixed by PR #163 (#163): index-first tray serving — covered pages cost 1 index GET + 1 HEAD per distinct repo, no LIST; LIST only for overflow pages; sort.Slice replaces the O(n²) sort. Cost tests verified failing pre-fix; -race green, coverage 96.1%.

Fixed by PR #163 (https://git.packden.us/crueber/walhub/pulls/163): index-first tray serving — covered pages cost 1 index GET + 1 HEAD per distinct repo, no LIST; LIST only for overflow pages; sort.Slice replaces the O(n²) sort. Cost tests verified failing pre-fix; -race green, coverage 96.1%.

crueber commented

2026-09-05 21:45:58 +00:00

Author

Owner

PR #163 review (fix/issue-157, index-first tray reads) — verified in scratch worktree, all green.

CORRECTNESS

Covered-window detection exact (http.go:420-452): trayPage returns covered only after collecting n+1 live rows, or (indexFull=false i.e. short index) the full live remainder. A page is NEVER wrongly judged covered: state-filtered/dead-skipped shortfalls with indexFull=true fall through (!ok) to the LIST merge; short index + hidden tail is only the stated crash-orphan trade-off (see below). Missing/corrupt index (haveIndex=false, http.go:362) always goes to LIST — says nothing about overflow. Correct.
Overflow seam (http.go:367-408): merged set = index rows + LIST objects with index-first remember + object-wins dedup (same as old order), one shared sort, cursor resolved in the merged order. Index cursor paging past the tail, overflow cursor, and unknown-cursor-restarts-at-first-page all preserved from old semantics. No skipped/duplicated rows: CreatedAt/id immutable (only state flips), so merged positions stable.
Lazy liveness fail-open confirmed both directions: dead repo hides row (repoAlive false → skip, #63 preserved); malformed repo keeps row (trayAlive http.go:458-462, pinned by TestTrayMalformedRepoKept); probe error keeps row (repoAlive fail-open in notify.go:691-697, pinned by TestTrayProbeErrorFailOpen). Memo is request-local map[string]bool, bounded by distinct repos in the examined window (collection stops at n+1 live rows), GC'd with the request. No new locks/goroutines (grep: none in http.go); only added import is stdlib sort — no dependency-budget impact.
Sort equivalence: same comparator (CreatedAt desc, ID asc) as the old insertion sort; keys are unique per row (ID deduped), so sort.Slice instability is unreachable — identical output on all inputs. Pinned at scale by TestSortNotificationsLarge (2000 rows) + TestSortNotificationsEqualAt.
sortStrings untouched (notify.go:709-716 still insertion sort) and write-path-bounded: only users are emit.go:391 (fan-out members), watch.go:126 (watcher list), webhooks.go:257 (event keys) — small slices, never the tray read path.

TRADE-OFF — accepted, one wording fix pushed

Short-but-readable index skips LIST, so a live-repo crash orphan stays hidden until overflow paging reaches it. Consistent with P4 (index is the hot window; bucket objects remain source of truth via overflow LIST) and proportionate: crash window is one request's object-Create→index-CAS gap, tray is not git data. BUT the entry said 'or retention converges it' — retention (tasks.go retainUser/retainOverflow) reaps dead-repo overflow and reconciles the window count, it never reindexes live orphans. Fixed in fbc46b4: now reads 'until its page is reached via overflow (paging past the window); retention reaps dead-repo overflow but never reindexes live orphans'. §1.2 liveness line ('memoized to one HEAD per distinct repo… since #157') verified accurate.

COST PINS — genuine, verified both directions

New tests fail pre-fix for the right reason (old http.go restored, new tests run): TestTrayIndexCoveredNoList → 'covered page LISTed 1 times, want 0'; TestTrayOverflowPageLists → 'overflow page HEADs = 80, want <= 2'. Matches the doc's 'verified LIST+80-HEADs pre-fix'. Post-fix: covered = 1 GET + 2 HEADs + 0 LISTs; overflow = exactly 1 LIST.

RESULTS (scratch worktree /tmp/pr163 @ fbc46b4, since removed)

go test -race ./internal/notify/ -count=1: ok (2.4s); new cost/sort tests -count=5: all PASS; coverage 96.1% (≥95% gate holds); gofmt clean; go vet clean.

MERGE RECOMMENDATION: ready to merge.

PR #163 review (fix/issue-157, index-first tray reads) — verified in scratch worktree, all green. CORRECTNESS - Covered-window detection exact (http.go:420-452): trayPage returns covered only after collecting n+1 live rows, or (indexFull=false i.e. short index) the full live remainder. A page is NEVER wrongly judged covered: state-filtered/dead-skipped shortfalls with indexFull=true fall through (!ok) to the LIST merge; short index + hidden tail is only the stated crash-orphan trade-off (see below). Missing/corrupt index (haveIndex=false, http.go:362) always goes to LIST — says nothing about overflow. Correct. - Overflow seam (http.go:367-408): merged set = index rows + LIST objects with index-first remember + object-wins dedup (same as old order), one shared sort, cursor resolved in the merged order. Index cursor paging past the tail, overflow cursor, and unknown-cursor-restarts-at-first-page all preserved from old semantics. No skipped/duplicated rows: CreatedAt/id immutable (only state flips), so merged positions stable. - Lazy liveness fail-open confirmed both directions: dead repo hides row (repoAlive false → skip, #63 preserved); malformed repo keeps row (trayAlive http.go:458-462, pinned by TestTrayMalformedRepoKept); probe error keeps row (repoAlive fail-open in notify.go:691-697, pinned by TestTrayProbeErrorFailOpen). Memo is request-local map[string]bool, bounded by distinct repos in the examined window (collection stops at n+1 live rows), GC'd with the request. No new locks/goroutines (grep: none in http.go); only added import is stdlib sort — no dependency-budget impact. - Sort equivalence: same comparator (CreatedAt desc, ID asc) as the old insertion sort; keys are unique per row (ID deduped), so sort.Slice instability is unreachable — identical output on all inputs. Pinned at scale by TestSortNotificationsLarge (2000 rows) + TestSortNotificationsEqualAt. - sortStrings untouched (notify.go:709-716 still insertion sort) and write-path-bounded: only users are emit.go:391 (fan-out members), watch.go:126 (watcher list), webhooks.go:257 (event keys) — small slices, never the tray read path. TRADE-OFF — accepted, one wording fix pushed - Short-but-readable index skips LIST, so a live-repo crash orphan stays hidden until overflow paging reaches it. Consistent with P4 (index is the hot window; bucket objects remain source of truth via overflow LIST) and proportionate: crash window is one request's object-Create→index-CAS gap, tray is not git data. BUT the entry said 'or retention converges it' — retention (tasks.go retainUser/retainOverflow) reaps dead-repo overflow and reconciles the window count, it never reindexes live orphans. Fixed in fbc46b4: now reads 'until its page is reached via overflow (paging past the window); retention reaps dead-repo overflow but never reindexes live orphans'. §1.2 liveness line ('memoized to one HEAD per distinct repo… since #157') verified accurate. COST PINS — genuine, verified both directions - New tests fail pre-fix for the right reason (old http.go restored, new tests run): TestTrayIndexCoveredNoList → 'covered page LISTed 1 times, want 0'; TestTrayOverflowPageLists → 'overflow page HEADs = 80, want <= 2'. Matches the doc's 'verified LIST+80-HEADs pre-fix'. Post-fix: covered = 1 GET + 2 HEADs + 0 LISTs; overflow = exactly 1 LIST. RESULTS (scratch worktree /tmp/pr163 @ fbc46b4, since removed) - go test -race ./internal/notify/ -count=1: ok (2.4s); new cost/sort tests -count=5: all PASS; coverage 96.1% (≥95% gate holds); gofmt clean; go vet clean. MERGE RECOMMENDATION: ready to merge.

crueber closed this issue

2026-09-05 21:46:15 +00:00

crueber referenced this issue from a commit

2026-09-05 21:46:15 +00:00

Merge pull request 'Fix #157: index-first tray reads' (#163) from fix/issue-157 into main

crueber commented

2026-09-05 21:46:15 +00:00

Author

Owner

Fixed by PR #163 incl. review doc precision fix (index-first serving, lazy liveness, identical sort; 96.1% coverage), merged. Closing.

crueber added the

webhooks