5 ms·

The traditional model of compilation is the biggest issue holding back fast incremental compilation IMHO. Swift suffers from this as well. Even a simple change

The traditional model of compilation is the biggest issue holding back fast incremental compilation IMHO. Swift suffers from this as well. Even a simple change to one file results in re-parsing the whole library because definitions come from anywhere and we have to obey the 1970s single file compilation model. The result is a driver spawns 8 threads and each one wastes time re-parsing every file in the library looking for definitions. AFAIK Rust doesn't really track dependencies at the file or function level either so it doesn't really know what changed. To me compilers should be content-addressed databases. Each declaration and its associated content generate hashes that roll up to its containing type or namespace, then to the file, then to the library as a whole, along with hashes of the dependencies. Changing the type signature of a single function should result in the compiler being able to cheaply determine whether that has any visibility and if so to what other files in the same library or if it affects the public interface. A file that hasn't changed and whos inputs hasn't changed should re-use the IR from the prior compilation. Even for an individual type that should be the case so changing the internals of a function in a struct only regnerates that one function and nothing else. The compiler knows deterministically that change can't have affected anything else. That has major benefits for code completion and editing as prior compilations can feed into generating errors or suggested corrections. Then you can take things a step further and JIT a changed function, injecting the new machine code on the fly so long as the shapes of the types don't change. Very useful for debugging. Compilers are mostly held back because the people who write compilers are stuck on certain ideas about how compilers should be written.

panstromek 2mo ago
> To me compilers should be content-addressed databases. There's a language called Unison that does that - and the "content" is the AST, so all functions that have the same shape are the same function. It's pretty interesting.
SkiFire13 2mo ago
> To me compilers should be content-addressed databases Rustc already does something like this. The issues are: - when you have to rehash everything to check that they indeed didn't change from the previous compilation. For big projects this takes _a lot_ of time. - when small changes do indeed change the hash of a lot of seemingly unrelated code, which is more common than you might think.
- tancop 2mo ago
  You dont need to rehash everything if you do multi level hashing (file -> mod/impl block -> function). The expensive part is doing lots of hash passes over small parts of a file, so if you break as early as possible the moment you can guarantee that part is unchanged you save a lot of time. And if you assume (and document) that libraries need to be rebuilt manually you can completely skip checking them. OP handles the small change problem by hashing IR instead of source text. If the new function compiles to the same IR as the old one its guaranteed to give the same machine code. You should repeat this after each lowering or optimization pass so functions with different HIR but same MIR are also marked as unchanged and dont cause items up the tree to rebuild.
  - mlugg 2mo ago
    > OP handles the small change problem by hashing IR instead of source text OP here---I think you got confused somewhere, because this isn't true! The hashes we take are of source code, they're just stored inside of the first IR. Source code is just pretty convenient to hash. If the change does turn out to be something trivial, we'll only invalidate the first-order dependencies of the source hash, which is never usually a big deal. In a particularly bad case, maybe we re-analyze, re-codegen, and re-link many different instances of a generic function, but even that wouldn't usually take long at all. Also, it's actually important that we do notice these kinds of "trivial" changes in some parts of the pipeline---see Andrew's comment [0] on the Lobsters discussion for this post. [0]: https://lobste.rs/s/rmzzdb/inside_zig_s_incremental_compilation#c_lkhjvp https://lobste.rs/s/rmzzdb/inside_zig_s_incremental_compilat...

panstromek 2mo ago

> To me compilers should be content-addressed databases. There's a language called Unison that does that - and the "content" is the AST, so all functions that have the same shape are the same function. It's pretty interesting.

SkiFire13 2mo ago

> To me compilers should be content-addressed databases Rustc already does something like this. The issues are: - when you have to rehash everything to check that they indeed didn't change from the previous compilation. For big projects this takes _a lot_ of time. - when small changes do indeed change the hash of a lot of seemingly unrelated code, which is more common than you might think.

tancop 2mo ago
You dont need to rehash everything if you do multi level hashing (file -> mod/impl block -> function). The expensive part is doing lots of hash passes over small parts of a file, so if you break as early as possible the moment you can guarantee that part is unchanged you save a lot of time. And if you assume (and document) that libraries need to be rebuilt manually you can completely skip checking them. OP handles the small change problem by hashing IR instead of source text. If the new function compiles to the same IR as the old one its guaranteed to give the same machine code. You should repeat this after each lowering or optimization pass so functions with different HIR but same MIR are also marked as unchanged and dont cause items up the tree to rebuild.
- mlugg 2mo ago
  > OP handles the small change problem by hashing IR instead of source text OP here---I think you got confused somewhere, because this isn't true! The hashes we take are of source code, they're just stored inside of the first IR. Source code is just pretty convenient to hash. If the change does turn out to be something trivial, we'll only invalidate the first-order dependencies of the source hash, which is never usually a big deal. In a particularly bad case, maybe we re-analyze, re-codegen, and re-link many different instances of a generic function, but even that wouldn't usually take long at all. Also, it's actually important that we do notice these kinds of "trivial" changes in some parts of the pipeline---see Andrew's comment [0] on the Lobsters discussion for this post. [0]: https://lobste.rs/s/rmzzdb/inside_zig_s_incremental_compilation#c_lkhjvp https://lobste.rs/s/rmzzdb/inside_zig_s_incremental_compilat...