psykotic

Moffat and Turpin's 1997 paper On The Implementation of Minimum Redundancy Prefix Codes contains all the usual tricks and then some: https://github.com/tpn/pdfs/blob/master/On%20the%20Implement...

Yeah, I'm happy to see more experimentation in the lightweight compiler space! My one-pass pipeline does forward greedy regalloc integrated with the approach I outlined in my post.

The next sweet spot seems to be a two-pass pipeline so you get a full forward and backward dataflow pass: your forward pass does SSA generation integrated with the forward dataflow analyses and the backward pass does machine code generation integrated with backward regalloc and dead code elimination. SSA with backward codegen/regalloc gives you an optimal coloring since the backward order for structured code matches the reverse postorder of the corresponding reducible CFG, and the greedy backward approach gives you decent splitting/coalescing for free. This is basically LuaJIT's approach but it can be extended beyond traces to reducible control flow if you replace the linear trace ordering with the dominator tree ordering. With two passes you should also be able to do something like Cliff Click's style of global code motion (as used in the HotSpot server compiler) with the early-schedule/late-schedule steps integrated into the two passes.

The main limitation of a pure two-pass approach is that you can't do precise SSA generation for loops at the same time you're doing your forward dataflow pass, so you have to be conservative. That blocks most LICM opportunities, so an extra micro-pass per loop is easy to justify, either an SSA pre-pass per loop or something like LuaJIT's loop peeling where you fully peel off the first iteration while identifying loop invariant variables before processing the loop a second time. Then LICM happens automatically via CSE since the peeled iteration dominates the loop body.

In a register-allocating one-pass backend you by necessity decide the register/stack map for a given label the first time you emit a branch that targets it. As a result you never have a problem with critical edges for two-way branches because the fall-through cannot be targeted directly by other branches; you always have a (possibly trivial) block for the fall-through edge with only one predecessor. Example:

    // The jump_if emits shuffle/spill/fill code before the 
    // conditional jump to conform to the L1 register/stack 
    // map. If the L1 map hasn't been created yet, we use 
    // the intersection of our map with the conservative 
    // live set (perhaps from the lexical scope) for L1
    // in which case there's nothing to emit except the jump.
    jump_if(value, L1);

    // The fall-through block starts here.

    // The join emits shuffle/spill/fill code to conform
    // our current map (which is equal to the L1 map) to
    // the L2 map. It then backpatches any existing refs
    // to L2 and updates L2's address to point here. As with
    // jump_if, if this is the first ref to L2 we just set
    // our current map as L2's map and emit no code.
    join(L2);

Multi-way branches (typically from switch jump tables) with critical edges are much rarer and can be handled in a one-pass backend by splitting on demand (by inserting jump pads) when a multi-way branch target has already been referenced and had its map assigned. That's rare enough in practice that doing something more global to decide where to place the splits probably isn't worth it in a one-pass backend.

It's more complicated than that. You can see what passes are run by clang with the flags -mllvm -debug-pass=Arguments. It's certainly true that -O0 involves fewer passes than -O1 which involves fewer passes than -O2. But the speed limit is defined by the architecture. A compiler that was engineered for compilation speed with a goal of -O1 tier code quality would have a very different architecture from day 1 (e.g. unified IR, fewer passes, integrated register allocation and code generation). There's been attempts at "punching through the layers" over the years with things like fastisel, but there are limits.

That said, all the major compilers can deliver adequate compilation speed on the order of 50-100 kloc/sec for well-structured C code bases. Speed is much more of a serious concern if you're working on large C++ code bases. Or if you're using LLVM as a backend from a language like Julia which does the moral equivalent of C++ template instantiation at runtime and feeds it to LLVM.

RAD always paid very well by gamedev standards. But that was never the main reason people worked there.

Some of the engineers are older but Fabian is in his thirties and last I checked his goatee wasn't greying.

He's right to emphasize the properties of the systems that support interactive development with a long-running image. In Common Lisp, the difference between defvar and defparameter is a simple example. Traditional Smalltalk systems only supported image-based development. But I always preferred the moderate approach exemplified by most Lisp systems where the source code isn't overly entangled with the image state.

As a long-time but now lapsed Lisper, I never understood some people's elevation of the REPL. A command-line REPL is a poor man's development environment. If you're doing interactive development in Lisp, you'll be far more productive if you use a normal buffer with eval-defun, eval-buffer and friends. When debugging, you'll primarily want auto-updating watch expressions and object inspectors. And when you do have good use for a REPL, you'll still want it to exist within a proper buffer with persistent history, inline object inspection, etc, instead of the low-effort rlwrap terminal experience which usually passes for a REPL.

All of this holds doubly true for Smalltalk environments.

Regarding state space blow-up, the only thing I'd add is that after DFA/NFA minimization you always get a canonical state machine (up to state relabeling) so the size will be the same regardless of how it was constructed. This doesn't mean that state space blow-up won't happen but that there isn't any inherent overhead (after minimization) compared to writing an equivalent regular expression by hand without using the product/complement constructions. But minimization interacts poorly with some practical features like capture groups, so you could probably only use the minimized automaton for matching and you'd have to compute the captures after a match some other way.

Yeah, the good news is that your tool can statically detect the ambiguities and you can let users specify priorities for the conflicting productions to define a unique mapping. That's a standard technique in parser generators. There the ambiguities are in the opposite direction, but the same idea applies.

I learned the specific 're1 string re2' decomposition with backward matching from Hyperscan but AFAIK several fast grep-oriented regex engines factor out both prefixes and suffixes and use whichever is longer/most rare as a substring anchor. For the suffix case you need backward matching to confirm the regex match after the substring match. Hyperscan actually decomposes the entire state machine graph into 're1 string re2' style fragments, which lets them select the fastest implementation technique for each sub-machine.

I think Russ Cox talks about backward matching in his article series on regular expressions, so it's probably used somewhere in re2.

"Reversible" meant consuming the character stream in reverse order while matching the same language, so it's different from what you have in mind--automatically generating a printer from a parser. On the surface it sounds very doable if each pattern of AST node is generated by a unique grammar production. Then pretty printing is the task of matching against an unambiguous tree grammar. It's not really different from what the compiler for a language like ML or Haskell does for pattern matching.

Deterministic/non-deterministic finite automaton. It's the standard term for a finite state machine which processes a stream of characters. All the examples in his article are DFAs.

Some random fun things you can do with DFAs/NFAs:

1. From two machines you can build a single machine that corresponds to running them in lockstep/parallel. Most language classes are closed under unions but regular languages stand out by being closed under intersections, and that relies on this construction. You can't replicate this construction with pushdown automata to show that context-free languages are closed under intersection because the product automata would require two stacks. But in fact the intersection of a context-free language with a regular language is context-free via this construction.

2. You can run them backwards. Usually works best with NFAs since reversing a DFA can seriously inflate the state space. E.g. if you're trying to match a regular expression of the form '<re1> string <re2>' you can search for 'string' and then match re1 backward and re2 forward. Running machines backwards can also be used for computing capture groups after a match has been found since the fastest methods for matching don't let you compute capture groups on the fly. Decoupling the re1 and re2 machines also means you end up with two independent machines with smaller state spaces, which means smaller, cache-friendlier lookup tables. See the next item for a less conventional example of what you can do with small state spaces.

3. While DFA execution seems inherently serial, it can actually be parallelized very effectively if the state space is small enough, through speculative execution. Suppose you want to lex a string in parallel by chopping it in half. You don't know what state the DFA will be in when it reaches the halfway point, but you can process the second half for all possible states at that point. Then when both halves are finished you throw away all but one of the speculative answers for the second half based on the final state for the first half. This is extremely fast and practical with PSHUFB/TBL-like instructions if your state space is small enough, at most 16 states for PSHUFB. You can mux together multiple PSHUFBs to go beyond that limit but the cost increases substantially. (This is a parallel prefix algorithm when applied recursively. As far as I know the application to parallel lexing goes back to the Hillis-Steele paper on data-parallel algorithms from 1986.)

4. There's a critical optimization for the last algorithm which is sometimes applicable. A log file processor might have numerous internal states while processing a line, so you'd rather not speculate on all of them. Instead you can chop the file in half and from the second half seek forward to the next newline and start there. This avoids speculation entirely if there's a unique state following a newline character regardless of what state you were in before the newline.

The power scales linearly, not quadratically with the amount of look-ahead. The "m" is the number of states you're speculating on which doesn't grow with look-ahead length. In the case where you're just speculating on whether an instruction starts at a given byte offset, you would have m = 2.

I don't think anyone is saying they could scale up the decoder "for free". If they had a fixed-length ISA, I'm sure they would have increased the decoder width sooner (and using different techniques) since with high-end out-of-order cores you're always looking for cheap ways to over-provision your pipeline even if it only helps on some workloads some of the time. Their current use of the uop cache tells us that they consider it the most economical trade-off at that point in the design space (where the decoder can output up to 4 instructions and the uop cache can output up to 6 instructions); you can't infer that they've hit an impassable brick-wall with instruction decoding.

Yeah, the algorithm for parallel decoding you outlined scales linearly in area and power with respect to the speculative look-ahead depth. This is true even if you speculate on more than the per-byte "boundary or not boundary" condition. A parallel-prefix circuit for processing a DFA with m states where you speculate on all m possible initial states for each of n bytes "only" consumes O(m n) power. [1] In absolute terms this is obviously still a problem as you crank up m or n, but the scaling is certainly not exponential. You do see local exponential scaling if the state space is large enough (think of minimax search in chess) but for these decoding problems the state space is tiny and you don't even need to speculate over all possible states (e.g. you're not going to decode all possible combinations of 4 instructions per cycle, only certain prefixes, etc).

[1] The Hillis-Steele paper on data-parallel algorithms from 1986 describes this algorithm for parallel lexing.

Of course a fixed-length ISA has an inherent advantage for parallel decoding efficiency. The question is whether that is a decisive advantage in M1's impressive performance. After Intel refined their decoder and uop cache, you virtually never see that part of the frontend as a bottleneck when doing microarchitectural profiling. That's been true since Sandy Bridge but even more so since Skylake.

All the legacy junk in x86 is obviously a pain for Intel to support. Any blank-slate ISA is going to have an advantage there.

It's true that ARM64 has a load-store architecture and fixed-length instructions (the latter depending on the former for encoding space efficiency). Other than that, the instruction set design is very far from minimalist textbook-style RISC ISAs like RISC-V. It has both flag-based branches and fused compare-to-zero-and-branch instructions. It has very complex immediate encodings. It has instructions for loading/storing register pairs. It has pre-increment/post-increment addressing modes of the kind that were hallmarks of CISCs like M68K and VAX.

It seems unwise to draw far-reaching conclusions about RISC-V or even ARM64's intrinsic merits versus Apple's CPU designers when there are so many variables. The frontend decoder hasn't been a frequent bottleneck in Intel cores for a long time and they could scale it up more aggressively if they wanted.

Apple's engineers did a great job. That seems to be the conclusion we can draw based on currently available evidence.

The term 'persistent data structure' goes back to papers by Tarjan, et al in the 80s but the path copying technique is much older. My favorite technique from one of those papers, the in-place v2 trick, is an alternative to path copying that achieves amortized O(1) space per update as opposed to O(depth) space per update for path copying; this only gives you partial persistence (linear history like an MVCC database system, not branching history like a purely functional data structure or Git) but often that's all you need. (There's also an extension of the trick to full persistence but it's not very practical.)

> I’m not a Clojure expert, but I believe you could trace a direct line to Clojure’s core immutable data structures from Okasaki’s doctoral thesis.

I believe the direct inspiration for Clojure's persistent vectors and maps are Bagwell's papers on HAMTs, which weren't so much a new data structure as an example of data structure engineering. Okasaki's thesis has several contributions but its main theme is how you can apply amortization in the purely functional setting if you have laziness or memoization, which is in a very different direction.

It's an important theoretical result, but the optimized library almost everyone uses (libdivsufsort) is based on an O(n log n) time algorithm; I haven't seen any competitive implementations of the linear-time algorithms.

While the difference is noticeable in that 30 vs 60 Hz example, high-contrast foreground/background scrolling is an even starker example: https://www.testufo.com/framerates-text. Just be warned high contrast examples like that can have confounding factors on some displays due to ghosting.

Log-depth circuits are a useful abstraction but the constraints of laying out circuits in physical space imposes a delay scaling limit of O(n^(1/2)) for planar circuits (with a bounded number of layers) and O(n^(1/3)) for 3D circuits. The problem should be familiar to anyone who's drawn a binary tree on paper.

I believe all his notable scientific works were in English. You can find some minor articles in Danish, e.g. this announcement of the RC4000 in an engineering periodical: https://datamuseum.dk/w/images/d/da/Rc4000d.pdf

Indeed, the difference is that the lexer offers guarantees about the synthetic INDENT/DEDENT tokens. From an error sync perspective, the benefit is that the programmer (redundantly) re-asserts the block level every line by the amount of indentation. As a small addendum on Python's suspension of indentation tracking when nesting > 0, when I designed the syntax for indentation-based block structure in another language, I required such nested code to always have indentation beyond the current block's level even though no INDENT/DEDENT/NEWLINE tokens are emitted in this state. So this was legal:

    x = (1 +
        2)

    x = (1 +
            2)

    x = (1 +
      2)

    x = (1 +
     2)

But this was illegal:

    x = (1 +
    2)

The legal variants are all identical to

    x = (1 + 2)

from the parser's perspective. Adding this restriction (which is already the idiomatic way to indent nested multi-line expressions) means that you can reliably sync to block levels even when recovering from an error in a nested state. If your lexer already strips leading indentation from multi-line string literals you could add a similar constraint for them.

The moral of a lot of these tricks is that by turning idioms and conventions into language enforced constraints you can detect programmer errors more reliably and you can do a better job of error recovery. That said, even in a curly brace language like C# you could still use the indentation structure as a heuristic guide for error recovery--it's just going to be less reliable.

With your IDE example you need the full parser and type checker to be "tolerant". For recursive-descent parsing, there isn't much to say about theory. You try to pick reliable synchronization points and prevent cascading errors. Here's the classic example:

In a statement-oriented language like C#, synchronizing to the next statement upon finding an error by scanning for a semicolon token is a good place to start. (Statements like 'if' with nested statement blocks as arguments have their own sync logic.) Aside from having reliable sync points, statements (unlike expressions) don't have a type that you need to propagate, so you don't usually have to worry about cascading errors in the type checker from skipping a faulty statement. That said, if you skip a faulty statement that was the sole reference to a local variable, that might get flagged as an 'unreferenced variable' warning. It's often a good idea to disable sensitive warnings (and some errors) for the rest of the function as soon as an error is found.

Probably the most important sync point is at the level of symbol declarations. Even if a function's body is totally botched up, as long as you could successfully resolve the function's signature (name, parameter types and return type) you don't get cascading errors from other functions that reference that function. Resyncing to top-level declarations is so important that if you're designing the syntax it's worth having a dedicated declaration keyword (especially for functions) which is only valid at top level. That way you have a reliable sync point even if everything else is out of wack (unbalanced braces, etc). Something like Go's 'func' keyword is close enough: it can appear in function literals and function types as 'func' followed by '(' but 'func' followed by a name is only valid in top-level declarations.

Fine-grained error recovery for expressions is the biggest problem from both a parsing and type checking perspective. There aren't any reliable expression sync points in a C#-like language and you need to fabricate best-effort types for the faulty expressions (with an 'error' type as a fallback) and make sure that the various operators for combining expressions have heuristics so you don't get spurious cascading errors. It generally involves numerous special cases to good results. If you have a choice in the matter, don't worry about expression error recovery: report the error, sync to the next statement and go for the lower-hanging fruit instead. In my experience it isn't worth it in a statement-oriented language.

If you want to eliminate as many spurious warnings/errors like this as possible during error recovery, you do end up adding many special cases over time. But it's an incremental process and you can get good results immediately with basic recovery techniques.

Various comments:

On the lexer side of things, if you get to design the syntax it helps to avoid multi-line lexemes in the common cases. That's why I cringed a little when I learned that Rust's "..." string literals are multi-line. It's fine to have multi-line lexemes like /* ... */ comments in C and """...""" string literals in Python but make the default choices be single-line lexemes like "..." and // ... so you can sync to the newline.

A benefit of a syntax with indentation-defined block structure is that you don't need to rely on balanced grouping tokens like { ... }, so it's easy and reliable to sync to the outer block levels. (In Python there's a caveat that the lexer suspends indentation tracking when the ([{ nesting level is nonzero, but it's still a robust heuristic even when recovering from an error in a nested state.) In particular, if you require top-level declarations to be at column 0 this avoids the need for dedicated keywords for reliable declaration resync. Then the only thing you have to worry about are unbalanced multi-line lexemes gobbling up chunks of your programs.

While I talked about error recovery, a lot of these syntactic properties help with fast symbol indexing. E.g. it's easy to write a fast symbol indexer when you can just sync to "\n<letter>" for top-level declarations and otherwise only need to worry about rare multi-line lexemes. This lets your outer scan loop avoid the byte-at-a-time bottleneck.

Neat, I didn't know about -fwhole-program as an alternative to -flto for single-file builds. It should help with compile times a little bit (though I normally only use LTO for release builds, rarely during development, so it's not a big deal either way). With MSVC I think you still have to use LTO (or LTCG as it's called there) to get this effect.

> The flip side of this technique is to be careful about blowing up the size of the final executable since everything gets included.

Yeah, the 1970s linker model is very silly like this. The good news is that link-time optimization will handle this for you nowadays without any special per-symbol mark-up. As an experiment, put an unused 'deadfunc' function definition in a file called ltotest.c and then compare

    gcc -O2 ltotest.c -o ltotest && (objdump -D ltotest | grep deadfunc)

and

    gcc -O2 -flto ltotest.c -o ltotest && (objdump -D ltotest | grep deadfunc)

> It’s more difficult to get right than one big single source file.

For all my personal projects, I use a single main.c file which #includes the topologically sorted .c files for each module, one file per module, preceded by a shared #include block for external library headers. If your module dependency graph is acyclic, you don't need any per-module headers; inside a module everything is sorted and you only need forward declarations for mutually recursive functions/types. The only real downside for me is that it breaks 'static' isolation. Even the slower C compilers like gcc, clang and msvc can build 50-100 kloc/sec on my aging laptop with code structured like this.

You get qualify of life benefits like fast, simple builds (one-liner scripts for building on each platform, no need for the compiler to chew through the same monstrous system headers for every .c file, fewer symbols for the linker to resolve) and less boilerplate you have to write (no redundant copies of declarations in headers, no redundant #include blocks at the top of every .c file). In case it's something you care about, structuring your code like this also makes it trivial to automatically amalgamate your entire project into an stb-style single-file header library for distribution purposes: it's already 'static' safe, you've already specified the topological order and you've already eliminated all the redundant boilerplate you wouldn't want in a single-file distribution, so it's mostly just a matter of writing a script that inlines the #include "foo.c" directives in the main.c file.

Leaving aside arguments about "what the drivers are", the kernel driver being discussed here generally doesn't have or need that kind of thing. The user-space drivers which talk to the kernel drivers are under the Mesa umbrella as part of Gallium for OpenGL and Direct3D support (e.g. https://github.com/mesa3d/mesa/tree/master/src/gallium/drive...) or as a standalone driver for Vulkan support (https://github.com/mesa3d/mesa/tree/master/src/amd/vulkan). That said, I haven't seen many app-specific hacks in the open source drivers, even in the user-space code.

If anyone wants to learn more about lower-level aspects of GPUs, the Vulkan driver code I linked is one of the best places to start. It directly implements the Vulkan API on one end and talks to the kernel drivers on the other end, so it's relatively easy to follow if you're a systems programmer with an API-level understanding of graphics. Just pick a Vulkan function of your choice and start tracing through the code, e.g. vkCmdDraw: https://github.com/mesa3d/mesa/blob/master/src/amd/vulkan/ra.... The Vulkan driver calls into some of the low-level radeonsi code I linked from the Gallium tree but it isn't a Gallium-based driver, so you don't have to deal with those extra layers of abstraction.

Yeah, I remember seeing your measurements at the time.

I did plots, but for most of the compilers I only measured at a handful of points in the parameter space since it took forever to run and I wanted to be able to regenerate the measurements in a reasonable amount of time if I changed the generator or parameters. I did dense multi-parameter measurements and model fitting for my own compiler; that's how it started, so the comparative data for other languages and compilers came later.

Delphi 2 was the version that introduced the 32-bit compiler and ran on Windows 95. My impression is that Embarcadero (who bought and own the rights to Delphi) still have customers with legacy Delphi applications who pay them for their newer backward-compatible Delphi product, so they're unlikely to release the older versions for free. It's also a bit of a hassle to run on modern PCs. With Turbo Pascal you can just use DOSBox but you need to run Delphi on an old Windows version. If it runs in Wine, that might be the easiest option.

For C compilers like gcc and clang it's comparing against -O0. Anyway, there are two issues with that long-term trend in compiler design from my perspective. The first is that the optimizing path is too slow and they don't offer an intermediate point on the Pareto frontier that reflects my trade-off preferences because too much of the slowness is architectural in origin. But the second and much worse problem is that the non-optimizing path is barely any faster. You can't make a fast non-optimizing or somewhat-optimizing compiler by taking the architecture of a heavyweight optimizing compiler and setting some internal flags and skipping a few passes. You need the fast compilation path to completely dictate the architecture from end to end, with the constraint of still supporting optimizing backends, and you need a development culture that treats the fast path's performance as inviolate and sacrosanct.