From f9eec0e748c2e735980bf80445535d32f27f8301 Mon Sep 17 00:00:00 2001 From: Arch Librarian Date: Mon, 20 Sep 2004 16:52:56 +0000 Subject: performance tuning Author: jgg Date: 1999-02-23 06:46:24 GMT performance tuning --- apt-pkg/cacheiterators.h | 36 +++++++++++++++++++----------------- apt-pkg/makefile | 2 +- apt-pkg/pkgcache.cc | 22 ++++++++++------------ apt-pkg/pkgcache.h | 8 ++++---- apt-pkg/pkgcachegen.cc | 40 +++++++++++++++++++++++++++------------- apt-pkg/pkgcachegen.h | 10 +++++++++- 6 files changed, 70 insertions(+), 48 deletions(-) diff --git a/apt-pkg/cacheiterators.h b/apt-pkg/cacheiterators.h index 6e71e8c8d..16088765d 100644 --- a/apt-pkg/cacheiterators.h +++ b/apt-pkg/cacheiterators.h @@ -1,6 +1,6 @@ // -*- mode: cpp; mode: fold -*- // Description /*{{{*/ -// $Id: cacheiterators.h,v 1.12 1999/02/01 02:22:11 jgg Exp $ +// $Id: cacheiterators.h,v 1.13 1999/02/23 06:46:24 jgg Exp $ /* ###################################################################### Cache Iterators - Iterators for navigating the cache structure @@ -93,17 +93,17 @@ class pkgCache::PkgIterator class pkgCache::VerIterator { Version *Ver; - pkgCache &Owner; + pkgCache *Owner; void _dummy(); public: // Iteration - void operator ++(int) {if (Ver != Owner.VerP) Ver = Owner.VerP + Ver->NextVer;}; + void operator ++(int) {if (Ver != Owner->VerP) Ver = Owner->VerP + Ver->NextVer;}; inline void operator ++() {operator ++(0);}; - inline bool end() const {return Ver == Owner.VerP?true:false;}; - inline void operator =(const VerIterator &B) {Ver = B.Ver;}; + inline bool end() const {return Ver == Owner->VerP?true:false;}; + inline void operator =(const VerIterator &B) {Ver = B.Ver; Owner = B.Owner;}; // Comparison inline bool operator ==(const VerIterator &B) const {return Ver == B.Ver;}; @@ -115,24 +115,26 @@ class pkgCache::VerIterator inline Version const *operator ->() const {return Ver;}; inline Version &operator *() {return *Ver;}; inline Version const &operator *() const {return *Ver;}; - inline operator Version *() {return Ver == Owner.VerP?0:Ver;}; - inline operator Version const *() const {return Ver == Owner.VerP?0:Ver;}; + inline operator Version *() {return Ver == Owner->VerP?0:Ver;}; + inline operator Version const *() const {return Ver == Owner->VerP?0:Ver;}; - inline const char *VerStr() const {return Ver->VerStr == 0?0:Owner.StrP + Ver->VerStr;}; - inline const char *Section() const {return Ver->Section == 0?0:Owner.StrP + Ver->Section;}; - inline const char *Arch() const {return Ver->Arch == 0?0:Owner.StrP + Ver->Arch;}; - inline PkgIterator ParentPkg() const {return PkgIterator(Owner,Owner.PkgP + Ver->ParentPkg);}; + inline const char *VerStr() const {return Ver->VerStr == 0?0:Owner->StrP + Ver->VerStr;}; + inline const char *Section() const {return Ver->Section == 0?0:Owner->StrP + Ver->Section;}; + inline const char *Arch() const {return Ver->Arch == 0?0:Owner->StrP + Ver->Arch;}; + inline PkgIterator ParentPkg() const {return PkgIterator(*Owner,Owner->PkgP + Ver->ParentPkg);}; inline DepIterator DependsList() const; inline PrvIterator ProvidesList() const; inline VerFileIterator FileList() const; - inline unsigned long Index() const {return Ver - Owner.VerP;}; + inline unsigned long Index() const {return Ver - Owner->VerP;}; bool Downloadable() const; const char *PriorityType(); bool Automatic() const; VerFileIterator NewestFile() const; - - inline VerIterator(pkgCache &Owner,Version *Trg = 0) : Ver(Trg), Owner(Owner) + + inline VerIterator() : Ver(0), Owner(0) {}; + inline VerIterator(pkgCache &Owner,Version *Trg = 0) : Ver(Trg), + Owner(&Owner) { if (Ver == 0) Ver = Owner.VerP; @@ -330,10 +332,10 @@ inline pkgCache::DepIterator pkgCache::PkgIterator::RevDependsList() const inline pkgCache::PrvIterator pkgCache::PkgIterator::ProvidesList() const {return PrvIterator(*Owner,Owner->ProvideP + Pkg->ProvidesList,Pkg);}; inline pkgCache::PrvIterator pkgCache::VerIterator::ProvidesList() const - {return PrvIterator(Owner,Owner.ProvideP + Ver->ProvidesList,Ver);}; + {return PrvIterator(*Owner,Owner->ProvideP + Ver->ProvidesList,Ver);}; inline pkgCache::DepIterator pkgCache::VerIterator::DependsList() const - {return DepIterator(Owner,Owner.DepP + Ver->DependsList,Ver);}; + {return DepIterator(*Owner,Owner->DepP + Ver->DependsList,Ver);}; inline pkgCache::VerFileIterator pkgCache::VerIterator::FileList() const - {return VerFileIterator(Owner,Owner.VerFileP + Ver->FileList);}; + {return VerFileIterator(*Owner,Owner->VerFileP + Ver->FileList);}; #endif diff --git a/apt-pkg/makefile b/apt-pkg/makefile index e4584700c..e135c8ee9 100644 --- a/apt-pkg/makefile +++ b/apt-pkg/makefile @@ -11,7 +11,7 @@ include ../buildlib/defaults.mak # The library name LIBRARY=apt-pkg -MAJOR=2.1 +MAJOR=2.2 MINOR=0 SLIBS=$(PTHREADLIB) diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc index 8ad501e96..017c4accb 100644 --- a/apt-pkg/pkgcache.cc +++ b/apt-pkg/pkgcache.cc @@ -1,6 +1,6 @@ // -*- mode: cpp; mode: fold -*- // Description /*{{{*/ -// $Id: pkgcache.cc,v 1.22 1998/12/14 08:07:29 jgg Exp $ +// $Id: pkgcache.cc,v 1.23 1999/02/23 06:46:24 jgg Exp $ /* ###################################################################### Package Cache - Accessor code for the cache @@ -44,7 +44,7 @@ pkgCache::Header::Header() /* Whenever the structures change the major version should be bumped, whenever the generator changes the minor version should be bumped. */ MajorVersion = 2; - MinorVersion = 2; + MinorVersion = 3; Dirty = true; HeaderSz = sizeof(pkgCache::Header); @@ -132,23 +132,20 @@ bool pkgCache::ReMap() /* This is used to generate the hash entries for the HashTable. With my package list from bo this function gets 94% table usage on a 512 item table (480 used items) */ -unsigned long pkgCache::sHash(string Str) +unsigned long pkgCache::sHash(string Str) const { unsigned long Hash = 0; for (const char *I = Str.begin(); I != Str.end(); I++) - Hash += *I * ((Str.end() - I + 1)); - Header H; - return Hash % _count(H.HashTable); + Hash = 5*Hash + *I; + return Hash % _count(HeaderP->HashTable); } -unsigned long pkgCache::sHash(const char *Str) +unsigned long pkgCache::sHash(const char *Str) const { unsigned long Hash = 0; - const char *End = Str + strlen(Str); - for (const char *I = Str; I != End; I++) - Hash += *I * ((End - I + 1)); - Header H; - return Hash % _count(H.HashTable); + for (const char *I = Str; *I != 0; I++) + Hash = 5*Hash + *I; + return Hash % _count(HeaderP->HashTable); } /*}}}*/ @@ -164,6 +161,7 @@ pkgCache::PkgIterator pkgCache::FindPkg(string Name) if (Pkg->Name != 0 && StrP[Pkg->Name] == Name[0] && StrP + Pkg->Name == Name) return PkgIterator(*this,Pkg); +// cout << "b" << flush; } return PkgIterator(*this,0); } diff --git a/apt-pkg/pkgcache.h b/apt-pkg/pkgcache.h index 4e4bf0290..7628cebd9 100644 --- a/apt-pkg/pkgcache.h +++ b/apt-pkg/pkgcache.h @@ -1,6 +1,6 @@ // -*- mode: cpp; mode: fold -*- // Description /*{{{*/ -// $Id: pkgcache.h,v 1.17 1999/02/21 08:38:53 jgg Exp $ +// $Id: pkgcache.h,v 1.18 1999/02/23 06:46:24 jgg Exp $ /* ###################################################################### Cache - Structure definitions for the cache file @@ -90,8 +90,8 @@ class pkgCache string CacheFile; MMap ⤅ - static unsigned long sHash(string S); - static unsigned long sHash(const char *S); + unsigned long sHash(string S) const; + unsigned long sHash(const char *S) const; public: @@ -165,7 +165,7 @@ struct pkgCache::Header DynamicMMap::Pool Pools[7]; // Rapid package name lookup - __apt_ptrloc HashTable[2048]; + __apt_ptrloc HashTable[2*1048]; bool CheckSizes(Header &Against) const; Header(); diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc index 959075c0f..80997c952 100644 --- a/apt-pkg/pkgcachegen.cc +++ b/apt-pkg/pkgcachegen.cc @@ -1,6 +1,6 @@ // -*- mode: cpp; mode: fold -*- // Description /*{{{*/ -// $Id: pkgcachegen.cc,v 1.28 1999/02/08 07:30:49 jgg Exp $ +// $Id: pkgcachegen.cc,v 1.29 1999/02/23 06:46:24 jgg Exp $ /* ###################################################################### Package Cache Generator - Generator for the cache structure. @@ -22,6 +22,7 @@ #include #include #include +#include #include #include @@ -44,6 +45,7 @@ pkgCacheGenerator::pkgCacheGenerator(DynamicMMap &Map,OpProgress &Prog) : Cache.HeaderP->Dirty = true; Map.Sync(0,sizeof(pkgCache::Header)); Map.UsePools(*Cache.HeaderP->Pools,sizeof(Cache.HeaderP->Pools)/sizeof(Cache.HeaderP->Pools[0])); + memset(UniqHash,0,sizeof(UniqHash)); } /*}}}*/ // CacheGenerator::~pkgCacheGenerator - Destructor /*{{{*/ @@ -69,11 +71,12 @@ bool pkgCacheGenerator::MergeList(ListParser &List) { List.Owner = this; - int Counter = 0; + unsigned int Counter = 0; while (List.Step() == true) { // Get a pointer to the package structure string PackageName = List.Package(); + Pkgs++; if (PackageName.empty() == true) return false; @@ -100,6 +103,7 @@ bool pkgCacheGenerator::MergeList(ListParser &List) int Res = 1; for (; Ver.end() == false; Last = &Ver->NextVer, Ver++) { + Cmps++; Res = pkgVersionCompare(Version.begin(),Version.end(),Ver.VerStr(), Ver.VerStr() + strlen(Ver.VerStr())); if (Res >= 0) @@ -120,6 +124,7 @@ bool pkgCacheGenerator::MergeList(ListParser &List) } // Add a new version + Vers++; *Last = NewVersion(Ver,Version,*Last); Ver->ParentPkg = Pkg.Index(); if (List.NewVersion(Ver) == false) @@ -250,9 +255,9 @@ bool pkgCacheGenerator::ListParser::NewDepends(pkgCache::VerIterator Ver, // Probe the reverse dependency list for a version string that matches if (Version.empty() == false) { - for (pkgCache::DepIterator I = Pkg.RevDependsList(); I.end() == false; I++) +/* for (pkgCache::DepIterator I = Pkg.RevDependsList(); I.end() == false; I++, Hit++) if (I->Version != 0 && I.TargetVer() == Version) - Dep->Version = I->Version; + Dep->Version = I->Version;*/ if (Dep->Version == 0) if ((Dep->Version = WriteString(Version)) == 0) return false; @@ -265,19 +270,17 @@ bool pkgCacheGenerator::ListParser::NewDepends(pkgCache::VerIterator Ver, /* Link it to the version (at the end of the list) Caching the old end point speeds up generation substantially */ - static pkgCache::VerIterator OldVer(Cache); - static __apt_ptrloc *OldLast; - if (OldVer != Ver) + if (OldDepVer != Ver) { - OldLast = &Ver->DependsList; + OldDepLast = &Ver->DependsList; for (pkgCache::DepIterator D = Ver.DependsList(); D.end() == false; D++) - OldLast = &D->NextDepends; - OldVer = Ver; + OldDepLast = &D->NextDepends; + OldDepVer = Ver; } - Dep->NextDepends = *OldLast; - *OldLast = Dep.Index(); - OldLast = &Dep->NextDepends; + Dep->NextDepends = *OldDepLast; + *OldDepLast = Dep.Index(); + OldDepLast = &Dep->NextDepends; return true; } @@ -362,6 +365,13 @@ bool pkgCacheGenerator::SelectFile(string File,unsigned long Flags) unsigned long pkgCacheGenerator::WriteUniqString(const char *S, unsigned int Size) { + /* We use a very small transient hash table here, this speeds up generation + by a fair amount on slower machines */ + pkgCache::StringItem *&Bucket = UniqHash[(S[0]*5 + S[1]) % _count(UniqHash)]; + if (Bucket != 0 && + stringcmp(S,S+Size,Cache.StrP + Bucket->String) == 0) + return Bucket->String; + // Search for an insertion point pkgCache::StringItem *I = Cache.StringItemP + Cache.HeaderP->StringList; int Res = 1; @@ -376,7 +386,10 @@ unsigned long pkgCacheGenerator::WriteUniqString(const char *S, // Match if (Res == 0) + { + Bucket = I; return I->String; + } // Get a structure unsigned long Item = Map.Allocate(sizeof(pkgCache::StringItem)); @@ -391,6 +404,7 @@ unsigned long pkgCacheGenerator::WriteUniqString(const char *S, if (ItemP->String == 0) return 0; + Bucket = ItemP; return ItemP->String; } /*}}}*/ diff --git a/apt-pkg/pkgcachegen.h b/apt-pkg/pkgcachegen.h index 4c22ecf6f..8ffb277c6 100644 --- a/apt-pkg/pkgcachegen.h +++ b/apt-pkg/pkgcachegen.h @@ -1,6 +1,6 @@ // -*- mode: cpp; mode: fold -*- // Description /*{{{*/ -// $Id: pkgcachegen.h,v 1.11 1998/12/14 02:23:47 jgg Exp $ +// $Id: pkgcachegen.h,v 1.12 1999/02/23 06:46:24 jgg Exp $ /* ###################################################################### Package Cache Generator - Generator for the cache structure. @@ -31,6 +31,10 @@ class OpProgress; class pkgCacheGenerator { + private: + + pkgCache::StringItem *UniqHash[26]; + public: class ListParser; @@ -74,6 +78,10 @@ class pkgCacheGenerator::ListParser pkgCacheGenerator *Owner; friend pkgCacheGenerator; + // Some cache items + pkgCache::VerIterator OldDepVer; + __apt_ptrloc *OldDepLast; + protected: inline unsigned long WriteUniqString(string S) {return Owner->WriteUniqString(S);}; -- cgit v1.2.3