[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