ClearCase has a clearaudit command that can be used to kick off any other arbitrary command and get dependency information (clearaudit /c <foo>). This is much better than using clearmake, because you otherwise depend on a users ability to (correctly) write makefiles upfront.
If you think of a build step as a function, taking some files as input (the source) and returning a result (the compiled artifact), then this tool is memoizing the that function.
Did you read the Wikipedia article you link to? This has everything to do with memoizing the result of running compilation programs (function) on input files (arguments).
The "trick" here is using strace to figure out the complete set of inputs to the (assumed to be) idempotent compilation steps.
That would make more sense. They use memoize they don't provide it, which is what I first thought they did when I read the name. They provide a make alternative.
MSBuild uses Tracker.exe (or Tracker.dll) which depends on Microsoft's Detours IAT hooking library, which works much differently. Sadly it has to be purchased separately.
I tried to contribute OS X support years ago but was too lazy to spend the time to polish it - sorry!
Neither tool supports any sort of parallelism, which caused me to eventually give up on them. (It is possible in theory! Though in the worst case it requires killing compiler invocations and rerunning them.)
Edit: Apparently fabricate does support parallel execution now, which is neat, but only with explicit markers, which I expect is somewhat detrimental to the magic feel of these tools... maybe I should try it. In the previous parenthetical I meant automatically detecting what can be run in parallel.
Nice, but a problem with this approach is that strace is not "re-entrant". That is you can't strace a program that uses strace (or more precisely, the ptrace syscall).
I played around with this a few years back when looking at build tools. strace is ungodly slow, and I wouldn't recommend using this for anything real. When I looked into why, it's basically the time it takes to print and read from strace - printing to stdout every time there is a syscall is obviously very slow.
Instead you can use tup, though someone mentioned it now requires Fuse, which obviously isn't good. So instead you can use an LD_PRELOAD to record all the file accesses, which is what I think tup used to do.
There is also some filesystem thing added to git that let's introspect file access, though I don't recall the details.
That said, I think memoize is the first use of this technique (record actual file accesses dynamically for dependency tracking), which is utterly genius. I worked with Bill McCloskey who wrote it, and he is an incredibly smart dude. He did a lot of work on making Firefox's GC better over the last few years.
memoize is certainly not the first use of this technique. Electric Make (http://electric-cloud.com/products/electricaccelerator) uses a custom filesystem to track file accesses for purposes of augmenting dependency information, and predates memoize by five years. It even goes beyond simply tracking accesses to using the information to correct for missing dependencies on the fly.
The main problem with strace is not the printing (although that doesn't help) but with the ptrace technology underneath, which basically hits the traced process with a SIGSTOP/SIGCONT pair on every system call, as well as a context switch to the tracing process and another back to the traced process. Even a no-op ptrace-based monitor that does nothing will make individual system calls ~10x slower. In my benchmarks, the best case overall performance impact was about 5%, but some processes were as much as 560% slower.
LD_PRELOAD is faster but has other deficiencies, like it's trivially easy to circumvent the tracing by wiping LD_PRELOAD from the environment before starting a new process. It can also be tricky (though not impossible) to manage implicit state, such as following an application as it first chdir's to a new location, then accesses paths like "../../include". LD_PRELOAD is also tough to get right in the face of multi-threaded applications.
FUSE is interesting but so far I've found the performance to be disappointing. I think that's mostly because it bounces everything through userspace and effectively doubles the filesystem activity for (nearly) everything. For example, with a normal filesystem a read from a user process basically works like this:
user process
-> read system call
-> filesystem read operation
-> return result to user process
With a FUSE filesystem it's something more like this:
user process
-> read system call
-> FUSE filesystem read operation
-> FUSE userspace driver
-> read system call on real filesystem
-> filesystem read operation
-> return result to FUSE userspace driver
-> relay result to FUSE filesystem
-> return result to user process
There are various caches in place to make this less disastrous than it seems on the surface, but fundamentally this is the architecture. For some applications that's fine; for high-performance build tools I think it's probably a deal-breaker.
This is why we wrote a custom filesystem for Electric Make, and why that's still the approach we take today, nearly 15 years later: nothing else is as robust, and nothing else comes close to the performance.
Every few years someone tries to reinvent make, and they usually end up with some unholy mess that complicates build systems or causes maintenance nightmares, and is never quite as good.
It turns out that make's syntax is actually quite simple and appropriate if you take a day or so to learn it properly. It's such a fantastic tool that if its syntax was really that problematic, someone would have created a new syntax front-end to GNU make by now. The fact that they haven't speaks volumes: by the time you learn enough to be able to do it, you realise you can't really come up with anything better.
22 comments
[ 2.4 ms ] story [ 58.6 ms ] threadThis is just a very bad naming choice for this library that seems to be an OK alternative to Make.
[1] https://en.wikipedia.org/wiki/Memoization
[2] https://docs.python.org/3/library/functools.html#functools.l...
The "trick" here is using strace to figure out the complete set of inputs to the (assumed to be) idempotent compilation steps.
[1] http://gittup.org/tup/ex_dependencies.html
https://code.google.com/p/fabricate/
I tried to contribute OS X support years ago but was too lazy to spend the time to polish it - sorry!
Neither tool supports any sort of parallelism, which caused me to eventually give up on them. (It is possible in theory! Though in the worst case it requires killing compiler invocations and rerunning them.)
Edit: Apparently fabricate does support parallel execution now, which is neat, but only with explicit markers, which I expect is somewhat detrimental to the magic feel of these tools... maybe I should try it. In the previous parenthetical I meant automatically detecting what can be run in parallel.
Instead you can use tup, though someone mentioned it now requires Fuse, which obviously isn't good. So instead you can use an LD_PRELOAD to record all the file accesses, which is what I think tup used to do.
There is also some filesystem thing added to git that let's introspect file access, though I don't recall the details.
That said, I think memoize is the first use of this technique (record actual file accesses dynamically for dependency tracking), which is utterly genius. I worked with Bill McCloskey who wrote it, and he is an incredibly smart dude. He did a lot of work on making Firefox's GC better over the last few years.
The main problem with strace is not the printing (although that doesn't help) but with the ptrace technology underneath, which basically hits the traced process with a SIGSTOP/SIGCONT pair on every system call, as well as a context switch to the tracing process and another back to the traced process. Even a no-op ptrace-based monitor that does nothing will make individual system calls ~10x slower. In my benchmarks, the best case overall performance impact was about 5%, but some processes were as much as 560% slower.
LD_PRELOAD is faster but has other deficiencies, like it's trivially easy to circumvent the tracing by wiping LD_PRELOAD from the environment before starting a new process. It can also be tricky (though not impossible) to manage implicit state, such as following an application as it first chdir's to a new location, then accesses paths like "../../include". LD_PRELOAD is also tough to get right in the face of multi-threaded applications.
FUSE is interesting but so far I've found the performance to be disappointing. I think that's mostly because it bounces everything through userspace and effectively doubles the filesystem activity for (nearly) everything. For example, with a normal filesystem a read from a user process basically works like this:
user process -> read system call -> filesystem read operation -> return result to user process
With a FUSE filesystem it's something more like this:
user process -> read system call -> FUSE filesystem read operation -> FUSE userspace driver -> read system call on real filesystem -> filesystem read operation -> return result to FUSE userspace driver -> relay result to FUSE filesystem -> return result to user process
There are various caches in place to make this less disastrous than it seems on the surface, but fundamentally this is the architecture. For some applications that's fine; for high-performance build tools I think it's probably a deal-breaker.
This is why we wrote a custom filesystem for Electric Make, and why that's still the approach we take today, nearly 15 years later: nothing else is as robust, and nothing else comes close to the performance.
_Disclaimer: I'm the architect of Electric Make_
http://cr.yp.to/redo.html
https://github.com/apenwarr/redo
It turns out that make's syntax is actually quite simple and appropriate if you take a day or so to learn it properly. It's such a fantastic tool that if its syntax was really that problematic, someone would have created a new syntax front-end to GNU make by now. The fact that they haven't speaks volumes: by the time you learn enough to be able to do it, you realise you can't really come up with anything better.