Stochastic superoptimization

By Eric Schkufza, Rahul Sharma, A. Aiken. 2012

383 citations recorded by the source corpus.

We formulate the loop-free binary superoptimization task as a stochastic search problem. The competing constraints of transformation correctness and performance improvement are encoded as terms in a cost function, and a Markov Chain Monte Carlo sampler is used to rapidly explore the space of all possible programs to find one that is an optimization of a given target program. Although our method sacrifices completeness, the scope of programs we are able to consider, and the resulting quality of the programs that we produce, far exceed those of existing superoptimizers. Beginning from binaries compiled by llvm -O0 for 64-bit x86, our prototype implementation, STOKE, is able to produce programs which either match or outperform the code produced by gcc -O3, icc -O3, and in some cases, expert handwritten assembly.

Subfields: Artificial Intelligence, Hardware and Architecture, Code Generation & Program Synthesis, Program Analysis & Verification

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

In Code Generation & Program Synthesis

In Program Analysis & Verification

Citations in the corpus

SPoC: Search-based Pseudocode to Code (2019, background): “For other problems, brute force enumeration of programs (with some optimization) works surprisingly well [26, 3], but when the search space is too large for enumeration, randomized search guided by a cost function can be effective [30].”
CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis (2022, methodology): “A large body of prior research attempted to address (1) by exploring methods like stochastic search techniques (Parisotto et al., 2017; Schkufza et al., 2013) and deductive top-down search (Gulwani, 2011; Polozov & Gulwani, 2015).”
Neuro-Symbolic Program Synthesis (2016, methodology): “…et al., 2005), Excel macros for data manipulation (Gulwani, 2011; Gulwani et al., 2012), superoptimization by ﬁnding smaller equivalent loop bodies (Schkufza et al., 2013), protocol synthesis from scenarios (Udupa et al., 2013), synthesis of loop-free programs (Gulwani et al., 2011), and…”
TerpreT: A Probabilistic Programming Language for Program Induction (2016, neutral): “08; Reynolds et al., 2015), smart enumerative algorithms with pruning (Udupa et al., 2013), version-space algebra based search algorithms (Gulwani et al., 2012; Gulwani, 2011), and stochastic search (Schkufza et al., 2013). There has also been some recent work on learning from inputs in addition to ”
Syntax-guided synthesis (2013, methodology): “[11] in three ways: (1) we do not attempt to optimize the size of the expression while the super-optimizer does so; (2) we synthesize expression graphs rather than straight-line assembly code, and (3) since we do not know the expression size n, we run concurrent searches for different values of n, w”
Program Synthesis (2017, background): “Second, novel approaches to program space enumeration such as stochastic techniques [105, 123] and deductive top-down search [43, 113] enabled synthesis applications in new domains that were difficult to formalize through theorems and rewrite rules.”
FlashMeta: a framework for inductive program synthesis (2015, methodology): “In particular, the participants of the SyGuS-COMP 2014 competition employed: SMT-based search [13], enumerative search [37], sketching [35], and stochastic search [31].”
Ansor : Generating High-Performance Tensor Programs for Deep Learning (2020, background): “Stock [44] is a super-optimizer based on random search.”
Guided differential testing of certificate validation in SSL/TLS implementations (2015, methodology): “…For MCMC sampling, mucert at ﬁrst transforms the ﬁtness function into a probability density function, by following a commonly used approach [42]: where β is a constant, Z a partition function that normalizes the distribution, and ⊥ a lower bound of coverage that can be achieved by a test…”
Neural Code Comprehension: A Learnable Representation of Code Semantics (2018, background): “In order to mechanize code comprehension, the research community typically employs reinforcement learning and stochastic compilation for super-optimization [13, 56]; or borrows concepts from Natural Language Processing (NLP) for human-authored code, relying on the following hypothesis: The naturalne”
Coverage-directed differential testing of JVM implementations (2016, background): “It provides a general solution to many intractable problems without exact algorithms [33].”
Mathematical discoveries from program search with large language models (2023, methodology): “86 used reinforcement learning to learn the sampling probabilities used within a hierarchical probabilistic model of simple program edits introduced by STOKE 87 .”
BUSTLE: Bottom-up program-Synthesis Through Learning-guided Exploration (2020, background): “, 2013), stochastic search (Schkufza et al., 2013), genetic programming (Koza, 1994), reducing the synthesis problem to logical satisfiability (Solar-Lezama et al.”
Neurosymbolic Program Synthesis (positive): “There is also a body of methods that use stochastic methods, for example, Metropolis-Hastings sampling [27] and Sequential Monte Carlo, to effectively sample desirable programs from a space defined by a DSL. Version space methods use a specialized data structure to represent exponentially sized…”
Post-compiler software optimization for reducing energy (2014, methodology): “The more recent MCMC project [51] leverages increased computing power and heuristic search to ﬁnd optimizations on the same scale of ˜10 instructions in the much larger x86 instruction set.”
Learning to Perform Local Rewriting for Combinatorial Optimization (2018, methodology): “Our approach is tested on multiple domains with extensive ablation studies, and could also be extended to other closely related tasks such as code optimization [41, 12], theorem proving [25, 30, 4, 24], text simplification [14, 37, 18], and classical combinatorial optimization problems beyond routin”
AlphaEvolve: A coding agent for scientific and algorithmic discovery (2025, positive): “The idea of code superoptimization goes back to the 1980s [69]; pre-LLM approaches to the problem included systematic enumeration [69], genetic search [20], Monte Carlo sampling [86], and deep reinforcement learning [68].”
Guided, stochastic model-based GUI testing of Android apps (2017, methodology): “For this reason, we set the target probability density function p (x ), by following a common method [25, 53], as”
Domain-specific Genetic Algorithm for Multi-tenant DNNAccelerator Scheduling (2021, methodology): “STOKE [92] and Tensor Comprehensions [113] use GA to search the space of DNN code optimization.”