Will Val take as long to compile as Rust?

[C-BJ]

The compiler for Val is written in Swift, does this affect compilation time significantly?
Does Val will be self hosted when the language is relatively stable.

What is the estimated compile time for Val based on the language design?

[kyouko-taiga]

Good questions.

The compiler for Val is written in Swift, does this affect compilation time significantly?

I don't think having the compiler written in Swift instead of Rust makes a significant impact. Rust is a fast language, so it should have very little impact on the speed Rust compiler. Instead, I think the compilation times in Rust have everything to do with the language design.

I don't know enough about Rust compiler to give an informed answer. I've heard Rust folks blaming LLVM, which would be an issue for Val too, but somehow I'm doubtful LLVM is the only culprit. Named lifetimes are probably hard to verify and it's possible they putting some heavy burden on the compiler. If I'm correct, then Val might have an edge because projections should be simpler to verify. But I'm only speculating.

What is the estimated compile time for Val based on the language design?

It's very hard to say without having an implementation.

For now, we have put little effort into optimization as our priority is to have a working version. Once we do, we'll start profiling. I'd be surprised if we can be competitive with Rust in the beginning; they've had a huge head start.

Does Val will be self hosted when the language is relatively stable.

I'd like that very much, but that will probably take a while.

Again, I don't see any reason this would give an edge to Val over Rust, though. I don't expect Val to significantly outperform Rust on most applications.

[kyouko-taiga]

What's N? The number of instructions?

I'd be grateful if you could point me to where you found that information. I have to admit I find it quite surprising. I would expect the complexity to be much higher (see https://arxiv.org/pdf/1303.4315.pdf).

[AbhinavK00]

I read it some time ago on some blog. Sorry, but can't find the source despite searching for two hours. Sorry, you can completely ignore my info.

[kyouko-taiga]

No worries. Thanks for looking.

[matklad]

I don't know enough about Rust compiler to give an informed answer.

I think I can chime in a bit, as I looked into that a fair amount, although mostly in the context of interactive compilation for IDE. There are indeed quite a few things slowing Rust down!

• LLVM is certainly not a speed demon. The fundamental fix here would be a performance-oriented backend for debug builds. The problem with this though is that Rust's heavy reliance on zero-cost abstractions makes debug builds disproportionally slow (which is unlike Zig, whose abstractions mostly dissolve before hitting the backend). So the "fast compiler" should also be able to do some amount of optimizations, https://robert.ocallahan.org/2020/08/what-is-minimal-set-of-optimizations.html explores this in some detail.
• Rust, like C++, and unlike Swift, lacks true separate compilation. If you define a generic function in one compilation unit, and use in a different CU, the actual compilation (monomorphisation) would happen in that second CU. This combinatorially increases the amount of code (every downstream CU gets a separate copy of generic function even when type parametres match), and makes incremental compilation less efficient (changing the body of deneric functions requires recompiling the consumers, even if signature stays the same). Swift model for generics, where they are monomorphised in the "current" CU, but pass runtime dictionaries across CUs, feels like the sweet spot.
• C-style linking model slows down optimized builds. Bodies of non-generic functions are not visible to downstream CUs. That means that they could not be inlined, which tanks performance. So you either need to manually annotate them with #[inline] (manual work + generic-style duplication) or you need to compile with lto, and lto is slow. It feels like a compilation model which doesn't rely on C "compile&link" phase separation, but rather freely rearranges monomorphisation and linking a-la map-reduce could be significantly faster for optimized builds.
• Compiling a single CU in parallel is not natural. In the ideal compilation model, you typecheck&compile all CU's functions independently, because signatures separate bodies of the functions from each other. IIRC, rustc doesn't actually do that. One reason for that is that front-end parts (parsing, macro expansion, name resolution) are hard to do in parallel, in Rust. You can't just parse all files in parallel, because the order in which things are parsed affects macro expansion. Similarly, after parsing you can't just name-resolve all files in parallel, because name resolution is CU-global fixed-point iteration. This also affects incermental compilation, if file foo.rs is modified, you can't trivially reparse&resolve&reexpand just that file, as dependencies of other files on foo.rs are really non trivial, and you need rather fancy incremental computation framework to sort those out.
• Trait resolution is global, to resolve foo in xs.foo compiler needs somewhat global view of the set of available traits&impls. This is a hot spot for IDEs in particular, as those want to be maximally lazy during analysis, but trait search forces you too look everywhere .
• Borrow checking and related control flow analysis is probably quite involved! Don't actually know about that much, because, from IDE perspective, that doesn't really matter --- this is strictly function-local work, so it's embarrassingly parallel and lazy. But, again, IIRC rustc doesn't actually do that, and borrow-checks functions sequentially. I would attribute that to the fact that early phases of compilation weren't trivial to parallelize, so compiler was written in single-threaded style, and then parallelizing a large program is hard.

In terms of what the next language can do better:

• Use Swift model for compilation for better incrementality and less work across CUs
• Design syntax&name resolution to make compilation within a CU parallel
• Start with a parallel compiler to use it as a forcing function on language design (again, the problem with Rust is not that compiler is single threaded, but rather that the language is hard to parallelize)

[kyouko-taiga]

Thanks a lot for these great insights. Some promising observations we can make early on w.r.t. Val:

• We plan on supporting a Swift-style separate compilation model using modules. Guaranteeing ABI stability between opaque module implementations will incur some cost (to wrap existentials) and impede on specialization, but we believe the tradeoff might be acceptable. There might be avenues to explore for allowing the user to force monorphisation across module boundaries.
• We started with an IR model to perform flow-sensitive analysis and optimizations. If I'm not mistaken, that is unlike Rust which only introduced MIR on the go. So while name resolution and type checking require an (almost) global view of the program, subsequent analyses don't. We can already parallelize all intraprocedural passes in the current implementation.
• Although type checking requires access to the whole AST, it only needs to see signatures (all in the current module, public ones in imported modules). So that means we can have the parser run a first pass that extracts signatures and skips all declaration bodies, and then parallelize type checking on a per-module (or perhaps even per-file) manner.