Git, the D package manager

H. S. Teoh via Digitalmars-d digitalmars-d at puremagic.com
Tue Feb 3 13:02:24 PST 2015


On Tue, Feb 03, 2015 at 08:41:38PM +0000, Jonathan Marler via Digitalmars-d wrote:
> On Tuesday, 3 February 2015 at 20:18:31 UTC, Paolo Invernizzi wrote:
> >[1] http://gittup.org/tup/
> 
> I don't know who wrote that site but they are quite hilarious :)
> 
> "Unfortunately, tup is so fast that your chair mounted jousting might
> suffer. I apologize in advance if someone besmirches your honor and
> you are unable to properly defend yourself as a result."
> 
> "In tup, the arrows go up. This is obviously true because it rhymes. "

Don't be fooled, though. Tup contains some revolutionary ideas that
would-be implementors of the Next Great Build System would do well to
take note.  The paper linked to by the website explains the difference
between "first generation" build algorithms vs. "second generation"
build algorithms.

In brief, first generation build algorithms are centered around linearly
scanning dependencies to update, which is not scalable, because it is
O(n), and as the size of the source tree grows large, linear scanning
becomes prohibitively expensive. Your code-compile-test cycle gets
bottlenecked at the compile step because every single time the poor
build tool has to scan the entire source tree of hundreds or even
thousands of source files, and rebuilding the graph from scratch.
Furthermore, any attempt to reduce the cost of the linear scan (e.g.,
invoke make from a subdirectory) breaks build correctness, because the
algorithm is unable to reliably determine the smallest consistent
subgraph that must be updated when some node(s) change unless it scans
everything.

Second generation build algorithms are centered around *not* scanning,
but taking advantage of modern OSes providing APIs for file change
notification. Rather than scan the whole source tree every time, it
takes the changeset as input -- either from the OS, or from some other
source of information. By leveraging OS features, we can obtain this
info on an as-needed basis instead of an O(n) scan. Upon this, a
modified algorithm with O(log n) complexity is built, that at the same
time also guarantees correctness -- by the modified representation of
the dependency graph, it is possible to derive the smallest consistent
subgraph that needs to be updated when some changes are made.

In addition to an overhaul of the core algorithm, tup also has some
clever tricks, like wrapping libc of executed commands, so that all
*actual* inputs to the compiler (and other build commands) are included
in the dependency graph -- if the compiler reads /usr/include/stdio.h,
for example, tup will know that the source file depends on stdio.h --
and this *without* needing to scan the source file manually or asking
the user to specify such tedious things.

In fact, tup is just a proof-of-concept tool (that's surprisingly usable
for what it is!); the author expects that build tools of the future will
develop its ideas further. As for me, I get the feeling that tup has the
right ideas, even if it isn't quite "it" yet -- the implementation isn't
quite what I would've chosen. But nevertheless, it holds a lot of
promise for the future, unlike most other alternative build tools, which
are just more-of-the-same-rehashed-the-nth-time.


T

-- 
What are you when you run out of Monet? Baroque.


More information about the Digitalmars-d mailing list