setup built with '-g -O0 -pg' flags, 'time ./setup.exe. -X -q' with both a cygwin and a cygport mirror selected, but nothing to install, takes rather a long time: real 5m52.001s user 0m0.046s sys 0m0.015s
start of the the call graph output from gprof: > granularity: each sample hit covers 4 byte(s) for 0.03% of 32.84 seconds > > index % time self children called name > 0.30 2.62 6001/29801 > IniDBBuilderPackage::buildPackageSource(std::string const&, std::string > const&) [16] > 1.18 10.39 23800/29801 > _packageversion::sourcePackage() [2] > [1] 44.1 1.48 13.01 29801 > packagedb::findSource(PackageSpecification const&) const [1] > 0.63 6.40 142604532/182305964 > PackageSpecification::satisfies(packageversion const&) const [4] > 0.18 2.86 118892225/153911466 std::set<packageversion, > std::less<packageversion>, std::allocator<packageversion> >::begin() const > [13] > 0.49 0.40 261489666/336261198 std::set<packageversion, > std::less<packageversion>, std::allocator<packageversion> >::end() const [35] > 0.53 0.32 118914935/153963867 bool > __gnu_cxx::operator!=<packagemeta**, std::vector<packagemeta*, > std::allocator<packagemeta*> > >(__gnu_cxx::__normal_iterator<packagemeta**, > std::vector<packagemeta*, std::allocator<packagemeta*> > > const&, > __gnu_cxx::__normal_iterator<packagemeta**, std::vector<packagemeta*, > std::allocator<packagemeta*> > > const&) [36] > 0.19 0.13 118914935/153939634 > std::vector<packagemeta*, std::allocator<packagemeta*> >::end() [48] > 0.27 0.00 142597441/182313940 > std::_Rb_tree_const_iterator<packageversion>::operator++() [50] > 0.23 0.00 380388982/422405973 > __gnu_cxx::__normal_iterator<packagemeta**, std::vector<packagemeta*, > std::allocator<packagemeta*> > >::operator*() const [53] > 0.22 0.00 261489666/336225400 > std::_Rb_tree_const_iterator<packageversion>::operator!=(std::_Rb_tree_const_iterator<packageversion> > const&) const [52] > 0.09 0.00 118885134/153990748 > __gnu_cxx::__normal_iterator<packagemeta**, std::vector<packagemeta*, > std::allocator<packagemeta*> > >::operator++() [59] > 0.08 0.00 142604532/182395438 > std::_Rb_tree_const_iterator<packageversion>::operator*() const [60] > 0.00 0.00 29801/6824761 std::vector<packagemeta*, > std::allocator<packagemeta*> >::begin() [107] I'm not sure if this data is accurate, as it seems to get the total runtime rather wrong, but looking at the source packagedb::findSource() is terrible: despite the fact that db.packages is maintained in alphabetic order, it searches the entire vector for a match every time, which is going to give O(n^2) behaviour. The attached patch converts the package lists from a vector to a map, so we can directly locate packages by name. This reduces 'time ./setup.exe. -X -q' for setup built with the same flags doing the same work to: real 0m15.142s user 0m0.031s sys 0m0.031s
>From 98764a4634945315ac35cd8191c7562b68f54038 Mon Sep 17 00:00:00 2001 From: Jon TURNEY <[email protected]> Date: Fri, 19 Nov 2010 15:27:42 +0000 Subject: [PATCH] Change package_db collection of packages from vector to a map so we can look things up in it quickly Change package_db collection of packages from vector to a map so we can look things up in it quickly This allows packagedb::findBinary() and packagedb::findSource() to be re-written to locate packages by name rather than searching the entire set, which makes a big difference to total execution time. 2010-11-19 Jon TURNEY <[email protected]> * IniDBBuilderPackage.cc (IniDBBuilderPackage): Remove db.packages vector sorting. (buildPackage, buildPackageSource): Change package collection from vector to map. * PickView.cc (setViewMode, init_headers, defaultTrust): Ditto. * choose.cc (createListview, logResults, keepClicked) (changeTrust): Ditto * install.cc (do_install_thread): Ditto * download.cc (do_download_thread): Ditto * prereq.cc (isMet): Ditto * package_meta.cc (ScanDownloadedFiles): Ditto * package_db.h (packagedb): Ditto * package_db.cc (packagedb, flush, markUnVisited, setExistence) (fillMissingCategory): Ditto (findBinary, findSource): Rewrite to locate packages in map rather than searching the whole vector, for performance. (ConnectedLoopFinder, doIt, visit): Rewrite to refer to package using a packagemeta *, as an index into the vector of packages can no longer be used. Signed-off-by: Jon TURNEY <[email protected]> --- IniDBBuilderPackage.cc | 9 +-- PickView.cc | 12 ++-- choose.cc | 25 ++++++-- download.cc | 8 +- install.cc | 4 +- package_db.cc | 165 ++++++++++++++++++++++++++--------------------- package_db.h | 5 +- package_meta.cc | 4 +- prereq.cc | 6 +- 9 files changed, 132 insertions(+), 106 deletions(-) diff --git a/IniDBBuilderPackage.cc b/IniDBBuilderPackage.cc index 50094fe..44a5eea 100644 --- a/IniDBBuilderPackage.cc +++ b/IniDBBuilderPackage.cc @@ -36,13 +36,8 @@ using namespace std; IniDBBuilderPackage::IniDBBuilderPackage (IniParseFeedback const &aFeedback) : cp (0), cbpv (), cspv (), currentSpec (0), currentOrList (0), currentAndList (0), trust (0), _feedback (aFeedback){} -inline bool lt_packagemeta(packagemeta *p1, packagemeta *p2) -{ return casecompare(p1->name, p2->name) < 0; } - IniDBBuilderPackage::~IniDBBuilderPackage() { - packagedb db; - sort (db.packages.begin(), db.packages.end(), lt_packagemeta); } void @@ -82,7 +77,7 @@ IniDBBuilderPackage::buildPackage (const std::string& name) if (!cp) { cp = new packagemeta (name); - db.packages.push_back (cp); + db.packages.insert (packagedb::packagecollection::value_type(cp->name,cp)); } cbpv = cygpackage::createInstance (name, package_binary); cspv = packageversion (); @@ -141,7 +136,7 @@ IniDBBuilderPackage::buildPackageSource (const std::string& path, csp->prev = packageversion(); csp->curr = packageversion(); csp->exp = packageversion(); - db.sourcePackages.push_back (csp); + db.sourcePackages.insert (packagedb::packagecollection::value_type(csp->name,csp)); } /* create a source packageversion */ cspv = cygpackage::createInstance (cbpv.Name(), package_source); diff --git a/PickView.cc b/PickView.cc index a24e2e2..27e53c2 100644 --- a/PickView.cc +++ b/PickView.cc @@ -175,10 +175,10 @@ PickView::setViewMode (views mode) { contents.ShowLabel (false); // iterate through every package - for (vector <packagemeta *>::iterator i = db.packages.begin (); + for (packagedb::packagecollection::iterator i = db.packages.begin (); i != db.packages.end (); ++i) { - packagemeta & pkg = **i; + packagemeta & pkg = *(i->second); if ( // "Full" : everything (view_mode == PickView::views::PackageFull) @@ -463,10 +463,10 @@ PickView::init_headers (HDC dc) width of the sdesc for the pkg_col. Also, if this is not a Category view, adjust the 'category' column so that the first NUM_CATEGORY_COL_WIDTH categories from each package fits. */ - for (vector <packagemeta *>::iterator n = db.packages.begin (); + for (packagedb::packagecollection::iterator n = db.packages.begin (); n != db.packages.end (); ++n) { - packagemeta & pkg = **n; + packagemeta & pkg = *(n->second); if (!showObsolete && isObsolete (pkg.categories)) continue; if (pkg.installed) @@ -972,10 +972,10 @@ PickView::defaultTrust (trusts trust) { this->deftrust = trust; packagedb db; - for (vector <packagemeta *>::iterator i = db.packages.begin (); + for (packagedb::packagecollection::iterator i = db.packages.begin (); i != db.packages.end (); ++i) { - packagemeta & pkg = **i; + packagemeta & pkg = *(i->second); if (pkg.installed || pkg.categories.find ("Base") != pkg.categories.end () || pkg.categories.find ("Misc") != pkg.categories.end ()) diff --git a/choose.cc b/choose.cc index 59654a8..7bf2b6a 100644 --- a/choose.cc +++ b/choose.cc @@ -150,7 +150,12 @@ ChooserPage::createListview () if (!SetDlgItemText (GetHWND (), IDC_CHOOSE_VIEWCAPTION, chooser->mode_caption ())) log (LOG_BABBLE) << "Failed to set View button caption %ld" << GetLastError () << endLog; - for_each (db.packages.begin(), db.packages.end(), bind2nd(mem_fun(&packagemeta::set_requirements), chooser->deftrust)); + + for (packagedb::packagecollection::iterator i = db.packages.begin(); i != db.packages.end(); i++) + { + i->second->set_requirements(chooser->deftrust); + } + /* FIXME: do we need to init the desired fields ? */ static int ta[] = { IDC_CHOOSE_KEEP, IDC_CHOOSE_PREV, IDC_CHOOSE_CURR, IDC_CHOOSE_EXP, 0 }; rbset (GetHWND (), ta, IDC_CHOOSE_CURR); @@ -281,7 +286,11 @@ ChooserPage::logResults() { log (LOG_BABBLE) << "Chooser results..." << endLog; packagedb db; - for_each (db.packages.begin (), db.packages.end (), mem_fun(&packagemeta::logSelectionStatus)); + + for (packagedb::packagecollection::iterator i = db.packages.begin(); i != db.packages.end(); i++) + { + i->second->logSelectionStatus(); + } } long @@ -312,10 +321,10 @@ void ChooserPage::keepClicked() { packagedb db; - for (vector <packagemeta *>::iterator i = db.packages.begin (); + for (packagedb::packagecollection::iterator i = db.packages.begin (); i != db.packages.end (); ++i) { - packagemeta & pkg = **i; + packagemeta & pkg = *(i->second); pkg.desired = pkg.installed; } chooser->refresh(); @@ -328,8 +337,12 @@ ChooserPage::changeTrust(trusts aTrust) chooser->defaultTrust (aTrust); packagedb db; db.markUnVisited (); - for_each (db.packages.begin (), db.packages.end (), - bind2nd (mem_fun (&packagemeta::set_requirements), aTrust)); + + for (packagedb::packagecollection::iterator i = db.packages.begin(); i != db.packages.end(); i++) + { + i->second->set_requirements(aTrust); + } + chooser->refresh(); PrereqChecker p; p.setTrust (aTrust); diff --git a/download.cc b/download.cc index 4b322eb..7c4a457 100644 --- a/download.cc +++ b/download.cc @@ -201,10 +201,10 @@ do_download_thread (HINSTANCE h, HWND owner) packagedb db; /* calculate the amount needed */ - for (vector <packagemeta *>::iterator i = db.packages.begin (); + for (packagedb::packagecollection::iterator i = db.packages.begin (); i != db.packages.end (); ++i) { - packagemeta & pkg = **i; + packagemeta & pkg = *(i->second); if (pkg.desired.picked () || pkg.desired.sourcePackage ().picked ()) { packageversion version = pkg.desired; @@ -242,10 +242,10 @@ do_download_thread (HINSTANCE h, HWND owner) /* and do the download. FIXME: This here we assign a new name for the cached version * and check that above. */ - for (vector <packagemeta *>::iterator i = db.packages.begin (); + for (packagedb::packagecollection::iterator i = db.packages.begin (); i != db.packages.end (); ++i) { - packagemeta & pkg = **i; + packagemeta & pkg = *(i->second); if (pkg.desired.picked () || pkg.desired.sourcePackage ().picked ()) { int e = 0; diff --git a/install.cc b/install.cc index 5344559..ede83e9 100644 --- a/install.cc +++ b/install.cc @@ -584,10 +584,10 @@ do_install_thread (HINSTANCE h, HWND owner) vector <packagemeta *> install_q, uninstall_q, sourceinstall_q; packagedb db; - for (vector <packagemeta *>::iterator i = db.packages.begin (); + for (packagedb::packagecollection::iterator i = db.packages.begin (); i != db.packages.end (); ++i) { - packagemeta & pkg = **i; + packagemeta & pkg = *(i->second); if (pkg.desired.picked()) { diff --git a/package_db.cc b/package_db.cc index f01624c..c52ab9a 100644 --- a/package_db.cc +++ b/package_db.cc @@ -97,7 +97,7 @@ packagedb::packagedb () if (!pkg) { pkg = new packagemeta (pkgname, inst); - packages.push_back (pkg); + packages.insert (packagedb::packagecollection::value_type(pkgname, pkg)); /* we should install a new handler then not check this... */ //if (!pkg) @@ -139,10 +139,10 @@ packagedb::flush () return errno ? errno : 1; ndb->write ("INSTALLED.DB 2\n", strlen ("INSTALLED.DB 2\n")); - for (vector <packagemeta *>::iterator i = packages.begin (); + for (packagedb::packagecollection::iterator i = packages.begin (); i != packages.end (); ++i) { - packagemeta & pkgm = **i; + packagemeta & pkgm = *(i->second); if (pkgm.installed) { /* size here is irrelevant - as we can assume that this install source @@ -169,10 +169,10 @@ packagedb::flush () packagemeta * packagedb::findBinary (PackageSpecification const &spec) const { - for (vector <packagemeta *>::iterator n = packages.begin (); - n != packages.end (); ++n) + packagedb::packagecollection::iterator n = packages.find(spec.packageName()); + if (n != packages.end()) { - packagemeta & pkgm = **n; + packagemeta & pkgm = *(n->second); for (set<packageversion>::iterator i=pkgm.versions.begin(); i != pkgm.versions.end(); ++i) if (spec.satisfies (*i)) @@ -184,31 +184,26 @@ packagedb::findBinary (PackageSpecification const &spec) const packagemeta * packagedb::findSource (PackageSpecification const &spec) const { - for (vector <packagemeta *>::iterator n=sourcePackages.begin(); - n != sourcePackages.end(); ++n) + packagedb::packagecollection::iterator n = sourcePackages.find(spec.packageName()); + if (n != sourcePackages.end()) { - for (set<packageversion>::iterator i = (*n)->versions.begin(); - i != (*n)->versions.end(); ++i) + packagemeta & pkgm = *(n->second); + for (set<packageversion>::iterator i = pkgm.versions.begin(); + i != pkgm.versions.end(); ++i) if (spec.satisfies (*i)) - return *n; + return &pkgm; } return NULL; } /* static members */ -int - packagedb::installeddbread = - 0; -vector < packagemeta * > packagedb::packages; -packagedb::categoriesType - packagedb::categories; -vector <packagemeta *> packagedb::sourcePackages; -PackageDBActions - packagedb::task = - PackageDB_Install; -std::vector <packagemeta *> -packagedb::dependencyOrderedPackages; +int packagedb::installeddbread = 0; +packagedb::packagecollection packagedb::packages; +packagedb::categoriesType packagedb::categories; +packagedb::packagecollection packagedb::sourcePackages; +PackageDBActions packagedb::task = PackageDB_Install; +std::vector <packagemeta *> packagedb::dependencyOrderedPackages; #include "LogSingleton.h" #include <stack> @@ -216,20 +211,25 @@ packagedb::dependencyOrderedPackages; class ConnectedLoopFinder { - public: - ConnectedLoopFinder(); - void doIt(); +public: + ConnectedLoopFinder(void); + void doIt(void); +private: + size_t visit (packagemeta *pkg); + packagedb db; size_t visited; - std::vector<size_t> visitOrder; - size_t visit (size_t const nodeToVisit); - std::stack<size_t> nodesInStronglyConnectedComponent; + + typedef std::map<packagemeta *, size_t> visitMap; + visitMap visitOrder; + std::stack<packagemeta *> nodesInStronglyConnectedComponent; }; ConnectedLoopFinder::ConnectedLoopFinder() : visited(0) { - for (size_t counter = 0; counter < db.packages.size(); ++counter) - visitOrder.push_back(0); + for (packagedb::packagecollection::iterator i = db.packages.begin (); + i != db.packages.end (); ++i) + visitOrder.insert(visitMap::value_type(i->second, 0)); } void @@ -247,30 +247,36 @@ ConnectedLoopFinder::doIt() future. FIXME: Find another depnendecy mechanism which ensures this without hardcoding. */ - for (size_t i = 0; i < db.packages.size(); ++i) + + packagedb::packagecollection::iterator i; + i= db.packages.find(std::string("base-cygwin")); + if (i != db.packages.end()) { - packagemeta &pkg (*db.packages[i]); - if (pkg.installed && (casecompare (pkg.name, "base-cygwin") == 0)) + packagemeta &pkg (*(i->second)); + if (pkg.installed) { - visit (i); - break; + visit (&pkg); } } - for (size_t i = 0; i < db.packages.size(); ++i) + + i = db.packages.find(std::string("base-passwd")); + if (i != db.packages.end()) { - packagemeta &pkg (*db.packages[i]); - if (pkg.installed && (casecompare (pkg.name, "base-passwd") == 0)) + packagemeta &pkg (*(i->second)); + if (pkg.installed && !visitOrder[&pkg]) { - visit (i); - break; + visit (&pkg); } } - for (size_t i = 0; i < db.packages.size(); ++i) + + for (i = db.packages.begin (); + i != db.packages.end (); ++i) { - packagemeta &pkg (*db.packages[i]); - if (pkg.installed && !visitOrder[i]) - visit (i); + packagemeta &pkg (*(i->second)); + if (pkg.installed && !visitOrder[&pkg]) + visit (&pkg); } + log (LOG_BABBLE) << "Visited: " << visited << " nodes out of " << db.packages.size() << " while creating dependency order." << endLog; @@ -292,9 +298,9 @@ checkForInstalled (PackageSpecification *spec) } size_t -ConnectedLoopFinder::visit(size_t const nodeToVisit) +ConnectedLoopFinder::visit(packagemeta *nodeToVisit) { - if (!db.packages[nodeToVisit]->installed) + if (!nodeToVisit->installed) /* Can't visit this node, and it is not less than any visted node */ return db.packages.size() + 1; @@ -304,16 +310,19 @@ ConnectedLoopFinder::visit(size_t const nodeToVisit) ++visited; visitOrder[nodeToVisit] = visited; +#if DEBUG + log (LOG_PLAIN) << "visited '" << nodeToVisit->name << "', assigned id " << visited << endLog; +#endif + size_t minimumVisitId = visited; nodesInStronglyConnectedComponent.push(nodeToVisit); - vector <vector <PackageSpecification *> *>::iterator dp = db.packages[nodeToVisit]->installed.depends ()->begin(); + vector <vector <PackageSpecification *> *>::const_iterator dp = nodeToVisit->installed.depends()->begin(); /* walk through each and clause (a link in the graph) */ - while (dp != db.packages[nodeToVisit]->installed.depends ()->end()) + while (dp != nodeToVisit->installed.depends()->end()) { /* check each or clause for an installed match */ - vector <PackageSpecification *>::iterator i = - find_if ((*dp)->begin(), (*dp)->end(), checkForInstalled); + vector <PackageSpecification *>::const_iterator i = find_if ((*dp)->begin(), (*dp)->end(), checkForInstalled); if (i != (*dp)->end()) { /* we found an installed ok package */ @@ -321,13 +330,13 @@ ConnectedLoopFinder::visit(size_t const nodeToVisit) /* UGLY. Need to refactor. iterators in the outer would help as we could simply * vist the iterator */ - size_t nodeJustVisited = 0; - while (nodeJustVisited < db.packages.size() && casecompare(db.packages[nodeJustVisited]->name, (*i)->packageName())) - ++nodeJustVisited; - if (nodeJustVisited == db.packages.size()) + const packagedb::packagecollection::iterator n = db.packages.find((*i)->packageName()); + + if (n == db.packages.end()) log (LOG_PLAIN) << "Search for package '" << (*i)->packageName() << "' failed." << endLog; else { + packagemeta *nodeJustVisited = n->second; minimumVisitId = std::min (minimumVisitId, visit (nodeJustVisited)); } /* next and clause */ @@ -337,21 +346,21 @@ ConnectedLoopFinder::visit(size_t const nodeToVisit) /* not installed or not available we ignore */ ++dp; } - + if (minimumVisitId == visitOrder[nodeToVisit]) { - size_t popped; + packagemeta *popped; do { popped = nodesInStronglyConnectedComponent.top(); nodesInStronglyConnectedComponent.pop(); - db.dependencyOrderedPackages.push_back(db.packages[popped]); + db.dependencyOrderedPackages.push_back(popped); /* mark as displayed in a connected component */ visitOrder[popped] = db.packages.size() + 2; } while (popped != nodeToVisit); } - + return minimumVisitId; -} +} PackageDBConnectedIterator packagedb::connectedBegin() @@ -380,10 +389,10 @@ packagedb::connectedEnd() void packagedb::markUnVisited() { - for (vector <packagemeta *>::iterator n = packages.begin (); + for (packagedb::packagecollection::iterator n = packages.begin (); n != packages.end (); ++n) { - packagemeta & pkgm = **n; + packagemeta & pkgm = *(n->second); pkgm.visited(false); } } @@ -394,20 +403,21 @@ packagedb::setExistence () /* binary packages */ /* Remove packages that are in the db, not installed, and have no mirror info and are not cached for both binary and source packages. */ - vector <packagemeta *>::iterator i = packages.begin (); + packagedb::packagecollection::iterator i = packages.begin (); while (i != packages.end ()) { - packagemeta & pkg = **i; + packagemeta & pkg = *(i->second); if (!pkg.installed && !pkg.accessible() && - !pkg.sourceAccessible() ) - { - packagemeta *pkgm = *i; - delete pkgm; - i = packages.erase (i); - } + !pkg.sourceAccessible() ) + { + packagemeta *pkgm = (*i).second; + delete pkgm; + packages.erase (i++); + } else - ++i; + ++i; } + #if 0 /* remove any source packages which are not accessible */ vector <packagemeta *>::iterator i = db.sourcePackages.begin(); @@ -429,8 +439,15 @@ packagedb::setExistence () void packagedb::fillMissingCategory () { - for_each(packages.begin(), packages.end(), visit_if(mem_fun(&packagemeta::setDefaultCategories), mem_fun(&packagemeta::hasNoCategories))); - for_each(packages.begin(), packages.end(), mem_fun(&packagemeta::addToCategoryAll)); - for_each(packages.begin(), packages.end(), visit_if(mem_fun(&packagemeta::addToCategoryBase), mem_fun(&packagemeta::isManuallyWanted))); + for (packagedb::packagecollection::iterator i = packages.begin(); i != packages.end(); i++) + { + if (i->second->hasNoCategories()) + i->second->setDefaultCategories(); + + i->second->addToCategoryAll(); + + if (i->second->isManuallyWanted()) + i->second->addToCategoryBase(); + } } diff --git a/package_db.h b/package_db.h index 57df13b..fe1ec4c 100644 --- a/package_db.h +++ b/package_db.h @@ -69,10 +69,11 @@ public: void fillMissingCategory(); void markUnVisited(); void setExistence(); + typedef std::map <std::string, packagemeta *> packagecollection; /* all seen binary packages */ - static std::vector < packagemeta *> packages; + static packagecollection packages; /* all seen source packages */ - static std::vector <packagemeta *> sourcePackages; + static packagecollection sourcePackages; /* all seen categories */ typedef std::map <std::string, std::vector <packagemeta *>, casecompare_lt_op > categoriesType; static categoriesType categories; diff --git a/package_meta.cc b/package_meta.cc index ce26c21..f3e3367 100644 --- a/package_meta.cc +++ b/package_meta.cc @@ -711,10 +711,10 @@ packagemeta::ScanDownloadedFiles () * and fill in the Cached attribute if it exists. */ packagedb db; - for (vector <packagemeta *>::iterator n = db.packages.begin (); + for (packagedb::packagecollection::iterator n = db.packages.begin (); n != db.packages.end (); ++n) { - packagemeta & pkg = **n; + packagemeta & pkg = *(n->second); set<packageversion>::iterator i = pkg.versions.begin (); while (i != pkg.versions.end ()) { diff --git a/prereq.cc b/prereq.cc index a049630..54d072e 100644 --- a/prereq.cc +++ b/prereq.cc @@ -164,11 +164,11 @@ PrereqChecker::isMet () queue <packagemeta *> todo; // go through all packages, adding desired ones to the initial work list - for (vector <packagemeta *>::iterator p = db.packages.begin (); + for (packagedb::packagecollection::iterator p = db.packages.begin (); p != db.packages.end (); ++p) { - if ((*p)->desired) - todo.push (*p); + if (p->second->desired) + todo.push (p->second); } int max = todo.size(); -- 1.7.2.3
