From e8a7b0b28ca01cd8c2c1bee0d83e5997b40de689 Mon Sep 17 00:00:00 2001 From: David Kalnischkies Date: Wed, 11 Jun 2014 20:42:16 +0200 Subject: increase hashtable size for packages/groups by factor 5 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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). --- apt-pkg/pkgcachegen.cc | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'apt-pkg/pkgcachegen.cc') diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc index 9615b4c22..360f19736 100644 --- 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; -- cgit v1.2.3