incremental
The context for this post is that at work I recently implemented Nix
ecosystem support for “incrementally” building Haskell packages. By
“incrementally” I mean that these Nix builds only need to build what
changed since the last full build of the package so that the package
doesn’t need to be built from scratch every time.
The pull requests implementing this feature have not yet been
approved or merged at the time of this writing, but I figured that I
would explain the motivation, design, results, and limitations of this
work to hopefully persuade people that this work should be merged.
If you’re not interested in the design then you can skip straight to
the Demo section below.
Background
I work on Mercury’s Backend
Development User Experience team and we support developers contributing
to a large Haskell monolith consisting of 3000+ modules. That may seem
like a lot but the vast majority of these modules are small and the
whole codebase takes ~14 minutes to compile in CI if we disable
optimizations (although we still build with optimizations enabled for
deployment).
In my experience, that’s pretty good for a Haskell project of this
size, thanks not only to the work of our team but also other teams who
also contribute to improving the development experience. In fact, the
pioneering work for this “incremental builds” feature actually
originated from two engineers outside our team.
First, Harry Garrood
improved GHC’s change detection algorithm so that GHC would use the hash
of the file to detect changes instead of using the timestamp. In this
post he explains how you can make use of this to implement
incremental builds for traditional CI services (e.g. GitHub actions)
where each build reuses the intermediate build products from the prior
build instead of building from scratch.
That alone would not be enough for us to use this at work since we
use Nix where this sort of build impurity doesn’t fly. However, Harry
and Jade Lovelace prototyped using
this feature in Nixpkgs so that Nix builds of Haskell packages could
also reuse intermediate build products from prior builds to save work.
You can find
their prototype here.
The basic idea behind the prototype Nixpkgs integration is that you
split a Haskell package build into two separate builds:
A “full build” that builds the Haskell package from scratch
This full build exports its intermediate build products (i.e. the
dist directory) which can then be reused by:
An “incremental build” that only builds what changed since the
full build
This incremental build imports the intermediate build products from
the corresponding full build so that it doesn’t have to build the
package from scratch.
So you might wonder: if that was already implemented then what work
still remained for me to do?
Problem
The main issue with the initial Nixpkgs integration is that it does
not provide any support for selecting which Git revision to use as the
basis for the full build. The existing solutions require some
out-of-band process to automatically select and lock the appropriate git
revision to use for the older (full) build.
Non-solution #0: Rolling
rebuilds
The first non-solution is for each revision to always reuse the build
products from the previous revision. This doesn’t work well with Nix
because it would create an increasingly-long chain of dependent
derivations; in order to build the most recent revision you’d have to
build all preceding revisions.
The dilemma here is that Nix is forcing us to confront something that
other build tools gloss over: if you’re always reusing build products
from the last build then you can’t accurately reproduce the most recent
build from scratch without reproducing all prior builds. You’ve
essentially “contaminated” the current build with all prior builds by
doing things in this way.
So what we really want is something more like this:
Periodically do a full build from scratch and then make each
incremental build relative to the last full rebuild.
That’s much more compatible with Nix because then we only need to do
two builds of our project if we rebuild things from scratch, instead of
one build for every revision in our project’s history.
There’s also another issue with rolling rebuilds when you’re not
using Nix, which is that most naïve attempts to do this don’t ensure
that the starting build products came from the parent commit. You can
end up with contamination of build products across branches if you’re
not careful, which further complicates reproducibility.
Non-solution #1: Lockfile
Okay, so suppose you periodically do a full build of the project from
scratch and then each incremental build is relative to the last full
build. You would need to do a full rebuild frequently enough so that the
incremental builds stay quick. If you wait too long in between full
rebuilds then the project will evolve to the point where the incremental
builds can no longer reuse most of the build products from the last full
build and in the extreme case the incremental builds degenerate into
full builds if they can’t reuse any old build products.
For example, at our work we currently do a full build of our large
package once a day, so we need some way to update the full build to
point to the last revision from the preceding day.
One
existing approach to solving this involved using Nix flakes to
manage the git revision for the older build. The idea is that you
periodically run nix flake update to update the revision
used for the full build and you might even automate this process by
having some recurring cron job generate a pull request or
commit to bump this revision on the main development branch. You don’t
have to use flakes for this purpose, but flakes are probably the most
ergonomic solution along these lines.
However, there are a few issues with this approach:
It only works well for short-lived pull requests
In other words, if you update the revision used for the full build
once a day then typically only pull requests that are less than a day
old will benefit from incremental builds.
Specifically, what we’d really like is “branch-local” incremental
builds. In other words if a longer-lived development branch were to
deposit a few commits a day we’d like there to be a full rebuild once a
day on that branch so that incremental builds against the tip of that
development branch remain snappy.
It pollutes the git history
If you bump the lockfile, say, once per day then that’s one junk
commit that you’ve added to your git history every
day.
It’s difficult to open source any useful automation around
this
If the solution requires out-of-band machinery (e.g. some recurring
cron job) to bump the lockfile you can’t provide a great
user experience for open source projects. It only really works well for
proprietary projects that can tolerate that complexity.
That last point was the most important one for me. Generally, when I
design something (even something intended for internal, proprietary use)
I try to design it in such a way that it works well in an open source
context, too. In my experience, doing things in this way tends to
improve the design, quality, and user experience of software that I
build.
In particular, I wanted a solution where all the automation could be
implemented entirely within the Nix language. However, this is not
possible in Nix’s present form!
Non-solution #2: Rollback
derivation
So what I really wanted was a Nix function (which I will call
“truncate”) that would take any git repository
and roll it back in time to the last commit before some repeating time
boundary (where the time boundary might be, say, an hour, or day, or
week). For simplicity, let’s just say that the desired time interval is
one day so I want to roll back the repository to the last revision from
the day before.
If I had such a truncate function then it would be easy
to automatically select which revision to use for the full build. I
would:
extract the source git repository from the current
Haskell package build
truncate that git repository to the
last revision from the day before
Use that “truncated” revision as the source for the full
build
Use that full build as the input to the current (incremental)
build
Then if I built multiple revisions for the same day they would all
share the same full build since they would all get “truncated” to the
same revision from the previous day.
However, there isn’t a great way to implement this
truncate function in Nix. To see why, consider the
following (wrong) solution:
extract the source git repository from the current
Haskell package build
Let’s call the derivation for this git repository
“src”
create a new Nix derivation (“src2”) that rolls back
src
In other words, this would be a trivial Nix derivation that begins
from src and runs something like:
$ git checkout $(git rev-list -1 --before '1 day ago' HEAD)
… and stores that as the result
Use src2 as the input to the full build
Do you see the problem with that approach?
The above wrong solution doesn’t allow multiple incremental builds
from the same day to share the same full build from the prior day. This
is because src2 depends on src and since each
incremental build has a different src repository then each
also have a different src2 derivation and therefore a
different full build. That in turn defeats the purpose of incremental
builds if we have to do a new full rebuild for each incremental
build.
For this to work we would need a way to roll back a git
repository to an older revision that less sensitive to the current
revision.
Non-solution #3: Plain
fetchGit
The builtins.fetchGit utility almost does what
we want! This primitive function lets you fetch a git
repository at evaluation time, like this:
nix-repl> builtins.fetchGit { url = ~/proj/turtle; revision = "837f52d2101368bc075d382774460a717904d2ab"; }
{ lastModified = 1655501878; lastModifiedDate = "20220617213758"; narHash = "sha256-Ic4N2gzm0hYsPCynkzETJv7lpAWO1KM+FO+r3ov60y0="; outPath = "/nix/store/ygznanxv6rmbxw5gkgk7axfxazhsa93z-source"; rev = "837f52d2101368bc075d382774460a717904d2ab"; revCount = 566; shortRev = "837f52d"; submodules = false; }
The above result is the same no matter what revision I currently have
checked out at ~/proj/turtle because Nix’s
fetchGit function produces a content-addressed derivation.
In other words, if two invocations of fetchGit generate the
same final repository state then they share the same
outPath. This is exactly the behavior we want: we need the
source repository for the full build to be content-addressed so that
multiple incremental builds can share the same full build.
However, the problem is that I don’t exactly know which
revision I want. What I really want to be able to say is “get
me the last revision from the day before this other revision”.
fetchGit does not expose any way to do something like
that.
That brings us to the actual solution:
Solution
The solution I went with was the following two pull requests:
Add optional
date argument to builtins.fetchGit
This amends builtins.fetchGit to allow a date
specification, which can either be a relative date
(e.g. 1 day ago) or an absolute date (e.g.
2020-01-01T00:00:00 or a Unix timestamp like
1671388622). Basically, this argument accepts anything
git accepts as a date specification (which is a lot since
git is pretty flexible in this regard).
The cool thing about this change is that it doesn’t compromise the
purity of builtins.fetchGit. If a given
fetchGit specification was pure then adding a date
specification preserves that purity.
Add
haskell.lib.incremental utility
This pull request actually does two separate things:
This polishes and upstreams the prototype support for incremental
builds
In other words, this upstreams Harry and Jade’s work to split a
Haskell build into two builds: a full build and incremental
build
This uses the fetchGit patch to automate the full
build selection
There’s a new pkgs.haskell.lib.incremental utility which
uses builtins.fetchGit to automatically update the full
build for you and it has all the desired behaviors (including
branch-local incrementalism).
I could have split this into two separate pull request (and I still
might) but for internal testing purposes it was easier to do everything
on one branch. I’m waiting for a decision on the other pull request
before deciding whether or not to split up this branch.
Demo
I’ll use my turtle package as the running example for
the demo. If you clone the gabriella/incremental branch of
my turtle repository:
$ git clone --branch gabriella/incremental \
https://github.com/Gabriella439/turtle.git
$ cd turtle
… you’ll find the following default.nix file making use
of the Nixpkgs support for incremental Haskell builds:
{ interval ? 24 * 60 * 60 }:
let
nixpkgs = builtins.fetchTarball {
url = "https://github.com/MercuryTechnologies/nixpkgs/archive/696e0820b03e8ea7ad6a9ba21a00a79c91efc580.tar.gz";
sha256 = "1k3swii3absl154154lmk6zjw11vzzqx8skaiw1250armgfyv9v8";
};
# We need GHC 9.4 or newer for this feature to work
compiler ="ghc94";
overlay = self: super: {
haskell = super.haskell // {
packages = super.haskell.packages // {
"${compiler}" =
super.haskell.packages."${compiler}".override (old: {
overrides =
self.lib.fold
self.lib.composeExtensions
(old.overrides or (_: _: { }))
[ (self.haskell.lib.packageSourceOverrides {
turtle = ./.;
})
(hself: hsuper: {
turtle-incremental =
self.haskell.lib.compose.incremental
{ inherit interval;
makePreviousBuild =
truncate: (import (truncate ./.) { }).turtle;
}
hsuper.turtle;
})
];
});
};
};
};
pkgs = import nixpkgs { config = { }; overlays = [ overlay ]; };
in
{ inherit (pkgs.haskell.packages."${compiler}")
turtle
turtle-incremental
;
}
However, that alone is not enough to make use of incremental builds.
If you attempt to build that (at the time of this writing) you’ll get an
error message like this:
$ nix build --file ./default.nix turtle-incremental
error: evaluation aborted with the following error message:
'pkgs.haskell.lib.incremental requires Nix version 2.12.0pre20221128_32c182b or
newer'
(use '--show-trace' to show detailed location information)
The Nixpkgs support for incremental builds depends on a matching
change to the Nix interpreter, so you actually have to run:
$ nix run github:Gabriella439/nix/gabriella/fetchGit -- \
build --file ./default.nix turtle-incremental
… or if you don’t yet have flakes enabled, then use this pedantically
complete command:
$ nix --option extra-experimental-features 'nix-command flakes' \
run github:Gabriella439/nix/gabriella/fetchGit -- \
build --file ./default.nix turtle-incremental
… and that will definitely work.
Once the build is complete you can inspect the logs and you should
see something like the following buildPhase:
…
@nix { "action": "setPhase", "phase": "buildPhase" }
building
Preprocessing library for turtle-1.6.1..
Building library for turtle-1.6.1..
Preprocessing test suite 'regression-broken-pipe' for turtle-1.6.1..
Building test suite 'regression-broken-pipe' for turtle-1.6.1..
[2 of 2] Linking dist/build/regression-broken-pipe/regression-broken-pipe [Libr>
Preprocessing test suite 'regression-masking-exception' for turtle-1.6.1..
Building test suite 'regression-masking-exception' for turtle-1.6.1..
[2 of 2] Linking dist/build/regression-masking-exception/regression-masking-exc>
Preprocessing test suite 'tests' for turtle-1.6.1..
Building test suite 'tests' for turtle-1.6.1..
[2 of 2] Linking dist/build/tests/tests [Library changed]
Preprocessing test suite 'system-filepath-tests' for turtle-1.6.1..
Building test suite 'system-filepath-tests' for turtle-1.6.1..
[2 of 2] Linking dist/build/system-filepath-tests/system-filepath-tests [Librar>
Preprocessing test suite 'cptree' for turtle-1.6.1..
Building test suite 'cptree' for turtle-1.6.1..
[2 of 2] Linking dist/build/cptree/cptree [Library changed]
…
This is shows that the incremental builds are indeed working. We
still have to re-link some executables (for reasons that are still not
clear to me), but none of the Haskell modules needed to be rebuilt since
nothing has changed (yet) since the last rebuild.
Now let’s test that by making a small whitespace change to one of the
Turtle modules:
$ echo >> src/Turtle/Prelude.hs
Then if we rebuild the package we’ll see the following build
phase:
$ nix --option extra-experimental-features 'nix-command flakes' \
run github:Gabriella439/nix/gabriella/fetchGit -- \
build --file ./default.nix --print-build-logs
…
turtle> building
turtle> Preprocessing library for turtle-1.6.1..
turtle> Building library for turtle-1.6.1..
turtle> [ 7 of 10] Compiling Turtle.Prelude ( src/Turtle/Prelude.hs, dist/build/Turtle/Prelude.o, dist/build/Turtle/Prelude.dyn_o ) [Source file changed]
turtle> src/Turtle/Prelude.hs:319:1: warning: [-Wunused-imports]
turtle> The import of ‘Data.Monoid’ is redundant
turtle> except perhaps to import instances from ‘Data.Monoid’
turtle> To import instances alone, use: import Data.Monoid()
turtle> |
turtle> 319 | import Data.Monoid ((<>))
turtle> | ^^^^^^^^^^^^^^^^^^^^^^^^^
turtle> Preprocessing test suite 'regression-broken-pipe' for turtle-1.6.1..
turtle> Building test suite 'regression-broken-pipe' for turtle-1.6.1..
turtle> [2 of 2] Linking dist/build/regression-broken-pipe/regression-broken-pipe [Library changed]
turtle> Preprocessing test suite 'regression-masking-exception' for turtle-1.6.1..
turtle> Building test suite 'regression-masking-exception' for turtle-1.6.1..
turtle> [2 of 2] Linking dist/build/regression-masking-exception/regression-masking-exception [Library changed]
turtle> Preprocessing test suite 'tests' for turtle-1.6.1..
turtle> Building test suite 'tests' for turtle-1.6.1..
turtle> [2 of 2] Linking dist/build/tests/tests [Library changed]
turtle> Preprocessing test suite 'system-filepath-tests' for turtle-1.6.1..
turtle> Building test suite 'system-filepath-tests' for turtle-1.6.1..
turtle> [2 of 2] Linking dist/build/system-filepath-tests/system-filepath-tests [Library changed]
turtle> Preprocessing test suite 'cptree' for turtle-1.6.1..
turtle> Building test suite 'cptree' for turtle-1.6.1..
turtle> [2 of 2] Linking dist/build/cptree/cptree [Library changed]
…
Our package only built the “diff” (the Turtle.Prelude
module we just changed)!
Benchmarks
For the turtle package the speed-up is not a huge deal
because the package doesn’t take long time to compile, but the benefit
for our main project at work is dramatic!
As I mentioned in the introduction, our work project normally takes
~14 minutes to build and after this change builds can be as fast as ~3.5
minutes. In fact, they could even be faster except for the presence of a
Paths_* module that is rebuilt each time and triggers a
large number of gratuitous downstream rebuilds (we’re working on fixing
that).
Limitations
There is one major issue with this work, which is that it does
not work well with flakes.
Specifically, if you try to turn the above default.nix
into the equivalent flake the build will fail because Nix’s flake
mechanism will copy the project into the /nix/store but
without the .git history, so builtins.fetchGit
will fail to to fetch the current repository’s history necessary to
truncate the build to the previous day.
I believe this can be fixed with a change to flakes to support
something like a ?shallow=false or
?allRefs=true addendum to git URLs, but I have
not implemented that, yet.