55 ms·
This is probably the most exciting thing I've read about compilers since Alexia Massalin's dissertation. gabrielsroka found this previous thread https://news.yc
by kragen 2y ago
This is probably the most exciting thing I've read about compilers since Alexia Massalin's dissertation. gabrielsroka found this previous thread https://news.ycombinator.com/item?id=35294111 https://news.ycombinator.com/item?id=35294111 with discussion with the author and a lot of related reading.
The title is an amusing crash blossom; it's about a generator of fast 6502 code, rather than a fast generator of 6502 code or one of the other four possibilities.
He says it generates better code than anything he's seen, and on reading the writeup, it's easy to see why:
> The ordered basic blocks are then processed from beginning to end, generating multiple assembly code combinations per operation. The list of combinations will grow at an exponential rate, but most can be pruned using ideas from dynamic programming and branch-and-bound. (...) simulated annealing (...) solving a partitioned boolean quadratic problem (PBQP).
It's tempting to assume that all this would have been infeasible for financial reasons when the 6502 was in common use, and maybe it is a little memory-hungry, but I think the bigger issue is that this is the kind of work you'd normally expect to see in a doctoral dissertation in operations research, applied mathematics, or GOFAI; there just weren't that many people out there who such an approach would occur to.
Now that it's out there, though, it seems like you could apply the same techniques to code generation for more mainstream hardware. (Some of the techniques like the tree-search register allocation would probably require adjustment.) Maybe it wouldn't provide the same benefits because generating optimal code is so easy now, I don't know. Has anyone tried?
- HarHarVeryFunny 2y agoRight, back in the day the main challenge was just to do what you wanted to do within memory and performance constraints, especially when trying to run a compiler on the target system as opposed to cross-compiling. This kind of super-sophisticated code generation, making the compiler itself larger and more memory hungry, just wasn't an option. This is a super hard-core hobby project! The 6502 is a great CPU, at least if you are hand-writing assembler for it, but a poor target for high level languages and difficult to generate high quality code for due to the extremely limited number of registers, quirky addressing modes, and lack of regularity. It's great to see the 6502 getting some love, even if it's 40 years too late to be very useful!
- twic 2y agoWasn't most performance-sensitive 6502 code back in the day handwritten in assembly? How does the performance of this compiler compare to that? Not to detract from this work - it's really cool and interesting! But i wonder if it would have been relevant at the time.
- dzdt 2y agoEssentially all commercial programs released for the 6502 were written in assembly language. Modern compiled languages like this hope to get close to the speed of hand-optimized assembly language while making the code much quicker and easier to write and modify. At the time systems like NES and C64 were popular, this would absolutely have been relevant. The time schedule for delivery of games was often extremely tight, and anything that would have let developers accomplish more in less time (with fairly minor compromises on execution speed) would have seen strong usage.
- lmm 2y agoI've done this kind of thing for a toy VLIW processor. In some sense it's the most obvious, naive way to write an optimising compiler: just generate all the possible combinations and then pick the fastest. I kind of assumed it wouldn't scale up to full size programs of the kind people write these days, but who knows.
- kragen 2y agoWell, it's not just doing exhaustive search. I don't think exhaustive search would get you far.
- lmm 2y agoFurther than you might think, but yeah then you use heuristics and various ways to prune the tree. But conceptually you're searching through the space, rather than optimising a single piece of code - I found it a useful way to flip my perception anyway.