๐Ÿ“–Build Systems a la Carte

Mokhov, Andrey and Mitchell, Neil and Peyton Jones, Simon
  • Build systems:

    • minimality
    • build order
  • Excel is a build system in disguise
  • Build systems are kinda incremental/adaptive/self-adjusting computations
  • Bazel uses content-addressable cache of builds (cloud build system)
  • store = key โ†’ value

    • filename โ†’ contents
    • cell โ†’ cell value (excel)
  • expanded version is available at https://www.microsoft.com/en-us/research/publication/build-systems-a-la-carte/
  • Build system can be split into two parts

    • scheduler: to determine the order in which to execute the tasks

      • topological: sort tasks in topological order (e.g., Make), only static dependencies
      • restarting: start building tasks, but stop if new dependency needs a rebuild (Excel)
      • suspending: suspend the task if dependency needs to be built (Shake)
    • rebuilder: to determine if key is out-of-date and needs rebuilding

      • dirty bit (e.g., Make, Excel)
      • verifying traces: store output hash and hash of all direct dependencies
      • constructive traces: store output (not hash) and hash of all direct dependencies (can cache multiple results per key)
      • deep constructive traces: store output + hashes of all terminal inputs (e.g., Nix)

        • allows skipping intermediate steps and download the result (shallow builds), but does not support early cutoff
        • the builds must be deterministic
rebuilder \ schedulerTopologicalRestartingSuspending
Dirty bitMakeExcel-
Verifying tracesNinja-Shake
Constructive tracesCloudBuildBazel-
Deep constructive tracesBuck-Nix