gyp: use a set() in DeepDependencies for less O(n^2).

gyp: use a set() in DeepDependencies for less O(n^2).

Another O(n^2) over the number of targets which used about half a second
for a 1000 target system (chromium) on a reasonable computer.

BUG=362075
r1899

[Daniel Bratell, 2014-04-11 14:07:33]

Dependency management function searched through lists that were longer than
expected when the code was written.

[Nico, 2014-04-11 16:11:00]

https://codereview.chromium.org/235193002/diff/1/pylib/gyp/input.py
File pylib/gyp/input.py (right):

https://codereview.chromium.org/235193002/diff/1/pylib/gyp/input.py#newcode1613
pylib/gyp/input.py:1613: return dependencies
DeepDependencies() now won't return results in deterministic order. Does that
matter?

[Daniel Bratell, 2014-04-11 16:13:57]

On 2014/04/11 16:11:00, Nico wrote:
> https://codereview.chromium.org/235193002/diff/1/pylib/gyp/input.py
> File pylib/gyp/input.py (right):
> 
>
https://codereview.chromium.org/235193002/diff/1/pylib/gyp/input.py#newcode1613
> pylib/gyp/input.py:1613: return dependencies
> DeepDependencies() now won't return results in deterministic order. Does that
> matter?

I don't know. It builds fine, but maybe there is some subtle effect I'm missing.

[Nico, 2014-04-11 16:17:13]

On 2014/04/11 16:13:57, Daniel Bratell wrote:
> On 2014/04/11 16:11:00, Nico wrote:
> > https://codereview.chromium.org/235193002/diff/1/pylib/gyp/input.py
> > File pylib/gyp/input.py (right):
> > 
> >
>
https://codereview.chromium.org/235193002/diff/1/pylib/gyp/input.py#newcode1613
> > pylib/gyp/input.py:1613: return dependencies
> > DeepDependencies() now won't return results in deterministic order. Does
that
> > matter?
> 
> I don't know. It builds fine, but maybe there is some subtle effect I'm
missing.

Looking through callers of this function, this might affect the order of
dependencies of a target, which might make the order of stuff on the link line
nondetermistic, which would make builds nondetermistic possibly.

[scottmg, 2014-04-11 16:30:42]

On 2014/04/11 16:17:13, Nico wrote:
> On 2014/04/11 16:13:57, Daniel Bratell wrote:
> > On 2014/04/11 16:11:00, Nico wrote:
> > > https://codereview.chromium.org/235193002/diff/1/pylib/gyp/input.py
> > > File pylib/gyp/input.py (right):
> > > 
> > >
> >
>
https://codereview.chromium.org/235193002/diff/1/pylib/gyp/input.py#newcode1613
> > > pylib/gyp/input.py:1613: return dependencies
> > > DeepDependencies() now won't return results in deterministic order. Does
> that
> > > matter?
> > 
> > I don't know. It builds fine, but maybe there is some subtle effect I'm
> missing.
> 
> Looking through callers of this function, this might affect the order of
> dependencies of a target, which might make the order of stuff on the link line
> nondetermistic, which would make builds nondetermistic possibly.

I think iteration order is consistent per python version (without python -R at
least). It would certainly change with this patch though.

[Daniel Bratell, 2014-04-15 14:58:17]

Rather than worrying about whether the ordering is important or not, I changed
the code to use a list for result gathering and a set for "already found"
checks. At my computer that is just 6 milliseconds slower than just a set so
well within the noise margin.

The total improvement with this change (on my computer) is 395 milliseconds on
average. The function will use ~120 ms instead of ~520 ms. Since this part of
gyp is not threaded, those 0.4s map directly to wall time.

[Nico, 2014-04-15 17:46:08]

lgtm

[Nico, 2014-04-16 15:36:08]

r1899