Servo also had some other novel architectural ideas IIRC, not directly related to paralelism, but it's been a while since I was looking into that, I don't remember much.
> For (1) and (2), the worst-case just doesn't occur.
I don't think 2. is a good example to be honest, It happens quite a lot. At least it's definitely not in the same category as dependency resolution, where people often don't even know that it's NP-hard.
Typescript, Rust or C++ type system complexity is routinely a compile time problem that people have to work around or tackle from both sides (i.e. either changing the compiler or changing the program).
> Typescript, Rust or C++ type system complexity is routinely a compile time problem that people have to work around or tackle from both sides
True, but this has very little to do with these being NP-hard.
As an example I know well: In Rust, exhaustiveness checking is NP-complete, and trait solving is undecidable. Exhaustiveness checking contributes basically nothing to compile times, and trait solving is significant but that's only because we do it many many times, each particular instance is solved very quickly (and we have limits for how long it can go). Optimizations of both are done using programming tricks and not via algorithmic improvements, almost always.
I think you severely underestimate how much effort goes into tackling the computation complexity of those problems as well. Multiple months (at least) went into tackling various exponential blowups in the next trait solver work. That's a typical symptom for NP-hard problems, there's a consistent stream of exponential cases for which you keep adding various fastpaths and caches for various patterns.
Various crates have explicit workarounds for these issues as well, typically using Box to avoid deep types, e.g. axum's `.route()` added it explicitly to avoid this, I believe.
For match exhaustivness, there's currently an active discussion on it again, because it comes up in derives for big enums, and we just landed an optimization that avoids it for some derive macros.
In other ecosystems, I remember a talk about avoiding exponential blowup for various constructs in C++ templates. Typescript even has a guide for how to write types to avoid complexity problems. With libriaries like `ArkType`, people hit these issues a quite a bit.
I won't claim that this is the majority of the compile time work, but it's something that comes up often enough that I think it's pretty ridiculous to say "the worst-case just doesn't occur."
Asking on zulip is the good first step, yes. But RFC or MCP is only needed for bigger changes. Majority of changes will not need that, especially the ones contributed by newcomers.
For everybody who doesn't have the context, just note that this is not an accepted langauge change. It's a just project goal, which means it's accepted as something people will work on, but the design might change significantly or it can even be abandoned completely (which is pretty unlikely for this one, to be fair).
I think it's absolutely amazing to have insight into long-term goals like this for open source projects. For one thing, it can help you plan your tech stack, and can even be a source of inspiration on what sorts of topics to learn and what sorts of research to do.
I second this. There’s so many OSS projects where long term plans live in private discords and maintainers act like it’s necessary to keep it all a secret
If anything, pin ergonomics is at greater risk. People still discuss if we need both, but if we don't, then we go for this goal and not pin ergonomics, as it's more general.
It (the immobile types proposal) is at a greater risk because it is a very pervasive and complicated change, and the expected semantics are not fully understood. It might be that there is no way to do this well.
> GHC currently needs to parse+typecheck+codegen a file before it can process other files that import it. Codegen is slow. Thus, there's currently demand split compilation into "stages", so that the next file can be typechecked after its imports have been just typechecked (not codegenned).
> I would also enjoy if recompilation avoidance were to happen at the function level, not the file level.
This sounds like Rust is already doing a lot more incremental then GHC then. Rustc only needs to parse, expand macros and do name resolution. Everything else is incremental after that, on a very granular level.
If you changed a function implementation in the libc crate, not changing that function's signature, how much codegen would happen in downstream packages?
The maximally recompilation-avoiding effect would be: Only that one function gets codegenned. Everything else just gets relinked into their final executable or .so.
This is difficult to answer, because these systems exhibit somewhat chaotic behaviour, and it gets even more complicated cross-crate. I was mostly talking about single crate scenario.
Since you mentioned libc, the likely answer is that nothing gets codegened in downstream crates. But this is only because libc functions are usually not generic or `#[inline]`. Changes to generic or inline functions can dirty downstream codegen units where the function was called. Inside `libc`, the change will trigger recompilation of at least one codegen unit, depending on how the function is used inside libc itself. Single crate is split into 256 units in incremental mode.
Nevertheless, even if the codegen is needed just for the `libc` crate, `libc` will dirty its metadata, which means that downstream crates will still need to recompile the initial steps before incremental kicks in (which is roughly parsing, macro expansion and name resolution). After that, the query system just returns cached results for all the subsequent steps.
There's some work going towards skipping the rustc invocation altogether in those cases (usually referred to as "Relink don't Rebuild" proposal), because even just loading the dependency graph and figuring out that you don't have to do anything can take quite bit of time for larger programs.
> 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.
reply