[Buildroot] [PATCH] support/graph-depends: detect circular dependencies

[Yann E. MORIN <yann.morin.1998@free.fr>]

Arnout, All,

On 2016-01-24 02:04 +0100, Arnout Vandecappelle spake thusly:
> On 24-01-16 00:00, Yann E. MORIN wrote:
> > Thomas, All,
> > 
> > On 2016-01-23 23:31 +0100, Yann E. MORIN spake thusly:
> >> On 2016-01-23 23:21 +0100, Thomas Petazzoni spake thusly:
> >>> On Sat, 23 Jan 2016 23:04:45 +0100, Yann E. MORIN wrote:
> >> [--SNIP--]
> >>> I am a bit worried about the algorithmic complexity of this new
> >>> function. As you know, we had issues with other parts of graph-depends
> >>> having a too high algorithmic complexity to handle large
> >>> configurations, or configurations having specific patterns of
> >>> dependencies.
> >>>
> >>> Have you measured the time impact of this new check on a very large
> >>> configuration (like allyespackageconfig) ?
> >>
> >> I have an allyespackageconfig with an recent toolchain so I get a lot
> >> of packages, and I tweaked the config to disable a few to enable others.
> >>
> >> And no, the speed impact is not measurable for me. I'll come up with
> >> numbers (of course, when there's no loop!) a bit later.
> > 
> > Damn, I spoke too fast. The speed was totally fine as long as there were
> > those circular dependencies I was hunting for.
> > 
> > But without any circular deps, the speed is awfull and totally
> > inacceptable.
> >
> > I'll see what I can do to speed this up.
> 
> 
>  Naive cycle detection is exponential. See [1] for a pythonese implementation of
> single-visit cycle detection. Note that you have to do it on the whole graph at
> once, not once per node, for this to work.

Yeah, I have already implemented such a cut:
    https://git.buildroot.org/~ymorin/git/buildroot/commit/?h=yem/fixes&id=451599b

This new circular dependency check just adds less than 0.5 seconds now,
which is IMHO totally acceptable. I'll respin the patch shortly.

> > One option is to not do the check in graph-depends, but to off-load that
> > into the package infrastructure, so we detect them even earlier.
> 
>  It's going to stay equally exponential when you do it in make... And since make
> already has cycle detection, I don't think it makes much sense to add a custom
> one there. What more is your custom cycle detection going to tell you? Ah, yes,
> you want it to show the entire cycle instead of just the place where it
> arbitrarily cut it.

Yes, that's what I wanted to get, the list of packages that makes the
loop, so it is easier to understand.

> Hm, I think graph-depends is still a better place for it -
> the make logic is going to look _very_ ugly.

Well, I managed to have a relatively simple code to detect circular
dependencies in generic-package, but all it was able to do is detect it,
not dump the loop.

And it was really expensive, but not quite as expensive as the Python
code, adding 'just' 2 minutes to the parsing of the Makefiles, instead
of the 10+ minutes for the python code (which I really don't know hiw
long it runs, as I always Ctrl-C-ed it after ~10 minutes).

Thanks! :-)

-- 
.-----------------.--------------------.------------------.--------------------.
|  Yann E. MORIN  | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +33 662 376 056 | Software  Designer | \ / CAMPAIGN     |  ___               |
| +33 223 225 172 `------------.-------:  X  AGAINST      |  \e/  There is no  |
| http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL    |   v   conspiracy.  |
'------------------------------^-------^------------------^--------------------'