[PATCH v2 0/6] Improve make and make check parallelism

[Adhemerval Zanella]

One thing that has bothered me for some time is that neither 'make' nor
'make check' scales well with the number of cores: although each
subdirectory builds with full internal parallelism, the top-level
recursion is marked .NOTPARALLEL and runs the sub-makes strictly one at
a time.

Every subdirectory's compile tail and link step therefore leaves most
cores idle, and the constant additions to the testsuite keep making it
worse.  Profiling the check phase also showed that some of the tests-special
are among the main culprits, most notably check-installed-headers, which
performs dozens of serial compiler invocations per installed header.

This series makes the subdirectory recursion run in parallel while
encoding the ordering the serial recursion relied on as explicit
dependencies:

  1. scripts/gen-sorted.awk also emits the dependency edges it already
     collects from the Depend files, so the parent makefile can use
     them as real rules instead of a flattened total order.

  2. The top-level Makefile drops .NOTPARALLEL.  The subdirectories
     that generate shared files consumed by the rest of the build run
     serially first (csu, plus mach and hurd on Hurd), the Depend
     edges become rule dependencies, elf stays last (its rtld link
     consumes the aggregated libc_pic.a), pass barriers keep others
     after lib and tests after others, and the subdirectory-built
     files that top-level rules list as prerequisites get order-only
     edges.

  3. The tests and xtests classes carry only the pass barrier and none
     of the csu-first or Depend edges, so 'make subdir/tests' runs just
     that subdirectory's tests.  A full 'make check' (run-built-tests=yes)
     additionally serializes the timing-sensitive runs (see below).

  4. elf is no longer forced last for the others and tests passes,
     where the pass barriers already provide everything it needs.

  5. The container testroot, which performs a full DESTDIR
     installation, is no longer created when run-built-tests=no, since
     no container test will run.

  6. check-installed-headers compiles each header through its own
     intermediate target so the compiler invocations spread across the
     jobserver; the per-subdirectory .out aggregates the results in
     the original order, so its contents and the test results are
     unchanged.

A new 'make check-parallel' (and 'xcheck-parallel') runs the whole
testsuite with *no serialization at all*, through a new
serialize-tests flag (default on) that gates the per-subdirectory
.NOTPARALLEL and the run-time ordering.

Unlike v1, the series now also speeds up a full 'make check' with
run-built-tests=yes.  The timing-sensitive subdirectories -- nptl (or
htl on Hurd) and rt -- must not have their tests run under heavy
parallel load, so their runs are serialized (each keeps a .NOTPARALLEL)
and ordered after the rest of the test run, one group at a time, the
threading subdirectory then rt.

Their test programs, however, are still built with full parallelism,
since building and running a subdirectory's tests are fused in a single
sub-make. The 'make check' now runs in two passes -- it builds every test
program with run-built-tests=no, where the recursion is fully parallel,
and then runs the tests with run-built-tests=yes.  

Build results are unchanged: all built objects, archives, and shared
objects are bit-identical to the serial build across repeated clean
parallel builds, the installed tree layout is identical, and the
tests.sum results are identical.  Since most of the possible failure
modes are races, the series was validated with repeated from-scratch
builds on x86_64-linux-gnu (24 threads), aarch64-linux-gnu (80 cores).

Benchmarks (cumulative; each percentage is relative to the previous
row, the first patch only adds data and acts as the baseline):

* x86_64 [1]

Commit                                                                | make                 | make check [3]
----------------------------------------------------------------------|----------------------|------------------------------------------
scripts/gen-sorted.awk: Also emit the subdirectory dependency edges   | 1m18,728s            | 6m14,957s
Makefile: Run the subdirectory recursion in parallel                  | 1m01,713s  (-21.6%)  | 3m10,413s  (-49.2%)
Makefile: Do not force elf last for the others and tests passes       | 1m00,562s  (-1.9%)   | 3m01,644s  (-4.6%)
Makefile: Do not install the container testroot if not running tests  | 1m00,703s  (+0.2%)   | 2m49,552s  (-6.7%)
Run check-installed-headers concurrently for each header              | 1m00,598s  (-0.2%)   | 2m50,389s  (+0.5%)
----------------------------------------------------------------------|----------------------|------------------------------------------

* aarch64: Neoverse-N1 / 80c [2]

Commit                                                                | make                 | make check [3]
----------------------------------------------------------------------|----------------------|------------------------------------------
scripts/gen-sorted.awk: Also emit the subdirectory dependency edges   | 1m45.251s            | 14m46.183s
Makefile: Run the subdirectory recursion in parallel                  | 0m56.703s  (-46.1%)  | 04m58.726s  (-66.3%)
Makefile: Do not force elf last for the others and tests passes       | 0m53.887s  (-5.0%)   | 04m23.790s  (-11.7%)
Makefile: Do not install the container testroot if not running tests  | 0m54.801s  (+1.7%)   | 04m01.574s  (-8.4%)
Run check-installed-headers concurrently for each header              | 0m54.978s  (+0.3%)   | 03m02.405s  (-24.5%)
----------------------------------------------------------------------|----------------------|------------------------------------------

A full 'make check' with run-built-tests=yes, baseline (serial
recursion) versus the full series, and with 'make check-parallel':

* x86_64: Ryzen 5900 / 12c/24t

Configuration							      | make check [3]
----------------------------------------------------------------------|---------------
baseline (serial recursion					      | 17m43,757s
this series (make check						      | 12m52,644s
this series (make check-parallel)				      |  5m54,945s
----------------------------------------------------------------------|---------------

* aarch64: Neoverse-N1 / 80c

Configuration							      | make check [3]
----------------------------------------------------------------------|---------------
baseline (serial recursion					      | 29m37.604s
this series (make check						      | 15m01.576s
this series (make check-parallel)				      | 12m52.494s
----------------------------------------------------------------------|---------------

On aarch64 (80c) 'make check-parallel' oversubscribes the machine
enough to produce spurious test timeouts (note the sys time), so it
needs a larger TIMEOUTFACTOR there; the default 'make check' does not.

[1] Ryzen 5900 / 12c/24t, gcc 16.1.1 / ld 2.46 / gnumake 4.3, targetting x86_64-linux-gnu
[2] Neoverse-N1 / 80c, gcc 15.2.1 / ld 2.45 / gnumake 4.3, targetting aarch64-linux-gnu
[3] run-built-tests=no
[4] run-built-tests=yes

Changes since v1:

* 'make subdir/tests' now runs only that subdirectory's tests; in v1
  the Depend edges on the tests class also pulled in (and ran) the
  tests of every subdirectory reachable through them.

* A full 'make check' (run-built-tests=yes) is now supported and
  faster: nptl/htl and rt are run serially and last, each with its
  own .NOTPARALLEL, while their test programs still build in parallel
  via the two-pass 'make check' described above.

* New 'make check-parallel'/'xcheck-parallel' to run the suite with no
  serialization (patch 6).

* catgets: declare its test locales through gen-locales.mk.  catgets runs
  gencat under those locales but never declared them as prerequisites.


Adhemerval Zanella (6):
  scripts/gen-sorted.awk: Also emit the subdirectory dependency edges
  Makefile: Run the subdirectory recursion in parallel
  Makefile: Do not force elf last for the others and tests passes
  Makefile: Do not install the container testroot if not running tests
  Run check-installed-headers concurrently for each header
  Makerules: add 'make check-parallel' to run tests without
    serialization

 Makeconfig             |   8 ++
 Makefile               | 195 ++++++++++++++++++++++++++++++++++++++---
 Makerules              |  44 +++++++++-
 Rules                  |  38 +++++---
 catgets/Makefile       |  14 ++-
 elf/Makefile           |   5 ++
 htl/Makefile           |   8 ++
 nptl/Makefile          |   5 +-
 rt/Makefile            |   9 ++
 scripts/gen-sorted.awk |   6 ++
 10 files changed, 298 insertions(+), 34 deletions(-)

-- 
2.43.0