The Rust compiler is still getting faster

I do use emacs! Can you integrate it with make and cmake via emacs somehow ?

Maybe doing `CXXFLAGS="$CXXFLAGS -fsyntax-check" CFLAGS="$CFLAGS -fsyntax-check" make ...` ?

> why doesn’t every language give me a batteries-included digraph ADT, that has every feature you’d need to implement a control flow graph, such that the compiler’s CFG is just a stdlib digraph instance?

Rust does give you access to its internal data-structures on nightly. These change quite often, so you will need to update code that uses them pretty much every week.

Why doesn't many language does this in some stable form? Because that sets the internal data-structures and APIs of the compiler in stone forever, which makes it infinitely harder to improve the compiler and implement new language features.

> Does LLVM still take up much of the overall time spent by the Rust compiler?

The faster Rust gets the more overall time LLVM takes.

> In the end, most graph algorithms are only about a dozen lines, much simpler than the abstractions that would be required to re-use them across completely different graphs

I guess that depends on the language; in dynamic, pure-functional languages (like Erlang) there’s nowhere you can go for further efficiency beyond “digraph expressed as labelled V and E sets held in dictionaries”, so the data structures themselves actually are quite generic, and you would never really need a separate specialization of them.

You’re probably right that in systems-level languages where you’re effectively programming a pointer / RAM word machine, you can get better specialized data structures per use-case, so writing the self-hosting compiler isn’t going to just “throw off” a handy reusable stdlib digraph library as a side-effect.

But in the cases where you’re not using a systems-level language—i.e. the cases where the graphwise algorithms you’re writing are being written against the same stdlib ADT anyway, even if you reimplemented it compiler-side—it doesn’t make sense to me to hide these algorithms away inside the compiler application package. They’re generic algorithms! (And since the ADT is a formal one from a paper, they’re probably very stable ones, too!)

As a restatement of my original premise: if your digraphs are generic, and topsort is a generic function on digraphs with only one obvious implementation given the digraph ADT you’re operating against; and given that you’ve implemented topsort for these stdlib digraphs; why aren’t you putting that algorithm in the stdlib, as a function of stdlib digraphs?

(And it’s not just a question of only putting the most common stuff into the stdlib. Erlang has lots of very arcane digraph operations only useful in proof-verification sitting around in the stdlib in the digraph_utils module. There’s no reason that operations only useful in compilers wouldn’t belong in there equally well. But instead, they’re in the compiler. Kinda weird, if you ask me.)

I want to make a distinction between three kinds of data structures.

1. Implementation-specific thing that has no formal equivalent. Structs of structs of structs, with business logic intermingled with the structure. Plenty of examples of this. I’m not suggesting anyone put these in the stdlib; that’d be silly.

2. ADT with no formalism behind it, that implements a particular set of behaviours “for best performance”, with no guarantee about the implementation or the time/space complexity, and a set of exposed operations that only state what they do, not how they do it, such that you can’t guess what algorithm a given operation is going to use.

Example of #2: Objective-C’s NSDictionary. It only guarantees that it “acts like” a dictionary; it doesn’t guarantee that it’s O(1), because being O(1) with a high constant can actually be worse for performance in some cases. So instead, it makes no guarantees, and tries to optimize for performance by actually switching between different implementations as the data held reaches different size thresholds.

I’m not suggesting anyone put these in the stdlib either, if they currently live in a specific application, because this widens the scope of their stability requirements. Right now only the compiler maintainers can optimize this ADT into doing something entirely different, and then ensure that the compiler (the only consumer) is happy with the result; if the ADT were available in the stdlib, they wouldn’t be able to test all consumers, so they’d have to be much more conservative with their changes, lest they break an edge-case. (Changing how sorting an array ADT works, for example, can break code that assumed that sorting either nearly-sorted or entirely-randomized sets was optimal.)

And, of course, sometimes in a compiler the Control Flow Graph ADT will be of this type. If it is, fine, don’t export it. But usually—because of how compiler maintainers interact heavily with compiler theorists—it’s instead the third kind:

3. Formal data structures, where the name comes from a paper which defines the expected behaviour and a base-level implementation; where either that implementation, or another paper’s pure improvement on said implementation (without changing any of the semantics) is what you can expect to find. As well, the names of all algorithms implemented against the ADT are also well-defined in papers, such that you can know what algorithm you’re using by the name of the function. (Usually, in these cases, you’ll have multiple algorithms that do the same thing differently living as sibling functions in the same module.)

Examples of #3: the geometric primitives and index search-tree types that PostGIS exposes to C-level code. Any implementation of vector clocks. Or, my favourite: regular expressions (i.e. deterministic and nondeterministic finite automata.)

Also, example to make the naming point: for a particular use-case, the use of a segment tree might be an optimization over use of an interval tree. But in code that uses these types of formal data structures, you’d never find an ADT named “IndexTree” that could happen to be either; instead, you’d expect separate SegmentTree and IntervalTree implementations, and then maybe a strategy-pattern ADT wrapping one or the other. But the concrete implementation of the formalism is very likely to exist, because people tend to just sit down and implement these things by translating pseudocode in papers into modules; and then tend to want things to stay that way, because keeping a 1:1 mapping from the module to the paper, and then linking the paper in module-doc, is one of the only good ways to get new maintainers to understand what the heck has been implemented here.

It’s #3 that I would suggest is a good candidate for stdlib inclusion. These data structures don’t change in a way that breaks their guarantees, because their existence is predicated on a particular formalism, and nobody cares about improvements to the performance of a formalism that break the formalism. (Fun analogy: nobody would care about improvements to speed running a video game that required changing the code of the game. You’re trying to optimize that game, not some other one!)