John Regehrregehr@mastodon.social
Oct 5, 2026, 10:46 PMI had the advanced compilers students read the Massalin superoptimizer paper for today, it's so fun
Replies
Funky BobFunkyBob@chaos.socialOct 5, 2026, 10:54 PM@regehr This reminds me of this gem of a site I stumbled across years ago:
Oct 5, 2026, 11:05 PM@regehr I'd heard of using program search to find computational kernels but I hadn't heard it called "superoptimization" before. kind of makes me want to try a trick I used to do basically genetic programming with bayesian optimization that might make this scale to larger programs. basically you assume that over fixed-length "snippets" the distribution of performance (eg change in runtime with the snippet added vs not) is zipfian and you to thompson sampling but you only store the top few percentile explicitly (in a heap) and you use a count-min sketch for the scores of all the other snippets. I got that to work for generating programs in a toy virtual machine (that's constructed so programs running in it can't crash) but in principle you could do the same thing with code for a real machine
- Oct 5, 2026, 11:36 PM
@regehr when I say thompson sampling I mean it's simulated annealing where you're using thompson sampling to generate the proposals
Garrett Wollmanwollman@mastodon.socialOct 6, 2026, 1:45 AM@regehr Before Synthesis, even!
- Garrett Wollmanwollman@mastodon.socialOct 6, 2026, 2:13 AM
@regehr (One of the first things I was suggested to read in my first real job was the Synthesis paper and it blew my mind. And of course I was on the same floor of NE43 as Kaashoek's group doing Exokernel, but I didn't end up working on anything like that. I guess stuff like eBPF JIT is the modern inheritor of both lines of research.)
geofflangdalegeofflangdale@mastodon.socialOct 6, 2026, 4:45 AM@regehr Beautiful stuff. I still think superoptimization is The Shit (non-pejorative). Very much a brutal wall of combinatorial explosions with modern architectures (trying to synthesize constants for GF2P8AFFINEQB and VPERMI2B will make you reconsider your life choices, as will all those irritating VNNI multiplies).
On a full "universe", 2 instructions is tough, 3 aspirational, 4 simply deranged.
synlogic4242synlogic4242@vivaldi.netOct 6, 2026, 5:18 AM@geofflangdale @regehr I'm writing a book on performance. I've added note to my research TODO to read that paper
- geofflangdalegeofflangdale@mastodon.socialOct 6, 2026, 7:43 AM
@synlogic4242 @regehr well worth doing. There are a number of papers worth reading in that space, some written by people on this thread.
- synlogic4242synlogic4242@vivaldi.netOct 6, 2026, 8:20 AM
@geofflangdale @regehr will do. I aim to write a book at similar quality/value level as Brendan Gregg's Sys Perf, while at same time merely complimenting it not repeating or replacing it. big challenge, but exciting