Re: build system rules & algorithms

[Mike Shal]

On 6/18/09, Paul Smith <address@hidden> wrote:
> The major difference between an "Alpha" and "Beta" build system is more
>  fundamental.  The idea behind a "Beta" system, as I understand the
>  paper, is that BECAUSE it knows a priori which source files have changed
>  it doesn't have to walk the DAG "backwards" starting from the goal and
>  working back to the sources like make does.  Instead it can start with
>  the sources, since it knows them already, and work forward towards the
>  goal.
>
>  This reduces the complexity and scope of the "possible paths" searching
>  through the DAG and gives you a lot of performance improvement,
>  especially on builds where only a few source files have changed.

This is an excellent summary. Perhaps I should've had you write the
paper - it would've been much more concise :).

>
>  I don't think replacing the current "stat" implementation with a query
>  to an oracle would be a performance improvement, without the rest of the
>  changes to the basic algorithm of make.

Based on grischka's earlier analysis I'm inclined to agree. Though if
anyone is willing to give it a shot, the file monitor code in tup may
help. It turned out to be a little trickier to write a recursive
inotify daemon than I had initially anticipated, for a few reasons:

 - Inotify doesn't give you a way to convert a watch descriptor to a
path, so you have to maintain a mapping of wd to the path in
userspace. (I imagine this is because it would be even harder to do in
the kernel).
 - There are a number of filesystem events that you likely don't care
about. For example, when saving a file in vim, it will create a new
temporary file, then rename the new file over the old file. This
triggers a number of events, but all that you need to know is "file
foo was written to". I try to work around this by buffering events and
do some coalescing to get rid of unnecessary events.

-Mike