| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Use a topological sort to get a sorted list of edges to perform
the critical path weigth propagation as fast as possible.
The previous version used a data flow algorithm that forced
the values to be recomputed several times for far too many
edges on complex build plans.
For example, for a Fuchsia build plan with 93339 edges,
this reduces the ComputeCriticalPath metric from 1.9s to 80ms!
The unit-tests still pass, and manual testing shows that the
order of commands does not change before and after this change
for the example build plan above.
|
| | |
|
| |
|
|
|
|
|
|
| |
It causes the cursor handling to be extremely slow on MinGW.
Added in #2321.
Fixes #2435.
|
| |
|
|
|
|
|
|
| |
Using simple unordered sets is enough to perform the same
computation with less complexity, smaller and faster code.
On a large Fuchsia build plan, this reduces the
ComputeCriticalPath metric from 2.6s to 2.1s!
|
| |
|
|
| |
24694d95f5ddc7fe86bdcf4da9d34aef0fd6033d
|
| |\ |
|
| | | |
|
| | |\
| | |
| | | |
Implement type hints in `ninja_syntax.py`
|
| | | | |
|
| | |\ \
| | |/
| |/| |
Fix cleanded with dyndeps
|
| | | |
| | |
| | |
| | |
| | |
| | |
| | | |
Add code to check "pending" so as to avoid loading dyndep files that
have already been loaded. This was missed by commit a3cbb4d (clean:
remove outputs specified by dyndep files, 2019-02-12,
v1.10.0~1^2~53^2~4).
|
| | | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
Load this information before cleaning, as the normal `clean` operation
does. This was accidentally missed when commit 714621db (Adding a way
to clean dead build artifacts ..., 2018-04-27, v1.10.0~1^2~9^2~1) was
rebased after the normal `clean` operation was updated by commit a3cbb4d
(clean: remove outputs specified by dyndep files, 2019-02-12,
v1.10.0~1^2~53^2~4).
This fixes a bug causing artifacts to be spuriously flagged as "dead"
and erased.
|
| | |\ \
| | | |
| | | | |
Gracefully handle outdated .ninja_log during '-t recompact'
|
| | | | |
| | | |
| | | |
| | | | |
When we explicitly unlink the file we should return LOAD_NOT_FOUND instead of LOAD_SUCCESS
|
| | |\ \ \
| | |/ /
| |/| | |
CanonicalizePath: fix 'a/b/.._foo' -> 'a' replacement
|
| | | | |
| | | |
| | | |
| | | | |
Signed-off-by: Pavel Boldin <pboldin@cloudlinux.com>
|
| | |\ \ \
| | | | |
| | | | | |
GitHub Actions: Update Ubuntu versions to 20.04, 22.04 and 24.04
|
| | | | | | |
|
| | |/ / / |
|
| | |\ \ \
| | | | |
| | | | | |
Fix crash when FormatMessageA sets lpBuffer to nullptr
|
| | | |/ /
| | | |
| | | |
| | | | |
The std::string constructor would try to perform a strlen() call on the invalid pointer
|
| | |\ \ \
| | | | |
| | | | | |
graph.h: Use default initializers to remove -Worder warnings.
|
| | | |/ /
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | | |
A recent pull request modified the Edge class default constructor
but placed a member initializer at the wrong location, creating
annoying -Worder compiler warnings with recent Clang versions.
This is a recurrent problem every time we modify the classes
in this header, so get rid of the problem once and for all by
using C++11 default initializers when defining the members,
and simplifying the constructor.
Do the same for the Node class.
|
| | |\ \ \
| | | | |
| | | | | |
Minor fix to output_test.py
|
| | | |/ /
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | | |
Do not use os.chdir() to change the current directory inside
the run() function, as doing this prevents the temporary directory
from being removed.
Moreover, this breaks pytest invocations when adding new regression
test scripts in this directory (as done in other forks).
+ Use dict.pop() to undefine environment variables in `default_env`
dictionary.
|
| | |\ \ \
| | | | |
| | | | | |
Reliable ETA and progress percentage.
|
| | | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | | |
This has been bugging me for *years*. :)
Count of finished edges isn't a great statistic, it isn't
really obvious if LLVM will take 8 minues to build, or 10 minutes.
But, it's actually pretty straight-forward to get some
more useful information. We already know how much time each edge
has taken, so we could just do the dumb thing, and assume that
every edge in the plan takes the same amount of time.
Or, we can do better. `.ninja_log` already contains
the historical data on how long each edge took to produce it's outs,
so we simply need to ensure that we populate edges with that info,
and then we can greatly improve our predictions.
The math is pretty simple i think.
This is largely a port of a similar change i did to LLVM LIT:
https://reviews.llvm.org/D99073
With this, i get something quite lovely:
```
llvm-project/build-Clang12$ NINJA_STATUS="[%f/%t %p %P][%w + %W] " /repositories/ninja/build-Clang-debug/ninja opt
[288/2527 11% 4%][00:27 + 08:52] Building CXX object lib/DebugInfo/CodeView/CMakeFiles/LLVMDebugInfoCodeView.dir/AppendingTypeTableBuilder.cpp.o
```
I hope people will find this useful, and it could be merged.
|
| | |\ \ \ \
| | |_|/ /
| |/| | | |
Support empty depfiles.
|
| | |/ / /
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | | |
Some tools generate completely empty depfiles when
there are no implicit inputs. This patch modifies the
depfile parser to support them.
Fixes #2357
|
| | | | | |
|
| | |\ \ \
| | | | |
| | | | | |
Consider the remaining job capacity in main loop
|
| | | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | | |
This changes CanRunMore() to return an int instead of a bool. The
return value is the "remaining load capacity. That is the number of
new jobs that can be spawned without saturating a potential enabled
load limitation (if ninja's -l option is used). We assume that every
started edge increases the load by one. Hence the available "load
capacity" is the maximum allowed load minus the current load.
Previously, ninja would oversaturate the system with jobs, even though
a load and job limit was provided, when multiple ninja builds are
running. This is because changes in load average are inert, newly
started dobs to no immediatly change the load average, yet ninja
assumed that new jobs are immediately reflected in the load
average. Ninja would retrieve the current 1min load average, check if
it is below the limit and, if so, start a new job, and then
repeat. Since it takes a while for the new job to get reflected in the
load average, ninja would often spawn jobs until the job limit ("-j")
is reached. If this is done by multiple parallel ninja builds, then
the system becomes oversaturated, causing excessing context switches,
which eventually slow down each and every build process.
We can easily prevent this by considering the remaining load capacity
in ninja's main loop.
The following benchmark demonstrates how the change of this comit
helps to speed up multiple parallel builds on the same host. We
compare the total build times of 8 parallel builds of LLVM on a
256-core system using "ninja -j 258".
ninja-master: 1351 seconds
ninja-load-capacity: 920 seconds
That is, with this commit, the whole process becomes 1.46× faster.
The used benchmark script created and prepared 8 build directories,
records the start time, spawns 8 subshells invoking "ninja -j 258",
awaits the termination of those subshells, and records the end
time. Besides the total running time, it also outputs /proc/loadavg,
provides an indication of where the performance is gained:
ninja-master: 3.90 93.94 146.38 1/1936 209125
ninja-load-capacity: 92.46 210.50 199.90 1/1936 36917
So with this change, ninja uses the available hardware cores better in
the presence of competing ninja processes, while it does not overload
the system.
Finally, let us look at the two "dstat -cdgyl 60" traces of 8
parallel LLVM builds on a 256-core machine using "ninja -l 258":
ninja-master
--total-cpu-usage-- -dsk/total- ---paging-- ---system-- ---load-avg---
usr sys idl wai stl| read writ| in out | int csw | 1m 5m 15m
1 0 99 0 0| 12k 4759k| 5B 55B|1135 455 |17.9 70.3 38.1
38 6 56 0 0|2458B 7988k| 205B 0 | 34k 23k| 466 170 73.2
26 3 71 0 0| 102k 94M| 0 0 | 22k 6265 | 239 156 74.3
50 5 45 0 0|3149B 97M| 0 0 | 37k 12k| 257 191 92.2
58 6 36 0 0| 90k 71M| 0 0 | 43k 12k| 320 224 110
50 4 46 0 0| 52k 78M| 0 0 | 38k 6690 | 247 223 117
50 5 45 0 0| 202k 90M| 0 0 | 37k 9876 | 239 238 130
60 5 34 0 0| 109k 93M| 0 0 | 44k 8950 | 247 248 140
69 5 26 0 0|5939B 93M| 0 0 | 50k 11k| 309 268 154
49 4 47 0 0| 172k 111M| 0 0 | 36k 7835 | 283 267 161
58 7 35 0 0| 29k 142M| 0 0 | 45k 7666 | 261 267 168
72 4 24 0 0| 46k 281M| 0 0 | 50k 13k| 384 296 183
49 6 46 0 0| 68B 198M| 0 0 | 37k 6847 | 281 281 185
82 6 12 0 0| 0 97M| 0 0 | 59k 15k| 462 323 205
31 5 63 0 0| 0 301M| 0 0 | 26k 5350 | 251 291 202
66 7 28 0 0| 68B 254M| 0 0 | 49k 9091 | 270 292 208
68 8 25 0 0| 0 230M| 0 0 | 51k 8186 | 287 292 213
52 5 42 1 0| 0 407M| 0 0 | 42k 5619 | 207 271 211
29 7 64 0 0| 0 418M| 0 0 | 27k 2801 | 131 241 205
1 1 98 0 0| 137B 267M| 0 0 |1944 813 |55.8 199 193
0 0 100 0 0|2253B 43M| 0 0 | 582 365 |26.8 165 181
0 0 99 0 0| 0 68M| 0 0 | 706 414 |11.5 136 170
4 0 96 0 0| 0 13M| 0 0 |2892 378 |10.0 113 160
ninja-load-capacity
--total-cpu-usage-- -dsk/total- ---paging-- ---system-- ---load-avg---
usr sys idl wai stl| read writ| in out | int csw | 1m 5m 15m
1 0 98 0 0| 12k 5079k| 5B 55B|1201 470 |1.35 40.2 115
43 6 51 0 0|3345B 78M| 0 0 | 34k 20k| 247 127 142
71 6 23 0 0| 0 59M| 0 0 | 53k 8485 | 286 159 152
60 5 35 0 0| 68B 118M| 0 0 | 45k 7125 | 277 178 158
62 4 35 0 0| 0 115M| 0 0 | 45k 6036 | 248 188 163
61 5 34 0 0| 0 96M| 0 0 | 44k 9448 | 284 212 173
66 5 28 0 0| 9B 94M| 0 0 | 49k 5733 | 266 219 178
64 7 29 0 0| 0 159M| 0 0 | 49k 6350 | 241 223 182
66 6 28 0 0| 0 240M| 0 0 | 50k 9325 | 285 241 191
68 4 27 0 0| 0 204M| 0 0 | 49k 5550 | 262 241 194
68 8 24 0 0| 0 161M| 0 0 | 53k 6368 | 255 244 198
79 7 14 0 0| 0 325M| 0 0 | 59k 5910 | 264 249 202
72 6 22 0 0| 0 367M| 0 0 | 54k 6684 | 253 249 205
71 6 22 1 0| 0 377M| 0 0 | 52k 8175 | 284 257 211
48 8 44 0 0| 0 417M| 0 0 | 40k 5878 | 223 247 210
23 4 73 0 0| 0 238M| 0 0 | 22k 1644 | 114 214 201
0 0 100 0 0| 0 264M| 0 0 |1016 813 |43.3 175 189
0 0 100 0 0| 0 95M| 0 0 | 670 480 |17.1 144 177
As one can see in the above dstat traces, ninja-master will have a
high 1min load average, of up to 462. This is because ninja will not
considered the remaining load capacity when spawning new jobs, but
instead spawn as new jobs until it runs into the -j limitation. This,
in turn, causes an increase of context switches: the rows with a high
1min load average also have >10k context switches (csw). Whereas a
remaining load-capacity aware ninja avoids oversaturing the system
with excessive additional jobs.
Note that since the load average is an exponentially damped moving
sum, build systems that take the load average into consideration to
limit the load average to the number of available processors will
always (slightly) overprovision the system with tasks. Eventually,
this change decreases the aggressiveness ninja schedules new jobs if
the '-l' knob is used, and by that, the level of overprovisioning, to
a reasonable level compared to the status quo. It should be mentioned
that this means that an individual build using '-l' will now be
potentially a bit slower. However, this can easily be fixed by
increase the value provided to the '-l' argument.
The benchmarks where performed using the following script:
set -euo pipefail
VANILLA_NINJA=~/code/ninja-master/build/ninja
LOAD_CAPACITY_AWARE_NINJA=~/code/ninja-load-capacity/build/ninja
CMAKE_NINJA_PROJECT_SOURCE=~/code/llvm-project/llvm
declare -ir PARALLEL_BUILDS=8
readonly TMP_DIR=$(mktemp --directory --tmpdir=/var/tmp)
cleanup() {
rm -rf "${TMP_DIR}"
}
trap cleanup EXIT
BUILD_DIRS=()
echo "Preparing build directories"
for i in $(seq 1 ${PARALLEL_BUILDS}); do
BUILD_DIR="${TMP_DIR}/${i}"
mkdir "${BUILD_DIR}"
(
cd "${BUILD_DIR}"
cmake -G Ninja "${CMAKE_NINJA_PROJECT_SOURCE}" \
&> "${BUILD_DIR}/build.log"
)&
BUILD_DIRS+=("${BUILD_DIR}")
done
wait
NPROC=$(nproc)
MAX_LOAD=$(echo "${NPROC} + 2" | bc )
SLEEP_SECONDS=300
NINJA_BINS=(
"${VANILLA_NINJA}"
"${LOAD_CAPACITY_AWARE_NINJA}"
)
LAST_NINJA_BIN="${LOAD_CAPACITY_AWARE_NINJA}"
for NINJA_BIN in "${NINJA_BINS[@]}"; do
echo "Cleaning build dirs"
for BUILD_DIR in "${BUILD_DIRS[@]}"; do
(
"${NINJA_BIN}" -C "${BUILD_DIR}" clean &> "${BUILD_DIR}/build.log"
)&
done
wait
echo "Starting ${PARALLEL_BUILDS} parallel builds with ${NINJA_BIN} using -j ${MAX_LOAD}"
START=$(date +%s)
for BUILD_DIR in "${BUILD_DIRS[@]}"; do
(
"${NINJA_BIN}" -C "${BUILD_DIR}" -l "${MAX_LOAD}" &> "${BUILD_DIR}/build.log"
)&
done
wait
STOP=$(date +%s)
DELTA_SECONDS=$((STOP - START))
echo "Using ${NINJA_BIN} to perform ${PARALLEL_BUILDS} of ${CMAKE_NINJA_PROJECT_SOURCE}"
echo "took ${DELTA_SECONDS} seconds on this ${NPROC} core system using -j ${MAX_LOAD}"
echo "/proc/loadavg:"
cat /proc/loadavg
echo "ninja --version:"
"${NINJA_BIN}" --version
if [[ "${NINJA_BIN}" != "${LAST_NINJA_BIN}" ]]; then
echo "Sleeping ${SLEEP_SECONDS} seconds to bring system into quiescent state"
sleep ${SLEEP_SECONDS}
fi
done
|
| | |\ \ \ \
| | | | | |
| | | | | | |
Add simplified critical path scheduler to improve build times
|
| | | | | | | |
|
| | | |\ \ \ \ |
|
| | | | | | | | |
|
| | | | | | | | |
|
| | | | | | | | |
|
| | | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | | |
AddTarget cannot add edges to the ready queue before the critical time
has been computed.
|
| | | | | | | | |
|
| | | | | | | | |
|
| | | | | | | | |
|
| | | | | | | | |
|
| | | |\ \ \ \ \ |
|
| | | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | | |
1. Move EdgePriorityQueue to graph.h and inherit from priority_queue
2. Add comment about edge->critical_time()
|
| | | | | | | | | |
|
| | | | | | | | | |
|
| | | | | | | | | |
|
| | | | | | | | | |
|
