From 88cad6148797c399764333fbae3ade3036eb7dc3 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 13 Aug 2024 11:47:06 +0200 Subject: Add a FIXME around the heap compaction Our work heap is currently cleaned from deeper levels by removing the entries from the heap and then remaking the heap which is very inefficient. We should mark the items as erased instead, and only do the remove & make_heap dance if we have a lot of erased entries in there. Possibly we maybe should use a structure that actually allows removing entries, that is, an std::set, but that warrants more investigation on performance aspects. --- apt-pkg/solver3.cc | 2 ++ 1 file changed, 2 insertions(+) (limited to 'apt-pkg/solver3.cc') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 7aa0bd0b2..328c52f99 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -766,6 +766,8 @@ bool APT::Solver::Pop() UndoOne(); // We need to remove any work that is at a higher depth. + // FIXME: We should just mark the entries as erased and only do a compaction + // of the heap once we have a lot of erased entries in it. choices.pop_back(); work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool { return w.depth > depth() || w.erased; }), -- cgit v1.2.3-70-g09d2