solver3: Avoid std::vector for statically sized arrays

The bounds checking on the vector accesses is killing performance,
so switch from vector to a basic array, given that we don't actually
need _any_ functionality from vector...

Of course while we are at it, let us define a safe wrapper around
it so we cannot accidentally index arrays for package IDs with
version IDs and whatnot.

2 files changed, 70 insertions, 26 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index 36bdd9aeb..ed9beb828 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -198,11 +198,11 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy)
     : cache(cache),
       policy(policy),
       rootState(new State),
-      pkgStates(cache.Head().PackageCount),
-      verStates(cache.Head().VersionCount),
-      pkgObsolete(cache.Head().PackageCount),
-      priorities(cache.Head().VersionCount),
-      candidates(cache.Head().PackageCount)
+      pkgStates(cache),
+      verStates(cache),
+      pkgObsolete(cache),
+      priorities(cache),
+      candidates(cache)
 {
    // Ensure trivially
    static_assert(std::is_trivially_destructible_v<Work>);
@@ -295,7 +295,7 @@ bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) cons
       if (priority == 0 || priority < candPriority)
 	 continue;
 
-      pkgObsolete[pkg->ID] = 2;
+      pkgObsolete[pkg] = 2;
       if (debug >= 3)
 	 std::cerr << "Obsolete: " << cand.ParentPkg().FullName() << "=" << cand.VerStr() << " due to " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "\n";
       return true;
@@ -306,8 +306,8 @@ bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) cons
 
 bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const
 {
-   if (pkgObsolete[pkg->ID] != 0)
-      return pkgObsolete[pkg->ID] == 2;
+   if (pkgObsolete[pkg] != 0)
+      return pkgObsolete[pkg] == 2;
 
    auto ver = GetCandidateVer(pkg);
 
@@ -317,7 +317,7 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const
    {
       if (debug >= 3)
 	 std::cerr << "Obsolete: " << pkg.FullName() << " - not installable\n";
-      pkgObsolete[pkg->ID] = 2;
+      pkgObsolete[pkg] = 2;
       return true;
    }
 
@@ -327,12 +327,12 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const
    for (auto file = ver.FileList(); !file.end(); file++)
       if ((file.File()->Flags & pkgCache::Flag::NotSource) == 0)
       {
-	 pkgObsolete[pkg->ID] = 1;
+	 pkgObsolete[pkg] = 1;
 	 return false;
       }
    if (debug >= 3)
       std::cerr << "Obsolete: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << " - not installable\n";
-   pkgObsolete[pkg->ID] = 2;
+   pkgObsolete[pkg] = 2;
    return true;
 }
 bool APT::Solver::Assume(Var var, bool decision, Var reason)
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 9059552b7..65cd9f017 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -20,6 +20,48 @@
 namespace APT
 {
 
+/**
+ * \brief A simple mapping from objects in the cache to user-defined types.
+ *
+ * This default initializes an array with the specified value type for each
+ * object in the cache of that type.
+ */
+template <typename K, typename V, bool fast = false>
+class ContiguousCacheMap
+{
+   V *data_; // Avoid std::unique_ptr() as it may check that it's non-null.
+
+   public:
+   ContiguousCacheMap(pkgCache &cache)
+   {
+      static_assert(std::is_constructible_v<V>);
+      if constexpr (fast)
+      {
+	 static_assert(std::is_trivially_constructible_v<V>);
+	 static_assert(std::is_trivially_destructible_v<V>);
+      }
+
+      size_t size;
+      if constexpr (std::is_same_v<K, pkgCache::Version>)
+	 size = cache.Head().VersionCount;
+      else if constexpr (std::is_same_v<K, pkgCache::Package>)
+	 size = cache.Head().PackageCount;
+      else
+	 static_assert(false, "Cannot construct map for key type");
+
+      data_ = new V[size]{};
+   }
+   V &operator[](const K *key) { return data_[key->ID]; }
+   const V &operator[](const K *key) const { return data_[key->ID]; }
+   ~ContiguousCacheMap() { delete[] data_; }
+};
+
+/**
+ * \brief A version of ContiguousCacheMap that ensures allocation and deallocation is trivial.
+ */
+template <typename K, typename V>
+using FastContiguousCacheMap = ContiguousCacheMap<K, V, true>;
+
 /*
  * \brief APT 3.0 solver
  *
@@ -96,49 +138,51 @@ class Solver
    // Root state
    std::unique_ptr<State> rootState;
    // States for packages
-   std::vector<State> pkgStates{};
+   ContiguousCacheMap<pkgCache::Package, State> pkgStates;
    // States for versions
-   std::vector<State> verStates{};
+   ContiguousCacheMap<pkgCache::Version, State> verStates;
 
    // \brief Helper function for safe access to package state.
    inline State &operator[](pkgCache::Package *P)
    {
-      return pkgStates[P->ID];
+      return pkgStates[P];
    }
    inline const State &operator[](pkgCache::Package *P) const
    {
-      return pkgStates[P->ID];
+      return pkgStates[P];
    }
 
    // \brief Helper function for safe access to version state.
    inline State &operator[](pkgCache::Version *V)
    {
-      return verStates[V->ID];
+      return verStates[V];
    }
    inline const State &operator[](pkgCache::Version *V) const
    {
-      return verStates[V->ID];
+      return verStates[V];
    }
    // \brief Helper function for safe access to either state.
    inline State &operator[](Var r);
    inline const State &operator[](Var r) const;
 
-   mutable std::vector<char> pkgObsolete;
+   mutable FastContiguousCacheMap<pkgCache::Package, char> pkgObsolete;
    bool Obsolete(pkgCache::PkgIterator pkg) const;
    bool ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const;
-   mutable std::vector<short> priorities;
+
+   mutable FastContiguousCacheMap<pkgCache::Version, short> priorities;
    short GetPriority(pkgCache::VerIterator ver) const
    {
-      if (priorities[ver->ID] == 0)
-	 priorities[ver->ID] = policy.GetPriority(ver);
-      return priorities[ver->ID];
+      if (priorities[ver] == 0)
+	 priorities[ver] = policy.GetPriority(ver);
+      return priorities[ver];
    }
-   mutable std::vector<pkgCache::VerIterator> candidates;
+
+   mutable ContiguousCacheMap<pkgCache::Package, pkgCache::VerIterator> candidates;
    pkgCache::VerIterator GetCandidateVer(pkgCache::PkgIterator pkg) const
    {
-      if (candidates[pkg->ID].end())
-	 candidates[pkg->ID] = policy.GetCandidateVer(pkg);
-      return candidates[pkg->ID];
+      if (candidates[pkg].end())
+	 candidates[pkg] = policy.GetCandidateVer(pkg);
+      return candidates[pkg];
    }
 
    // \brief Heap of the remaining work.