Re: A build system using ``Recursive Make Considered harmful''

[Scott A Crosby]

On 2 Aug 2001, Tom Tromey wrote:

> >>>>> "Scott" == Scott A Crosby <address@hidden> writes:
>
> Scott> First, 'make clean' builds dependencies before doing any
> Scott> cleaning.
>
> This is a known flaw in the dependency tracking implementation
> recommended by GNU make.  You can read about this problem, and the
> fix, in the Automake dependency tracking history:
>
>     http://sources.redhat.com/automake/dependencies.html
>

Irrelevant. I think I can define the semantics of 'make' to make such a
requirement obsolete.

> Scott> I have not tested it with program-built code. IE. the case
> Scott> where one program is run to generate code that is later
> Scott> compiled.  (IE: './genCode interp.spec > interp.c') My problem
> Scott> is is with how and when do I create and include the dependency
> Scott> file on the generated code.  ('interp.c') Suggestions/fixes
> Scott> welcome.
>
> There's a kind of deep, generic problem here.  It isn't really easy to
> fix, at least not if you want automatic dependency tracking as well.
> Automake takes one particular hacky approach (BUILT_SOURCES).  This is
> also discussed in the paper.
>

I think some sort of solution along the lines of 'if a file I include is
out-of-date, do not include it until it is rebuilt'.

This is if I have:
%.o: %.c %.d
        gcc ....
program:  program.o
        gcc ....
out.c: program
        program >out.c
out: out.o
        gcc ....
all: out

And I'll instantiate the %.o:%.c %.d rule with:
        program.o :program.c program.d
        out.o :out.c out.d

With dependencies of:
        program.o program.d: include1.h
        out.o out.d: include2.h

If after including all of the *.d files, we compute a list of all targets
that have to be up-to-date to satisfy 'all'. If the rule building
program.d is in that list of things that need to be brought up-to-date,
and program.d is out-of-date or does not exist, we want make to throw out
anything it learned from program.d, suspend building any other targets
until it can build program.d, and then include it. In practice, we want to
be able to attach to any dependency where it came from, and support a
stack of such 'interrupted' targets so we can reprioritize on the most
critical target.

Another way to think of it is that if any of the 'dirty' rules we will
need to run to bring 'all' up to date have building foo.d, bar.d, etc as a
side effect We throw out anything we learned in foo.d, bar.d, etc, and
then make them our targets temporarily.

--

This can even be extended to work OK even if you had several such
programs: program1, and program2. Where program1 generated code for
program2 which generated code to compile.

As stated above, this will fail, because make won't know which to build
first, program1.d or program2.d. So, you'd require the programmer to
encode this explicitly.

program2.cpp: program1.d
  -- OR --
program2.d: program1.d

And, if header2.h changes, we just rebuild out.o

--

Now, going through the URL you gave about the problems with this scheme:

In the case of an error in a rule that has building %.d as a side-effect,
we ignore the error and don't worry about it.

For 'make dist'. Well, because we are non-recursive, all paths in all
rules are relative from the toplevel and should never ever contain '..',
unless you have a program-generated %.cpp file?  But in this case,
patternmatch the dependencies to see if any of them have ${builddir} as a
prefix. If so, replace that prefix with the variable reference ${builddir}

--

This would also help the 'make clean' problem

To bring 'clean' up to date would should not use any rules that would
build %.d as a side effect. Thus, it would not bother to build them.

--

Note one of the nuances of this specification I am giving explicit
requirements for the semantics of including another makefile that is
also the target of a rule.  I do not know what the generally accepted
semantics of this situation are.

Also, these semantics are somewhat incompatible with having
dependency-generation done as a side-effect of compilation[1]. On the
other hand, I think that they may fix the two annoying problems that you
have.

I benchmarked this with GCC 2.95.2 on a dual P2-450..

Dependency generation is only 5-10% the cost of compilation.

deps only:
        real    0m1.521s
        user    0m1.130s
        sys     0m0.380s

building only objs, no libs, no link, no opt:
        real    0m13.554s
        user    0m23.460s
        sys     0m1.090s

building only objs, no libs, no link, -O -Wuninitialized:
        real    0m17.724s
        user    0m31.090s
        sys     0m1.500s

[1] Because if you change any %.h file, it'll see that the %.o %.d: rule
will need to be rebuilt, and these semantics will notice this case and
immediately retarget to building %.d immediately. First, this will destroy
parallel building, second, depending on implementaiton we may have O(n^2)
running time on the number of files. I've not thought out the
implications far enough to be sure, but I think make may still have
correct, if ineffecient operation.


> Scott> $(patsubst %.c,%.d,$(filter %.c,$(SRC))) : %.d: %.c
> Scott> [ ... ]
> Scott>                 $(CC) -MM $(CPPFLAGS) $< \
>
> Your approach only works when you use gcc and GNU make.  Our
> experience in automake (and this is also in the paper) is that this is
> insufficient.  In fact, this was one of the most frequently reported
> problems with automake 1.4.
>

Ah, I suspected I had that requirement. Oh well.

>
> Scott> -- The future
> Scott> But, if we fix these warts, maybe we can convince people to
> Scott> trash the more crazy build systems that do use recursive make?
> Scott> Its nice for things to 'just work', and in complete
> Scott> parallelization.
> Scott> So, what do you think?
>
> I think it is great that your work confirms the results in the
> Recursive Make Harmful paper.  Since automake is probably the craziest
> of the crazy build systems, I think it is reasonable that it look in
> this direction in the future.  And, in fact, we've been planning this

Yep.. I thought I'd put up my results and assessments.
Parallel/distributed building will likely become a more and more valuable
thing in the future, and its something that is very hard to do without
this.

> as (possibly) one of the major new features in a later automake
> release.  (Actually there is already some support for it already,
> though not as nice as we would like.)  Unfortunately, automake
> operates under many constraints which means that we won't be able to
> use your code as-is.  Instead we'll need our own implementation.

I offered my code as both usable as-is in some circumstances, as example
code to fixup some broken code I found on the web, and as something to
inspire someone else who wanted to do it right.

>
> Another approach, of course, is to get rid of automake and do
> something new.  Unless you are willing to relax the constraints (e.g.,
> require GNU make and gcc), I think that would be as much work as
> reimplementing automake.  Even assuming GNU make it would still be a
> significant effort.

I'm not offering to do that level of work. I'm mostly happy with linux.
But, if you can offer a dependency-generation script and the changes above
with the semantics of make.  I dunno.

What do you think?


--
No DVD movie will ever enter the public domain, nor will any CD. The last CD
and the last DVD will have moldered away decades before they leave copyright.
This is not encouraging the creation of knowledge in the public domain.