The priority queue does more work than its contract requires

Timing: Follow-up after trial/3 merges into main; defer implementation until then.

Review baseline: Local trial/3 at a094418baf6388e3eeca23821df481a7f0a8751c. This branch is not yet on the remote. Source locations below refer to that snapshot and should be rechecked after merge.

Problem

ItemQueue::add sorts the entire collection after every insertion. pop removes index zero from a Vec, shifting the remaining entries. Fully draining n queued items therefore entails O(n²) element movement. This is a scaling concern; no current-workload latency regression has been measured.

Evidence

crates/lib/src/queue.rs:80-103: append followed by full sorting.
crates/lib/src/queue.rs:163-169: entries.remove(0).

Acceptance criteria

Choose storage/scheduling that avoids repeated full sorting and front-shifting, justified against expected queue sizes.
Preserve descending priority, FIFO ties, checked sequence/priority arithmetic, retained high/low watermarks, and cooperative execution behavior.
Verify ordering, mixed insertion/removal, and front/back insertion after draining; record the resulting complexity or focused performance evidence.

Code examples and suggested direction

The current queue must preserve entries() -> &[Item<T>] in execution order. A heap alone does not provide that view. One candidate is a sorted VecDeque kept contiguous after every insertion:

// Sketch inside add(), after all fallible arithmetic checks.
// New entries go after existing entries with the same priority.
let index = self.entries
    .iter()
    .position(|queued| queued.priority < entry.priority)
    .unwrap_or(self.entries.len());
self.entries.insert(index, entry);
self.entries.make_contiguous();

// pop() can then avoid shifting every remaining entry:
self.entries.pop_front().map(|entry| entry.item)

This candidate still has O(n) insertion; the improvement is removing repeated full sorting and making a complete drain linear. It is a suggestion to evaluate, not an accepted storage change.

Suggested investigation and fix notes

Deferred until trial/3 is merged into main. Recheck the merged source and tests first. The snippets are examples/proposals, not an approved patch or a change to frozen contracts.

Read ItemQueue, TaskQueue::run, and stable_item_queue_ties_extremes_and_drain in crates/lib/tests/event_contracts.rs. Inventory the sorted borrowed entries() contract before selecting storage.
Compare the sorted-contiguous deque candidate in the description with other compatible approaches. A plain BinaryHeap is insufficient: its slice/iteration is heap order, and requiring T: Ord or Clone would narrow the API.
If using the deque, establish contiguity after every mutator. Popping the front preserves that invariant. Keep priority/sequence exhaustion checks before any mutation, and retain historical watermarks after draining.
Extend ordering checks with insertion after partial drain, many equal-priority values, and payloads that implement neither Clone nor Ord. Preserve before/action/after abort and error behavior.
Record focused insert/drain measurements across increasing sizes; keep noisy wall-clock thresholds out of unit tests.

Illustrative entries() implementation only if every mutator establishes the invariant:

pub fn entries(&self) -> &[Item<T>] {
    let (ordered, wrapped) = self.entries.as_slices();
    debug_assert!(wrapped.is_empty());
    ordered
}

Start verification with cargo test -p stackpress-lib --test event_contracts --locked. See the standard BinaryHeap contract when comparing alternatives.

Implementation workflow: After the merge, follow .agents/workflows/rust-programming.md: prove the affected behavior, complete the three test-verified review rounds, and record relevant formatting/lints/docs, feature/platform scope, and applicable development coverage. Preserve unrelated changes.

Fixed on trial/3 in 644795f (merged as 64a5b70, task 00010 lane 1; not yet on main, so leaving open).

ItemQueue now keeps a sorted VecDeque: binary upper-bound insertion after equal priorities (FIFO ties), kept contiguous so entries() -> &[Item<T>] is unchanged.
Complexity: O(log n) comparisons + O(n) worst-case insertion movement, O(1) pop, O(n) full drain (was O(n²)). Not claiming heap-like insertion.
Tests: descending priority, FIFO ties, 400-operation mixed insert/remove with slice comparisons, front/back insertion after a full drain, retained watermarks, checked arithmetic and sequence exhaustion.

Coordinator-verified: fmt, Clippy -D warnings, Rustdoc -D warnings, cargo +1.96.0 check, 454 workspace tests, 856 doctests pass; lib production coverage 93.64%.

Fix owner review issues #11, #1, #2, #5 and lib parts of #4, #7 (task…

Navigation Menu

Repository navigation

The priority queue does more work than its contract requires #1

Problem

Evidence

Acceptance criteria

Code examples and suggested direction

Suggested investigation and fix notes

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

The priority queue does more work than its contract requires #1

Description

Problem

Evidence

Acceptance criteria

Code examples and suggested direction

Activity

cblanquera commented on Oct 26, 2026

Suggested investigation and fix notes

cblanquera commented on Oct 26, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions