increase hashtable size for packages/groups by factor 5

It also makes the size configureable, so it can be adapted in the future
without the need for an abi break - and even by users…

The increase was long overdue as it gives a >10% decrease in runtime of
e.g. 'apt-get check -s'. Some (useless) benchmark with 69933 groups and
187796 packages without a pre-built cache:
time apt-get check -so APT::Cache-HashTableSize=1 → 20m
time apt-get check -so APT::Cache-HashTableSize=1000 → 6,41s
time apt-get check -so APT::Cache-HashTableSize=2000 → 5,64s (old)
time apt-get check -so APT::Cache-HashTableSize=3000 → 5,30s
time apt-get check -so APT::Cache-HashTableSize=5000 → 5,08s
time apt-get check -so APT::Cache-HashTableSize=6000 → 5,05s
time apt-get check -so APT::Cache-HashTableSize=7000 → 5,02s
time apt-get check -so APT::Cache-HashTableSize=8000 → 5,00s
time apt-get check -so APT::Cache-HashTableSize=9000 → 4,98s
time apt-get check -so APT::Cache-HashTableSize=10000 → 4,96s (new)
time apt-get check -so APT::Cache-HashTableSize=15000 → 4,90s
time apt-get check -so APT::Cache-HashTableSize=20000 → 4,86s
time apt-get check -so APT::Cache-HashTableSize=30000 → 4,77s
time apt-get check -so APT::Cache-HashTableSize=40000 → 4,74s
time apt-get check -so APT::Cache-HashTableSize=50000 → 4,73s
time apt-get check -so APT::Cache-HashTableSize=60000 → 4,71s

The gap increases further for operations which have more package
lookups. Factor 5 was chosen as higher values do not provide any
really significant timing advantage anymore compared to the memory
increase in my testing and there is always the possibility to increase
it now if that changes. (also most users will not have 3 releases and
4 architectures in the cache, so theirs will be much smaller and faster).

diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc
index 4fbdc93d519a56085b5befa38aa14abd618f2833..7b092f07e64a5c01802f7f2eac3a280b83cb6e0d 100644 (file)
--- a/apt-pkg/pkgcache.cc
+++ b/apt-pkg/pkgcache.cc
@@ -54,8 +54,8 @@ pkgCache::Header::Header()
    
    /* Whenever the structures change the major version should be bumped,
       whenever the generator changes the minor version should be bumped. */
-   MajorVersion = 9;
-   MinorVersion = 2;
+   MajorVersion = 10;
+   MinorVersion = 0;
    Dirty = false;
    
    HeaderSz = sizeof(pkgCache::Header);
@@ -85,8 +85,7 @@ pkgCache::Header::Header()
    StringList = 0;
    VerSysName = 0;
    Architecture = 0;
-   memset(PkgHashTable,0,sizeof(PkgHashTable));
-   memset(GrpHashTable,0,sizeof(GrpHashTable));
+   HashTableSize = _config->FindI("APT::Cache-HashTableSize", 10 * 1048);
    memset(Pools,0,sizeof(Pools));
 
    CacheFileSize = 0;
@@ -194,7 +193,7 @@ unsigned long pkgCache::sHash(const string &Str) const
    unsigned long Hash = 0;
    for (string::const_iterator I = Str.begin(); I != Str.end(); ++I)
       Hash = 41 * Hash + tolower_ascii(*I);
-   return Hash % _count(HeaderP->PkgHashTable);
+   return Hash % HeaderP->HashTableSize;
 }
 
 unsigned long pkgCache::sHash(const char *Str) const
@@ -202,7 +201,7 @@ unsigned long pkgCache::sHash(const char *Str) const
    unsigned long Hash = tolower_ascii(*Str);
    for (const char *I = Str + 1; *I != 0; ++I)
       Hash = 41 * Hash + tolower_ascii(*I);
-   return Hash % _count(HeaderP->PkgHashTable);
+   return Hash % HeaderP->HashTableSize;
 }
                                                                        /*}}}*/
 // Cache::SingleArchFindPkg - Locate a package by name                 /*{{{*/
@@ -213,7 +212,7 @@ unsigned long pkgCache::sHash(const char *Str) const
 pkgCache::PkgIterator pkgCache::SingleArchFindPkg(const string &Name)
 {
    // Look at the hash bucket
-   Package *Pkg = PkgP + HeaderP->PkgHashTable[Hash(Name)];
+   Package *Pkg = PkgP + HeaderP->PkgHashTable()[Hash(Name)];
    for (; Pkg != PkgP; Pkg = PkgP + Pkg->Next)
    {
       if (unlikely(Pkg->Name == 0))
@@ -278,7 +277,7 @@ pkgCache::GrpIterator pkgCache::FindGrp(const string &Name) {
                return GrpIterator(*this,0);
 
        // Look at the hash bucket for the group
-       Group *Grp = GrpP + HeaderP->GrpHashTable[sHash(Name)];
+       Group *Grp = GrpP + HeaderP->GrpHashTable()[sHash(Name)];
        for (; Grp != GrpP; Grp = GrpP + Grp->Next) {
                if (unlikely(Grp->Name == 0))
                   continue;
@@ -432,10 +431,10 @@ void pkgCache::GrpIterator::operator ++(int)
       S = Owner->GrpP + S->Next;
 
    // Follow the hash table
-   while (S == Owner->GrpP && (HashIndex+1) < (signed)_count(Owner->HeaderP->GrpHashTable))
+   while (S == Owner->GrpP && (HashIndex+1) < (signed)Owner->HeaderP->HashTableSize)
    {
       HashIndex++;
-      S = Owner->GrpP + Owner->HeaderP->GrpHashTable[HashIndex];
+      S = Owner->GrpP + Owner->HeaderP->GrpHashTable()[HashIndex];
    }
 }
                                                                        /*}}}*/
@@ -449,10 +448,10 @@ void pkgCache::PkgIterator::operator ++(int)
       S = Owner->PkgP + S->Next;
 
    // Follow the hash table
-   while (S == Owner->PkgP && (HashIndex+1) < (signed)_count(Owner->HeaderP->PkgHashTable))
+   while (S == Owner->PkgP && (HashIndex+1) < (signed)Owner->HeaderP->HashTableSize)
    {
       HashIndex++;
-      S = Owner->PkgP + Owner->HeaderP->PkgHashTable[HashIndex];
+      S = Owner->PkgP + Owner->HeaderP->PkgHashTable()[HashIndex];
    }
 }
                                                                        /*}}}*/

diff --git a/apt-pkg/pkgcache.h b/apt-pkg/pkgcache.h
index 55f0187f9fd6195e5040abf93e21c22132442fc2..b6b2894cffeb688f966f5b2806870543e8c7b3e5 100644 (file)
--- a/apt-pkg/pkgcache.h
+++ b/apt-pkg/pkgcache.h
@@ -304,20 +304,20 @@ struct pkgCache::Header
        stores this information so future additions can make use of any unused pool
        blocks. */
    DynamicMMap::Pool Pools[9];
-   
+
    /** \brief hash tables providing rapid group/package name lookup
 
-       Each group/package name is inserted into the hash table using pkgCache::Hash(const &string)
+       Each group/package name is inserted into a hash table using pkgCache::Hash(const &string)
        By iterating over each entry in the hash table it is possible to iterate over
        the entire list of packages. Hash Collisions are handled with a singly linked
        list of packages based at the hash item. The linked list contains only
        packages that match the hashing function.
        In the PkgHashTable is it possible that multiple packages have the same name -
        these packages are stored as a sequence in the list.
-
-       Beware: The Hashmethod assumes that the hash table sizes are equal */
-   map_ptrloc PkgHashTable[64*1048];
-   map_ptrloc GrpHashTable[64*1048];
+       The size of both tables is the same. */
+   unsigned int HashTableSize;
+   map_ptrloc * PkgHashTable() const { return (map_ptrloc*) (this + 1); }
+   map_ptrloc * GrpHashTable() const { return PkgHashTable() + HashTableSize; }
 
    /** \brief Size of the complete cache file */
    unsigned long  CacheFileSize;

diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc
index 9615b4c22303347cf6095f659c76a195103b28bb..360f197363fc45cb8cdb79bed279c0ddf960421c 100644 (file)
--- a/apt-pkg/pkgcachegen.cc
+++ b/apt-pkg/pkgcachegen.cc
@@ -73,6 +73,11 @@ pkgCacheGenerator::pkgCacheGenerator(DynamicMMap *pMap,OpProgress *Prog) :
 
       // Starting header
       *Cache.HeaderP = pkgCache::Header();
+
+      // make room for the hashtables for packages and groups
+      if (Map.RawAllocate(2 * (Cache.HeaderP->HashTableSize * sizeof(map_ptrloc))) == 0)
+        return;
+
       map_ptrloc const idxVerSysName = WriteStringInMap(_system->VS->Label);
       if (unlikely(idxVerSysName == 0))
         return;
@@ -110,9 +115,9 @@ pkgCacheGenerator::pkgCacheGenerator(DynamicMMap *pMap,OpProgress *Prog) :
       {
         _error->Error(_("Cache has an incompatible versioning system"));
         return;
-      }      
+      }
    }
-   
+
    Cache.HeaderP->Dirty = true;
    Map.Sync(0,sizeof(pkgCache::Header));
 }
@@ -618,7 +623,7 @@ bool pkgCacheGenerator::NewGroup(pkgCache::GrpIterator &Grp, const string &Name)
 
    // Insert it into the hash table
    unsigned long const Hash = Cache.Hash(Name);
-   map_ptrloc *insertAt = &Cache.HeaderP->GrpHashTable[Hash];
+   map_ptrloc *insertAt = &Cache.HeaderP->GrpHashTable()[Hash];
    while (*insertAt != 0 && strcasecmp(Name.c_str(), Cache.StrP + (Cache.GrpP + *insertAt)->Name) > 0)
       insertAt = &(Cache.GrpP + *insertAt)->Next;
    Grp->Next = *insertAt;
@@ -654,7 +659,7 @@ bool pkgCacheGenerator::NewPackage(pkgCache::PkgIterator &Pkg,const string &Name
       Grp->FirstPackage = Package;
       // Insert it into the hash table
       unsigned long const Hash = Cache.Hash(Name);
-      map_ptrloc *insertAt = &Cache.HeaderP->PkgHashTable[Hash];
+      map_ptrloc *insertAt = &Cache.HeaderP->PkgHashTable()[Hash];
       while (*insertAt != 0 && strcasecmp(Name.c_str(), Cache.StrP + (Cache.PkgP + *insertAt)->Name) > 0)
         insertAt = &(Cache.PkgP + *insertAt)->Next;
       Pkg->Next = *insertAt;