Adaptive restarts for stochastic synthesis
| Autor: | Oded Padon, Jason R. Koenig, Alex Aiken |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Series (mathematics)
Computer science Superoptimization 020207 software engineering 02 engineering and technology Naive algorithm Distribution (mathematics) 020204 information systems 0202 electrical engineering electronic engineering information engineering Code (cryptography) Benchmark (computing) Feature (machine learning) Algorithm Program synthesis |
| Zdroj: | PLDI |
| DOI: | 10.1145/3453483.3454071 |
| Popis: | We consider the problem of program synthesis from input-output examples via stochastic search. We identify a robust feature of stochastic synthesis: The search often progresses through a series of discrete plateaus. We observe that the distribution of synthesis times is often heavy-tailed and analyze how these distributions arise. Based on these insights, we present an algorithm that speeds up synthesis by an order of magnitude over the naive algorithm currently used in practice. Our experimental results are obtained in part using a new program synthesis benchmark for superoptimization distilled from widely used production code. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|