Compare size before data when ordering cache bucket entries

This has the effect of significantly reducing actual string
comparisons, and should improve the performance of FindGrp
a bit, although it's hardly measureable (callgrind says it
uses 10% instructions less now).

3 files changed, 14 insertions, 3 deletions

diff --git a/apt-pkg/contrib/string_view.h b/apt-pkg/contrib/string_view.h
index f158ef8d6..c504edd27 100644
--- a/apt-pkg/contrib/string_view.h
+++ b/apt-pkg/contrib/string_view.h
@@ -112,6 +112,17 @@ public:
     constexpr size_t length() const { return size_; }
 };
 
+/**
+ * \brief Faster comparison for string views (compare size before data)
+ *
+ * Still stable, but faster than the normal ordering. */
+static inline int StringViewCompareFast(StringView a, StringView b) {
+    if (a.size() != b.size())
+        return a.size() - b.size();
+
+    return memcmp(a.data(), b.data(), a.size());
+}
+
 
 }
 
diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc
index b0ba1597f..67d4bc007 100644
--- a/apt-pkg/pkgcache.cc
+++ b/apt-pkg/pkgcache.cc
@@ -309,7 +309,7 @@ pkgCache::GrpIterator pkgCache::FindGrp(StringView Name) {
 	// Look at the hash bucket for the group
 	Group *Grp = GrpP + HeaderP->GrpHashTableP()[sHash(Name)];
 	for (; Grp != GrpP; Grp = GrpP + Grp->Next) {
-		int const cmp = Name.compare(ViewString(Grp->Name));
+		int const cmp = StringViewCompareFast(Name, ViewString(Grp->Name));
 		if (cmp == 0)
 			return GrpIterator(*this, Grp);
 		else if (cmp < 0)
diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc
index f0b5a982e..1d997678c 100644
--- a/apt-pkg/pkgcachegen.cc
+++ b/apt-pkg/pkgcachegen.cc
@@ -568,7 +568,7 @@ bool pkgCacheGenerator::NewGroup(pkgCache::GrpIterator &Grp, StringView Name)
    unsigned long const Hash = Cache.Hash(Name);
    map_pointer_t *insertAt = &Cache.HeaderP->GrpHashTableP()[Hash];
 
-   while (*insertAt != 0 && Name.compare(Cache.ViewString((Cache.GrpP + *insertAt)->Name)) > 0)
+   while (*insertAt != 0 && StringViewCompareFast(Name, Cache.ViewString((Cache.GrpP + *insertAt)->Name)) > 0)
       insertAt = &(Cache.GrpP + *insertAt)->Next;
    Grp->Next = *insertAt;
    *insertAt = Group;
@@ -616,7 +616,7 @@ bool pkgCacheGenerator::NewPackage(pkgCache::PkgIterator &Pkg, StringView Name,
       // Insert it into the hash table
       map_id_t const Hash = Cache.Hash(Name);
       map_pointer_t *insertAt = &Cache.HeaderP->PkgHashTableP()[Hash];
-      while (*insertAt != 0 && Name.compare(Cache.StrP + (Cache.GrpP + (Cache.PkgP + *insertAt)->Group)->Name) > 0)
+      while (*insertAt != 0 && StringViewCompareFast(Name, Cache.ViewString((Cache.GrpP + (Cache.PkgP + *insertAt)->Group)->Name)) > 0)
 	 insertAt = &(Cache.PkgP + *insertAt)->NextPackage;
       Pkg->NextPackage = *insertAt;
       *insertAt = Package;