The interesting question for me is where the crossover is now that IDEs and incremental compilation dominate the workload. If your front-end is effectively a long-running service, it might be worth keeping a friendlier AST around and only using a super-flat representation for hot paths like analysis passes or bulk refactors. Otherwise you risk saving a few hundred MB while spending engineer-months making every new pass fight the layout.
That's not nothing. But a parser is rarely the most time-intensive part of a production compiler. And the parser does get iterated on a lot in languages that are evolving and adding new syntax.
Given that, I'd be inclined to take the performance hit and stick with a simpler AST representation if that yields a more hackable, maintainable compiler front end.
I didn't go into this at all, but the main benefit of this design is how well it interacts with CPU cache. This has almost no effect on the parser, because you're typically just writing the AST, not reading it. I believe that subsequent stages benefit much more from faster traversal.
(By the way, I am a huge fan of your work. Crafting interpreters was my introduction to programming languages!)
E.g., https://github.com/llvm/llvm-project/blob/62e00a03fba029f82d...
and
https://github.com/llvm/llvm-project/blob/62e00a03fba029f82d...
I mean if you do an off by one error on indices, essentially you are readin the pointer of another node.
Because it is a correct one. std::vector can do this in debug mode, Zig and a bunch of other languages do as well. But that's not the point of why memory safety's important. You opt out of all aliasing and lifetime checks this way, which means an easy off-by one indexing bug (which would be a compiler error otherwise), silently propagates through the system, and you can reference wrong nodes, invalid nodes, uninitalized nodex.
It's even worse in some aspects that a dangling pointer, because you can quickly tell a dangling pointer contains garbage data, but here, the stuff looks plausible.
I am not sure this is a critique of Rust - this certainly goes against the grain of how the language has been designed - which in the case of Rust, might make things easier, since lifetimes are not checked for individual elements, but also less safe.
> you can reference wrong nodes, invalid nodes, uninitalized nodex.
No, you cannot access uninitialized nodes in safe Rust.
When investigating performance issues its often very helpful to run with profiling instrumentation enabled and start by looking at some top-down "cumulative sum" profiler output to get a big picture view of which functions/phases are consuming most of the running time, to see where it may be worth spending some effort.
Getting familiar with linux's perf [1] tool is also helpful, both in terms of interpreting summary statistics from perf stat (instructions per cycle, page faults, cache misses, etc) that can give clues what to focus on, but also being able to use it to annotate source line by line with time spent.
I'm not familiar with rust, but e.g. the rustc compiler dev guide has a tutorial on how to profile rustc using perf [2]
[1] Brendan Gregg's Linux perf examples is an excellent place to start https://www.brendangregg.com/perf.html [2] https://rustc-dev-guide.rust-lang.org/profiling/with_perf.ht...
mitchellh•1mo ago
More generally, I believe its fair to call this a form of handle-based designs: https://en.wikipedia.org/wiki/Handle_(computing) Which are EXTREMELY useful for a variety of reasons and imo woefully underused above the lowest system level.
sestep•1mo ago
My current research is about how to make handles just as convenient to use as pointers are, via a form of context: like a souped-up version of context in Odin or Jai if one is familiar with those, or like a souped-up version of coeffects if one has a more academic background.
densh•1mo ago
faresahmed•1mo ago
As far as I know no language allows expressing that kind of thing.
sestep•1mo ago
But from what I understand (being a nonexpert on Scala), this scheme actually causes a lot of problems. I think I've even heard that it adds more undecidability to the type system? So I'm exploring ways of managing context that don't depend on inferring backward from the type.
debugnik•1mo ago
You can do this with path-dependent types in Scala, or more verbosely with modules in OCaml. The hard part is keeping the container name in scope wherever these handle types are used: many type definitions will need to reference the container handle types. I'm currently trying to structure code this way in my pet compiler written in OCaml.