I'm following Nora Sandler's book, writing the code in Rust. I'm aiming for functionally working, then will do a pass on performance.
Chapter 5: bitwise compound assignment Chapter 8: switch, case, default statements
I got nerdsniped after chapter 15 to do some perf work. I had Claude write a python script that generates very large files so I could see the movement. Benching on a file with 40k functions, I got some nice wins
Using /usr/bin/time -l:
| Stage | Real | User | Sys | Instructions | Cycles | Peak Memory |
|---|---|---|---|---|---|---|
| Baseline (string-keyed symbol tables, O(n²) scope-clone resolver) | 206.62s | 177.73s | 15.85s | 2.138T | 588.9B | 714.3MB |
+ String interning (Symbol-keyed, clone still O(n²)) |
13.58s | 13.22s | 0.25s | 91.18B | 41.22B | 445.3MB |
+ Scope-stack undo-log + FxHash for Symbol keys |
1.04s | 0.84s | 0.15s | 9.17B | 2.94B | 430.5MB |
Net: ~199x faster wall-clock, ~233x fewer instructions retired, ~200x fewer cycles, ~1.7x less peak memory.
Commit: https://github.com/nt591/c-compiler-rust/commit/558d8ad31f5fd0269c5fa9360730d38d8d42bec5
A very boring, hand-rolled string interner that copies strings into a Vec for every unique string. No sharing, e.g. swimmer and swimmers are separately allocated. We do the very normal thing of limiting to u32, having a transparent wrapper Symbol around it and do the following:
For a new string, we grab the offset (where we start writing) and the length of the input, then write it to the bytes buffer. We store that (offset, len) combination in a flat vector, and keep the index of that as Symbol. We then replace all references to the raw string with this symbol. The AST and compiler pipeline now carry a u32 in place, so we can copy it cheaply vs cloning. Lookups are as simple as
(offset, len) = symbol_list[symbol.0]
raw string = bytes[offset..offset+len]
Simple enough. That's the big win here that drags down the wall time from ~200 seconds to 13.5 seconds. Ends up also 23.4x fewer instructions (>2 trillion to 91 billion) and 14.3x fewer cycles. Reduction in IPC, but probably due to more hashmap probing on every lookup. Didn't spend too much time on that, I just learned how sample on MacOS works tbh.
https://github.com/nt591/c-compiler-rust/commit/2227a8934a9a6d5c27cc2235109a30ee3a06b228
I've seen something like this with Hack's emitter for locals. It just maintains scope by tracking how many locals were on the stack at the time, see source. I also ran into something similar during my OpenAI technical interview, which I managed to stumble into correctly. The tl;dr is that we just keep a SINGLE hashmap of symbols to resolved identifiers, and when introducing a new scope rather than clone the whole thing (admittedly cheap now that strings are gone) we just track previous state in a flat array.
The tempting thing here is to have a vec-of-vecs, where the top vec is the undo log for the current scope but that causes a bit more locality pressure. Vecs are 3 pointers (size, capacity, data) and we'd need to go allocate a vec and THEN go chase it down to write to it. It's just easier to remember the scope in place in a flat vector, then play it backwards when we pop.
The scopeguard is for general ergonomics and correctness. I feel like the C++ way to do it is to hand back the scope guard directly (Folly does this), and Rust does the same for mutex guards. But for this it seemed nice to just hide it. I THINK the closure can get inlined here but I haven't benchmarked that.
Time: 13.58 ÷ 1.11 ≈ 12.23x faster (91.8% reduction) Instructions: 91,180,601,376 ÷ 10,038,824,038 ≈ 9.08x fewer (89.0% reduction) Cycles: 41,218,371,520 ÷ 3,298,200,176 ≈ 12.50x fewer (92.0% reduction)
Net improving cycles more than instructions also gave me better IPC.
Crazy what flat data structures can do for you.
Not even gonna copy the data here, it knocked off some time and samples from my benchmarks by moving from the default SipHash to FxHash. Before this change, sample showed that all my hashing was making up like 30-40% of my callstack which was crazy. After, it's fairly evenly distributed across the compiler pipeline.
Before this commit (using jj so no idea what Git'll call it). I carried a bit of bookkeeping around for the scopes. A resolver had (example)
struct Resolver {
// Stuff
scope_idx: u32,
change_log: Vec<(u32, Symbol, Option<ResolvedIdentifier>)
}
This required carrying, on every change log entry, plus a top level counter. Then for every resolved identifier, I need to carry a u32 so I can compare right to the changelog. I realized I can drop the u32 altogether from the vector of events if I just instead mark scopes as the index of the last edit in the changelog. This reduces me to something like
struct Resolver {
// Stuff
scopes: Vec<usize>,
change_log: Vec<(Symbol, Option<ResolvedIdentifier>)
}
This bumps my scope tracker from a u32 to 3 words for the vec, but reduces the entries in my changelog to just the two parts. Then my scope entry is just pushing the length of the changelog (effectively the index of the first entry of the NEW scope) onto the scopes stack, and we can use that to undo changes cheaply.
The idea: not all strings need to be interned. We can represent temps, labels, jumps, etc as placeholders and only create the string when we need them. Just place a placeholder in the vec so we have a symbol, then when we actually need it we write the bytes to the buffer and modify the placeholder to a real span. Lots of tmps don't need to be strings, just used for pseudo replacement, so this is free memory. Additionally, no box in the key of the hashmap since it's never a string we'll compare: it's not in the source text.
Vec preallocation is pretty straightforward here.
These two changes compared to the commit previous:
| Metric | Previous commit | This commit | Absolute change | Relative |
|---|---|---|---|---|
| Instructions | 9,158,638,398 | 7,846,692,003 | -1,311,946,395 | 1.17x fewer |
| Cycles | 3,048,993,229 | 2,439,402,519 | -609,590,710 | 1.25x fewer |