3 ms·

Build Systems à La Carte: Theory and Practice (2020) [pdf]

45 points by signa11 3y ago

gavinhoward 3y ago
I just released a build system. This paper guided the design. It's one of my favorites, and I read it once a year.
- mdaniel 3y ago
  Ah, I thought the title was (build)v (systems a la carte) but your comment primed me that it's (build systems)n (a la carte)
  - gavinhoward 3y ago
    No idea why you are downvoted; that is a valid reading of the title!
Mathnerd314 3y ago
There are also forward build systems (https://arxiv.org/abs/2202.05328 https://arxiv.org/abs/2202.05328), and Tup's partial dependency graphs.
- gavinhoward 3y ago
  I made a build system, and it turns out that if you have dynamic dependencies, you can implement both.
  - Mathnerd314 3y ago
    ... no? I looked at your build system, and it seems clear that it does not trace command dependencies at runtime, and it also goes through the entire dependency graph on every rebuild - there is no place to integrate a list of changed files from a filesystem watcher.
    - gavinhoward 3y ago
      That's because my build system is not done yet. Once it is, these will be possible. And I did misspeak: filesystem watching is not easily done by dynamic dependencies, but it will be easy for Rig. Speaking as though Rig is full-featured, tracing command dependencies can easily be implemented by users (by adding strace on commands), and then the data from those traces can be stored in the build database. Then dynamic dependencies can be used to make those as dependencies on subsequent builds. For filesystem watchers, Rig has the capability of having different build types. One of the functions of a build type is how to check a file for modification. As of right now, it just returns true. Once incremental builds are added, files will be checked for modification in that build type's function. To add support for filesystem watchers, I simply add a build type that checks the watcher for modifications in that function.
      - Mathnerd314 3y ago
        Neither of those sound like you have actually understood the feature. The point of Tup's partial DAG is that it starts from the file changes and only loads relevant dependency information for those files (and its transitive closure). So for example if you have 1 million .c files and one of them is changed, say a.c, then it does 3 lookups: "what depends on a.c?" (a.o), "what depends on a.o?" (the .exe), "what depends on the .exe?" (nothing, it is a target). So dependency chasing is minimal and it takes very little time until the commands for a.o and the .exe are loaded and rerun. In contrast, in your approach, you will still have to go through the million files - maybe Rig won't require an OS 'stat' call and can just check the watcher's list in-memory for each file, but it will still burn a significant number of cycles following dependency chains even though they are up-to-date. And for command tracing, the most significant issue is that it records both files read and files output. Even with dynamic dependencies it is difficult to record both of these dependency types properly. For example, Shake has this "multiple outputs" feature but it is actually really hacky and doesn't work. https://github.com/ndmitchell/shake/issues/382 https://github.com/ndmitchell/shake/issues/382 The Pluto "sound and optimal" build paper discusses this briefly - they use a two-level file-command graph specifically to solve this problem. Since you have files-as-targets you will have trouble recording write dependencies, similarly to Shake.
dang 3y ago
Build systems a la carte: theory and practice (2020) - https://news.ycombinator.com/item?id=39763074 https://news.ycombinator.com/item?id=39763074 - March 2024 (16 comments) also, earlier: Build systems à la carte: theory and practice (revised and expanded) [pdf] - https://news.ycombinator.com/item?id=25113759 https://news.ycombinator.com/item?id=25113759 - Nov 2020 (3 comments)

45 points by signa11 3y ago

gavinhoward 3y ago

I just released a build system. This paper guided the design. It's one of my favorites, and I read it once a year.

mdaniel 3y ago
Ah, I thought the title was (build)v (systems a la carte) but your comment primed me that it's (build systems)n (a la carte)
- gavinhoward 3y ago
  No idea why you are downvoted; that is a valid reading of the title!

Mathnerd314 3y ago

There are also forward build systems (https://arxiv.org/abs/2202.05328 https://arxiv.org/abs/2202.05328), and Tup's partial dependency graphs.

gavinhoward 3y ago
I made a build system, and it turns out that if you have dynamic dependencies, you can implement both.
- Mathnerd314 3y ago
  ... no? I looked at your build system, and it seems clear that it does not trace command dependencies at runtime, and it also goes through the entire dependency graph on every rebuild - there is no place to integrate a list of changed files from a filesystem watcher.
  - gavinhoward 3y ago
    That's because my build system is not done yet. Once it is, these will be possible. And I did misspeak: filesystem watching is not easily done by dynamic dependencies, but it will be easy for Rig. Speaking as though Rig is full-featured, tracing command dependencies can easily be implemented by users (by adding strace on commands), and then the data from those traces can be stored in the build database. Then dynamic dependencies can be used to make those as dependencies on subsequent builds. For filesystem watchers, Rig has the capability of having different build types. One of the functions of a build type is how to check a file for modification. As of right now, it just returns true. Once incremental builds are added, files will be checked for modification in that build type's function. To add support for filesystem watchers, I simply add a build type that checks the watcher for modifications in that function.
    - Mathnerd314 3y ago
      Neither of those sound like you have actually understood the feature. The point of Tup's partial DAG is that it starts from the file changes and only loads relevant dependency information for those files (and its transitive closure). So for example if you have 1 million .c files and one of them is changed, say a.c, then it does 3 lookups: "what depends on a.c?" (a.o), "what depends on a.o?" (the .exe), "what depends on the .exe?" (nothing, it is a target). So dependency chasing is minimal and it takes very little time until the commands for a.o and the .exe are loaded and rerun. In contrast, in your approach, you will still have to go through the million files - maybe Rig won't require an OS 'stat' call and can just check the watcher's list in-memory for each file, but it will still burn a significant number of cycles following dependency chains even though they are up-to-date. And for command tracing, the most significant issue is that it records both files read and files output. Even with dynamic dependencies it is difficult to record both of these dependency types properly. For example, Shake has this "multiple outputs" feature but it is actually really hacky and doesn't work. https://github.com/ndmitchell/shake/issues/382 https://github.com/ndmitchell/shake/issues/382 The Pluto "sound and optimal" build paper discusses this briefly - they use a two-level file-command graph specifically to solve this problem. Since you have files-as-targets you will have trouble recording write dependencies, similarly to Shake.

dang 3y ago

Build systems a la carte: theory and practice (2020) - https://news.ycombinator.com/item?id=39763074 https://news.ycombinator.com/item?id=39763074 - March 2024 (16 comments) also, earlier: Build systems à la carte: theory and practice (revised and expanded) [pdf] - https://news.ycombinator.com/item?id=25113759 https://news.ycombinator.com/item?id=25113759 - Nov 2020 (3 comments)