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

2 files changed, 50 insertions, 48 deletions

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 <config.h>
 
 #include <apt-pkg/algorithms.h>
@@ -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<pkgCache::Package> Pkg() const
+   constexpr map_pointer<pkgCache::Package> Pkg() const noexcept
    {
       return isVersion() ? 0 : map_pointer<pkgCache::Package>{mapPtr()};
    }
    // \brief Return the version, if any, otherwise 0.
-   map_pointer<pkgCache::Version> Ver() const
+   constexpr map_pointer<pkgCache::Version> Ver() const noexcept
    {
       return isVersion() ? map_pointer<pkgCache::Version>{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<Lit>;
    // 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<int32_t>(var.value)} {}
+   constexpr Lit(Var var) noexcept : value{static_cast<int32_t>(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<pkgCache::Version, State> 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<const Clause *> &watches(Lit lit);
+   constexpr std::vector<const Clause *> &watches(Lit lit) noexcept;
 
    // \brief Heap of the remaining work.
    //
@@ -375,8 +375,8 @@ class Solver
    {
       return static_cast<level_type>(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> 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<Solver &>(*this)[r];
 }
@@ -612,7 +612,7 @@ struct std::hash<APT::Solver::Lit>
    std::size_t operator()(const APT::Solver::Lit &v) const noexcept { return hash_value(v.value); }
 };
 
-inline std::vector<const APT::Solver::Clause *> &APT::Solver::Solver::watches(Lit lit)
+constexpr std::vector<const APT::Solver::Clause *> &APT::Solver::Solver::watches(Lit lit) noexcept
 {
    return (*this)[lit.var()].watches[lit.sign()];
 }