From f378b41f9ab2493bcbc5892d482b18826b0b84c0 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 27 Sep 2016 18:59:11 +0200 Subject: 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). --- apt-pkg/contrib/string_view.h | 11 +++++++++++ apt-pkg/pkgcache.cc | 2 +- apt-pkg/pkgcachegen.cc | 4 ++-- 3 files changed, 14 insertions(+), 3 deletions(-) (limited to 'apt-pkg') 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; -- cgit v1.2.3-70-g09d2