Re:Show HN: A weekend replication of STOKE, a stochastic sup...
by jcranmer on Monday July 22, 2019 @01:45PM
(#20500382)
I'm not the OP, but I have a little bit of experience with STOKE.
STOKE is a superoptimizer, which seeks to solve the problem of optimizing code essentially by means of mathematical optimization (finding the optimal point), in this case on a discrete, highly non-linear input space. These optimizers usually focus on peephole optimizations, which look at short sequences of instructions, because the problem is much less intractable.
The classic superoptimizers (say, http://theory.stanford.edu/~sbansal/pubs/asplos06.pdf) solved the problem by precomputing the best assembly variant for all short (~4 instruction) sequences, but that clearly doesn't scale. STOKE instead approaches the problem in a manner more similar to classic hill-climbing algorithms from machine learning: you randomly mutate the program to discover alternatives, accept the mutation under certain conditions, and do a random walk on these mutations to hopefully arrive at the best result. The result is sensitive to how you implement the details, but it does scale somewhat better (tens of instructions).
STOKE is a superoptimizer, which seeks to solve the problem of optimizing code essentially by means of mathematical optimization (finding the optimal point), in this case on a discrete, highly non-linear input space. These optimizers usually focus on peephole optimizations, which look at short sequences of instructions, because the problem is much less intractable.
The classic superoptimizers (say, http://theory.stanford.edu/~sbansal/pubs/asplos06.pdf) solved the problem by precomputing the best assembly variant for all short (~4 instruction) sequences, but that clearly doesn't scale. STOKE instead approaches the problem in a manner more similar to classic hill-climbing algorithms from machine learning: you randomly mutate the program to discover alternatives, accept the mutation under certain conditions, and do a random walk on these mutations to hopefully arrive at the best result. The result is sensitive to how you implement the details, but it does scale somewhat better (tens of instructions).