905973 - Add dependencies and rules allowing to rebuild shared libraries without a complete directory traversal

Status: RESOLVED FIXED

(Firefox Build System :: General, defect)

Description

[Mike Hommey [:glandium]]

Attachment: PoC

The attached proof of concept modifies the targetted build rule for shared libraries (as in make -C dir libfoo.so) so that it has dependencies on all the source and header files involved in the shared library creation.

It also adds a helper rule so that make -C objdir gecko or mach build gecko build libxul.so/xul.dll/XUL.

First run has an overhead of about 6.6s on my machine with warm cache. Subsequent no-ops are currently < 0.4s with make and around 2.7s with pymake with bug 905938 applied.

Now, for the gory details, instead of doing a complete derecursification that is hard to do correctly without the moz.build migration being complete, it relies on the current build rules, and just invokes submakes in the relevant directories. That is, it doesn't have rules to build each file individually with make -C other-dir foo.o, which would have a huge make overhead, but instead, it tracks in what directories there were changes and just runs make -C other-dir libs in those directories. On top of allowing to build without a complete directory traversal (a no-op does no directory traversal at all), it allows more parallelism (I'm very close to 100% cpu usage on large rebuilds such as after "touch js/src/jsapi.h")

There are a few things I want to change before I can consider it ready for a first landing, early next week. My plan is to keep it under the mach build gecko command so that it stays opt-in until it's deemed reliable.

Comment 1

[Mike Hommey [:glandium]]

Attachment: part 1 - Add a function to read simple dependency makefiles, and make makeutil.Rule faster

The SimpleOrderedSet may look fishy and kind of non-pythonic, but it's the only way i found that is fast. Anything else I tried turns a 3.5s process into a 6s one.

Comment 2

[Mike Hommey [:glandium]]

Attachment: part 2 - Add a tool to link several dependency files together in three different ways

I'm sure this can be made even faster, but let's already worry about getting review on something that I know works.

Comment 3

[Mike Hommey [:glandium]]

Attachment: part 3 - Add a "binaries" tier that optimizes for recompilation times

After doing a normal build with MOZ_PSEUDO_DERECURSE enabled, mach build binaries allows to handle incremental code and header changes. A few caveats with the current patch:
- it doesn't do nspr, nss, icu or ffi. Changes there will need a normal build for now.
- it doesn't handle gyp managed makefiles, nor js/src/Makefile, so those directories are always traversed, even to do nothing. This also makes the interdependencies based on those manual (in top-level Makefile.in), and makes toolkit/library always traversed even when there's nothing to build. As well as the various directories where stuff builds against libxul. As well as the aggregated dependency file. This puts the no-op at around 6s on my machine with gnu make, and 19s with pymake. The depfile aggregator is responsible for 3.5s, and that can be made faster.
- while it does handle install-manifest installed headers, it doesn't handle webidl, xpidl and other such related things, which still need manual intervention. Hopefully, at some point we'll have a top-level rule to rebuild those code-related export things, without the rest of export.

The latter two can be handled in followups. Considering how much overhead the former represents, and how not often nss, nspr, ffi and icu are modified, I'm inclined to say i don't really care for now.

I had njn test a previous iteration of those patches and he found a couple issues that i fixed in the patches i attached today. I'd like to land this so that more people can test it. Since it requires running a special command, it's not going to break things badly. And failures can be worked around by running a normal build.

For the record, after adding a dummy statement in netwerk/cache/nsCacheEntry.h, on my machine:
- mach build: 1m24s.
- mach build binaries: 29s (half of which are libxul linking).
(with gold, without split-dwarf)

For things with a long tail of effects (think touch js/src/jsapi.h), this is not entirely efficient because compilation is not completely parallelized yet. This will be a followup.

Comment 4

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Looks interesting -- please grab some numbers on Windows.

Comment 5

[Gregory Szorc [:gps]]

Comment on attachment 810494 [details] [diff] [review]
part 1 - Add a function to read simple dependency makefiles, and make makeutil.Rule faster

Review of attachment 810494 [details] [diff] [review]:
-----------------------------------------------------------------

SimpleOrderedSet is really tickling me the wrong way. I'd like to hear your response before granting r+.

::: python/mozbuild/mozbuild/makeutil.py
@@ +53,5 @@
>              guard = Rule(sorted(all_deps - all_targets))
>              guard.dump(fh)
>  
>  
> +class SimpleOrderedSet(list):

Please add a docstring here stating what exactly this class is and more importantly is not supposed to do.

As your patch comment says, this is fishy.

I don't like that this claims to be a "set" yet it inherits from list. That's wonky. I'd rather see it inherit from object or the appropriate collections interfaces.

What worries me greatly is that calls to .append() .extend(), __setitem__, etc won't go through your update() code path and duplicates can be inserted. That's very fragile and will be the cause of future bugs.

I'm pretty sure you can roll your own class that doesn't derive from list or set without much trouble while still preserving the performance characteristics of this class.

@@ +136,5 @@
> +# colon followed by anything except a slash (Windows path detection)
> +_depfilesplitter = re.compile(r':(?![\\/])')
> +
> +
> +def ReadDepMakefile(fh):

Nit: underscores.

@@ +145,5 @@
> +    """
> +
> +    rule = ''
> +    for line in fh.readlines():
> +        line = line.strip()

Is it worth adding an assertion to ensure we don't have recipes / tabs here?

@@ +150,5 @@
> +        if line.endswith('\\'):
> +            rule += line[:-1]
> +        else:
> +            rule += line
> +            rule = _depfilesplitter.split(rule, 1)

The variable reuse here makes this hard to read. I'd just just create a new variable for the split() result.

Comment 6

[Mike Hommey [:glandium]]

Attachment: part 1 - Add a function to read simple dependency makefiles, and make makeutil.Rule faster

Refreshed with review comments.

Comment 7

[Mike Hommey [:glandium]]

Attachment: part 2 - Add a tool to link several dependency files together in three different ways

Refreshed against changes to part 1.

Comment 8

[Mike Hommey [:glandium]]

Attachment: part 3 - Add a "binaries" tier that optimizes for recompilation times

Refreshed after bug 921070.

Comment 9

[Mike Hommey [:glandium]]

Attachment: part 2 - Add a tool to link several dependency files together in three different ways

Moved, as per irc discussion.

Comment 10

[Mike Hommey [:glandium]]

Attachment: part 3 - Add a "binaries" tier that optimizes for recompilation times

Adjusted to part 2 move, and added a couple guards against filling things up for the binaries target when pseudo derecurse is off.

Comment 11

[Mike Hommey [:glandium]]

Attachment: part 3 - Add a "binaries" tier that optimizes for recompilation times

This adds proper recursion for the gyp-managed directories.

Comment 12

[Mike Hommey [:glandium]]

Attachment: part 3 - Add a "binaries" tier that optimizes for recompilation times

I missed that I had a conflict in Makefile.in when i rebased.

Comment 13

[(no longer active)]

What is the performance numbers for no-op builds with this patch on different platforms?  I am not sure how to interpret the numbers in comment 3; nsCacheEntry.h seems like a random file to test this patch based on.

Comment 14

[Mike Hommey [:glandium]]

(In reply to :Ehsan Akhgari (needinfo? me!) from comment #13)
> What is the performance numbers for no-op builds with this patch on
> different platforms?  I am not sure how to interpret the numbers in comment
> 3; nsCacheEntry.h seems like a random file to test this patch based on.

No-op is not really an interesting case. On linux, changing a cpp file and doing mach build binaries should take the time it takes to build that .cpp, link libxul.so, and a few more seconds overhead. To compare with the headaches from dumbmake, which barely handles a few directories, and the three full directory recursal you get from the usual incremental make build. I took nsCacheEntry.h randomly, because it triggers more than rebuilding a single object file, and does so across several directories (which is nice to test the patch).

I don't have mac and windows systems that are fast enough to get relevant data. Although I'm switching my windows vm from kvm to virtualbox, and that may improve things a little.

Comment 15

[Mike Hommey [:glandium]]

On mac, I'd expect the results to be the same. On windows, that's pending pymake fixes.

Comment 16

[Gregory Szorc [:gps]]

Comment on attachment 810878 [details] [diff] [review]
part 2 - Add a tool to link several dependency files together in three different ways

Review of attachment 810878 [details] [diff] [review]:
-----------------------------------------------------------------

Did you do a performance evaluation without the variables in the generated make file? I would think expanding the variables at make file generation time would net an evaluation time win.

I haven't looked at part 3 yet, but I think link_deps.py is something we may want to put in mozbuild.action and $(call py_action) with. Which reminds me - now that we have the virtualenv in pymake's sys.path, we can have all the $(call py_action) use native execution!

::: python/mozbuild/mozbuild/link_deps.py
@@ +4,5 @@
> +
> +'''
> +Read dependency Makefiles and merge them together. Also normalizes paths
> +relative to a given topobjdir and topsrcdir, and drops files outside topobjdir
> +and topsrcdir.

Could you expand on this a little more to include what the overall goal is.

@@ +28,5 @@
> +class DependencyLinker(Makefile):
> +    def __init__(self, topsrcdir, topobjdir, dist, group=Grouping.NO):
> +        topsrcdir = os.path.normcase(os.path.abspath(topsrcdir)).replace(os.sep, '/')
> +        topobjdir = os.path.normcase(os.path.abspath(topobjdir)).replace(os.sep, '/')
> +        dist = os.path.normcase(os.path.abspath(dist)).replace(os.sep, '/')

Isn't there an API in mozpath to do this? Should there be?

@@ +53,5 @@
> +            if deps:
> +                deps = list(self.normpaths(deps))
> +                for t in self.normpaths(rule.targets()):
> +                    if t in self._targets:
> +                        raise 'Found target %s in %s and %s' % (t, self._targets[t][0], depfile)

Nit: Raise Exception instances, not strings.

Comment 17

[Mike Hommey [:glandium]]

(In reply to Gregory Szorc [:gps] from comment #16)
> Comment on attachment 810878 [details] [diff] [review]
> part 2 - Add a tool to link several dependency files together in three
> different ways
> 
> Review of attachment 810878 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Did you do a performance evaluation without the variables in the generated
> make file? I would think expanding the variables at make file generation
> time would net an evaluation time win.

On gnu make it doesn't matter. On pymake it might, but bug 918652 prevents any serious evaluation. Let's keep this as followup fodder.

> I haven't looked at part 3 yet, but I think link_deps.py is something we may
> want to put in mozbuild.action and $(call py_action) with. Which reminds me
> - now that we have the virtualenv in pymake's sys.path, we can have all the
> $(call py_action) use native execution!

only if they do the right thing with their arguments.

Comment 18

[Mike Hommey [:glandium]]

(In reply to Mike Hommey [:glandium] from comment #17)
> (In reply to Gregory Szorc [:gps] from comment #16)
> > - now that we have the virtualenv in pymake's sys.path, we can have all the
> > $(call py_action) use native execution!
> 
> only if they do the right thing with their arguments.

which they don't.

Comment 19

[Gregory Szorc [:gps]]

Comment on attachment 810920 [details] [diff] [review]
part 3 - Add a "binaries" tier that optimizes for recompilation times

Review of attachment 810920 [details] [diff] [review]:
-----------------------------------------------------------------

Nice hack.

We're introducing yet more dependencies on Makefile and backend.mk. This scares me a bit. I hope to soon find time to refactor that whole mess. In the mean time, I guess we live with a slightly more fragile than desired implementation.

There are a number of caveats with the "binaries" target and they are only documented in this bug's comments. Please throw something into build/docs. As I type this, I'm writing up a file documenting common build targets. Should commit to m-c within in hour. Just add this there.

I'd like to see final version before r+.

::: Makefile.in
@@ +32,5 @@
>  
>  ifndef MOZ_PROFILE_USE
>  # We need to explicitly put backend.RecursiveMakeBackend.built here
>  # otherwise the rule in rules.mk doesn't run early enough.
> +libs binaries export tools:: CLOBBER $(topsrcdir)/configure config.status backend.RecursiveMakeBackend.built js-config-status

You bit rotted yourself in bug 921770.

@@ +236,5 @@
>  js/src/export: mfbt/export
> +# Interdependencies for binaries
> +# Avoid traversal of those directories when creating the aggregate dependency file
> +ifneq (binaries-deps,$(MAKECMDGOALS))
> +toolkit/library/binaries: js/src/binaries media/webrtc/trunk/binaries media/webrtc/signaling/binaries media/webrtc/trunk/testing/binaries media/webrtc/signalingtest/binaries media/mtransport/third_party/nrappkit/binaries media/mtransport/third_party/nICEr/binaries

Having a hard-coded list of directories with binaries seems fragile. File a bug to pull this from moz.build and add a TODO, please. (It looks like it depends on integrating GYP data into moz.build too - fun.)

::: config/config.mk
@@ +823,5 @@
> +ifdef .PYMAKE
> +LINK_DEPS = %mozbuild.link_deps link_deps
> +else
> +LINK_DEPS = $(PYTHON) -m mozbuild.link_deps
> +endif

Yeah, link_deps.py should be in mozbuild.action. If you want to convert py_action to use native invocation, go for it!

::: config/makefiles/target_libs.mk
@@ +123,5 @@
> +# need to be recursed to do their duty, and creating a stamp would prevent that.
> +# In the future, we'll aggregate those.
> +ifneq (.,$(DEPTH))
> +ifndef EXTERNALLY_MANAGED_MAKE_FILE
> +	@$(if $^,$(LINK_DEPS) -o binaries --group-all --topsrcdir $(topsrcdir) --topobjdir $(DEPTH) --dist $(DIST) $(BINARIES_PP) $(wildcard $(addsuffix .pp,$(addprefix $(MDDEPDIR)/,$(notdir $(sort $(filter-out $(BINARIES_PP),$^) $(OBJS) $(PROGOBJS) $(HOST_OBJS) $(HOST_PROGOBJS)))))),$(TOUCH) binaries)

Fun.

::: config/recurse.mk
@@ +120,5 @@
> +# used and allow to skip recursing directories where changes are not going to require
> +# rebuild. A few directories, however, are still traversed all the time, mostly, the
> +# gyp managed ones and js/src.
> +# A few things that are not traversed by a "binaries" build, but should, in an ideal
> +# world, are nspr, nss, icu and ffi.

I assume you didn't implement the ideal world for performance reasons?

Comment 20

[Gregory Szorc [:gps]]

(In reply to Mike Hommey [:glandium] from comment #18)
> (In reply to Mike Hommey [:glandium] from comment #17)
> > (In reply to Gregory Szorc [:gps] from comment #16)
> > > - now that we have the virtualenv in pymake's sys.path, we can have all the
> > > $(call py_action) use native execution!
> > 
> > only if they do the right thing with their arguments.
> 
> which they don't.

Can we fix that?

Comment 21

[Mike Hommey [:glandium]]

(In reply to Gregory Szorc [:gps] from comment #19)
> We're introducing yet more dependencies on Makefile and backend.mk. This
> scares me a bit.

Why? In the case of the binaries target, the goal is to traverse directories where the makefile or backend.mk have changed. Which doesn't say whether something relevant to the target changed, but at least, it's going to traverse those directories in that case, instead of ignoring them, in which case we'd only hear complains.

Comment 22

[Mike Hommey [:glandium]]

Attachment: part 2 - Add a tool to link several dependency files together in three different ways

Just for proofreading of the added docstring.

Comment 23

[Mike Hommey [:glandium]]

Attachment: part 3 - Add a "binaries" tier that optimizes for recompilation times

Comment 24

[Gregory Szorc [:gps]]

Comment on attachment 812469 [details] [diff] [review]
part 3 - Add a "binaries" tier that optimizes for recompilation times

Review of attachment 812469 [details] [diff] [review]:
-----------------------------------------------------------------

The make code is very difficult to read. But the true test is always whether it works. And this patch does! I'm sure we'll find a bug somewhere. But, I think landing this code as an opt-in feature to make building faster is worth the complexity.

::: build/docs/build-targets.rst
@@ +19,5 @@
>     IDLs, etc.
>  
>  compile
>     Build the *compile* tier. The *compile* tier compiles all C/C++ files.
> +   Only applies to builds with MOZ_PSEUDO_DERECURSE.

``MOZ_PSEUDO_DERECURSE`` to get <code> treatment.

@@ +34,5 @@
> +binaries:
> +   Recompiles and relinks C/C++ files. Only works after a complete normal
> +   build, but allows for much faster rebuilds of C/C++ code. For performance
> +   reasons, however, it skips nss, nspr, icu and ffi.
> +   Only applies to builds with MOZ_PSEUDO_DERECURSE.

Perhaps add a note that this is targeted to improve the local developer workflow where developers are touching C/C++ files?

::: config/makefiles/target_libs.mk
@@ +115,5 @@
> +		)\
> +	))" | tr % '\n' > $@
> +endif
> +
> +binaries libs:: $(LIBRARY) $(SHARED_LIBRARY) $(PROGRAM) $(SIMPLE_PROGRAMS) $(HOST_LIBRARY) $(HOST_PROGRAM) $(HOST_SIMPLE_PROGRAMS) $(IMPORT_LIBRARY) $(BINARIES_PP)

This list mostly appears above. Do you think we should capture it in a variable? $(BINARY_TARGETS)?

@@ +123,5 @@
> +# need to be recursed to do their duty, and creating a stamp would prevent that.
> +# In the future, we'll aggregate those.
> +ifneq (.,$(DEPTH))
> +ifndef EXTERNALLY_MANAGED_MAKE_FILE
> +	@$(if $^,$(call py_action,link_deps,-o binaries --group-all --topsrcdir $(topsrcdir) --topobjdir $(DEPTH) --dist $(DIST) $(BINARIES_PP) $(wildcard $(addsuffix .pp,$(addprefix $(MDDEPDIR)/,$(notdir $(sort $(filter-out $(BINARIES_PP),$^) $(OBJS) $(PROGOBJS) $(HOST_OBJS) $(HOST_PROGOBJS))))))),$(TOUCH) binaries)

Ditto. $(OBJ_TARGETS)?

Comment 25

[Gregory Szorc [:gps]]

I forgot to mention it in part 2's review, but great documentation block in link_deps.py! You made future lives much easier.

Comment 26

[Mike Hommey [:glandium]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/ac89c4925d22
https://hg.mozilla.org/integration/mozilla-inbound/rev/99e29833c316
https://hg.mozilla.org/integration/mozilla-inbound/rev/6be8c784235c

Comment 27

[Mike Hommey [:glandium]]

And a fixup for test_link_deps to pass on windows:
https://hg.mozilla.org/integration/mozilla-inbound/rev/9e2b5c77f8fd

Comment 28

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/ac89c4925d22
https://hg.mozilla.org/mozilla-central/rev/99e29833c316
https://hg.mozilla.org/mozilla-central/rev/6be8c784235c
https://hg.mozilla.org/mozilla-central/rev/9e2b5c77f8fd