Re: build system rules & algorithms

[Paul Smith]

On Tue, 2009-06-09 at 21:08 -0400, Mike Shal wrote:
> Hey everyone,
> 
> I wrote a paper that analyzes some of the algorithms in make. If you
> get annoyed when you have a large project and 'make' takes a long time
> to do nothing, or if you think doing 'make clean' is silly, or if you
> are just generally intrigued by build systems, you might be interested
> to read it. If not, maybe it'll help you get to sleep at night :).

> http://gittup.org/tup/build_system_rules_and_algorithms.pdf

Hi Mike, thanks for that!  It is indeed very interesting.

My concern about this is that it sort of glosses over the most critical
aspect.  The basic information required by any build system is and has
always been, "what's been changed?"  Without a highly accurate
accounting of what's been changed since the last successful build, even
the most advanced build system in the world will not work properly.

When make was created 30+ years ago, the only way to determine what's
been changed with any accuracy and reliability is modification times,
because these are maintained by the operating system and are unlikely to
be changed "arbitrarily" by hand... at any rate, requiring that the user
not do so is not an onerous burden since they rarely want to anyway.
Once this is decided, the current algorithms and behavior of make
follow: there is no way to know what's been changed without going out
and looking at each file.  Further, make gains a lot of simplicity (but
at the cost of some performance as you point out) by avoiding the need
to maintain a separate state: make is completely stateless or, at least,
it uses no state other than what is automatically maintained for it by
the operating system.

Going to a Beta build system, on the other hand, requires that some
entity maintain a highly if not completely accurate accounting of all
the files that have changed.  That is NOT a simple problem to solve.
Delegating that problem to IDEs and similar simply ignores the reality
of development (at least in my world).  People don't tend to use IDEs
much, and when they do they certainly don't do every operation using
them.  People remove files by hand, they rename files by hand, they edit
files using vi "just for a quick fix" rather than boot up the IDE, etc.
Further the act of updating the workspace via external tools such as
source control operations needs to be integrated.  I'm not aware of any
existing IDE or other userspace tool that has that level of integration
across the variety of tools and editors available: invariably they
relegate support for "other" tools to some kind of scripting engine or
"shell out" facility, which certainly means they cannot track "what's
changed".

Any discrepancy in the list of modified files results in incorrect
results of a Beta build, and possibly in very subtle and hard to
discover ways.

Although writing reliable and correct makefiles is arcane and much
harder than we'd like it to be, it can be done once by a central
designer and that complexity can be contained and not exposed to the
development community at large.  In contrast, the requirement for a
complete and accurate list of "what's changed" must, by necessity, rely
on every developer doing everything "the right way" all the time, or the
list becomes inaccurate.  Then you're back to some kind of "reset"
operation similar to "make clean" to get back to a known state.

Of course, the solution to this is to get the operating system involved
with tracking changes.  Certainly there are lots of reasons that
userspace tools want to know "what's changed": not just build systems
but also indexers, etc. all want to know.  And Linux, at least, has
evolved some relatively nice utilities to provide this information.
However, there is certainly no general, portable method for the
operating system to track this.  And, we've not even touched the
complexities involved with things like sources built from NFS-mounted
partitions, etc.


I really do like the ideas in your paper and I think it's a worthwhile
exercise to skip over the very hard initial problem (knowing "what's
changed") to see what we could do if we knew that: whether it's even
worthwhile to try to solve it.  I think your paper shows very nicely
that we could do a lot better if we can solve that problem, so it's
worth thinking about those solutions.

Cheers!

-- 
-------------------------------------------------------------------------------
 Paul D. Smith <address@hidden>          Find some GNU make tips at:
 http://www.gnu.org                      http://make.mad-scientist.us
 "Please remain calm...I may be mad, but I am a professional." --Mad Scientist