diff options
author | Julian Andres Klode <julian.klode@canonical.com> | 2020-12-13 21:07:03 +0100 |
---|---|---|
committer | Julian Andres Klode <julian.klode@canonical.com> | 2020-12-15 13:47:22 +0100 |
commit | 1460eebf2abe913df964e031eff081a57f043697 (patch) | |
tree | be92fe9f5d240d7d448f57805445fe20a265e79b /apt-pkg | |
parent | b6c8c5ce2b255eb03554435a620934d47a2a14d5 (diff) |
Use XXH3 for cache, hash table hashing
XXH3 is faster than both our CRC32c implementation as well
as DJB hash for hash table hashing, so meh, let's switch to
it.
Diffstat (limited to 'apt-pkg')
-rw-r--r-- | apt-pkg/CMakeLists.txt | 2 | ||||
-rw-r--r-- | apt-pkg/pkgcache.cc | 74 | ||||
-rw-r--r-- | apt-pkg/pkgcachegen.h | 8 |
3 files changed, 20 insertions, 64 deletions
diff --git a/apt-pkg/CMakeLists.txt b/apt-pkg/CMakeLists.txt index 7e51b1775..5c97493af 100644 --- a/apt-pkg/CMakeLists.txt +++ b/apt-pkg/CMakeLists.txt @@ -49,6 +49,7 @@ target_include_directories(apt-pkg $<$<BOOL:${SYSTEMD_FOUND}>:${SYSTEMD_INCLUDE_DIRS}> ${ICONV_INCLUDE_DIRS} $<$<BOOL:${GCRYPT_FOUND}>:${GCRYPT_INCLUDE_DIRS}> + $<$<BOOL:${XXHASH_FOUND}>:${XXHASH_INCLUDE_DIRS}> ) target_link_libraries(apt-pkg @@ -63,6 +64,7 @@ target_link_libraries(apt-pkg $<$<BOOL:${SYSTEMD_FOUND}>:${SYSTEMD_LIBRARIES}> ${ICONV_LIBRARIES} $<$<BOOL:${GCRYPT_FOUND}>:${GCRYPT_LIBRARIES}> + $<$<BOOL:${XXHASH_FOUND}>:${XXHASH_LIBRARIES}> ) set_target_properties(apt-pkg PROPERTIES VERSION ${MAJOR}.${MINOR}) set_target_properties(apt-pkg PROPERTIES SOVERSION ${MAJOR}) diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc index 64c97811a..458860b0a 100644 --- a/apt-pkg/pkgcache.cc +++ b/apt-pkg/pkgcache.cc @@ -31,7 +31,6 @@ #include <apt-pkg/strutl.h> #include <apt-pkg/version.h> -#include <zlib.h> #include <algorithm> #include <sstream> #include <string> @@ -39,6 +38,7 @@ #include <stddef.h> #include <string.h> #include <sys/stat.h> +#include <xxhash.h> #include <apti18n.h> /*}}}*/ @@ -213,79 +213,35 @@ map_id_t pkgCache::sHash(StringView Str) const Hash = 33 * Hash + tolower_ascii_unsafe(*I); return Hash % HeaderP->GetHashTableSize(); } - -#ifdef HAVE_FMV_SSE42_AND_CRC32 -__attribute__((target("sse4.2"))) static uint32_t hash32(uint32_t crc32, const unsigned char *input, size_t size) -{ - if (input == nullptr) - return 0; - - crc32 ^= 0xffffffffU; -#ifdef HAVE_FMV_SSE42_AND_CRC32DI - while (size >= 8) { - crc32 = __builtin_ia32_crc32di(crc32, *(uint64_t *)input); - input += 8; - size -= 8; - } - - if (size >= 4) { -#else - while (size >= 4) { -#endif - 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; -} - -__attribute__((target("default"))) -#endif -static uint32_t hash32(uint32_t crc32, const unsigned char *input, size_t size) -{ - return adler32(crc32, input, size); -} - uint32_t pkgCache::CacheHash() { pkgCache::Header header = {}; - uLong adler = hash32(0L, Z_NULL, 0); + XXH3_state_t *state = XXH3_createState(); if (Map.Size() < sizeof(header)) - return adler; + return 0; + + XXH3_64bits_reset(state); memcpy(&header, GetMap().Data(), sizeof(header)); header.Dirty = false; header.CacheFileSize = 0; - adler = hash32(adler, - reinterpret_cast<const unsigned char *>(PACKAGE_VERSION), - APT_ARRAY_SIZE(PACKAGE_VERSION)); + XXH3_64bits_update(state, + reinterpret_cast<const unsigned char *>(PACKAGE_VERSION), + APT_ARRAY_SIZE(PACKAGE_VERSION)); - adler = hash32(adler, - reinterpret_cast<const unsigned char *>(&header), - sizeof(header)); + XXH3_64bits_update(state, + reinterpret_cast<const unsigned char *>(&header), + sizeof(header)); if (Map.Size() > sizeof(header)) { - adler = hash32(adler, - static_cast<const unsigned char *>(GetMap().Data()) + sizeof(header), - GetMap().Size() - sizeof(header)); + XXH3_64bits_update(state, + static_cast<const unsigned char *>(GetMap().Data()) + sizeof(header), + GetMap().Size() - sizeof(header)); } - return adler; + return XXH3_64bits_digest(state) & 0xFFFFFFFF; } /*}}}*/ // Cache::FindPkg - Locate a package by name /*{{{*/ diff --git a/apt-pkg/pkgcachegen.h b/apt-pkg/pkgcachegen.h index f5b4c80b3..9a88b45e7 100644 --- a/apt-pkg/pkgcachegen.h +++ b/apt-pkg/pkgcachegen.h @@ -29,6 +29,8 @@ #endif #include <apt-pkg/string_view.h> +#include <xxhash.h> + class FileFd; class pkgSourceList; class OpProgress; @@ -63,11 +65,7 @@ class APT_HIDDEN pkgCacheGenerator /*{{{*/ }; struct hash { uint32_t operator()(string_pointer const &that) const { - uint32_t Hash = 5381; - const char * const end = that.data() + that.size; - for (const char *I = that.data(); I != end; ++I) - Hash = 33 * Hash + *I; - return Hash; + return XXH3_64bits(that.data(), that.size) & 0xFFFFFFFF; } }; |