core: add rule to dump packages' build order

When debugging hidden dependencies, the build order is very important. Most notably, it is interesting to identify potential culprits.

Add a new top-level rule, show-biuld-order, that dumps all the packages in the order they would get built.

Note that there are a few differences with show-targets:

- more packages are reported, becasue show-targets does not report

    host packages that have no prompt;

- the output is line-based, because we're using $(info $(1)); getting

    a single output line like show-targets would require we use an
    actual command, like printf '%s ' $(1); but that takes a lot of
    time, while $(info $(1)) is almost instantaneous (the time to parse
    the Makefiles);

- rootfs targets are not reported.

Signed-off-by "Yann E. MORIN" <[email protected]>

Cc Thomas Petazzoni <[email protected]>

Cc Arnout Vandecappelle <[email protected]>

Cc Peter Korsgaard <[email protected]>

---
 Makefile               | 2 ++
 package/pkg-generic.mk | 3 +++
 2 files changed, 5 insertions(+)

Makefile +2 -0

index 941bf78..919d589 100644
@@ -757,6 +757,8 @@ legal-info: dirs legal-info-clean legal-info-prepare $(foreach p,$(PACKAGES),$(p
 show-targets:
 	@echo $(PACKAGES) $(TARGETS_ROOTFS)
 
+show-build-order: $(patsubst %,%-show-build-order,$(PACKAGES))
+
 graph-build: $(O)/build/build-time.log
 	@install -d $(GRAPHS_DIR)
 	$(foreach o,name build duration,./support/scripts/graph-build-time \

package/pkg-generic.mk +0 -0

index 31dbc54..3b26e6b 100644

package/pkg-generic.mk +0 -0

 $(1)-graph-depends: graph-depends-requirements
 	$(call pkg-graph-depends,$(1),--direct)
 

Quoted 46 lines

When debugging hidden dependencies, the build order is very important. Most notably, it is interesting to identify potential culprits.

Add a new top-level rule, show-biuld-order, that dumps all the packages in the order they would get built.

Note that there are a few differences with show-targets:

- more packages are reported, becasue show-targets does not report

    host packages that have no prompt;

- the output is line-based, because we're using $(info $(1)); getting

    a single output line like show-targets would require we use an
    actual command, like printf '%s ' $(1); but that takes a lot of
    time, while $(info $(1)) is almost instantaneous (the time to parse
    the Makefiles);

- rootfs targets are not reported.

Signed-off-by "Yann E. MORIN" <[email protected]>

Cc Thomas Petazzoni <[email protected]>

Cc Arnout Vandecappelle <[email protected]>

Cc Peter Korsgaard <[email protected]>

---
 Makefile               | 2 ++
 package/pkg-generic.mk | 3 +++
 2 files changed, 5 insertions(+)

Makefile +2 -0

index 941bf78..919d589 100644
@@ -757,6 +757,8 @@ legal-info: dirs legal-info-clean legal-info-prepare $(foreach p,$(PACKAGES),$(p
 show-targets:
 	@echo $(PACKAGES) $(TARGETS_ROOTFS)
 
+show-build-order: $(patsubst %,%-show-build-order,$(PACKAGES))
+
 graph-build: $(O)/build/build-time.log
 	@install -d $(GRAPHS_DIR)
 	$(foreach o,name build duration,./support/scripts/graph-build-time \

package/pkg-generic.mk +0 -0

index 31dbc54..3b26e6b 100644

package/pkg-generic.mk $(1)-show-depends: · line 742

Quoted 6 lines

package/pkg-generic.mk +3 -0

@@ -737,6 +737,9 @@ $(1)-show-depends:
 $(1)-show-rdepends:
 			@echo $$($(2)_RDEPENDENCIES)
 
+$(1)-show-build-order: $$(patsubst %,%-show-build-order,$$($(2)_FINAL_ALL_DEPENDENCIES))
+	$$(info $(1))
+

I don't like this...

IMO we already have way too many of these informational targets messing up
pkg-generic.mk. This is bad for two reasons:

- it makes the code more complicated, more difficult to understand what's going on int pkg-generic.mk;

- it's bad for performance. This adds 2000 rules to the make rules database, which makes the dependency resolution slower (even if this rule is not used). Just this one extra rule doesn't make much of a difference, but it's all these extra rules that we've added over the years combined that make it slower. That said, there is probably some refactoring that could be done to make it less bad, so it's not too big of a factor.

But I wonder why you need this feature anyway. If you just build, you see the
build order as well, right?

And if you don't want to see the actual build, you can do 'make -nk'.

OK, it looks a lot nicer with this show-build-order target, but I wouldn't say it's very valuable.

Arnout, All,

On 2017-04-03 12:10 +0200, Arnout Vandecappelle spake thusly:

Quoted 1 line · Yann E. MORIN

Quoted 12 lines

package/pkg-generic.mk $(1)-show-depends: · line 742

Quoted 3 lines

+$(1)-show-build-order: $$(patsubst %,%-show-build-order,$$($(2)_FINAL_ALL_DEPENDENCIES))

package/pkg-generic.mk +2 -0

+	$$(info $(1))
+

I don't like this...

IMO we already have way too many of these informational targets messing up
pkg-generic.mk. This is bad for two reasons:

- it makes the code more complicated, more difficult to understand what's going on int pkg-generic.mk;

Quoted 6 lines

- it's bad for performance. This adds 2000 rules to the make rules database, which makes the dependency resolution slower (even if this rule is not used). Just this one extra rule doesn't make much of a difference, but it's all these extra rules that we've added over the years combined that make it slower. That said, there is probably some refactoring that could be done to make it less bad, so it's not too big of a factor.

Timing the run before/after this change does not yield a noticeable difference

, tested with:

    $ for((i=0;i<50;i++)); do
        /usr/bin/time make CMD 2>&1 >/dev/null |head -n 1

done

with CMD = help, before and after the patch, and then with CMD = show-build-order (obviously, after the patch), and using the 'user' part of the timings:

                    Help, before    Help, after     Build order
Mean                2.9612          2.9934          2.9716

Quoted 2 lines

But I wonder why you need this feature anyway. If you just build, you see the
build order as well, right?

Oh yeah, and I pay the price of a three-hour build, jsut to see the build order...

Quoted 2 lines

And if you don't want to see the actual build, you can do 'make -nk'.

I hope you were kidding? For a config with 227 packages, this yields:

    $ make -nk 2>&1 |wc -l
    8459

And I'm not doing the statistical analysis I did above, but a few runs give a runtime of ~5s. So it is a 66% overhead just for this, while the new rules add just about 1% overhead (30ms for 3s).

Plus, it requires non-trivial post-processing... :-(

Quoted 2 lines

OK, it looks a lot nicer with this show-build-order target, but I wouldn't say it's very valuable.

Well, I've been tracking build-order issues for a while last WE, and believe me, I was very happy to be able to see the build order before I attempted a build, yes.

Quoted 3 lines

Well, I've been tracking build-order issues for a while last WE, and believe me, I was very happy to be able to see the build order before I attempted a build, yes.

That's my biggest problem with this feature: I have no idea how to use it.
Could you add some explanation somewhere?

Hello,

Quoted 6 lines · Arnout Vandecappelle

Quoted 3 lines

Well, I've been tracking build-order issues for a while last WE, and believe me, I was very happy to be able to see the build order before I attempted a build, yes.

That's my biggest problem with this feature: I have no idea how to use it.
Could you add some explanation somewhere?

Yann was tracking down the dc3dd failure. With some configurations it was building, with others not. So he was trying to figure which package that gets built before dc3dd causes the problem. For this, it was really nice to be able to load a configuration, and immediately see in which order packages would be built, and therefore which packages would be built before dc3dd, without having to do the build itself.

Does that explain better the use case for this?

Best regards,

Thomas

Quoted 7 lines

Quoted 6 lines

- it's bad for performance. This adds 2000 rules to the make rules database, which makes the dependency resolution slower (even if this rule is not used). Just this one extra rule doesn't make much of a difference, but it's all these extra rules that we've added over the years combined that make it slower. That said, there is probably some refactoring that could be done to make it less bad, so it's not too big of a factor.

Quoted 2 lines

Timing the run before/after this change does not yield a noticeable difference

As I wrote: "Just this one extra rule doesn't make much of a difference".
However, we have about a dozen rules like this, and added together they *do* make a noticable difference (I did a much less thorough benchmark; after removing all these one-shot rules that are not used in a normal build, a 'make -qp >/dev/null' became about 15% faster).

Quoted 4 lines

, tested with:

    $ for((i=0;i<50;i++)); do
        /usr/bin/time make CMD 2>&1 >/dev/null |head -n 1

What I'm interested in is the overhead of running make. We unfortunately don't
have a good target for that. 'make -q' after finishing a build is a nice approximation because it doesn't actually run the target-finalize step (as opposed to just 'make'). I usually use 'make -qp' because that's what's used by bash-completion and that is one of my big annoyances: accidentally typing TAB-TAB freezes the shell for almost 10 seconds.

'make help' isn't a bad approximation either. It doesn't evaluate the .stamp_*
files so it will be a bit faster than the real overhead.

Now, I repeat: adding this single thing is not a big deal. I just say we have
to be careful about adding things all the time that slow things down. We are very quickly approaching the speed of bitbake, and that is one of the main reasons I spit out OE the first time I used it...

Quoted 2 lines

Quoted 2 lines

And if you don't want to see the actual build, you can do 'make -nk'.

Quoted 1 line

Plus, it requires non-trivial post-processing... :-(

TERM=dumb make -nk 2>/dev/null | grep 'Configuring"' | cut -d ' ' -f 3-4

True, it's not trivial. But it's shorter than your patch :-) And indeed it's 4
times slower than 'make build-order'. But that's just 12 seconds for an allyesconfig. Is that really too much?

However, it turns out not to work :-( Any rule which contains $(MAKE) is still
going to be executed, and that will inevitably lead to errors, so any package that depends on a package that errors out will also not be executed.

So, I can think of no viable alternative, so there is no way to stop this patch :-)

Quoted 6 lines

Quoted 2 lines

OK, it looks a lot nicer with this show-build-order target, but I wouldn't say it's very valuable.

Well, I've been tracking build-order issues for a while last WE, and believe me, I was very happy to be able to see the build order before I attempted a build, yes.

That's my biggest problem with this feature: I have no idea how to use it.
Could you add some explanation somewhere?

Quoted 1 line

So, I can think of no viable alternative, so there is no way to stop this patch :-)

What about the following (just proof-of-concept):

Arnout, All,

On 2017-04-07 12:30 +0200, Arnout Vandecappelle spake thusly:

Quoted 8 lines · Yann E. MORIN

Quoted 7 lines

Quoted 6 lines

- it's bad for performance. This adds 2000 rules to the make rules database, which makes the dependency resolution slower (even if this rule is not used). Just this one extra rule doesn't make much of a difference, but it's all these extra rules that we've added over the years combined that make it slower. That said, there is probably some refactoring that could be done to make it less bad, so it's not too big of a factor.

Quoted 8 lines

Quoted 2 lines

Timing the run before/after this change does not yield a noticeable difference

As I wrote: "Just this one extra rule doesn't make much of a difference".
However, we have about a dozen rules like this, and added together they *do* make a noticable difference (I did a much less thorough benchmark; after removing all these one-shot rules that are not used in a normal build, a 'make -qp >/dev/null' became about 15% faster).

OK, adding features makes the stuff slower; that I do understand.

However, what I argue is that the overhead added by that one extra rule is negligible, relatively to the existing startup time.

Quoted 4 lines

Now, I repeat: adding this single thing is not a big deal. I just say we have
to be careful about adding things all the time that slow things down. We are very quickly approaching the speed of bitbake, and that is one of the main reasons I spit out OE the first time I used it...

Eh... The startup tiem is annoying, but it is not awfull. Yet. Howeber, in my (arguably limited) experience of OE, the build time was much longer overall for a similar setup. So we still win AFAICS...

The only thing that would be a killer feature is TLPB (as long as it yields a correct build, of course).

Quoted 3 lines

Quoted 3 lines

Quoted 3 lines

And if you don't want to see the actual build, you can do 'make -nk'.

[--SNIP--]

Quoted 7 lines

Quoted 1 line

Plus, it requires non-trivial post-processing... :-(

TERM=dumb make -nk 2>/dev/null | grep 'Configuring"' | cut -d ' ' -f 3-4

True, it's not trivial. But it's shorter than your patch :-) And indeed it's 4
times slower than 'make build-order'. But that's just 12 seconds for an allyesconfig. Is that really too much?

Quoted 5 lines

However, it turns out not to work :-( Any rule which contains $(MAKE) is still
going to be executed, and that will inevitably lead to errors, so any package that depends on a package that errors out will also not be executed.

So, I can think of no viable alternative, so there is no way to stop this patch :-)

What about the following (just proof-of-concept):

Makefile +8 -0

index 919d589..a1540fc 100644
@@ -759,6 +759,14 @@ show-targets:
 
 show-build-order: $(patsubst %,%-show-build-order,$(PACKAGES))
 
+define show-build-order-deps
+	$(foreach p,$($(call UPPERCASE,$(1))_FINAL_ALL_DEPENDENCIES),\
+		$(call show-build-order-deps-deps,$(p))) $(1)
+endef
+
+show-build-order-2:
+	@./toto $(foreach p,$(PACKAGES),$(call show-build-order-deps-deps,$(p)))
+
 graph-build: $(O)/build/build-time.log
 	@install -d $(GRAPHS_DIR)
 	$(foreach o,name build duration,./support/scripts/graph-build-time \

toto new file +20 -0

new file mode 100755
index 0000000..6962083
@@ -0,0 +1,30 @@
+#!/bin/bash
+
+# input on stdin: list of packages, each rpreceded by its
+# direct dependencies; so, packages may be listed more than
+# once, but at least the build order is gurranteed for the
+# first occurence of each package.
+
+# We first output each item of the list on its own line.
+# Then we number those lines.
+# We sort by package name as first key, and on line number
+# as second key.
+# For each package, we keep only the first occurence, which
+# is the one with the lowest line number.
+# We re-sort on the line number.
+# And eventually, we remove the line number and only keep
+# the package name.
+
+# The output is thus the build order.
+
+printf "%s\n" "${@}"

This has the advantage that it adds a single rule, and the price of expansion is paid only when the rule is actually called.

Plus, the runtime is not worse than my initial solution.

Quoted 3 lines

Quoted 3 lines

Quoted 2 lines

OK, it looks a lot nicer with this show-build-order target, but I wouldn't say it's very valuable.

Quoted 6 lines

Quoted 3 lines

Well, I've been tracking build-order issues for a while last WE, and believe me, I was very happy to be able to see the build order before I attempted a build, yes.

That's my biggest problem with this feature: I have no idea how to use it.
Could you add some explanation somewhere?

I hope the explanations from Thomas are enough? ;-)

In my experience, there are two big reasons why an OE build is much slower:

1. A typical configuration is much bigger (more packages selected).

2. They do per-package staging in order to enable TLPB.

Quoted 4 lines · Arnout Vandecappelle

In my experience, there are two big reasons why an OE build is much slower:

1. A typical configuration is much bigger (more packages selected).

Quoted 1 line

2. They do per-package staging in order to enable TLPB.

This point (2) is in fact not correct, at least according to what I understood. My colleague Alexandre can confirm, but apparently, per-package staging has only been very recently introduced in OE. And yes, top-level parallel build was causing some spurious build failures.

Alex, if you have more details, we're interested :)

When debugging hidden dependencies, the build order is very important. Most notably, it is interesting to identify potential culprits.

Add a new top-level rule, show-biuld-order, that dumps all the packages

in the order they would get built.

Note that there are a few differences with show-targets:

- more packages are reported, becasue show-targets does not report

    host packages that have no prompt;

- the output is line-based, because we're using $(info $(1)); getting

    a single output line like show-targets would require we use an
    actual command, like printf '%s ' $(1); but that takes a lot of
    time, while $(info $(1)) is almost instantaneous (the time to parse
    the Makefiles);

- rootfs targets are not reported.

Signed-off-by "Yann E. MORIN" <[email protected]>

Cc Thomas Petazzoni <[email protected]>

Cc Arnout Vandecappelle <[email protected]>

Cc Peter Korsgaard <[email protected]>

---
 Makefile               | 2 ++
 package/pkg-generic.mk | 3 +++
 2 files changed, 5 insertions(+)

Makefile +2 -0

index 941bf78..919d589 100644
@@ -757,6 +757,8 @@ legal-info: dirs legal-info-clean legal-info-prepare $(foreach p,$(PACKAGES),$(p
 show-targets:
 	@echo $(PACKAGES) $(TARGETS_ROOTFS)
 
+show-build-order: $(patsubst %,%-show-build-order,$(PACKAGES))
+
 graph-build: $(O)/build/build-time.log
 	@install -d $(GRAPHS_DIR)
 	$(foreach o,name build duration,./support/scripts/graph-build-time \

package/pkg-generic.mk +3 -0

index 31dbc54..3b26e6b 100644
@@ -737,6 +737,9 @@ $(1)-show-depends:
 $(1)-show-rdepends:
 			@echo $$($(2)_RDEPENDENCIES)
 
+$(1)-show-build-order: $$(patsubst %,%-show-build-order,$$($(2)_FINAL_ALL_DEPENDENCIES))
+	$$(info $(1))
+
 $(1)-graph-depends: graph-depends-requirements
 	$(call pkg-graph-depends,$(1),--direct)
 

Quoted 4 lines · Yann E. MORIN

When debugging hidden dependencies, the build order is very important. Most notably, it is interesting to identify potential culprits.

Add a new top-level rule, show-biuld-order, that dumps all the packages

build

Quoted 5 lines

in the order they would get built.

Note that there are a few differences with show-targets:

- more packages are reported, becasue show-targets does not report

because

Quoted 8 lines

    host packages that have no prompt;

- the output is line-based, because we're using $(info $(1)); getting

    a single output line like show-targets would require we use an
    actual command, like printf '%s ' $(1); but that takes a lot of
    time, while $(info $(1)) is almost instantaneous (the time to parse
    the Makefiles);

Quoted 3 lines

- rootfs targets are not reported.

Signed-off-by "Yann E. MORIN" <[email protected]>

Reviewed-by Arnout Vandecappelle (Essensium/Mind) <[email protected]>

When debugging hidden dependencies, the build order is very important. Most notably, it is interesting to identify potential culprits.

Add a new top-level rule, show-biuld-order, that dumps all the packages in the order they would get built.

Note that there are a few differences with show-targets:

- more packages are reported, becasue show-targets does not report

    host packages that have no prompt;

- the output is line-based, because we're using $(info $(1)); getting

    a single output line like show-targets would require we use an
    actual command, like printf '%s ' $(1); but that takes a lot of
    time, while $(info $(1)) is almost instantaneous (the time to parse
    the Makefiles);

- rootfs targets are not reported.

Signed-off-by "Yann E. MORIN" <[email protected]>

Cc Thomas Petazzoni <[email protected]>

Cc Arnout Vandecappelle <[email protected]>

Cc Peter Korsgaard <[email protected]>

---
 Makefile               | 2 ++
 package/pkg-generic.mk | 3 +++
 2 files changed, 5 insertions(+)