Beating the Compiler
mattkeeter.com
mattkeeter.com
1 - The compiler has more "fingers" than a human does. Back when I wrote programs in assembly I would use printout to keep track of what I was doing and for debugging, and so would often put a finger on the paper to mark where a jump was and then go to the destination to see if it matched up, etc. This process isn't at all scalable, so the compiler is inevitably going to do better than I ever could on anything more than something trivial.
2 - I know more about the program constraints than I could ever express (much less be bothered expressing) in a HLL. "All the values will be less than 16" or "I can use this memory location for something else after I've read from it" or who knows what. So sometimes I can chop stuff out or even rewrite the compiler output locally to speed it up.
Also I can only do this for a few architectures...and with modern x86 there are so many variants with all sorts of microoptimization affordances that I can rarely beat the compiler (this is a corollary of lemma 1)
I think a slower, search based compiler could have a lot of potential for the hottest parts you're willing to spend exorbitant time on a search.
This is false. Any compiler that does register allocation and instruction scheduling (all of them) is searching for an optimal (or just good enough) solution to an optimization problem.
In general, searching any significant space is very slow, applying heuristics is much quicker.
For example, here is a pass that reorders WebAssembly globals in the Binaryen optimizer:
https://github.com/WebAssembly/binaryen/blob/main/src/passes...
We have a simple criteria for the quality of a solution - how big the binary size is with an order - but the space of possible orders is huge (every permutation that keeps every global after its dependencies). What we do is a targeted search of that space using some heuristics using parameters that work well enough and aren't too slow in practice.
There is and it's quite simple: if your heuristic reduces the size of your search space faster than it takes to perform the search (ie try solutions) then you have a real algo on your hands. Otherwise you're just searching. This is basically the border between P and NP and it's just that in compilers most of the problems are NP hard so none of the heuristics are really that good.
> then you have a real algo on your hands
To me an algorithm is closed, while a heuristic (aka rule of thumb) is just a fast way to probably get a better solution / subset of the solution space at the cost of possibly missing the optimal result or even ending up in a pessimal corner case.
With an NP complete problem you'd rather have some solution rather than use up your lifetime searching for the best.
i dunno what "closed" means here? converges? lots of things with heuristics converge...
most things people think of as algorithms are just heuristics codified. take for example unit propagation in DPLL (fairly modern SAT approach); quoting wiki[1]
> In practice, this often leads to deterministic cascades of units, thus avoiding a large part of the naive search space.
that *in practice* there means there's no guarantee because ofc not - otherwise they would've proven something about NP. but they didn't, they just came up with a way to search that's sometimes/often not bad. a lot of people call this an algorithm ("... is a refinement of the earlier Davis–Putnam algorithm") because it fits the dictionary definiton (a repeatable process) but i do not because it's a repeatable process that isn't proven to produce anything (ie faster than brute force). and the intuition i'm proposing for why it doesn't is because it doesn't actually shrink the search space fast enough.
note, my definitions/intuitions don't translate/have the same force elsewhere (especially in continuous/differentiable spaces) but they're a pretty standard/obvious perspective in combinatorial optimization (np-hard/np-complete problems).
[1] https://en.wikipedia.org/wiki/DPLL_algorithm#The_algorithm
In the context of compilers there are many. Look at this block diagram for Chaitin's register allocator:
https://en.wikipedia.org/wiki/Register_allocation#Principle_...
That's a search because it tries an allocation, possibly incurs a spill, tries again.
It's like designing a house. If you want the master closet bigger, the master bath has to shrink. Everything is a tradeoff.
Combinatorial Register Allocation and Instruction Scheduling
Doesn't make any sense. The "type constraints" on assembly operands (registers and numbers) is the ISA and thus those constraints are combinatorial not logical
that's not a type system, that's an ILP. and we already have that in many compilers (bindings to ILP solvers).
> Maybe the ISA can now do something clever to further optimize my program.
this is a malformed sentence - the ISA is fixed and isn't making any gametime decisions about your code (modulo branch prediction/cache-fretching). it's all in the compiler and like i said we already have this in many many compilers and it's surfaced in various ways (eg trip count on loops).
https://www.cs.cmu.edu/~rwh/papers/dtal/OGI-CSE-99-008.pdf
It's not perfect, but dependently typed assembly languages isn't something I just made up. Maybe there's a mismatch between the terms we're using?
Modern branch predictors can actually predict indirect branches with multiple destinations, because they hash recent branch history into the prediction. The exact same indirect branch will end up with multiple BTB entries, based on previous control flow.
I was curious where the threaded code speedup is actually coming from. It's possible much of the speedup is coming from eliminating the extra branch back to the dispatch loop. Or maybe the history tracking in the M1's branch predictor doesn't work well for this type of control flow.
So I checked out this code and modified the next macro, adding a dummy branch over a nop, to roughly isolate this factor.
On my M1, the extra unconditional branch benchmarks at 1.08 sec for fib, and 1.19 sec for Mandelbrot (all other times were the same).
Looks like the speedup is a mixture of the two. Eliminating that extra branch is responsible for about 20-30% of the speedup, and improving prediction on indirect branches is responsible for the other 70-80%
The branch predictor is really accurate with a common dispatcher, it predicts those indirect branches correctly 99.25% of the time. Switching to threaded jumps improves this slightly to 99.75%, but not because the indirect branches are at different addresses. This improvement in accuracy is entirely because of the unconditional branch back the dispatcher that was removed as a side effect. With that gone, the branch predictor can now track branch histories that are about twice as many VM instructions long.
My modified version with a dummy branch in the threaded dispatcher negates this longer history and (according to the performance counters) results in the exact same 99.25% correctly predicted branches as the common dispatcher, yet it's still significantly faster, only 20% slower than threaded jumps.
-------------------
Why are threaded jumps faster on the M1, if it's not increasing branch prediction accuracy?
Well, the M1 essentially has two branch predictors[1]. The faster one can return a prediction in one cycle, but it's not checking branch history it all, and it's almost always wrong for these unpredictable indirect branches. The slower predictor does take branch history into account, but takes three cycles to produce the correct result.
Which means there is a short pipeline stall when the second prediction comes in. This stall doesn't show up as a BRANCH_INDIR_MISPRED_NONSPEC, because the branch was correctly predicted. Instead, it seems to show up in the FETCH_RESTART counter.
So while threaded jumps doesn't improve overall branch prediction accuracy (except because of the longer history), it does slightly improve the accuracy of the faster branch predictor. With a common dispatcher, it predicts wrong almost 100% of the time, but with threaded code, the accuracy improves to 40%.
[1] Or at least that's a decent mental model. I suspect it's actually be a single ITTAGE branch predictor that returns the zero-history result in 1 cycle
This blog post [1] from CloudFlare has a few interesting hints about the M1's branch predictor. First, (in their testing) to get the one cycle predictions at all, your hot code needs to fit in just 4KB.
Second, if the brach target isn't in L1 cache, you don't get a prediction at all. The branch target prediction probably points directly at the cache line + way, so even if a cache line moves to a different way, the prediction will still fail.
Which means, I'm not sure this optimisation is worth while. It works for fibonacci and mandelbrot because they have reasonably tight loops, and adding a dispatcher to each instruction handler doesn't push the hot code over the limit. But when interpreting more generic code, you might be better off trying to minimise cache usage.
> Making all of the opcode implementations the same size (padding to the size of the largest opcode implementation with .balign 256), then removing the jump table entirely. This was also slower, also probably because of cache friendliness: the opcode implementations go from 16.6 KiB total to 64 KiB.
Probably normalizing the opcode implementations length to the maximum length is not optimal. A possible experiment would be to normalize to the modal length. I would expect most opcodes to be arithmetic or logic operations and to share the same implementation length. The (hopefully few) more complex ones would need a trampoline.
Is this a crazy idea?
Fun maybe/maybe not, but define "performant". I might drop into assembly for 1 or 2 orders of magnitude faster for a non-toy project. Even then, what are my requirements? What is the bus factor of LuaJIT again? Try getting support for s390x, or your patch accepted.
Look at the speedup of Lua v. LuaJIT (C language VM v. C/Lua VM with JIT code gen):
https://web.archive.org/web/20180430211146/https://luajit.or...
And by the way, probably the absolute worst things the compiler does are the "smart" things. I write my code knowing what the emit should look like, and the compiler sometimes thinks it has a better idea than how I wrote the code and makes the emit a lot more convoluted and slower than it would be if it just did what I said. Actually, I do know the machine decently well, thank you.
Saying "centuries of engineering" is misleading. A lot of those centuries are people arguing about theoretical optimizations of dubious value while we still haven't even finished on the most basic optimizations that are obviously beneficial.
The second paragraph making it sound all mysterious that compilers are even more awful at interpreters than normal code really speaks to a complete lack of exposure to the subject matter. This stuff is only esoteric because you couldn't be bothered to look at godbolt.org. Which is totally fine by the way, just don't go telling me how high quality compilers are if you've never even looked.
That would be like me telling web developers that Dreamweaver produces phenomenal HTML and CSS, without ever looking at what it emits.
Sorry for the rant but it just bothers me how much praise is heaped upon compilers like they are some kind of gift from God, forged by monks, wizards, and unrivaled geniuses. A compiler is just a tool. There is no magic.
When people call themselves engineers, without placing their feets on an engineering school, with compiler development degrees, rather a six weeks bootcamp, their compilers feel like a sufficient advanced technology.
The theoritical stuff, history and evolution of programming languages, compiler and language design, the actuall toy language implementation all the way to native code.
30 years ago, maybe the quality of teaching went down, I guess.
No problem here. I deleted a rant turning into a screed about blog articles superimposing "The Book of Dragon" and "The Dragon Book", but after some consideration found this link:
https://en.wikipedia.org/wiki/File:Graham%27s_Hierarchy_of_D...
With respect to "refuting the central point", if in the OP it is "Performance engineering should be about knowledge and science, not superstition and myth. (Godbolt not Godwin?)", then I agree. See:
https://ocw.mit.edu/courses/6-172-performance-engineering-of...
[I think Graham's hierarchy of disagreement ought to be used to color down votes, especially here.]
I see you already tried what I thought of, which is getting rid of the jump table and making each instruction handler the same size. Do you think that could still work if you limited each instruction handler to 64 or 32 bytes instead of 256, and then for longer handlers jumped to a larger body of code somewhere else?
Instead of using unsafe Rust to optimize the interpreter loop, I would prefer to write a transpiler that compiles the source UXN binaries to local CPU binaries, which would not require making code unsafe/less readable and would permit further speed enhancements by getting rid of an interpreter loop altogether.
There are Uxn instructions which write to RAM; normally, this is used for storing data, but nothing prevents programs from editing their own code as they're running.
On some platforms writing to memory mapped in with PROT_EXEC will trigger a page fault and the process will be killed. In other words, self modifying executables are effectively forbidden by design (the workaround is to unmap the memory, map it as PROT_WRITE, modify, unmap, map it in as PROT_EXEC, and resume execution - which is what JITs do on MacOS, for example).
Another idea would be to sort the opcodes by size (32-byte, 64-byte, 128-byte, 256-byte - or perhaps +1 to avoid the set-associativity problem below) rather than simply indexing.
> This was also slower, also probably because of cache friendliness: the opcode implementations go from 16.6 KiB total to 64 KiB.
This is probably cache-unfriendly due to alignment too (associativity limits mean more conflict misses for highly-aligned memory), not just size. Most documentation only talks about this problem regarding the data cache though ...
0x100002ec0: b 0x100002d1c ; jump back to the dispatch loop
Currently that's hard to achieve in Rust. There's an experiment in progress to see if guaranteed tail calls can be added to the language
The 518ms profile result for the branch-table load is very peculiar. To my eyes, it suggests that the branch-table load is is incurring cache misses at a furious rate. But I can't honestly think of why that would be. On a Pi-4 everything should fit in L2 comfortably. Are you using a low-performance ARM processor like an A53?
Also, it has jump-to-register immediately after the instruction that sets that register. Wouldn't it be faster if it went like:
get jmp address
execute VM opcode
jmp to next instruction
The M1's frontend at least 24 instruction past the unconditional branch before the early possible moment it can even see it.
So the branch predictor isn't just responsible for predicting which way conditional branches go. It must remember where all branches are, and their target so that the front end can follow them with zero cycle delay. This means all branches, including call and return instructions too.
Which means that unconditional immediate branches cost about the same as a correctly predicted conditional branch.
But that's not actually why the fetch has been moved.
The other thing to note is that the frontend and backend of a modern CPU are completely disconnected. The frontend doesn't even try to get the correct address of an indirect jump from the backend. It always uses the branch predictor to predict the indirect branch.
And by inlining, each VM instruction has its own indirect jump, which means it gets different slot in the branch predictor allowing for better predictions.
At least that's the theory behind threaded code. I'm unsure how much of this speedup is coming from eliminating the extra unconditional immediate branch and how much is from better prediction of indirect branches.
I just assumed the M1 branch predictor would also be in the same class, but I guess not. In another comment (https://news.ycombinator.com/item?id=40952404), I did some tests to confirm that it was actually the threaded jumps responsible for the speedup.
I'm tempted to dig deeper, see what the M1's branch predator can and can't do.
Turns out that M1 can track the history of indirect branches just fine, but it takes 3 cycles for a correct prediction. With threaded jumps, the M1 gets a slightly higher hit rate for the initial 1 cycle prediction.
Unfortunately, it was hard to read with the monokai.css theme because comments were nearly invisible, and a lot of your information was in comments. Changing the color from #75715e to #95917e did the trick. I guess Monokai is for programmers who never read comments.
&mut h as *mut _ as *mut _
&mut DeviceHandle -> *mut DeviceHandle -> *mut c_void
No.
Have you seen the safer-ffi crate? Then you won't have to commit the deadly sin of writing unsafe Rust
It looks to me like that crate is supposed to help with exposing rust functions to C safely, not calling foreign functions in foreign code safely. Am I missing something?