9 ms·
Superoptimizer – A Look at the Smallest Program [pdf] (1987)
- rcgorton 6y agoIt is now Alexia Massalin
- mikequinlan 6y ago1987 and I would love to see the source code.
- taliesinb 6y agoBrute force search of the computational universe of simple programs for useful ones – that rings a bell, but I can’t think where I have seen that before!
- eslaught 6y agoSee also: Conditionally Correct Superoptimization https://theory.stanford.edu/~aiken/publications/papers/oopsla15a.pdf https://theory.stanford.edu/~aiken/publications/papers/oopsl... Stochastic Superoptimization https://theory.stanford.edu/~aiken/publications/papers/asplos13.pdf https://theory.stanford.edu/~aiken/publications/papers/asplo... Automatic Generation of Peephole Superoptimizers https://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf https://theory.stanford.edu/~aiken/publications/papers/asplo...
- read_if_gay_ 6y agohttps://github.com/google/souper https://github.com/google/souper
- jl6 6y agoAm I reading this right that this process optimizes for program length but not necessarily program performance?
- superjan 6y agoYes. I think that this paper’s contribution is not that it pretends to be the final answer, but that this technique is even feasible at all.
- DoofusOfDeath 6y ago(Apologies because I don't have time to read that paper right now, but...) Program length can be evaluated (more or less) without ambiguity, non-determinism, or the need for actual benchmarking. In contrast, program performance (in practice) is hard to accurately predict via model, and on a typical computer system is affected by a lot of hidden initial state and other random variables. So unless you're content to use a simplistic model to grade a program's performance, I would guess that searching over that space would require actual benchmarking, which could significantly slow the search process. (Although various techniques like ceasing evaluation after a program takes longer than the best-so-far might help.)
- jcranmer 6y agoIf you exclude branches, integer division, and memory instructions, it's easy to perfectly model your program's performance. Even for memory, if you assume it's all L1 cache hits, performance is again perfectly predictable--and if it's not all L1 cache hits, the optimization of the surrounding code basically doesn't matter (not on the level of superoptimization). The state-of-the-art for superoptimization would be Aiken's work (linked elsewhere in the comments). The hardest part here is building the formal specifications of every single instruction, but their group also showed that it's possible to automatically generate these from a small seed set by similar techniques.
- DoofusOfDeath 6y ago> If you exclude branches, integer division, and memory instructions, it's easy to perfectly model your program's performance. Assuming you're right about that, those seem to me like very big caveats. Also, wouldn't thermals-based clock throttling be a factor as well, assuming that we're talking about wall-clock performance instead of clock-cycles performance? I'd be surprised if their impact on program performance is easy to perfectly model.
- glangdale 6y agoThis is a cool paper. I'm building a SMT-based superoptimizer for SIMD sequences that is still pretty stupid (it can only handle "lanewise" SIMD i.e. some op on each lane, it can only do AVX2, it can only handle arbitrary graphs up to 4 instructions before it gets too slow). And yet... it concocted a good chunk of a PSHUFB based pattern matcher (effectively "shufti" from https://github.com/intel/hyperscan https://github.com/intel/hyperscan) that I invented in 2009. If I could push further on this and scale from 4 instructions handled in about 45 minutes (single core, though it scales well) up to 5 instructions (currently takes a month of single-core search time) to 6-7 instructions (I don't even know!), this system would be able to come up with the full version of shufti, a "quite commercially relevant" SIMD sequence that I invented in 2009. Not saying that sequence was the cleverest thing ever, but it seemed novel enough, and to have a machine just spew it out when given the black box description of what it's meant to achieve... it would be pretty cool. All I need is a few orders of magnitude worth of search optimizations. That's OK - when I started, my superoptimizer took a couple days to handle 4 instructions, so it might still happen.
- jcranmer 6y agoAs superoptimizer research papers go, this is pretty ancient and very far behind the state-of-the-art. The paper describing STOKE (https://theory.stanford.edu/~aiken/publications/papers/asplos13.pdf https://theory.stanford.edu/~aiken/publications/papers/asplo...) is what I would recommend as the starting point instead.
- glangdale 6y agoSorry, my original post was confusing. I did not meant to imply that I based my work on the Massalin paper, just that I liked it. As I said, my work is SMT-based and more closely related to Regehr's 'souper' or the one described in Gulwani's "Synthesis of Loop Free Programs" in PLDI '11 (I think). While STOKE is interesting, I have trouble understanding why they even call it a "superoptimizer". The point of appending "super-" to optimizer was to get away from the (strictly speaking incorrect) practice of referring to compiler improvements as "optimizations" (when they don't achieve optimal outcomes). STOKE is "stochastic", so it cannot realistically claim to always find optimal sequences. So it's just another "improver", or if you will, an "optimizer".
- deleted 6y ago[deleted]
- WalterBright 6y agoThis paper changed compiler code generators, the sequences it discovered were rapidly adopted. It's nice to see it again.
- jhoechtl 6y agoIn 1987 we had beautifully typeset papers. A craft which got apparently lost.
- nextaccountic 6y agoIn which ways this paper is better typeset than the typical LaTeX paper?
- WillFlux 6y ago“This method has been used by the author (along with another program that optimizes code emulating state machines) to write the C library function printf in only 500 bytes.” I wonder how big libc would have been if they applied Superoptimizer to all its functions.