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.
