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?

View original on GitHub ↗

This issue has 1 comment on GitHub. Read the full discussion on GitHub ↗