[PATCH] A setup.exe performance enhancement

Jon TURNEY jon.turney@dronecode.org.uk
Fri Nov 19 16:08:00 GMT 2010


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
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: 0001-Change-package_db-collection-of-packages-from-vector.patch
URL: <http://cygwin.com/pipermail/cygwin-apps/attachments/20101119/2a66d594/attachment.ksh>


More information about the Cygwin-apps mailing list