perf(process_manager): replace sort with BinaryHeap in process_id_to_prune_from_meta
Resolved 💬 1 comment Opened Apr 30, 2026 by thisusedtobekshitijshresth Closed Jul 1, 2026
optimize: improve process pruning performance with BinaryHeap
Replace O(n log n) sorting operations with O(n) BinaryHeap-based algorithm
for process pruning in unified exec manager. This reduces computational
complexity and improves memory usage while maintaining identical behavior.
Performance improvement:
- Protected set identification: O(n log 8) → O(n)
- Candidate selection: O(n log n) → O(n)
- Eliminates full array allocations
All existing tests pass with no functional changes.
Implementation
let mut recent: BinaryHeap<Reverse<(Instant, i32)>> = BinaryHeap::with_capacity(9);
for &(process_id, last_used, _) in meta {
if recent.len() < 8 {
recent.push(Reverse((last_used, process_id)));
} else if let Some(&Reverse((min_time, _))) = recent.peek() {
if last_used > min_time {
recent.pop();
recent.push(Reverse((last_used, process_id)));
}
}
}
let protected: HashSet<i32> = recent.into_iter().map(|Reverse((_, pid))| pid).collect();
let mut best_exited: Option<(Instant, i32)> = None;
let mut best_any: Option<(Instant, i32)> = None;
for &(process_id, last_used, exited) in meta {
if protected.contains(&process_id) {
continue;
}
if best_any.map_or(true, |(t, _)| last_used < t) {
best_any = Some((last_used, process_id));
}
if exited && best_exited.map_or(true, |(t, _)| last_used < t) {
best_exited = Some((last_used, process_id));
}
}
best_exited.or(best_any).map(|(_, process_id)| process_id)
Would you invite my PR for this?
This issue has 1 comment on GitHub. Read the full discussion on GitHub ↗