Bug 54716 - pkg-config takes very long time
pkg-config takes very long time
Status: RESOLVED FIXED
Product: pkg-config
Classification: Unclassified
Component: src
unspecified
x86 (IA32) Linux (All)
: medium normal
Assigned To: Tollef Fog Heen
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2012-09-10 08:37 UTC by Slawomir Czarko
Modified: 2012-10-30 13:13 UTC (History)
0 users

See Also:


Attachments
Files to reproduce the problem (105.94 KB, application/x-xz)
2012-09-10 08:37 UTC, Slawomir Czarko
Details
[PATCH] Combine copying and merging of flags to avoid repeated traversals (2.36 KB, patch)
2012-10-30 00:38 UTC, Dan Nicholson
Details | Splinter Review
.pc files and test script showing problem (2.79 MB, application/x-gzip)
2012-10-30 12:38 UTC, Dan Nicholson
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Slawomir Czarko 2012-09-10 08:37:33 UTC
Created attachment 66905 [details]
Files to reproduce the problem

Attached script calls pkg-config and it takes a very long time to complete. On my system it takes 11 minutes while by comparison pykg-config (https://github.com/gbiggs/pykg-config) takes 0.25 second with the same files.

atop shows pkg-config using 100% of one core during that time and very little disk activity.

Version of pkg-config used is pkg-config-0.27.1 from git (commit a35c3fc95e00c6817be124ec335713edfbfe913d).

To run:
tar xJf pkg-config-test.tar.xz
cd pkg-config-test.tar/
./pkg-config-test.sh

External dependencies (.pc files for these packages must be present plus their dependencies):
gl
glu
ImageMagick++
lua
packagekit-qt
QtCore
QtDBus
QtGui
QtOpenGL
QtSql
QtXml
sdl
x11
xtst
Comment 1 Dan Nicholson 2012-10-30 00:38:35 UTC
Created attachment 69267 [details] [review]
[PATCH] Combine copying and  merging of flags to avoid repeated traversals


When combining the flags from all the packages together, each flags list
was being copied and then concatenated to then end of the combined list.
This was extremely inefficient because it caused the combined list to be
traversed multiple times to find the end. Instead, combine the copying
and merging of the flags together so the last element is always tracked
and can easily be appended to.

Freedesktop #54716 (https://bugs.freedesktop.org/show_bug.cgi?id=54716)
---
 pkg.c |   38 +++++++++++++++++++++++---------------
 1 files changed, 23 insertions(+), 15 deletions(-)
Comment 2 Dan Nicholson 2012-10-30 00:45:13 UTC
After getting all the pc files together to actually get pkg-config to resolve, I found one spot that was definitely inefficient. I have to say that this is the most extreme usage of pkg-config I've come across. pkg-config uses a lot of single-linked lists, which is no big deal when the lists of packages and arguments are relatively small. When the lists become large like this, it becomes very painful to find the list endpoint.

The attached patch gets rid of the worst bottleneck. It got me from not being able to finish your test in 1 minute to about 1 second of runtime. That's still pretty bad, but obviously an improvement from useless to usable. Can you give it a try?
Comment 3 Slawomir Czarko 2012-10-30 08:44:08 UTC
It is much better. Still about 2x slower than pykg-config when running the test case but good enough to be usable when there's a large amount of .pc files.

I'm unable to run pkg-config on my project at the moment due to an incompatibility between pkg-config and pykg-config in handling --variable switch.
Comment 4 Dan Nicholson 2012-10-30 12:38:26 UTC
Created attachment 69303 [details]
.pc files and test script showing problem

.pc files with all external dependencies copied in to demonstrate slowness. Unpack, cd to directory, and run ./test.sh. pkg-config is expected to be in the parent directory, but can be set via PKG_CONFIG environment variable, too.
Comment 5 Dan Nicholson 2012-10-30 13:06:28 UTC
(In reply to comment #3)
> It is much better. Still about 2x slower than pykg-config when running the
> test case but good enough to be usable when there's a large amount of .pc
> files.

Yeah, I suspect we're still losing a lot of time traversing these large single-linked lists in your case. A project for another day is to trade size for speed and convert all the GSLists to GLists and make them double-linked. Then again, I just need to attach a proper profiler and see where the hot spots are.

> I'm unable to run pkg-config on my project at the moment due to an
> incompatibility between pkg-config and pykg-config in handling --variable
> switch.

What's the issue there? Could you open a separate bug about this if there isn't one already?

This bug should be fixed in commit 90e0ec0 after minor refactoring and rewording of the commit message.
Comment 6 Slawomir Czarko 2012-10-30 13:13:17 UTC
(In reply to comment #5)
> > I'm unable to run pkg-config on my project at the moment due to an
> > incompatibility between pkg-config and pykg-config in handling --variable
> > switch.
> 
> What's the issue there? Could you open a separate bug about this if there
> isn't one already?

I'm not sure whether it's a bug or a feature.

pkg-config will print variables defined only directly in the queried package's .pc file while pykg-config will print them also if they're defined in .pc files listed in "Requires" section. I need the recursive behaviour of pykg-config.