From 5cbf75ac2e4845b9ed1026f1d11af129e54aaf5b Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sat, 31 Jan 2026 21:04:02 +0100 Subject: solver3: Remove dead code It used to be that we reached conflict clauses from the Solve() loop, however that is no longer the case, so remove the else branch, and turn the `else if (item.clause->optional)` into a new `else` with an `assert(item.clause->optional)`. --- apt-pkg/solver3.cc | 11 +---------- 1 file changed, 1 insertion(+), 10 deletions(-) (limited to 'apt-pkg/solver3.cc') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index e4449339e..ca32cd1d4 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -596,20 +596,11 @@ bool Solver::Solve() << "(try it: " << candidate->toString(cache) << ")\n"; must_succeed(Assume(*candidate, item.clause)); } - else if (item.clause->optional) - { - if (unlikely(debug >= 1)) - std::cerr << item.toString(cache) << "\n"; - } else { - abort(); + assert(item.clause->optional); if (unlikely(debug >= 1)) std::cerr << item.toString(cache) << "\n"; - // Enqueue produces the right error message for us here, given that reason has been assigned true already... - assert(value(item.clause->reason) == LiftedBool::True); - must_succeed(not Enqueue(~item.clause->reason, item.clause)); - assert(value(item.clause->reason) == LiftedBool::True); } // Must push to trail after any Assume() above. trail.push_back(Trail{Var(), item}); -- cgit v1.2.3-70-g09d2 From 7d5ec84c13227290cfb1bb83d27ae354200bcb02 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sat, 31 Jan 2026 21:59:32 +0100 Subject: solver3: Refactor Propagate() using lazy head/tail Calculate the head and the tail of the clause in Propagate() and check based on that if the clause is conflict/unit/undecided. Special care has been taken to avoid the calculation of tail when it is not necessary by placing it inside a helper lambda; as well as skipping the calculation when the clause is inactive. --- apt-pkg/solver3.cc | 42 ++++++++++++++++++------------------------ 1 file changed, 18 insertions(+), 24 deletions(-) (limited to 'apt-pkg/solver3.cc') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index ca32cd1d4..ed2382432 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -420,37 +420,31 @@ bool Solver::Propagate(const Clause *clause, Lit p) } // Check if the clause is unit, conflict, or undecided - Lit unit; - for (auto sol : clause->solutions) + auto not_false = [&](auto lit) { return value(lit) != LiftedBool::False; }; + auto head = std::ranges::find_if(clause->solutions, not_false); + auto find_tail = [&]() { return std::ranges::find_last_if(clause->solutions, not_false); }; + if (head == clause->solutions.end()) { - if (value(sol) == LiftedBool::False) - continue; - if (not unit.empty() || clause->optional) - { - // We found a second solution, so we are undecided - if (p == clause->reason) - return AddWork(Work{clause, decisionLevel()}); - return true; - } - - unit = sol; + // Conflict clause. If this clause is non-optional; reject its "reason". + if (not clause->optional) + return Enqueue(~clause->reason, clause); } - - // The clause is now either unit or conflict - if (not unit.empty()) + else if (value(clause->reason) != LiftedBool::True) { - // Unit clause. If it is an active clause, enqueue the unit literal. - if (value(clause->reason) == LiftedBool::True) - return Enqueue(unit, clause); - return true; + // Inactive clause, nothing to do + } + else if (not clause->optional && head == find_tail().begin()) + { + // Unit clause. Enqueue the only possible solution + return Enqueue(*head, clause); } else { - // Conflict clause. If this clause is non-optional; reject it's "reason". - if (not clause->optional) - return Enqueue(~clause->reason, clause); - return true; + // Undecided clause. If this is an activation, queue it for solving + if (p == clause->reason) + return AddWork(Work{clause, decisionLevel()}); } + return true; } void Solver::UndoOne() -- cgit v1.2.3-70-g09d2 From 7d84e1f830727ca5008566113e7dfd35df049bd6 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sat, 31 Jan 2026 22:33:40 +0100 Subject: solver3: Fix off-by-one missing optimization We were trying to compare the dependencies in the first version with the dependencies in later version, but our loop started at the first version as well due to an oversight in the use of the increment operator. Change the increment from postfix to prefix such that we start iterating with the 2nd version in the list only. This should yield minute performance optimizations: before: 12: 17.80% 0.00% apt libapt-pkg.so.7.0.0 [.] EDSP::ResolveExternal(char const*, pkgDepCache&, unsigned int, OpProgress*) 14: --17.80%--EDSP::ResolveExternal(char const*, pkgDepCache&, unsigned int, OpProgress*) 20: | | |--6.34%--APT::Solver::DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator) 44: | | --0.85%--APT::Solver::DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator) after: 12: 16.98% 0.00% apt libapt-pkg.so.7.0.0 [.] EDSP::ResolveExternal(char const*, pkgDepCache&, unsigned int, OpProgress*) 14: --16.98%--EDSP::ResolveExternal(char const*, pkgDepCache&, unsigned int, OpProgress*) 20: | | |--5.65%--APT::Solver::DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator) 42: | | --0.70%--APT::Solver::DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator) --- apt-pkg/solver3.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'apt-pkg/solver3.cc') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index ed2382432..2727c3a1d 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -1008,7 +1008,7 @@ void DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg) dep.GlobOr(start, end); // advances dep bool allHaveDep = true; - for (auto ver = Pkg.VersionList()++; allHaveDep && not ver.end(); ver++) + for (auto ver = ++Pkg.VersionList(); allHaveDep && not ver.end(); ver++) { bool haveDep = false; for (auto otherDep = ver.DependsList(); not haveDep && not otherDep.end();) -- cgit v1.2.3-70-g09d2 From e7c1adda00abd16285f5eb53c48587855f2a2992 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sat, 31 Jan 2026 22:41:04 +0100 Subject: solver3: Avoid manual delete[] in favor of RAII --- apt-pkg/solver3.cc | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'apt-pkg/solver3.cc') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 2727c3a1d..326e43529 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -1053,9 +1053,9 @@ Clause DependencySolver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache: } else { - auto all = start.AllTargets(); + std::unique_ptr all(start.AllTargets()); - for (auto tgt = all; *tgt; ++tgt) + for (auto tgt = all.get(); *tgt; ++tgt) { pkgCache::VerIterator tgti(cache, *tgt); @@ -1063,7 +1063,6 @@ Clause DependencySolver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache: std::cerr << "Adding work to item " << reason.toString(cache) << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << (clause.negative ? " (negative)" : "") << "\n"; clause.solutions.push_back(Var(pkgCache::VerIterator(cache, *tgt))); } - delete[] all; std::stable_sort(clause.solutions.begin() + begin, clause.solutions.end(), CompareProviders3{cache, policy, start.TargetPkg(), *this}); } if (start == end) -- cgit v1.2.3-70-g09d2 From 8e1750a22ef8be521bdb0542a78438f8d8abc54e Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sun, 1 Feb 2026 09:25:31 +0100 Subject: solver3: Minor style refactorings The for loop with if(foo) continue; return false; was highly unusual as were the bunch of uses of `!` instead of `not`. Gbp-dch: ignore --- apt-pkg/solver3.cc | 11 ++++------- 1 file changed, 4 insertions(+), 7 deletions(-) (limited to 'apt-pkg/solver3.cc') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 326e43529..d8d350dc5 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -87,7 +87,7 @@ std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty, bool sho out.append(dep.TargetPkg().FullName(true)); if (dep.TargetVer()) out.append(" (").append(dep.CompType()).append(" ").append(dep.TargetVer()).append(")"); - if (!(dep->CompareOp & pkgCache::Dep::Or)) + if (not(dep->CompareOp & pkgCache::Dep::Or)) break; out.append(" | "); } @@ -376,7 +376,7 @@ bool Solver::Enqueue(Lit lit, const Clause *reason) bool Solver::Propagate() { - while (!propQ.empty()) + while (not propQ.empty()) { Var var = propQ.front(); propQ.pop(); @@ -391,11 +391,8 @@ bool Solver::Propagate() Discover(lit.var()); for (auto clause : watches(lit)) - { - if (Propagate(clause, lit)) - continue; - return false; - } + if (not Propagate(clause, lit)) + return false; } return true; } -- cgit v1.2.3-70-g09d2 From 42dab6a46748ac80f0217212932b74af1af94017 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Fri, 6 Feb 2026 15:50:04 +0100 Subject: solver3: Use constexpr and noexcept in most places Aside from Clause, which initializes an std::vector and an std::forward_list, which do not have constexpr constructors in C++17, we can turn our inline functions constexpr. Using `constexpr` implies `inline`, so simplify that accordingly where needed. Adding noexcept to the function allows STL components to utilize more optimized code paths. Marking SameOrGroup as constexpr significantly improves performance due to being in the hot path and it now being inlined - removing branching by 10%. iolveiolver --- apt-pkg/solver3.cc | 24 ++++++++++-------- apt-pkg/solver3.h | 74 +++++++++++++++++++++++++++--------------------------- 2 files changed, 50 insertions(+), 48 deletions(-) (limited to 'apt-pkg/solver3.cc') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index d8d350dc5..6d818ed67 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -18,8 +18,6 @@ * classic APT solver. */ -#define APT_COMPILING_APT - #include #include @@ -59,7 +57,7 @@ Solver::Solver(pkgCache &cache) Solver::~Solver() = default; // This function determines if a work item is less important than another. -bool Solver::Work::operator<(Solver::Work const &b) const +constexpr bool Solver::Work::operator<(Solver::Work const &b) const noexcept { if ((not clause->optional && size < 2) != (not b.clause->optional && b.size < 2)) return not b.clause->optional && b.size < 2; @@ -130,7 +128,7 @@ std::string Solver::Work::toString(pkgCache &cache) const return out.str(); } -inline Var Solver::bestReason(Clause const *clause, Var var) const +constexpr Var Solver::bestReason(Clause const *clause, Var var) const noexcept { if (not clause) return Var{}; @@ -145,7 +143,7 @@ inline Var Solver::bestReason(Clause const *clause, Var var) const return clause->reason; } -inline LiftedBool Solver::value(Lit lit) const +constexpr LiftedBool Solver::value(Lit lit) const noexcept { return lit.sign() ? ~(*this)[lit.var()].assignment : (*this)[lit.var()].assignment; } @@ -417,9 +415,9 @@ bool Solver::Propagate(const Clause *clause, Lit p) } // Check if the clause is unit, conflict, or undecided - auto not_false = [&](auto lit) { return value(lit) != LiftedBool::False; }; + auto not_false = [&](auto lit) noexcept { return value(lit) != LiftedBool::False; }; auto head = std::ranges::find_if(clause->solutions, not_false); - auto find_tail = [&]() { return std::ranges::find_last_if(clause->solutions, not_false); }; + auto find_tail = [&]() noexcept { return std::ranges::find_last_if(clause->solutions, not_false); }; if (head == clause->solutions.end()) { // Conflict clause. If this clause is non-optional; reject its "reason". @@ -773,7 +771,11 @@ DependencySolver::DependencySolver(pkgCache &cache, pkgDepCache::Policy &policy, DependencySolver::~DependencySolver() = default; -static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b) +// This is called in the hot path of Discover() as we are trying to determine if a dependency +// is the same in all packages. +// Marking it constexpr causes it to be inlined, which significantly improves solver performance, +// around 5%; but it produces more LL cache misses. +constexpr bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b) noexcept { while (1) { @@ -813,14 +815,14 @@ const Clause *DependencySolver::RegisterClause(Clause &&clause) earlierDep.end() || (earlierDep->CompareOp & pkgCache::Dep::Or) || earlierDep.TargetPkg() != dep.TargetPkg()) continue; - if (std::none_of(earlierClause->solutions.begin(), earlierClause->solutions.end(), [&clause](auto earlierSol) + if (std::none_of(earlierClause->solutions.begin(), earlierClause->solutions.end(), [&clause](auto earlierSol) noexcept { return std::ranges::contains(clause.solutions, earlierSol); })) continue; if (earlierClause->optional == clause.optional) { - std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol) + std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol) noexcept { return not std::ranges::contains(clause.solutions, earlierSol); }); @@ -830,7 +832,7 @@ const Clause *DependencySolver::RegisterClause(Clause &&clause) else if (clause.optional) { // If say a Depends has fewer solution than a Recommends, remove the Recommend's extranous ones. - std::erase_if(clause.solutions, [&earlierClause, this](auto sol) + std::erase_if(clause.solutions, [&earlierClause, this](auto sol) noexcept { return not std::ranges::contains(earlierClause->solutions, sol); }); diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 4390d589b..380aa3ad6 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -56,8 +56,8 @@ class ContiguousCacheMap data_ = new V[size]{}; } - V &operator[](const K *key) { return data_[key->ID]; } - const V &operator[](const K *key) const { return data_[key->ID]; } + constexpr V &operator[](const K *key) noexcept { return data_[key->ID]; } + constexpr const V &operator[](const K *key) const noexcept { return data_[key->ID]; } ~ContiguousCacheMap() { delete[] data_; } // Delete copy constructors for memory safety (rule of 3) @@ -136,45 +136,45 @@ struct Var { uint32_t value; - explicit constexpr Var(uint32_t value = 0) : value{value} {} - explicit Var(pkgCache::PkgIterator const &Pkg) : value(uint32_t(Pkg.MapPointer()) << 1) {} - explicit Var(pkgCache::VerIterator const &Ver) : value(uint32_t(Ver.MapPointer()) << 1 | 1) {} + explicit constexpr Var(uint32_t value = 0) noexcept : value{value} {} + explicit Var(pkgCache::PkgIterator const &Pkg) noexcept : value(uint32_t(Pkg.MapPointer()) << 1) {} + explicit Var(pkgCache::VerIterator const &Ver) noexcept : value(uint32_t(Ver.MapPointer()) << 1 | 1) {} - inline constexpr bool isVersion() const { return value & 1; } - inline constexpr uint32_t mapPtr() const { return value >> 1; } + constexpr bool isVersion() const noexcept { return value & 1; } + constexpr uint32_t mapPtr() const noexcept { return value >> 1; } // \brief Return the package, if any, otherwise 0. - map_pointer Pkg() const + constexpr map_pointer Pkg() const noexcept { return isVersion() ? 0 : map_pointer{mapPtr()}; } // \brief Return the version, if any, otherwise 0. - map_pointer Ver() const + constexpr map_pointer Ver() const noexcept { return isVersion() ? map_pointer{mapPtr()} : 0; } // \brief Return the package iterator if storing a package, or an empty one - pkgCache::PkgIterator Pkg(pkgCache &cache) const + constexpr pkgCache::PkgIterator Pkg(pkgCache &cache) const noexcept { return isVersion() ? pkgCache::PkgIterator() : pkgCache::PkgIterator(cache, cache.PkgP + Pkg()); } // \brief Return the version iterator if storing a package, or an empty end. - pkgCache::VerIterator Ver(pkgCache &cache) const + constexpr pkgCache::VerIterator Ver(pkgCache &cache) const noexcept { return isVersion() ? pkgCache::VerIterator(cache, cache.VerP + Ver()) : pkgCache::VerIterator(); } // \brief Return a package, cast from version if needed - pkgCache::PkgIterator CastPkg(pkgCache &cache) const + constexpr pkgCache::PkgIterator CastPkg(pkgCache &cache) const noexcept { return isVersion() ? Ver(cache).ParentPkg() : Pkg(cache); } // \brief Check if there is no reason. - constexpr bool empty() const { return value == 0; } + constexpr bool empty() const noexcept { return value == 0; } constexpr bool operator!=(Var const other) const noexcept { return value != other.value; } constexpr bool operator==(Var const other) const noexcept { return value == other.value; } /// \brief Negate - constexpr Lit operator~() const; + constexpr Lit operator~() const noexcept; std::string toString(pkgCache &cache) const { @@ -196,21 +196,21 @@ struct Lit private: friend struct std::hash; // Private constructor from a number, to be used with operator~ - explicit constexpr Lit(int32_t value) : value{value} {} + explicit constexpr Lit(int32_t value) noexcept : value{value} {} int32_t value; public: - constexpr Lit() : value{0} {} + constexpr Lit() noexcept : value{0} {} // SAFETY: value must be 31 bit, one bit is needed for the sign. - constexpr Lit(Var var) : value{static_cast(var.value)} {} + constexpr Lit(Var var) noexcept : value{static_cast(var.value)} {} // Accessors - constexpr Var var() const { return Var(std::abs(value)); } - constexpr bool sign() const { return value < 0; } - constexpr Lit operator~() const { return Lit(-value); } + constexpr Var var() const noexcept { return Var(std::abs(value)); } + constexpr bool sign() const noexcept { return value < 0; } + constexpr Lit operator~() const noexcept { return Lit(-value); } // Properties - constexpr bool empty() const { return value == 0; } + constexpr bool empty() const noexcept { return value == 0; } constexpr bool operator!=(Lit const other) const noexcept { return value != other.value; } constexpr bool operator==(Lit const other) const noexcept { return value == other.value; } @@ -250,12 +250,12 @@ struct Clause std::string toString(pkgCache &cache, bool pretty = false, bool showMerged = true) const; }; -constexpr Lit Solver::Var::operator~() const +constexpr Lit Solver::Var::operator~() const noexcept { return ~Lit(*this); } -inline LiftedBool operator~(LiftedBool value) +constexpr LiftedBool operator~(LiftedBool value) noexcept { switch (value) { @@ -307,29 +307,29 @@ class Solver ContiguousCacheMap verStates; // \brief Helper function for safe access to package state. - inline State &operator[](const pkgCache::Package *P) + constexpr State &operator[](const pkgCache::Package *P) noexcept { return pkgStates[P]; } - inline const State &operator[](const pkgCache::Package *P) const + constexpr const State &operator[](const pkgCache::Package *P) const noexcept { return pkgStates[P]; } // \brief Helper function for safe access to version state. - inline State &operator[](const pkgCache::Version *V) + constexpr State &operator[](const pkgCache::Version *V) noexcept { return verStates[V]; } - inline const State &operator[](const pkgCache::Version *V) const + constexpr const State &operator[](const pkgCache::Version *V) const noexcept { return verStates[V]; } // \brief Helper function for safe access to either state. - inline State &operator[](Var r); - inline const State &operator[](Var r) const; + constexpr State &operator[](Var r) noexcept; + constexpr const State &operator[](Var r) const noexcept; - inline std::vector &watches(Lit lit); + constexpr std::vector &watches(Lit lit) noexcept; // \brief Heap of the remaining work. // @@ -375,8 +375,8 @@ class Solver { return static_cast(trailLim.size()); } - inline Var bestReason(Clause const *clause, Var var) const; - inline LiftedBool value(Lit lit) const; + constexpr Var bestReason(Clause const *clause, Var var) const noexcept; + constexpr LiftedBool value(Lit lit) const noexcept; public: // \brief Revert to the previous decision level. @@ -514,9 +514,9 @@ struct APT::Solver::Solver::Work /// Number of valid choices at insertion time size_t size{0}; - bool operator<(APT::Solver::Solver::Work const &b) const; + constexpr bool operator<(APT::Solver::Solver::Work const &b) const noexcept; std::string toString(pkgCache &cache) const; - inline Work(const Clause *clause, level_type level) : clause(clause), level(level) {} + constexpr Work(const Clause *clause, level_type level) noexcept : clause(clause), level(level) {} }; /** @@ -582,7 +582,7 @@ struct APT::Solver::Solver::Trail std::optional work; }; -inline APT::Solver::Solver::State &APT::Solver::Solver::operator[](APT::Solver::Var r) +constexpr APT::Solver::Solver::State &APT::Solver::Solver::operator[](APT::Solver::Var r) noexcept { if (auto P = r.Pkg()) return (*this)[cache.PkgP + P]; @@ -591,7 +591,7 @@ inline APT::Solver::Solver::State &APT::Solver::Solver::operator[](APT::Solver:: return *rootState.get(); } -inline const APT::Solver::Solver::State &APT::Solver::Solver::operator[](APT::Solver::Var r) const +constexpr const APT::Solver::Solver::State &APT::Solver::Solver::operator[](APT::Solver::Var r) const noexcept { return const_cast(*this)[r]; } @@ -612,7 +612,7 @@ struct std::hash std::size_t operator()(const APT::Solver::Lit &v) const noexcept { return hash_value(v.value); } }; -inline std::vector &APT::Solver::Solver::watches(Lit lit) +constexpr std::vector &APT::Solver::Solver::watches(Lit lit) noexcept { return (*this)[lit.var()].watches[lit.sign()]; } -- cgit v1.2.3-70-g09d2