Please explain, several minutes until the first g++ (or another
compiler call)? Or several minutes to complete an entire --dry-run
incremental or full build?
I'm thinking now it is somewhat difficult to actually measure the
performance of the build system itself. I've always used time to
first compiler execution because even though I would prefer to do
something like a --dry-run a --dry-run will obviously not trigger
all the dependencies that would be triggered in a real run since
the targets of multiple output rules are not understood by make
and will not actually be modified.
I've included several metrics, most of the relevant ones. I did not
include any good testing of an actual incremental build, as that would
be more involved than I have time for right now, but I believe that it
should lie somewhere between the times for "all build from all build"
and "all build from clean".
Furthermore, I wasn't making any effort to sporadically touch
multiple files which could effect the analysis time. Though I have
not thought that through and given your experience in writing make
clones you would be in a much better position to comment on that
possibility?
However, there is still a chance that this could be as simple as
a poor choice of = when := would have done.
As I promised earlier, here is some speed testing between my make
clone and GNU Make.
The source code for the test generator, and the script used to run the
tests, is at the end of this post.
The short version of what my tests were is: The dependency graph is a
balanced binary tree with roughly 25,000 nodes, with a single root,
where each node has 75 children except for the leafs. I figured that
this is somewhat indicative of the dependency graph of C++ source
code. (At least, without header dependencies. That could get a lot
more complex trying to model. I figure that this is still a relatively
indicative test of real world usage, though by no means exhaustive or
foolproof.) I hope I have no glaring mistakes or oversights. I'm
welcome to rerun it or redesign the test if you find any problems.
The command to "build" each node is simply touch. Rules for cleaning
are also present. It's only a skeleton implementation of a correct
incremental build system, but hopefully it is indicative of a fully
fleshed out build system. I think it is. This testing here also fits
with my previous experience implementing such a fully fleshed out
build system and comparing the time with GNU Make and my make clone.
Tests were run on the same machine listed in my above post. I ran the
tests twice, and the numbers were reasonably close.
Results:
my make clone using new built-in no-process-spawn touch and rm
** notarget -- ~1 second
** all from clean -- 55 seconds overall -- ~1 second in phase 1
** all from all -- ~3 seconds
** all from single leaf out of date -- ~2 seconds
** clean from all -- 24 seconds overall -- ~1 second in phase 1
** clean from clean -- 13 seconds overall -- ~1 second in phase 1
my make clone using $(process touch ...) and $(process rm ...)
** notarget -- ~1 second
** all from clean -- 225 seconds overall -- ~1 second in phase 1
** all from all -- ~2 seconds
** all from single leaf out of date -- ~1 second in phase 1
** clean from all -- 136 seconds overall -- ~1 second in phase 1
** clean from clean -- 125 seconds overall -- ~1 second in phase 1
my make clone using $(shell touch ...) and $(shell rm ...)
** notarget -- ~1 second
** all from clean -- 150 seconds overall -- ~1 second in phase 1
** all from all -- ~3 seconds
** all from single leaf out of date -- ~2 seconds
** clean from all -- 134 seconds overal -- ~1 second in phase 1
** clean from clean -- 137 seconds overall -- ~1 second in phase 1
GNU Make 3.81 using $(shell touch ...) and $(shell rm ...)
** notarget -- 32 seconds overall -- 19 seconds spent in phase 1
** all from clean -- 95 seconds overall -- 20 seconds spent in phase 1
** all from all -- 44 seconds overall -- 20 seconds spent in phase 1
** all from single leaf out of date -- 44 seconds overall -- 20
seconds spent in phase 1
** clean from all -- 63 seconds overall -- 20 seconds spent in phase 1
** clean from clean -- 46 seconds overall -- 20 seconds spent in phase
1
Let me talk about a couple things about the tests.
The first set of tests for my make clone does not spawn processes. It
uses the C APIs of POSIX and WIN32 directly. The next set uses my new
built-in $(process ) which directly spawns the process without a shell
inbetween. The last set of tests of my make clone uses $(shell ),
which uses an intermediary shell to spawn the process just like Make
is advertised to do. (See gen_tests.cpp in the appendex for a more
complete description.)
One thing to note: I remember that GNU Make is optimized so that if it
sees a single "simple" command, then it bypasses the shell entirely
and directly spawns the process. Similarly, my $(process ) primitive
does not spawn a shell and spawns the process directly. However, it
appears that my underlying process library, used to implement $
(shell ) and $(process ), written by me, is rather inefficient. I need
to look at it. If I was doing this again, I would just use Boost.
(However, I am not pursing a Make clone any more, for the
aforementioned reasons.)
I just now noticed this inefficiency in my process spawning because I
wasn't really planning on using $(shell ) and $(process ) all that
often. I was planning on using built-ins to avoid a lot of process
spawning. These built-ins are one of the major motivating factors
behind me writing my make clone. The performance of using an external
shell for "read from file" and "write to file" was especially bad on
windows. (That, and I really did not feel like learning in depth the C
code for GNU Make. It has some particularly annoying hacks and styles
devoted to avoiding string copies.) I also did it as a learning
exercise. I never expected that I would so outperform GNU Make on
Linux.
One can also see that my parsing code and string interpreter code is
the neighborhood of 20 times faster than GNU Make's. Why? I do not
know. Figuring that out would involve profiling and looking at the GNU
Make source code in depth, and one of my explicit goals in writing
this clone has been to avoid looking at GNU Make's source in depth.
From what I recall on an actual production-ready makefile
implementation for incremental C++, this number was about the same.
Similarly, we can compare the "all from all" tests, and we see that my
phase 2 code (including dependency graph walking, where we stat files,
decide if a node's commands need to be run, etc.), is also in the
neighborhood of 10 to 20 times faster. Why? Again I do not know.
The rest of this post is just an explanation of what my make clone is
and why I think this is a fair comparison (and appendix).
My make clone is in many ways a near drop-in replacement for GNU Make.
It's written in portable C++, uses only the C++ standard, POSIX, and
WIN32 headers. It still interprets the makefiles, doesn't compile
anything at runtime, or anything else fancy. It supports recursive and
simple variables. It supports a large portion of the GNU Make built-in
functions, including:
and, abspath, addprefix, addsuffix, basename, call, delete-files, dir,
error, eval, filter, filter-out, findstring, firstword, foreach, if,
index, info, lastword, notdir, or, patsubst, shell, sort, strip,
subst, suffix, value, warning, wildcard, word, wordlist, words.
I also support the additional new built-in functions:
append-to-file [especially useful to get around command line length
limitations with $(shell echo )], cat, cwd, def-recursive-var, eq, eq-
ci [equals case insensitive ASCII], eval-value [equivalent to eval and
value, but allows use of line numbers in the stack trace from the
original variable definition given to $(eval-value ...)], foreach-
line, index-ci, lowercase [ASCII], makedirs, namespace, neq, neq-ci,
not, print-to-file, process [allows spawning a process directly
without a shell], recursive-wildcard, remove-dirs, sleep, sort, sort-
ci, touch, uppercase [ASCII],
However, I do honestly admit that I do not have all of the
functionality of GNU Make, some of which favors the results in my
make's favor. Things which immediately jump out at me are:
1- I don't support vpath or VPATH. (I don't think this is a
significant contributer to the slowness when all the files of the test
are in a single directory, though.)
2- I do not have $(origin ) nor $(flavor ), which would make GNU Make
slower than mine. I don't believe this is a significant contributer to
the difference in observed speed though.
3- My make does not have any implicit rules, nor pattern rules, nor
any other kind of rule which isn't the simple explicit kind. (However,
I don't think that these features would apply a significant penalty
when they are not applied such as this test.) (My clone, however, does
support rules with multiple targets made by a single command
invocation which GNU Make does not.)
#### ####
#### test_driver.sh contents
#! /bin/sh
date | tee foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile1.mk -j=8 -d=phase notarget | tee -a
foo.txt ; infamake -f infamakefile1.mk -j=8 -d=phase notarget 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile1.mk -j=8 -d=phase all | tee -a
foo.txt ; infamake -f infamakefile1.mk -j=8 -d=phase all 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile1.mk -j=8 -d=phase all | tee -a
foo.txt ; infamake -f infamakefile1.mk -j=8 -d=phase all 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- echo "" > aasuaa' | tee -a
foo.txt ; echo "" > aasuaa
echo ---- infamake -f infamakefile1.mk -j=8 -d=phase all | tee -a
foo.txt ; infamake -f infamakefile1.mk -j=8 -d=phase all 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile1.mk -j=8 -d=phase clean | tee -a
foo.txt ; infamake -f infamakefile1.mk -j=8 -d=phase clean 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile1.mk -j=8 -d=phase clean | tee -a
foo.txt ; infamake -f infamakefile1.mk -j=8 -d=phase clean 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile2.mk -j=8 -d=phase notarget | tee -a
foo.txt ; infamake -f infamakefile2.mk -j=8 -d=phase notarget 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile2.mk -j=8 -d=phase all | tee -a
foo.txt ; infamake -f infamakefile2.mk -j=8 -d=phase all 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile2.mk -j=8 -d=phase all | tee -a
foo.txt ; infamake -f infamakefile2.mk -j=8 -d=phase all 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- echo "" > aasuaa' | tee -a
foo.txt ; echo "" > aasuaa
echo ---- infamake -f infamakefile2.mk -j=8 -d=phase all | tee -a
foo.txt ; infamake -f infamakefile2.mk -j=8 -d=phase all 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile2.mk -j=8 -d=phase clean | tee -a
foo.txt ; infamake -f infamakefile2.mk -j=8 -d=phase clean 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile2.mk -j=8 -d=phase clean | tee -a
foo.txt ; infamake -f infamakefile2.mk -j=8 -d=phase clean 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile3.mk -j=8 -d=phase notarget | tee -a
foo.txt ; infamake -f infamakefile3.mk -j=8 -d=phase notarget 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile3.mk -j=8 -d=phase all | tee -a
foo.txt ; infamake -f infamakefile3.mk -j=8 -d=phase all 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile3.mk -j=8 -d=phase all | tee -a
foo.txt ; infamake -f infamakefile3.mk -j=8 -d=phase all 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- echo "" > aasuaa' | tee -a
foo.txt ; echo "" > aasuaa
echo ---- infamake -f infamakefile3.mk -j=8 -d=phase all | tee -a
foo.txt ; infamake -f infamakefile3.mk -j=8 -d=phase all 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile3.mk -j=8 -d=phase clean | tee -a
foo.txt ; infamake -f infamakefile3.mk -j=8 -d=phase clean 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a
foo.txt ; ls | wc |
tee -a foo.txt ; date | tee -a foo.txt
echo ---- infamake -f infamakefile3.mk -j=8 -d=phase clean | tee -a
foo.txt ; infamake -f infamakefile3.mk -j=8 -d=phase clean 2>&1 |
tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a foo.txt ; ls | wc
| tee -a foo.txt ; date | tee -a foo.txt
echo ---- make -j8 notarget | tee -a foo.txt ; make -j8 notarget 2>&1
| tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a foo.txt ; ls | wc
| tee -a foo.txt ; date | tee -a foo.txt
echo ---- make -j8 all | tee -a foo.txt ; make -j8 all 2>&1
| tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a foo.txt ; ls | wc
| tee -a foo.txt ; date | tee -a foo.txt
echo ---- make -j8 all | tee -a foo.txt ; make -j8 all 2>&1
| tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a foo.txt ; ls | wc
| tee -a foo.txt ; date | tee -a foo.txt
echo '---- echo "" > aasuaa' | tee -a foo.txt ; echo "" > aasuaa
echo ---- make -j8 all | tee -a foo.txt ; make -j8 all 2>&1
| tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a foo.txt ; ls | wc
| tee -a foo.txt ; date | tee -a foo.txt
echo ---- make -j8 clean | tee -a foo.txt ; make -j8 clean 2>&1
| tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a foo.txt ; ls | wc
| tee -a foo.txt ; date | tee -a foo.txt
echo ---- make -j8 clean | tee -a foo.txt ; make -j8 clean 2>&1
| tee -a foo.txt ; date | tee -a foo.txt
echo '---- ls | wc' | tee -a foo.txt ; ls | wc
| tee -a foo.txt ; date | tee -a foo.txt
#### ####
#### gen_tests.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
struct Node
{ Node() : parent(0) {}
~Node() { for (int i=0; i<children.size(); ++i) delete
children
; }
string name;
Node * parent; //does not own
vector<Node*> children; //this object owns these
private:
Node(Node const& ); //not copyable
Node& operator= (Node const& ); //not copyable
};
string& makeNextName(string& name)
{ while (name.size() < 2)
name.push_back('a');
for (int i=2; ; )
{ if (i >= name.size())
{ name.push_back('a');
return name;
}
if (name == 'z')
{ name = 'a';
++i;
continue;
}
++name;
return name;
}
};
string getChildrenNameList(Node const* n)
{ string x;
for (int i=0; i<n->children.size(); ++i)
{ x += ' ';
x += n->children->name;
}
return x;
}
ostream& print(ostream& out, Node* n)
{ out << "$(call macro," << n->name << "," << getChildrenNameList(n)
<< ")" "\n";
for (int i=0; i<n->children.size(); ++i)
print(out, n->children);
return out;
}
int main()
{
int const cap = 25 * 1000;
int const branchingFactor = 75;
string name;
Node base;
base.name = makeNextName(name);
queue<Node*> q;
q.push(&base);
int numNodes = 1;
while (numNodes < cap)
{ Node * const next = q.front();
q.pop();
for (int i=0; i<branchingFactor; ++i)
{ auto_ptr<Node> child(new Node);
child->name = makeNextName(name);
++numNodes;
q.push(child.get());
next->children.push_back(child.get());
child.release();
}
}
ofstream gnumakefile("makefile");
ofstream infamakefile1("infamakefile1.mk");
ofstream infamakefile2("infamakefile2.mk");
ofstream infamakefile3("infamakefile3.mk");
gnumakefile <<
"all : ; $(info all) \n"
".PHONY : all " "\n"
"\n"
"clean : ; $(info clean) \n"
".PHONY : clean " "\n"
"\n"
"notarget : ; $(info notarget) \n"
".PHONY : notarget " "\n"
"\n"
"macro = $(eval $(value macro_impl))" "\n"
"define macro_impl" "\n"
" # $1 name of file" "\n"
" # $2 list of dependencies" "\n"
" " "\n"
" $1 : $2 ; @touch $@" "\n"
" " "\n"
" all : $1" "\n"
" " "\n"
" $1.clean : ; @rm -f $(basename $@)" "\n"
" .PHONY : $1.clean " "\n"
" clean : $1.clean " "\n"
"endef" "\n"
"\n"
;
infamakefile1 <<
".PHONY.all : ; $(info all)" "\n"
".PHONY.clean : ; $(info clean)" "\n"
".PHONY.notarget : ; $(info notarget)" "\n"
"\n"
"macro = $(eval $(value macro_impl))" "\n"
"define macro_impl" "\n"
" # $1 name of file" "\n"
" # $2 list of dependencies" "\n"
" " "\n"
" $1 : $2 ; $(touch $@)" "\n"
" " "\n"
" .PHONY.all : $1" "\n"
" " "\n"
" .PHONY.$1.clean : ; $(delete-files $(basename $@))" "\n"
" .PHONY.clean : .PHONY.$1.clean " "\n"
"endef" "\n"
"\n"
;
infamakefile2 <<
".PHONY.all : ; $(info all)" "\n"
".PHONY.clean : ; $(info clean)" "\n"
".PHONY.notarget : ; $(info notarget)" "\n"
"\n"
"macro = $(eval $(value macro_impl))" "\n"
"define macro_impl" "\n"
" # $1 name of file" "\n"
" # $2 list of dependencies" "\n"
" " "\n"
" $1 : $2 ; $(process touch $@)" "\n"
" " "\n"
" .PHONY.all : $1" "\n"
" " "\n"
" .PHONY.$1.clean : ; $(process rm $(basename $@))" "\n"
" .PHONY.clean : .PHONY.$1.clean " "\n"
"endef" "\n"
"\n"
;
infamakefile3 <<
".PHONY.all : ; $(info all)" "\n"
".PHONY.clean : ; $(info clean)" "\n"
".PHONY.notarget : ; $(info notarget)" "\n"
"\n"
"macro = $(eval $(value macro_impl))" "\n"
"define macro_impl" "\n"
" # $1 name of file" "\n"
" # $2 list of dependencies" "\n"
" " "\n"
" $1 : $2 ; $(shell touch $@)" "\n"
" " "\n"
" .PHONY.all : $1" "\n"
" " "\n"
" .PHONY.$1.clean : ; $(shell rm $(basename $@))" "\n"
" .PHONY.clean : .PHONY.$1.clean " "\n"
"endef" "\n"
"\n"
;
print(gnumakefile, &base);
print(infamakefile1, &base);
print(infamakefile2, &base);
print(infamakefile3, &base);
gnumakefile << "$(info $(shell date) -- done with phase 1)" "\n";
infamakefile1 << "$(info $(shell date) -- done with phase 1)" "\n";
infamakefile2 << "$(info $(shell date) -- done with phase 1)" "\n";
infamakefile3 << "$(info $(shell date) -- done with phase 1)" "\n";
gnumakefile.close();
if (!gnumakefile)
{ cerr << "error" << endl;
return 1;
}
infamakefile1.close();
if (!infamakefile1)
{ cerr << "error" << endl;
return 1;
}
infamakefile2.close();
if (!infamakefile2)
{ cerr << "error" << endl;
return 1;
}
infamakefile3.close();
if (!infamakefile3)
{ cerr << "error" << endl;
return 1;
}
}