GYP: Make GYP build deterministic

GYP: Make GYP build deterministic

Currently, the GYP build is non-deterministic: See issue 557851 for
discussion of how this came to be.

There's a small performance regression (19.73s to 19.98s average on my
z860).

BUG=557851, 566922
R=thakis@chromium.org

Committed: https://chromium.googlesource.com/external/gyp/+/9e2ceaef535255b1024889fdc268dfa784b472ca

[Zachary Forman, 2015-12-07 04:09:35]

Description was changed from

==========
GYP: Make GYP build deterministic

Currently, the GYP build is non-deterministic: See issue 557851 for
discussion of how this came to be.

There's a small performance regression (19.73s to 19.98s average on my
z860).

BUG=55781,566922
==========

to

==========
GYP: Make GYP build deterministic

Currently, the GYP build is non-deterministic: See issue 557851 for
discussion of how this came to be.

There's a small performance regression (19.73s to 19.98s average on my
z860).

BUG=557851,566922
==========

[Zachary Forman, 2015-12-08 23:48:48]

zforman@google.com changed reviewers:
+ mithro@mithis.com

[Zachary Forman, 2015-12-08 23:48:49]

Hi Mithro,

Could you please review this CL for python style / readability?

Thanks,
Zac

[mithro-old, 2015-12-09 04:15:36]

On 2015/12/08 at 23:48:49, zforman wrote:
> Hi Mithro,
> 
> Could you please review this CL for python style / readability?
> 
> Thanks,
> Zac

Hi Zac,

The overall Python style looks okay. I'm pondering the approach here and
wondering if there is a better way to solve this problem rather then adding all
these sorts in the output path.

Lets add scottmg and thakis to give some advice on what to do here?

Tim 'mithro' Ansell

[Zachary Forman, 2015-12-09 04:38:35]

zforman@google.com changed reviewers:
+ scottmg@chromium.org, thakis@chromium.org

[Zachary Forman, 2015-12-09 04:38:36]

Hi!

I've been working on making builds in Chromium deterministic, and as part of
that I've been
working on making each of the components of the build process deterministic.
This CL
makes GYP deterministic, even under a change in PYTHONHASHSEED.

Could you please take a look at this CL and let me know what you think?

Cheers,
Zac.

[scottmg, 2015-12-09 19:29:06]

I had this discussion a little with Nico in the bug, but I still don't
understand where the non-determinism is coming from. As far as I can tell,
Python 2 doesn't randomize the hash seed, so I don't understand why iteration
breaks in practice.

Were all of the `sorted()`s necessary? I don't think you really need a comment
at each callsite, preferring rather that each required sorted would cause
something in a test to fail if it didn't exist.

That said, I think this is worthwhile. We could add a flag, but since the
performance difference is minimal, it doesn't seem necessary.

[Nico, 2015-12-09 20:25:00]

I agree with everything scott said :-) It'd be good if each of the sorted()
calls was covered by some kind of test

https://codereview.chromium.org/1506733002/diff/120001/pylib/gyp/ninja_syntax.py
File pylib/gyp/ninja_syntax.py (right):

https://codereview.chromium.org/1506733002/diff/120001/pylib/gyp/ninja_syntax...
pylib/gyp/ninja_syntax.py:2: #  
https://github.com/martine/ninja/blob/master/misc/ninja_syntax.py
see this comment

https://codereview.chromium.org/1506733002/diff/120001/pylib/gyp/ninja_syntax...
pylib/gyp/ninja_syntax.py:71: all_inputs.sort()
i think callers should do this. this script is just a thin wrapper that
translates python to ninja syntax, it shouldn't contain logic like this

[mithro-old, 2015-12-10 03:15:28]

Hi Scott (and Nico),

On 2015/12/09 at 19:29:06, scottmg wrote:
> I had this discussion a little with Nico in the bug, but I still don't
understand where the non-determinism is coming from. As far as I can tell,
Python 2 doesn't randomize the hash seed, so I don't understand why iteration
breaks in practice.

This are is an annoyingly complicated area of Python which is made more
confusing by the fact that things /mostly/ work without having to understand any
of this :(

You are correct in Python 2 doesn't turn on hash seed randomization by default.
Using different hash seed values is just a quick way to find places were you are
dependent on hash values for ordering.

For most Python objects, the hash value is the memory location of the object
(because objects are pretty much created in the same order). In a single
threaded application this turns out to be pretty deterministic as things are
always created in the same order -- once you add any type of threading this no
longer becomes the case (except the GIL can end up making it *very* close).

Being dependent on memory location for hash ordering also means that any time
you make even a small change to the code or environment, the output ordering can
change *drastically*.

Hope that helps explain what is going on.

Tim 'mithro' Ansell

https://codereview.chromium.org/1506733002/diff/140001/pylib/gyp/generator/ni...
File pylib/gyp/generator/ninja.py (right):

https://codereview.chromium.org/1506733002/diff/140001/pylib/gyp/generator/ni...
pylib/gyp/generator/ninja.py:74: return sorted(l, **kwargs)
I think this should be in gyp.common with OrderedSet?

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

https://codereview.chromium.org/1506733002/diff/140001/pylib/gyp/input.py#new...
pylib/gyp/input.py:63: return sorted(l, **kwargs)
DRY

[Zachary Forman, 2015-12-10 07:28:16]

I've addressed all of your statements and reshuffled things so that - hopefully
- as little code as possible is being touched to make it deterministic.

Regarding tests: Other than needed_variables, all other changes that regress
determinism will cause test failures in this patch. I'll take another look at
needed_variables tomorrow morning, but so far I haven't been able to reproduce
it outside of chromium.

I wrapped the calls to sorted() in a helper function, OrderDeterministically to
make it clearer why things are being done.

As far as I can tell, each sorted() call (as of now) is required - removing any
one regresses the gyp files generated for chromium. The changes in ninja.py seem
to only take effect when PYTHONHASHSEED is changed; but from what mithro has
said, this may not be the only time that can happen. Changes in input.py have an
effect even with constant PYTHONHASHSEED.

Cheers,
Zac

[Zachary Forman, 2015-12-10 10:00:01]

On 2015/12/10 at 07:28:16, Zachary Forman wrote:
> I've addressed all of your statements and reshuffled things so that -
hopefully - as little code as possible is being touched to make it
deterministic.
> 
> Regarding tests: Other than needed_variables, all other changes that regress
determinism will cause test failures in this patch. I'll take another look at
needed_variables tomorrow morning, but so far I haven't been able to reproduce
it outside of chromium.
> 
> I wrapped the calls to sorted() in a helper function, OrderDeterministically
to make it clearer why things are being done.
> 
> As far as I can tell, each sorted() call (as of now) is required - removing
any one regresses the gyp files generated for chromium. The changes in ninja.py
seem to only take effect when PYTHONHASHSEED is changed; but from what mithro
has said, this may not be the only time that can happen. Changes in input.py
have an effect even with constant PYTHONHASHSEED.
> 
> Cheers,
> Zac

Addendum: There is now a test case that checks for determinism in
needed_variables; so all changes are backed by a test.

[Nico, 2015-12-10 20:30:24]

Looking pretty good, thanks!

Can you time a full and an incremental build of chrome with this change? I don't
think it should change much, but the performance of the build is at least
somewhat related to how things are ordered in the ninja files, so it'd be good
to check that.

https://codereview.chromium.org/1506733002/diff/260001/pylib/gyp/common.py
File pylib/gyp/common.py (right):

https://codereview.chromium.org/1506733002/diff/260001/pylib/gyp/common.py#ne...
pylib/gyp/common.py:114: def OrderDeterministically(l, **kwargs):
I'd just call sorted() directly everywhere. if someone removes a sorted() and a
test in test/determinism fails, that's clear enough

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

https://codereview.chromium.org/1506733002/diff/260001/pylib/gyp/input.py#new...
pylib/gyp/input.py:1552: in_degree_zeros =
OrderDeterministically(self.dependents[:],
should this just be an gyp.common.OrderedSet?

[Zachary Forman, 2015-12-13 21:38:33]

On 2015/12/10 at 20:30:24, thakis wrote:
> Looking pretty good, thanks!
> 
> Can you time a full and an incremental build of chrome with this change? I
don't think it should change much, but the performance of the build is at least
somewhat related to how things are ordered in the ninja files, so it'd be good
to check that.
> 
> https://codereview.chromium.org/1506733002/diff/260001/pylib/gyp/common.py
> File pylib/gyp/common.py (right):
> 
>
https://codereview.chromium.org/1506733002/diff/260001/pylib/gyp/common.py#ne...
> pylib/gyp/common.py:114: def OrderDeterministically(l, **kwargs):
> I'd just call sorted() directly everywhere. if someone removes a sorted() and
a test in test/determinism fails, that's clear enough
> 
> https://codereview.chromium.org/1506733002/diff/260001/pylib/gyp/input.py
> File pylib/gyp/input.py (right):
> 
>
https://codereview.chromium.org/1506733002/diff/260001/pylib/gyp/input.py#new...
> pylib/gyp/input.py:1552: in_degree_zeros =
OrderDeterministically(self.dependents[:],
> should this just be an gyp.common.OrderedSet?

For a full build (single repetition because of the time it takes to do a full
build) speed was ~the same, maybe slightly faster, but certainly not a major
change.

Partial builds are pretty much the same in build time, at least for the sampling
that I did.

[Zachary Forman, 2015-12-16 02:00:35]

I've fixed trybot failures on Windows (due to non-determinism in Windows causing
the new tests to fail) - can you PTAL?

[Zachary Forman, 2015-12-30 02:18:43]

Hi all - just a friendly ping.

Hope everyone's enjoying holidays :D.

--Zac

https://codereview.chromium.org/1506733002/diff/120001/pylib/gyp/ninja_syntax.py
File pylib/gyp/ninja_syntax.py (right):

https://codereview.chromium.org/1506733002/diff/120001/pylib/gyp/ninja_syntax...
pylib/gyp/ninja_syntax.py:2: #  
https://github.com/martine/ninja/blob/master/misc/ninja_syntax.py
On 2015/12/09 at 20:25:00, Nico wrote:
> see this comment

Oops - my bad. Thanks for the heads up :).

https://codereview.chromium.org/1506733002/diff/120001/pylib/gyp/ninja_syntax...
pylib/gyp/ninja_syntax.py:71: all_inputs.sort()
On 2015/12/09 at 20:25:00, Nico wrote:
> i think callers should do this. this script is just a thin wrapper that
translates python to ninja syntax, it shouldn't contain logic like this

I think you're probably right, I've changed this to be done in the callers.

https://codereview.chromium.org/1506733002/diff/140001/pylib/gyp/generator/ni...
File pylib/gyp/generator/ninja.py (right):

https://codereview.chromium.org/1506733002/diff/140001/pylib/gyp/generator/ni...
pylib/gyp/generator/ninja.py:74: return sorted(l, **kwargs)
On 2015/12/10 at 03:15:27, mithro wrote:
> I think this should be in gyp.common with OrderedSet?

Yeah, you caught me mid refactor. Good spot for it.

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

https://codereview.chromium.org/1506733002/diff/140001/pylib/gyp/input.py#new...
pylib/gyp/input.py:63: return sorted(l, **kwargs)
On 2015/12/10 at 03:15:28, mithro wrote:
> DRY

Done.

https://codereview.chromium.org/1506733002/diff/260001/pylib/gyp/common.py
File pylib/gyp/common.py (right):

https://codereview.chromium.org/1506733002/diff/260001/pylib/gyp/common.py#ne...
pylib/gyp/common.py:114: def OrderDeterministically(l, **kwargs):
On 2015/12/10 at 20:30:24, Nico wrote:
> I'd just call sorted() directly everywhere. if someone removes a sorted() and
a test in test/determinism fails, that's clear enough

Yeah, seems reasonable. I've swapped it back to sorted() :).

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

https://codereview.chromium.org/1506733002/diff/260001/pylib/gyp/input.py#new...
pylib/gyp/input.py:1552: in_degree_zeros =
OrderDeterministically(self.dependents[:],
On 2015/12/10 at 20:30:24, Nico wrote:
> should this just be an gyp.common.OrderedSet?

Nope, that fails the test; I believe because the order of OrderedSet would be
the non-deterministic ordering of the dependents.

[mithro-old, 2016-01-08 16:33:42]

Friendly ping?

Nico can you take another look?

[Nico, 2016-01-13 20:16:55]

lgtm except for some cosmetic questions, thanks

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/generator/ni...
File pylib/gyp/generator/ninja.py (left):

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/generator/ni...
pylib/gyp/generator/ninja.py:690: 
what was wrong with the 3 newlines here?

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/generator/ni...
File pylib/gyp/generator/ninja.py (right):

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/generator/ni...
pylib/gyp/generator/ninja.py:18: 
why this newline?

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/generator/ni...
pylib/gyp/generator/ninja.py:2342: master_ninja.build(short_name, 'phony',
([x.FinalOutput() for x in
why the additional parens?

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

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/input.py#new...
pylib/gyp/input.py:30: 
why this newline?

[Zachary Forman, 2016-01-18 20:44:36]

Fixed cosmetic issues - unless any issues with fixes, will merge later today or
tomorrow.

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/generator/ni...
File pylib/gyp/generator/ninja.py (left):

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/generator/ni...
pylib/gyp/generator/ninja.py:690: 
On 2016/01/13 at 20:16:54, Nico wrote:
> what was wrong with the 3 newlines here?

Reverted

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/generator/ni...
File pylib/gyp/generator/ninja.py (right):

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/generator/ni...
pylib/gyp/generator/ninja.py:18: 
On 2016/01/13 at 20:16:54, Nico wrote:
> why this newline?

Fixed

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/generator/ni...
pylib/gyp/generator/ninja.py:2342: master_ninja.build(short_name, 'phony',
([x.FinalOutput() for x in
On 2016/01/13 at 20:16:54, Nico wrote:
> why the additional parens?

Corrected.

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

https://codereview.chromium.org/1506733002/diff/340001/pylib/gyp/input.py#new...
pylib/gyp/input.py:30: 
On 2016/01/13 at 20:16:54, Nico wrote:
> why this newline?

Reverted

[Nico, 2016-01-18 20:57:40]

sounds good. gyp has a separate committers list though – if `git cl land` gives
you some error, let me know and i'll land this for you

[Zachary Forman, 2016-01-19 21:29:34]

On 2016/01/18 at 20:57:40, thakis wrote:
> sounds good. gyp has a separate committers list though – if `git cl land`
gives you some error, let me know and i'll land this for you

I wasn't able to land this - would you please be able to land it for me?

Thanks!

[Nico, 2016-01-20 02:46:24]

Description was changed from

==========
GYP: Make GYP build deterministic

Currently, the GYP build is non-deterministic: See issue 557851 for
discussion of how this came to be.

There's a small performance regression (19.73s to 19.98s average on my
z860).

BUG=557851,566922
==========

to

==========
GYP: Make GYP build deterministic

Currently, the GYP build is non-deterministic: See issue 557851 for
discussion of how this came to be.

There's a small performance regression (19.73s to 19.98s average on my
z860).

BUG=557851,566922
R=thakis@chromium.org

Committed:
https://chromium.googlesource.com/external/gyp/+/9e2ceaef535255b1024889fdc268...
==========

[Nico, 2016-01-20 02:46:26]

Committed patchset #19 (id:360001) manually as
9e2ceaef535255b1024889fdc268dfa784b472ca.

[Nico, 2016-01-20 02:47:00]

Done. You will need to land a gyp roll in chromium to let this have an effect
there.

[Nico, 2016-01-20 02:47:18]

And thank you very much for working on this :-)