From 71c9e95b223517b5f51c4627f6ad4cce8af0d901 Mon Sep 17 00:00:00 2001 From: David Kalnischkies Date: Mon, 13 Jul 2015 16:28:21 +0200 Subject: split-up Dependency struct Having dependency data separated from the link between version/package and the dependency allows use to work on sharing the depdency data a bit as it turns out that many dependencies are in fact duplicates. How many are duplicates various heavily with the sources configured, but for a single Debian release the ballpark is 2 duplicates for each dependency already (e.g. libc6 counts 18410 dependencies, but only 45 unique). Add more releases and the duplicates count only rises to get ~6 for 3 releases. For each architecture a user has configured which given the shear number of dependencies amounts to MBs of duplication. We can cut down on this number, but pay a heavy price for it: In my many releases(3) + architectures(3) test we have a 10% (~ 0.5 sec) increase in cache creationtime, but also 10% less cachesize (~ 10 MB). Further work is needed to rip the whole benefits from this through, so this is just the start. Git-Dch: Ignore --- apt-pkg/cacheiterators.h | 43 +++++++++++++++++++------ apt-pkg/depcache.cc | 11 +++---- apt-pkg/pkgcache.cc | 56 ++++++++++++++++++++------------ apt-pkg/pkgcache.h | 27 ++++++++++------ apt-pkg/pkgcachegen.cc | 83 ++++++++++++++++++++++++++++++++++++++++-------- 5 files changed, 162 insertions(+), 58 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/cacheiterators.h b/apt-pkg/cacheiterators.h index 06deef950..82c5d082b 100644 --- a/apt-pkg/cacheiterators.h +++ b/apt-pkg/cacheiterators.h @@ -275,6 +275,7 @@ class pkgCache::DescIterator : public Iterator { // Dependency iterator /*{{{*/ class pkgCache::DepIterator : public Iterator { enum {DepVer, DepRev} Type; + DependencyData * S2; public: inline Dependency* OwnerPointer() const { @@ -282,13 +283,12 @@ class pkgCache::DepIterator : public Iterator { } // Iteration - inline DepIterator& operator++() {if (S != Owner->DepP) S = Owner->DepP + - (Type == DepVer ? S->NextDepends : S->NextRevDepends); return *this;} + DepIterator& operator++(); inline DepIterator operator++(int) { DepIterator const tmp(*this); operator++(); return tmp; } // Accessors - inline const char *TargetVer() const {return S->Version == 0?0:Owner->StrP + S->Version;} - inline PkgIterator TargetPkg() const {return PkgIterator(*Owner,Owner->PkgP + S->Package);} + inline const char *TargetVer() const {return S2->Version == 0?0:Owner->StrP + S2->Version;} + inline PkgIterator TargetPkg() const {return PkgIterator(*Owner,Owner->PkgP + S2->Package);} inline PkgIterator SmartTargetPkg() const {PkgIterator R(*Owner,0);SmartTargetPkg(R);return R;} inline VerIterator ParentVer() const {return VerIterator(*Owner,Owner->VerP + S->ParentVer);} inline PkgIterator ParentPkg() const {return PkgIterator(*Owner,Owner->PkgP + Owner->VerP[S->ParentVer].ParentPkg);} @@ -303,23 +303,48 @@ class pkgCache::DepIterator : public Iterator { void GlobOr(DepIterator &Start,DepIterator &End); Version **AllTargets() const; bool SmartTargetPkg(PkgIterator &Result) const; - inline const char *CompType() const {return Owner->CompType(S->CompareOp);} - inline const char *DepType() const {return Owner->DepType(S->Type);} + inline const char *CompType() const {return Owner->CompType(S2->CompareOp);} + inline const char *DepType() const {return Owner->DepType(S2->Type);} + + // overrides because we are special + struct DependencyProxy + { + map_stringitem_t &Version; + map_pointer_t &Package; + should_be_map_id_t &ID; + unsigned char &Type; + unsigned char &CompareOp; + map_pointer_t &ParentVer; + map_pointer_t &DependencyData; + map_pointer_t &NextRevDepends; + map_pointer_t &NextDepends; + DependencyProxy const * operator->() const { return this; } + DependencyProxy * operator->() { return this; } + }; + inline DependencyProxy operator->() const {return { S2->Version, S2->Package, S->ID, S2->Type, S2->CompareOp, S->ParentVer, S->DependencyData, S->NextRevDepends, S->NextDepends };} + inline DependencyProxy operator->() {return { S2->Version, S2->Package, S->ID, S2->Type, S2->CompareOp, S->ParentVer, S->DependencyData, S->NextRevDepends, S->NextDepends };} + void ReMap(void const * const oldMap, void const * const newMap) + { + Iterator::ReMap(oldMap, newMap); + if (Owner == 0 || S == 0 || S2 == 0) + return; + S2 += (DependencyData const * const)(newMap) - (DependencyData const * const)(oldMap); + } //Nice printable representation friend std::ostream& operator <<(std::ostream& out, DepIterator D); inline DepIterator(pkgCache &Owner, Dependency *Trg, Version* = 0) : - Iterator(Owner, Trg), Type(DepVer) { + Iterator(Owner, Trg), Type(DepVer), S2(Trg == 0 ? Owner.DepDataP : (Owner.DepDataP + Trg->DependencyData)) { if (S == 0) S = Owner.DepP; } inline DepIterator(pkgCache &Owner, Dependency *Trg, Package*) : - Iterator(Owner, Trg), Type(DepRev) { + Iterator(Owner, Trg), Type(DepRev), S2(Trg == 0 ? Owner.DepDataP : (Owner.DepDataP + Trg->DependencyData)) { if (S == 0) S = Owner.DepP; } - inline DepIterator() : Iterator(), Type(DepVer) {} + inline DepIterator() : Iterator(), Type(DepVer), S2(0) {} }; /*}}}*/ // Provides iterator /*{{{*/ diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc index 6271a024a..7b1448c73 100644 --- a/apt-pkg/depcache.cc +++ b/apt-pkg/depcache.cc @@ -348,22 +348,21 @@ bool pkgDepCache::CheckDep(DepIterator const &Dep,int const Type,PkgIterator &Re bug. Conflicts may never self match */ if (Dep.IsIgnorable(Res) == false) { - PkgIterator Pkg = Dep.TargetPkg(); // Check the base package if (Type == NowVersion) { - if (Pkg->CurrentVer != 0 && Dep.IsSatisfied(Pkg.CurrentVer()) == true) + if (Res->CurrentVer != 0 && Dep.IsSatisfied(Res.CurrentVer()) == true) return true; } else if (Type == InstallVersion) { - if (PkgState[Pkg->ID].InstallVer != 0 && - Dep.IsSatisfied(PkgState[Pkg->ID].InstVerIter(*this)) == true) + if (PkgState[Res->ID].InstallVer != 0 && + Dep.IsSatisfied(PkgState[Res->ID].InstVerIter(*this)) == true) return true; } else if (Type == CandidateVersion) - if (PkgState[Pkg->ID].CandidateVer != 0 && - Dep.IsSatisfied(PkgState[Pkg->ID].CandidateVerIter(*this)) == true) + if (PkgState[Res->ID].CandidateVer != 0 && + Dep.IsSatisfied(PkgState[Res->ID].CandidateVerIter(*this)) == true) return true; } diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc index 897f1ee2a..8cd716c6e 100644 --- a/apt-pkg/pkgcache.cc +++ b/apt-pkg/pkgcache.cc @@ -66,6 +66,7 @@ pkgCache::Header::Header() VersionSz = sizeof(pkgCache::Version); DescriptionSz = sizeof(pkgCache::Description); DependencySz = sizeof(pkgCache::Dependency); + DependencyDataSz = sizeof(pkgCache::DependencyData); ProvidesSz = sizeof(pkgCache::Provides); VerFileSz = sizeof(pkgCache::VerFile); DescFileSz = sizeof(pkgCache::DescFile); @@ -75,6 +76,7 @@ pkgCache::Header::Header() VersionCount = 0; DescriptionCount = 0; DependsCount = 0; + DependsDataCount = 0; ReleaseFileCount = 0; PackageFileCount = 0; VerFileCount = 0; @@ -110,6 +112,7 @@ bool pkgCache::Header::CheckSizes(Header &Against) const VersionSz == Against.VersionSz && DescriptionSz == Against.DescriptionSz && DependencySz == Against.DependencySz && + DependencyDataSz == Against.DependencyDataSz && VerFileSz == Against.VerFileSz && DescFileSz == Against.DescFileSz && ProvidesSz == Against.ProvidesSz) @@ -150,6 +153,7 @@ bool pkgCache::ReMap(bool const &Errorchecks) DescP = (Description *)Map.Data(); ProvideP = (Provides *)Map.Data(); DepP = (Dependency *)Map.Data(); + DepDataP = (DependencyData *)Map.Data(); StrP = (char *)Map.Data(); if (Errorchecks == false) @@ -408,7 +412,7 @@ pkgCache::PkgIterator pkgCache::GrpIterator::NextPkg(pkgCache::PkgIterator const return PkgIterator(*Owner, Owner->PkgP + LastPkg->NextPackage); } /*}}}*/ -// GrpIterator::operator ++ - Postfix incr /*{{{*/ +// GrpIterator::operator++ - Prefix incr /*{{{*/ // --------------------------------------------------------------------- /* This will advance to the next logical group in the hash table. */ pkgCache::GrpIterator& pkgCache::GrpIterator::operator++() @@ -420,16 +424,16 @@ pkgCache::GrpIterator& pkgCache::GrpIterator::operator++() // Follow the hash table while (S == Owner->GrpP && (HashIndex+1) < (signed)Owner->HeaderP->GetHashTableSize()) { - HashIndex++; + ++HashIndex; S = Owner->GrpP + Owner->HeaderP->GrpHashTableP()[HashIndex]; } return *this; } /*}}}*/ -// PkgIterator::operator ++ - Postfix incr /*{{{*/ +// PkgIterator::operator++ - Prefix incr /*{{{*/ // --------------------------------------------------------------------- /* This will advance to the next logical package in the hash table. */ -pkgCache::PkgIterator& pkgCache::PkgIterator::operator ++() +pkgCache::PkgIterator& pkgCache::PkgIterator::operator++() { // Follow the current links if (S != Owner->PkgP) @@ -438,12 +442,24 @@ pkgCache::PkgIterator& pkgCache::PkgIterator::operator ++() // Follow the hash table while (S == Owner->PkgP && (HashIndex+1) < (signed)Owner->HeaderP->GetHashTableSize()) { - HashIndex++; + ++HashIndex; S = Owner->PkgP + Owner->HeaderP->PkgHashTableP()[HashIndex]; } return *this; } /*}}}*/ +pkgCache::DepIterator& pkgCache::DepIterator::operator++() /*{{{*/ +{ + if (S == Owner->DepP) + return *this; + S = Owner->DepP + (Type == DepVer ? S->NextDepends : S->NextRevDepends); + if (S == Owner->DepP) + S2 = Owner->DepDataP; + else + S2 = Owner->DepDataP + S->DependencyData; + return *this; +} + /*}}}*/ // PkgIterator::State - Check the State of the package /*{{{*/ // --------------------------------------------------------------------- /* By this we mean if it is either cleanly installed or cleanly removed. */ @@ -543,8 +559,8 @@ std::string pkgCache::PkgIterator::FullName(bool const &Pretty) const bool pkgCache::DepIterator::IsCritical() const { if (IsNegative() == true || - S->Type == pkgCache::Dep::Depends || - S->Type == pkgCache::Dep::PreDepends) + S2->Type == pkgCache::Dep::Depends || + S2->Type == pkgCache::Dep::PreDepends) return true; return false; } @@ -555,9 +571,9 @@ bool pkgCache::DepIterator::IsCritical() const are negative like Conflicts which can and should be handled differently */ bool pkgCache::DepIterator::IsNegative() const { - return S->Type == Dep::DpkgBreaks || - S->Type == Dep::Conflicts || - S->Type == Dep::Obsoletes; + return S2->Type == Dep::DpkgBreaks || + S2->Type == Dep::Conflicts || + S2->Type == Dep::Obsoletes; } /*}}}*/ // DepIterator::SmartTargetPkg - Resolve dep target pointers w/provides /*{{{*/ @@ -686,7 +702,7 @@ void pkgCache::DepIterator::GlobOr(DepIterator &Start,DepIterator &End) End = *this; for (bool LastOR = true; end() == false && LastOR == true;) { - LastOR = (S->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or; + LastOR = (S2->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or; ++(*this); if (LastOR == true) End = (*this); @@ -714,15 +730,15 @@ bool pkgCache::DepIterator::IsIgnorable(PkgIterator const &PT) const if ((PV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) { // Replaces: ${self}:other ( << ${binary:Version}) - if (S->Type == pkgCache::Dep::Replaces) + if (S2->Type == pkgCache::Dep::Replaces) { - if (S->CompareOp == pkgCache::Dep::Less && strcmp(PV.VerStr(), TargetVer()) == 0) + if (S2->CompareOp == pkgCache::Dep::Less && strcmp(PV.VerStr(), TargetVer()) == 0) return false; } // Breaks: ${self}:other (!= ${binary:Version}) - else if (S->Type == pkgCache::Dep::DpkgBreaks) + else if (S2->Type == pkgCache::Dep::DpkgBreaks) { - if (S->CompareOp == pkgCache::Dep::NotEquals && strcmp(PV.VerStr(), TargetVer()) == 0) + if (S2->CompareOp == pkgCache::Dep::NotEquals && strcmp(PV.VerStr(), TargetVer()) == 0) return false; } return true; @@ -755,9 +771,9 @@ bool pkgCache::DepIterator::IsIgnorable(PrvIterator const &Prv) const bool pkgCache::DepIterator::IsMultiArchImplicit() const { if (ParentPkg()->Arch != TargetPkg()->Arch && - (S->Type == pkgCache::Dep::Replaces || - S->Type == pkgCache::Dep::DpkgBreaks || - S->Type == pkgCache::Dep::Conflicts)) + (S2->Type == pkgCache::Dep::Replaces || + S2->Type == pkgCache::Dep::DpkgBreaks || + S2->Type == pkgCache::Dep::Conflicts)) return true; return false; } @@ -765,11 +781,11 @@ bool pkgCache::DepIterator::IsMultiArchImplicit() const // DepIterator::IsSatisfied - check if a version satisfied the dependency /*{{{*/ bool pkgCache::DepIterator::IsSatisfied(VerIterator const &Ver) const { - return Owner->VS->CheckDep(Ver.VerStr(),S->CompareOp,TargetVer()); + return Owner->VS->CheckDep(Ver.VerStr(),S2->CompareOp,TargetVer()); } bool pkgCache::DepIterator::IsSatisfied(PrvIterator const &Prv) const { - return Owner->VS->CheckDep(Prv.ProvideVersion(),S->CompareOp,TargetVer()); + return Owner->VS->CheckDep(Prv.ProvideVersion(),S2->CompareOp,TargetVer()); } /*}}}*/ // ostream operator to handle string representation of a dependecy /*{{{*/ diff --git a/apt-pkg/pkgcache.h b/apt-pkg/pkgcache.h index 0042eac96..41709eae8 100644 --- a/apt-pkg/pkgcache.h +++ b/apt-pkg/pkgcache.h @@ -139,6 +139,7 @@ class pkgCache /*{{{*/ struct Description; struct Provides; struct Dependency; + struct DependencyData; struct StringItem; struct VerFile; struct DescFile; @@ -226,6 +227,7 @@ class pkgCache /*{{{*/ Description *DescP; Provides *ProvideP; Dependency *DepP; + DependencyData *DepDataP; APT_DEPRECATED StringItem *StringItemP; char *StrP; @@ -310,6 +312,7 @@ struct pkgCache::Header unsigned short VersionSz; unsigned short DescriptionSz; unsigned short DependencySz; + unsigned short DependencyDataSz; unsigned short ProvidesSz; unsigned short VerFileSz; unsigned short DescFileSz; @@ -324,6 +327,7 @@ struct pkgCache::Header map_id_t VersionCount; map_id_t DescriptionCount; map_id_t DependsCount; + map_id_t DependsDataCount; map_fileid_t ReleaseFileCount; map_fileid_t PackageFileCount; map_fileid_t VerFileCount; @@ -711,7 +715,7 @@ struct pkgCache::Description The base of the linked list is pkgCache::Version::DependsList. All forms of dependencies are recorded here including Depends, Recommends, Suggests, Enhances, Conflicts, Replaces and Breaks. */ -struct pkgCache::Dependency +struct pkgCache::DependencyData { /** \brief string of the version the dependency is applied against */ map_stringitem_t Version; @@ -720,21 +724,26 @@ struct pkgCache::Dependency The generator will - if the package does not already exist - create a blank (no version records) package. */ map_pointer_t Package; // Package - /** \brief next dependency of this version */ - map_pointer_t NextDepends; // Dependency - /** \brief next reverse dependency of this package */ - map_pointer_t NextRevDepends; // Dependency - /** \brief version of the package which has the reverse depends */ - map_pointer_t ParentVer; // Version - /** \brief unique sequel ID */ - should_be_map_id_t ID; /** \brief Dependency type - Depends, Recommends, Conflicts, etc */ unsigned char Type; /** \brief comparison operator specified on the depends line If the high bit is set then it is a logical OR with the previous record. */ unsigned char CompareOp; +}; +struct pkgCache::Dependency +{ + map_pointer_t DependencyData; // DependencyData + /** \brief version of the package which has the depends */ + map_pointer_t ParentVer; // Version + /** \brief next reverse dependency of this package */ + map_pointer_t NextRevDepends; // Dependency + /** \brief next dependency of this version */ + map_pointer_t NextDepends; // Dependency + + /** \brief unique sequel ID */ + should_be_map_id_t ID; }; /*}}}*/ // Provides structure /*{{{*/ diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc index 0eba5795f..d5b282007 100644 --- a/apt-pkg/pkgcachegen.cc +++ b/apt-pkg/pkgcachegen.cc @@ -950,19 +950,75 @@ bool pkgCacheGenerator::NewDepends(pkgCache::PkgIterator &Pkg, if (unlikely(Dependency == 0)) return false; - // Fill it in - pkgCache::DepIterator Dep(Cache,Cache.DepP + Dependency); - Dynamic DynDep(Dep); - Dep->ParentVer = Ver.Index(); - Dep->Type = Type; - Dep->CompareOp = Op; - Dep->Version = Version; - Dep->ID = Cache.HeaderP->DependsCount++; + bool isDuplicate = false; + map_pointer_t DependencyData = 0; + map_pointer_t * PkgRevDepends = &Pkg->RevDepends; + map_pointer_t previous_id = 0; - // Link it to the package - Dep->Package = Pkg.Index(); - Dep->NextRevDepends = Pkg->RevDepends; - Pkg->RevDepends = Dep.Index(); + while (*PkgRevDepends != 0) + { + pkgCache::Dependency * const L = Cache.DepP + *PkgRevDepends; + PkgRevDepends = &L->NextRevDepends; + if (L->DependencyData == previous_id) + break; + previous_id = L->DependencyData; + pkgCache::DependencyData const * const D = Cache.DepDataP + previous_id; + if (D->Type == Type && D->CompareOp == Op && D->Version == Version) + { + DependencyData = previous_id; + isDuplicate = true; + break; + } + } + + if (isDuplicate == false) + { + void const * const oldMap2 = Map.Data(); + DependencyData = AllocateInMap(sizeof(pkgCache::DependencyData)); + if (unlikely(DependencyData == 0)) + return false; + if (oldMap2 != Map.Data()) + PkgRevDepends += (map_pointer_t const * const) Map.Data() - (map_pointer_t const * const) oldMap2; + } + + pkgCache::Dependency * Link = Cache.DepP + Dependency; + Link->ParentVer = Ver.Index(); + Link->DependencyData = DependencyData; + Link->ID = Cache.HeaderP->DependsCount++; + + pkgCache::DepIterator Dep(Cache, Link); + Dynamic DynDep(Dep); + if (isDuplicate == false) + { + Dep->Type = Type; + Dep->CompareOp = Op; + Dep->Version = Version; + Dep->Package = Pkg.Index(); + ++Cache.HeaderP->DependsDataCount; + Link->NextRevDepends = Pkg->RevDepends; + Pkg->RevDepends = Dependency; + } + else + { + // dependency data is already fine, we just set the reverse link + // and in such a way that the loop above can finish fast, so we keep + // non-duplicates at the front and for the duplicates we: + // a) move to the end of the list, b) insert before another own duplicate + // or c) find two duplicates behind each other. + map_pointer_t const own_id = Link->DependencyData; + while (*PkgRevDepends != 0) + { + pkgCache::Dependency * const L = Cache.DepP + *PkgRevDepends; + PkgRevDepends = &L->NextRevDepends; + if (L->DependencyData == own_id || L->DependencyData == previous_id) + { + Link->NextRevDepends = L->NextRevDepends; + break; + } + previous_id = L->DependencyData; + } + *PkgRevDepends = Dependency; + } // Do we know where to link the Dependency to? if (OldDepLast == NULL) @@ -974,9 +1030,8 @@ bool pkgCacheGenerator::NewDepends(pkgCache::PkgIterator &Pkg, OldDepLast += (map_pointer_t const * const) Map.Data() - (map_pointer_t const * const) oldMap; Dep->NextDepends = *OldDepLast; - *OldDepLast = Dep.Index(); + *OldDepLast = Dependency; OldDepLast = &Dep->NextDepends; - return true; } /*}}}*/ -- cgit v1.2.3