1

I'm looking for a memoizing build system*. The requirements:

  • active development or community
  • not tied to any particular language
  • supports variant builds

I took a look at fbuild. It seems help back by concepts from waf - every action has to go through the context object - and monolithic - special path objects with builtin file functionality (copy, install, etc). I'd say it was dead but recently it has received a flurry of patches.

Mem looks promising - more natural and lightweight - but also super dead. Is it finished, or abandoned?

I've only taken a cursory look at either, so perhaps one has a significant lead over the other. Are they the only contenders, or are there other memoizing build systems (of production quality)?

..

By the way, why do all such build systems seem dead? Is there some deep dark disadvantage of which I'm unaware?

..

Edit, for context:

Memoization maintains a dictionary of hash(function-inputs) -> function-outputs. The principle of memoizing build systems is to reuse as much of the underlying programming language to simplify the build system. So whereas standard build systems require as input a predetermined directed acyclic graph (DAG) of dependencies, memoizing build systems express the dependency DAG using function call hierarchies. For memoizing build systems, this means:

  • Graph connections are explicit function calls, compared to standard build systems where graph nodes are only implicitly connected.
  • Because the graph is not known until runtime, unlike standard build systems, automatic parallelization isn't possible. Instead, parallelization has to be expressed at the programming language level (depending on the language or the library, this can be quite simple).

Memoization is involved during traversal of the dependency DAG and execution of each graph node's build tasks. For example, a standard build system will implicitly cache and check hashes of every node's dependencies. If the dependencies are found to be unchanged, then traversal down that node's children is cancelled and the node's target (output) is reused. At the simplest level, GNU Make uses modification times to infer dependency hashes.

Memoization is how build systems based on programming languages implement this feature. Function arguments determine the requirements for a deterministic build - environment, sources (inputs) and targets (outputs) - so that they are effectively "pure" from side-effects. If all inputs to a function are unchanged, then the output is reused from a file-based (the build directory) cache mapping inputs->outputs.

Now obviously the hash of a path (string) remains unchanged irrespective of that path's contents. Therefore a special path wrapper class must be defined to overload the hash function to be dependent on content. If every build node (function) returns such a wrapper instance representing the output target, detection of file modifications will remain automatic for all non-leaf nodes. Leaf nodes, by virtue of being first, do not have the convenience of receiving wrapper instances as arguments (instead, strings). Therefore, the build system must provide a facility for specifying external dependencies beyond just function parameters. I won't go into the details, but while this makes memoization more difficult (mem uses a two-pass approach), it also has a surprising number of uses outside the case I presented. For example, some of the additional features outlined below depend on this facility.

Such modern build systems have a number of additional features:

  • Automatic detection of dependencies using the compiler
  • Automatic conversion from string-hash based paths to contents-hash based paths
  • Automatic restoration of modified or removed non-leaf node targets, from the build cache

Details on memoizing build systems can be found:

I think most (all?) memoizing build systems have been built in python because of its natural metaprogramming facilities. In fact, while my description may seem overwhelmingly technical, I find such build systems surprisingly fluid and comprehensible.

That said, most memoizing build systems are either emergent or abandoned, so either they haven't the feature set to compete with established systems, or they are a dead end.

  • 2
    Since I've never heard of what a memoizing build system is, it might be worth adding what that is into your question a little more clearly. Someone might have renamed the wheel/ – Journeyman Geek Apr 23 '16 at 7:36
  • 1
    Also, if you reference software, please add a link. – Jan Doggen Apr 23 '16 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.