From c6d40932f81edc656bbcc8dbd9d277aba543bc5b Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 15 Dec 2020 20:57:32 +0100 Subject: Unroll pkgCache::sHash 8 time, break up dependency Unroll pkgCache::sHash 8 times and break up the dependency between the iterations by expanding the calculation H(n) = 33 * H(n-1) + c 8 times rather than performing it 8 times. This seems to yield about a 0.4% performance improvement. I tried unrolling 4 and 2 bytes as well, those only having 3 ifs at the end rather than 1 small loop; but that was actually slower - potentially the code got to large and the cache went bonkers. I also tried unrolling 4 times instead of 8, thinking that smaller code might yield better results overall then, but that was slower as well. --- apt-pkg/pkgcache.cc | 18 ++++++++++++++++-- 1 file changed, 16 insertions(+), 2 deletions(-) diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc index 458860b0a..f7f3537aa 100644 --- a/apt-pkg/pkgcache.cc +++ b/apt-pkg/pkgcache.cc @@ -209,8 +209,22 @@ bool pkgCache::ReMap(bool const &Errorchecks) map_id_t pkgCache::sHash(StringView Str) const { uint32_t Hash = 5381; - for (auto I = Str.begin(); I != Str.end(); ++I) - Hash = 33 * Hash + tolower_ascii_unsafe(*I); + auto I = Str.begin(); + auto End = Str.end(); + for (; I + 7 < End; I += 8) + { + Hash = (33u * 33u * 33u * 33u * 33u * 33u * 33u * 33u * Hash + + 33u * 33u * 33u * 33u * 33u * 33u * 33u * tolower_ascii_unsafe(I[0]) + + 33u * 33u * 33u * 33u * 33u * 33u * tolower_ascii_unsafe(I[1]) + + 33u * 33u * 33u * 33u * 33u * tolower_ascii_unsafe(I[2]) + + 33u * 33u * 33u * 33u * tolower_ascii_unsafe(I[3]) + + 33u * 33u * 33u * tolower_ascii_unsafe(I[4]) + + 33u * 33u * tolower_ascii_unsafe(I[5]) + + 33u * tolower_ascii_unsafe(I[6]) + + tolower_ascii_unsafe(I[7])); + } + for (; I != End; ++I) + Hash = 33u * Hash + tolower_ascii_unsafe(*I); return Hash % HeaderP->GetHashTableSize(); } uint32_t pkgCache::CacheHash() -- cgit v1.2.3