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).

diff --git a/apt-pkg/contrib/string_view.h b/apt-pkg/contrib/string_view.h
index f158ef8d6c84da6fa5e41f29359def01c7ceb91e..c504edd27717178920875a34c421399d03601d6c 100644 (file)
--- 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 b0ba1597fffdce6b772a074cfebb2defac9d3814..67d4bc0075ec7d9a3944edef429baf4f497e02b1 100644 (file)
--- 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 f0b5a982eb2d4c50248c886584efb701e568b1ae..1d997678cbc76dfe2af0bfdd7ebe14ddd7560235 100644 (file)
--- 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;