psykotic

10 ms·

31.
by psykotic 6y ago
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...
32.
by psykotic 6y ago
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
33.
by psykotic 6y ago
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
34.
by psykotic 6y ago
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
35.
by psykotic 6y ago
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.
36.
by psykotic 6y ago
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 onl
37.
by psykotic 6y ago
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 doe
38.
by psykotic 6y ago
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 th
39.
by psykotic 6y ago
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 s
40.
by psykotic 6y ago
"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 ver
41.
by psykotic 6y ago
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.
42.
by psykotic 6y ago
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
43.
by psykotic 6y ago
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
44.
by psykotic 6y ago
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" con
45.
by psykotic 6y ago
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 virtuall
46.
by psykotic 6y ago
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
47.
by psykotic 6y ago
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 co
48.
by psykotic 6y ago
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.
49.
by psykotic 6y ago
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 l
50.
by psykotic 6y ago
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 circu
51.
by psykotic 6y ago
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&#x
52.
by psykotic 6y ago
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 o
53.
by psykotic 6y ago
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 erro
54.
by psykotic 6y ago
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
55.
by psykotic 6y ago
> 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
56.
by psykotic 6y ago
> 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 #in
57.
by psykotic 6y ago
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 umbrel
58.
by psykotic 6y ago
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 measurem
59.
by psykotic 6y ago
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 newe
60.
by psykotic 6y ago
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 a

More ›