Build System Schedulers

Topological

Precomputes a linear order of tasks and then executes them in that order

  • Applicative or weaker. No static dependencies.
  • Minimal

Restarting

build tasks in arbitrary order. If task wants an out-of-date dependency, abort it and build that dependency

  • To minimize restarts, bazel stores most recent task dependency info and computes linear order from that
  • excel stores discovered task order and uses it as starting point for next build
  • Monadic or weaker
  • Not minimal

Suspending

build dependencies when requested, suspending tasks if necessary

  • Suspension can be implemented with blocking threads or CPS. CPS requires the build script to be architectured correclty, which shake does automatically.
  • Suspension is theoretically optimal but only better than restarting if the cost of avoided duplicate work outweighs the cost of of suspending tasks.
  • Monadic or weaker
  • Minimal