Dear viewer, these subtitles were generated by a machine via the service YouTube and therefore are (very) buggy. If you are capable, please help us to create good quality subtitles: https://c3subtitles.de/talk/2571 Thanks!
[Music]
thank you all for coming today this is
ear and we are going to get a fantastic
presentation put it together fora thank
[Applause]
you am I Al okay so um I'm going to talk
about build system faer modes like um I
can't see most of you but like if
there's a build system uh you might have
used it as a developer um es especially
in an iterative way that you change some
stuff and and then you rebuild and this
is all about what can go wrong and how
you shouldn't do it and how you might be
able to fix this so um first question is
like what's the topic of the talk what
is a build system and it's uh most basic
way a build system evaluates rules and
consumes inputs generates outputs and
you can if you only change some of the
inputs partially evaluate the build and
not recompute everything but only the
things that should be recomputed um
which uh necessarily leads us to okay
make is a build system C cake is a build
system ninja is a build system but excel
in that sense is also a build system
yeah you have formulas and inputs and no
one prevents you from like I don't know
making a Rog like an Exel but um it's
actually relevant to like the formalisms
that you would use to analyze this you
want your outputs to change when you
change the inputs but you do not want to
recalculate entire spreadsheets when you
press one key so
um the thing is build times matter the
someone suggested they should include
this compiling comic from XKCD but um uh
she also said if you had one dirty sock
would you wash all your socks again and
same is like if you have one dirty uh
file how would you get a clean build
like how would you like it um if it it
didn't take like 40 minutes but like 4
minutes the only way you get there is
partially rebuilding only that what you
need to change and um many people think
build times don't matter that's usually
because they have beefy computers or I
don't know pipelines or whatever um you
reality might change it might be that uh
stuff takes hours um I personally got
into build systems because I had a
podcast that exide generator and if you
mess anything up then there are like a
lots of audio files which want to be
re-encoded so I had uh no really
motivation to get this wrong if I
accidentally do stuff that they
shouldn't it take it would would have
taken hours um and if I had always
rebuilt everything I wouldn't be done
and at some any point so um now uh the
thing is you want to rebuild Target
files when their prerequisites change
and it will talk like this talk is like
structure three parts first like common
issues and you might have noticed these
but only like have a feeling or like
ignored them or something many people do
notice them but think yeah it just
happens um then why do these happen why
I think they do happen maybe you have
different opinions but I think I'm right
because obviously um and uh then an
example of how to do that correctly
which is like not as seen as an
advertisement but more like if you
change how you approach the problem then
you can actually do a lot of tasks in a
much simpler way yeah so um first um
common issues so um
uh your target files do depend on source
files and you can simplify this well if
you build some other F Target files they
can also become source files for some
next step and there are three popular
approaches well the first one is very
popular the last modifi time stamp like
when did I touch this last and if if you
like uh touched it then uh the Target is
out of date and something needs to be
rebuilt like there's a file you edited
it the thing doesn't even check if you
changed anything you just like you open
and saved it and the time stamp in the
file system gets updated um the build
system figures out oh no the the source
file has changed now I need to compile
again or I don't know what or convert
some media files um uh more correct
approach so to say like that lets you
rebuild less is hashing everything but
the problem is that hashing again takes
time so um a really good approach is
check the loss modified time stamp and
if it's mismatching only then hash um
depending on what approach you use you
might have problems for example with the
first approach you have the problem that
H git touches everything it sees when
you do a checkout so stuff gets rebuilt
all the time uselessly if you use make
um but uh with a hash thing I once
generated a 16 GB Spar image for some SD
card yeah and then the build system
hashed it and it took a long time um
that was not very smart of me but um
basically you know this issue um the
second uh thing oh well that's the same
I'm sorry I should have gone there yeah
the first is wrong the second is slow
and the third is fast and correct so
there's no excuse for build systems that
use a last modified Tim stamp to like
not hash to avoid usess busy
work so um then the second thing is
dependencies are actually recursive like
people only often think oh I checked the
file it's up to date and that's okay
yeah it's uh now I can just forget about
it but you not only have to like check
the the thing you dependency you have to
check all the dependencies of all your
dependencies like if you generate some
source code file from something else and
then you compile something from
that one thing tains the entire chain
and if any prerequisites of anything
regardless how far away it is changes
the target needs to be rebuilt um some
build systems forget this to whichever
we coming so one thing that often
happens is that people UND specify their
dependencies yeah um you have to list
all of them and maybe you have to list
them manually and um uh the time stamp
based build systems rebuild often anyway
because you use git or maybe you finger
all the files and have them all open in
your editor and it Autos saves so the
problem is that the second thing that
the time stamp based build systems
rebuild so often that masks it like you
will maybe never as a developer get a
failing build
um because like yeah it rebuilds lots of
useless stuff anyway without needing to
and that uh prevents you from noticing
it um the prime suspect is get checkout
and it's really hard to convince people
of uh that this is happening but what
you can do is make a post checkout hook
forget that sets the uh timestamp of the
files that you checked out to when they
were last committed and lots of things
will break I can guarantee it because I
tried it and then people
that just don't do that but it's more
like proving that the dependencies are
under specified um pretty uh easy
experiment so one thing that is often
ignored is that Target files actually
depend on their own build rules so if
the build rules change the target needs
to be rebuil that sounds obvious right I
have a different build Rule and um uh my
favorite build system Exel does this
right if you change the formula the
sellers updated but make does not and
neither do a lot of other systems that
basically work like make
and the trick question is should targets
depend on the make file I have rarely
seen this in the wild the advantage is
whenever you change your build rule your
target is rebuilt the disadvantage is
whenever you change any buildt rule all
Targets are rebuilt yeah um to me it
suggest that maybe the idea of like
putting all the rules in one file and so
on and so on is done but it's a funny
trick question like maybe if you meet
someone who didn't go to this talk and
they're like really enthusiastic about
build systems that could make them shut
up um
so then something that is ignored even
more often is that targets actually
depend on non-existent files it might be
that a new file appears and the target
needs to be rebuilt a header file
appears in the current directory and the
processor would find it or you have an
image gallery a new image appears you do
not want to rebuild all the thumbnails
but the index file that shows all the
pictures needs to be invalidated um when
a new image appears
and if you have a webcam that does a
photo every minute or so you already
know the file name of the non-existent
file that as soon as it appears inv
validates your build a surprisingly
large number of build systems are
entirely unable by architecture like
architectural limits to actually do this
and ignore it entirely but the problem
is this is a very common thing and uh
basically every one of these uh
non-existence
dependencies uh is uh uh the case of I
make uh a new file in the file system
and this invalidates my build and if I
then rebuild I might get a binary that
doesn't correspond to my source code
that all of all of the problems where
you have a build that seemingly succeeds
like not not go but doesn't build enough
mean your result is not guaranteed to be
correct maybe some of you had this that
they uh partially rebuild something it
didn't work and you delete like uh all
the make and C files and whatever and
then you rebuild completely and then it
worked yeah that was one maybe not this
one but this is one of the common issues
often people don't know why it happened
but you can blame the bill systems
basically by for not tracking something
that it should have tracked so now the
thing is even more specifically
combination targets depend on
non-existent build rules it might be
that in the
future uh a Target is built using a enal
rule like a rule for all HTML files or
all object files or something you in the
future you have a more specific rule
that would override this yeah well when
this rule appears in the make file which
we already know is rarely considered
anyway you also need to rebuild the
Target and I've actually never seen this
in software that I this like um
unrelated to the proposed solution like
uh it seems to be often for forgotten or
people use weird uh domain specific
languages to handle this yeah um then so
the thing is like why do these problems
happen and I am convinced that the
reason is because the common approach to
build systems is you treat everything as
a directed a graph that's an image from
Wikipedia where the notes are files like
like in the graph and the edges are
dependencies like to build a I need to
build C and B and B and C both need D
and D need e so I first start uh yeah I
I I have this information and then the
procedure is I construct this graph I
topologically sort it so I have an
ordering in which I can build these
things so that they satisfy all these
errors there and then I schedule the
build task and this is very easy to
implement you it's very easy to paralyze
and it's uh obvious but wrong like
because while you you idealized build
the spherical how in a vacuum um might
sometimes uh be modeled like that uh
usually you don't want that um because
at the point where you construct the
graph you do not have enough info like
you cannot actually do this successfully
in almost all cases that I can say for
example because you do not know the
non-existence dependencies like you do
not know which file the pre-processor
did not find that did not include but
would find in the future um and as soon
as you have scheduled the build task you
might get new information like um uh the
thing is like to deal with this people
pretend for example that the world is
Frozen that the entire file system is as
the same as when you started the build
but the problem is obviously it isn't
because you're outputting stuff and
generating files left and right because
that's the purpose of your system so
it's it's kind of a bit weird that
people then for the dependency
evaluation pretend well all is still
like it's in the start it doesn't work
and the second thing is like there are
some people who are like oh just list
every dependency yeah you're a
programmer list every file yeah and this
obviously does work and embedded
developers rarely have these kind of
problems because they are seem to be
like a special breed and have very
little in terms of dependencies they
know absolutely nothing but compared to
application developers but um if you
have a build system that says oh if you
don't list the dependency it will not
show up in the file system View for the
uh for the build because of some overlay
or so then uh you will be annoyed pretty
fast because this [ __ ] robot work to
like figure out which files are there
like why should you do that if the
computer can do it for you then so the
most popular approach to um uh make it
work is just ignore the issues like the
previously mentioned problems and
similar problems that result from this
because it's
also seducing to have a way that you can
easily model something and maybe it's
sometimes wrong but um it's fast right
and you totally understand it um build
system authors do not like it when you
point out that they're ignoring stuff
they I've literally seen people say well
then just don't do that like don't have
that build but that doesn't help me
because I have the build and I want to
like I want to results so how would you
do it correctly what I uh figured is
that um
actually you can treat bills as some
kind of like huge function that you can
partially evaluate to to partially
rebuild and then you can rebuild
recursively until outputs do not change
like until you reach a fixed point and
obviously the one iteration is a common
case you get something you get the
output if you would do it again you get
the same thing but if you use this make
depense thing where you use make and it
outputs it us and the compiler outputs
the uh dependenc es in a format that
make understands and then you rebuild a
second time and then you get the same
output you have two iterations and you
have found your fixed point and perhaps
the most common example uh that people
are familiar with is lates like you have
these like line numbers and references
and figure stuff and you need to compile
three times because this thing the build
needs to be iterated until you reach the
fixed point where everything points to
the correct page um
this is kind of obvious once you see it
you see it everywhere that that
intuitively you expect the thing to have
a fixed Point um if not you have a
haling problem but um obviously you
cannot model the lat thing with a
directed iy graph so um Daniel J
Bernstein uh lot long time ago put some
notes on the website and uh never
release the tool I met him twice and he
didn't so um how to fix a bunch of of
stuff um and uh I read them at some
point when I did the the podcast thing
and someone else wrote a thesis on the
topic like how build systems should work
and several implementations of this idea
were created um mostly incomplete I also
have one I I consider it complete um but
uh the important thing is like uh
because Burnin Never released it um I
still I don't know if he has one but he
writes make files the way someone would
translate them from another tool
sometimes maybe he does it in his head
so um like the same way you can like
spot the python code that was written by
the C programmer who is barely familiar
with python um uh so the essentials is
um basically the idea allows uh any
language to use to create some targets
like just you no special thing like use
shrips use Pyon scrips use Ruby whatever
uh random executables but uh you have to
build top down instead of bottom up
which means when you start the build you
do not start at the leave notes at the
stuff that you that you need to like
build higher stuff but you start at the
end Target like I want this binary what
do I need to do to get it then uh you
recurse down to the sub targets more and
more um this uh is for some reason
people don't like this approach but you
avoid the topological sorting at a bunch
of other issues like that and also build
rules are files this will become
important later um
because build rule each build rule is
one file this means you can change the
build rules um the same way you track
change to files you do not need a
different first class primitive uh that
you can depend on and if a build rule
changes all its targets are rebuilt and
obviously if you have more specific
build rules they will have different
file names and you can have a more a
non-existence dependency on this not yet
existing more specific build Rule and if
that file is ever created and you write
a build rule in it the target will be
rebelled
solves a bunch of issues people hate it
because then they suddenly have more
files um there are four commands um
which make this possible I have a
separate talk that I can give you like
not here but um that explains how to use
them but basically these are Primitives
if you implement these four Primitives
in your top- down recursive build
systems I think you can avoid most of
these problems and have something that
is um very small uh very small in terms
of implementations very flexible because
you can combine them in weird ways and
actually is correct um and faster than
the toos sort thing for the Comm for
many common cases so the first is
command uh is a redo if change basically
you have some script that builds
something maybe a shell script or
something and re of change is a command
that only has a meaning within a build
script for a Target and it means first
you it checks if the file is out of date
like it can be something that you
generated or it can be source file then
it rebuilds it if necessary obviously it
will only happen for stuff that you
generate and third if that thing was out
of date at the point where you where
this command was executed like the
argument to this command a file name
then the current Target is rebelled this
is a bit weird but it's a really
powerful primitive that enables you to
make a to basically this means oh yeah
this thing is a dependency but it
enables you to declare this in an
imperative way with from within a shell
script or from within a python or
program um as I said it's a bit weird
the second redo have create basically
the same thing for the non-existence
dependency first you check that the file
argument does not exist second if that
thing exists in the future the current
Target will be rebuilt don't think too
hard about how this is implemented um
it's a bit um brain teaser and then
people often forgot this but makers
phony rules and other uh other systems
have as well uh there's a
that you need to Mark a Target is always
out of date and here you see the
directed asly graph thing will have a
problem with that because if you have
something that's always out of date and
then you do the Topo sort it only
appears once in the list but it may need
to appear several
times because it's always out of date
when you want it so you always need to
rebuild it whenever anything depends on
it and so you can actually spot uh build
systems that do not handle a case
correctly by having figuring out how
they make targets always out of date and
then figuring out if you have like
several things depending on an always
out of dat Target is it built only one
time if yes the build system is faulty
in a way that makes it way easier to
implement parallel builds but also makes
them incorrect um so there's one fourth
thing that you need for some reasons
because sometimes you might notice
during a build that something that you
build while it was considered um out of
date is actually up to dat for example
if you have a Target that depends on
something that is always out of date you
might want that always out of date thing
to be regenerated but the thing that
depends on it by the well transitive
property would also be always out of
date and then you would end up
rebuilding everything all the time that
depends on anything that at some distant
point in the graph is out of date um so
basically this tool reads the standard
input and if the in in any future build
the input is the same then the build is
only speculatively executed up until
this point and it says oh no no no the
target is up to date everything is okay
and this is very rarely needed but when
you need when you need this and your
build system cannot provide it like
actually canceling a scheduled uh build
command during a build to save time
because you it would be useless busy
work you you will totally notice it
missing um so this is the end of the
explanation and um I have a few more
slides um I hope do I can I still
continue okay then come to me afterwards
and um there are very predictable
questions I can answer most of them and
if you want to fix a build system or
whatever um talk to
me let's have a great Round of Applause
for a
yeah
[Music]