Makefile parallelism respects dependency graph

If we take this Makefile:

.PHONY: one
one:
	echo "one" && sleep 1

.PHONY: two
two: one
	echo "two" && sleep 1

.PHONY: three-a
three-a: two
	echo "three-a" && sleep 2

.PHONY: three-b
three-b: two
	echo "three-b" && sleep 2

.PHONY: three-c
three-c: two
	echo "three-c" && sleep 2

.PHONY: final
final: three-a three-b three-c
	echo "final" && sleep 1

# shortest path (-j):    1+1+2+1=5
# two parallelism (-j2): 1+1+2+2+1=7
# serial path (-j1):     1+1+2+2+2+1=9

…and run it under 3 different scenarios, we can see that Makefile

• understands the dependency graph
• is smart enough to run parallel steps where it can

Unlimited parallelism gives the fastest possible run:

$ time make -j final
echo "one" && sleep 1
one
echo "two" && sleep 1
two
echo "three-a" && sleep 2
echo "three-b" && sleep 2
echo "three-c" && sleep 2
three-a
three-b
three-c
echo "final" && sleep 1
final
make -j final  0.01s user 0.01s system 0% cpu 5.017 total

Parallelism=2 gives slower, but still faster than serial performance:

$ time make -j2 final
echo "one" && sleep 1
one
echo "two" && sleep 1
two
echo "three-a" && sleep 2
echo "three-b" && sleep 2
three-a
three-b
echo "three-c" && sleep 2
three-c
echo "final" && sleep 1
final
make -j2 final  0.01s user 0.01s system 0% cpu 7.020 total

And serial execution is the slowest:

$ time make -j1 final
echo "one" && sleep 1
one
echo "two" && sleep 1
two
echo "three-a" && sleep 2
three-a
echo "three-b" && sleep 2
three-b
echo "three-c" && sleep 2
three-c
echo "final" && sleep 1
final
make -j1 final  0.02s user 0.00s system 0% cpu 9.022 total

This is a pretty “yeah, duh” type of realisation, but it’s nice to have simple proof that it works.