From b291aa59ee63983204d8aeb166c388b1f97edce7 Mon Sep 17 00:00:00 2001 From: David Kalnischkies Date: Tue, 14 Jul 2015 13:41:11 +0200 Subject: link DependencyData structs together Cache generation needs a way of quickly iterating over the unique potion of the dependencies to be able to share them. By linking them together we can reduce the speed penality (~ 80%) with only a small reduction in saved size (~ 20%). Git-Dch: Ignore --- apt-pkg/cacheiterators.h | 5 ++-- apt-pkg/pkgcache.h | 4 ++- apt-pkg/pkgcachegen.cc | 77 +++++++++++++++++++++++------------------------- 3 files changed, 43 insertions(+), 43 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/cacheiterators.h b/apt-pkg/cacheiterators.h index 82c5d082b..4173326ca 100644 --- a/apt-pkg/cacheiterators.h +++ b/apt-pkg/cacheiterators.h @@ -318,11 +318,12 @@ class pkgCache::DepIterator : public Iterator { map_pointer_t &DependencyData; map_pointer_t &NextRevDepends; map_pointer_t &NextDepends; + map_pointer_t &NextData; 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 };} + inline DependencyProxy operator->() const {return { S2->Version, S2->Package, S->ID, S2->Type, S2->CompareOp, S->ParentVer, S->DependencyData, S->NextRevDepends, S->NextDepends, S2->NextData };} + inline DependencyProxy operator->() {return { S2->Version, S2->Package, S->ID, S2->Type, S2->CompareOp, S->ParentVer, S->DependencyData, S->NextRevDepends, S->NextDepends, S2->NextData };} void ReMap(void const * const oldMap, void const * const newMap) { Iterator::ReMap(oldMap, newMap); diff --git a/apt-pkg/pkgcache.h b/apt-pkg/pkgcache.h index 41709eae8..b3a2e3184 100644 --- a/apt-pkg/pkgcache.h +++ b/apt-pkg/pkgcache.h @@ -366,7 +366,7 @@ struct pkgCache::Header the same number of pools as there are structure types. The generator stores this information so future additions can make use of any unused pool blocks. */ - DynamicMMap::Pool Pools[9]; + DynamicMMap::Pool Pools[12]; /** \brief hash tables providing rapid group/package name lookup @@ -731,6 +731,8 @@ struct pkgCache::DependencyData If the high bit is set then it is a logical OR with the previous record. */ unsigned char CompareOp; + + map_pointer_t NextData; }; struct pkgCache::Dependency { diff --git a/apt-pkg/pkgcachegen.cc b/apt-pkg/pkgcachegen.cc index d5b282007..a82483d15 100644 --- a/apt-pkg/pkgcachegen.cc +++ b/apt-pkg/pkgcachegen.cc @@ -952,33 +952,30 @@ bool pkgCacheGenerator::NewDepends(pkgCache::PkgIterator &Pkg, bool isDuplicate = false; map_pointer_t DependencyData = 0; - map_pointer_t * PkgRevDepends = &Pkg->RevDepends; - map_pointer_t previous_id = 0; - - while (*PkgRevDepends != 0) + map_pointer_t PreviousData = 0; + if (Pkg->RevDepends != 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; - } + pkgCache::Dependency const * const L = Cache.DepP + Pkg->RevDepends; + DependencyData = L->DependencyData; + do { + pkgCache::DependencyData const * const D = Cache.DepDataP + DependencyData; + if (Version > D->Version) + break; + if (D->Version == Version && D->Type == Type && D->CompareOp == Op) + { + isDuplicate = true; + break; + } + PreviousData = DependencyData; + DependencyData = D->NextData; + } while (DependencyData != 0); } 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; @@ -987,7 +984,6 @@ bool pkgCacheGenerator::NewDepends(pkgCache::PkgIterator &Pkg, Link->ID = Cache.HeaderP->DependsCount++; pkgCache::DepIterator Dep(Cache, Link); - Dynamic DynDep(Dep); if (isDuplicate == false) { Dep->Type = Type; @@ -995,31 +991,32 @@ bool pkgCacheGenerator::NewDepends(pkgCache::PkgIterator &Pkg, Dep->Version = Version; Dep->Package = Pkg.Index(); ++Cache.HeaderP->DependsDataCount; - Link->NextRevDepends = Pkg->RevDepends; - Pkg->RevDepends = Dependency; + if (PreviousData != 0) + { + pkgCache::DependencyData * const D = Cache.DepDataP + PreviousData; + Dep->NextData = D->NextData; + D->NextData = DependencyData; + } + else if (Pkg->RevDepends != 0) + { + pkgCache::Dependency const * const D = Cache.DepP + Pkg->RevDepends; + Dep->NextData = D->DependencyData; + } + } + + if (isDuplicate == true || PreviousData != 0) + { + pkgCache::Dependency * const L = Cache.DepP + Pkg->RevDepends; + Link->NextRevDepends = L->NextRevDepends; + L->NextRevDepends = 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; + Link->NextRevDepends = Pkg->RevDepends; + Pkg->RevDepends = Dependency; } + // Do we know where to link the Dependency to? if (OldDepLast == NULL) { -- cgit v1.2.3