Build System Rebuilders

Decides if a scheduled task is already up to date or not.

  • dirty bit: file system modified time, actual dirty bit, etc.
    • can be minimal, but difficult to support early cutoff
    • useful to reduce memory consumption
  • verifying traces: hash dependencies. Rebuild if changed.
    • for suspending schedulers with dynamic dependencies, often the build steps are performed in order to check if a key needs to be rebuilt.
  • verifying step traces: instead of hashing dependencies, store built+changed time for each key and list of dependency keys (without hashes)
    • stores less data than verifying traces
    • allows values to be considered equal without being bit-for-bit equal
    • slightly different early cutoff semantics
      • if a subset of target is built, changed, then reverted, verifying traces do not rebuild but verifying step traces will.
  • Constructive Traces

deep constructive traces are merely constructive traces that consider n=infinity levels of transitive dependencies. constructive traces are the special case of n=1. deep constructive traces can pick any n to regain some early cutoff at the cost of more expensive shallow builds. Any n > 1 requires determinstic builds

Rebuild strategyTopological schedulerRestarting schedulerSuspending scheduler
dirty bitmakeexcel
verifying tracesninjashake
constructive tracescloudbuildbazelcloud shake
deep constructive tracesbucknix
Links to this page