From 37ae749b20485b6c8237d5b5a08cfdd58a2364e1 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 26 Dec 2018 12:39:56 +0100 Subject: cache hash: Use sse4.2 CRC32c on x86-64 where available This is more than twice as fast as adler32, but could be made another 50% faster by calculating crcs for 8 byte blocks in "parallel" (without data dependency) and then combining them. But that's complicated code. Reference measurements for hashing the cache 100 times: adler32=2.46s xxhash64=0.64 xxhash32=1.12 crc32c(this)=1.10 crc32c(opt)=0.44s --- apt-pkg/pkgcache.cc | 58 ++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 51 insertions(+), 7 deletions(-) diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc index 058e389a5..12c116901 100644 --- a/apt-pkg/pkgcache.cc +++ b/apt-pkg/pkgcache.cc @@ -231,10 +231,54 @@ map_id_t pkgCache::sHash(const char *Str) const return Hash % HeaderP->GetHashTableSize(); } +#if defined(__GNUC__) + +#if defined(__x86_64__) +__attribute__((target("sse4.2"))) static int hash32(int crc32, const unsigned char *input, size_t size) +{ + if (input == nullptr) + return 0; + + crc32 ^= 0xffffffffU; + while (size >= 8) { + crc32 = __builtin_ia32_crc32di(crc32, *(uint64_t *)input); + input += 8; + size -= 8; + } + + if (size >= 4) { + crc32 = __builtin_ia32_crc32si(crc32, *(uint32_t *)input); + input += 4; + size -= 4; + } + + if (size >= 2) { + crc32 = __builtin_ia32_crc32hi(crc32, *(uint16_t *)input); + input += 2; + size -= 2; + } + + if (size >= 1) { + crc32 = __builtin_ia32_crc32qi(crc32, *(uint8_t *)input); + input += 1; + size -= 1; + } + crc32 ^= 0xffffffffU; + return crc32; +} +#endif + +__attribute__((target("default"))) +#endif +static int hash32(int crc32, const unsigned char *input, size_t size) +{ + return adler32(crc32, input, size); +} + uint32_t pkgCache::CacheHash() { pkgCache::Header header = {}; - uLong adler = adler32(0L, Z_NULL, 0); + uLong adler = hash32(0L, Z_NULL, 0); if (Map.Size() < sizeof(header)) return adler; @@ -243,14 +287,14 @@ uint32_t pkgCache::CacheHash() header.Dirty = false; header.CacheFileSize = 0; - adler = adler32(adler, - reinterpret_cast(&header), - sizeof(header)); + adler = hash32(adler, + reinterpret_cast(&header), + sizeof(header)); if (Map.Size() > sizeof(header)) { - adler = adler32(adler, - static_cast(GetMap().Data()) + sizeof(header), - GetMap().Size() - sizeof(header)); + adler = hash32(adler, + static_cast(GetMap().Data()) + sizeof(header), + GetMap().Size() - sizeof(header)); } return adler; -- cgit v1.2.3 From 6018a849f46c7f701adbc4c2474de0b1177f3711 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 26 Dec 2018 12:40:06 +0100 Subject: configuration: Compare size first during lookup --- apt-pkg/contrib/configuration.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/apt-pkg/contrib/configuration.cc b/apt-pkg/contrib/configuration.cc index 1c000e586..997ef7423 100644 --- a/apt-pkg/contrib/configuration.cc +++ b/apt-pkg/contrib/configuration.cc @@ -252,7 +252,7 @@ Configuration::Item *Configuration::Lookup(Item *Head,const char *S, if (Len != 0) { for (; I != 0; Last = &I->Next, I = I->Next) - if ((Res = stringcasecmp(I->Tag,S,S + Len)) == 0) + if (Len == I->Tag.length() && (Res = stringcasecmp(I->Tag,S,S + Len)) == 0) break; } else -- cgit v1.2.3 From 563fedea263361b0786303f58dccc1a9a733e1d9 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 26 Dec 2018 12:40:09 +0100 Subject: debListParser: Avoid native arch lookup in ParseDepends We called low-level ParseDepends without an architecture each time, which means each call looked up the native architecture. Store the native architecture in the class and use that when calling low-level ParseDepends from the high-level ParseDepends(). This improves performance for a cache build from 2.7 to 2.5 seconds for me. Also avoid a call when stripping multiarch, as the native architecture is passed in. --- apt-pkg/deb/deblistparser.cc | 6 +++--- apt-pkg/deb/deblistparser.h | 1 + 2 files changed, 4 insertions(+), 3 deletions(-) diff --git a/apt-pkg/deb/deblistparser.cc b/apt-pkg/deb/deblistparser.cc index e8dff833d..80ca10e37 100644 --- a/apt-pkg/deb/deblistparser.cc +++ b/apt-pkg/deb/deblistparser.cc @@ -61,6 +61,7 @@ debListParser::debListParser(FileFd *File) : else forceEssential.emplace_back("apt"); forceImportant = _config->FindVector("pkgCacheGen::ForceImportant"); + myArch = _config->Find("APT::Architecture"); } /*}}}*/ // ListParser::Package - Return the package name /*{{{*/ @@ -621,12 +622,11 @@ const char *debListParser::ParseDepends(const char *Start,const char *Stop, // We don't want to confuse library users which can't handle MultiArch if (StripMultiArch == true) { - string const arch = _config->Find("APT::Architecture"); size_t const found = Package.rfind(':'); if (found != StringView::npos && (Package.substr(found) == ":any" || Package.substr(found) == ":native" || - Package.substr(found +1) == arch)) + Package.substr(found +1) == Arch)) Package = Package.substr(0,found); } @@ -848,7 +848,7 @@ bool debListParser::ParseDepends(pkgCache::VerIterator &Ver, StringView Version; unsigned int Op; - Start = ParseDepends(Start, Stop, Package, Version, Op, false, false, false); + Start = ParseDepends(Start, Stop, Package, Version, Op, false, false, false, myArch); if (Start == 0) return _error->Error("Problem parsing dependency %zu",static_cast(Key)); // TODO size_t const found = Package.rfind(':'); diff --git a/apt-pkg/deb/deblistparser.h b/apt-pkg/deb/deblistparser.h index 09b56665f..f02252d58 100644 --- a/apt-pkg/deb/deblistparser.h +++ b/apt-pkg/deb/deblistparser.h @@ -45,6 +45,7 @@ class APT_HIDDEN debListParser : public pkgCacheListParser std::vector forceEssential; std::vector forceImportant; std::string MD5Buffer; + std::string myArch; protected: pkgTagFile Tags; -- cgit v1.2.3