Fast synthesis of fast collections
| Autor: | Calvin Loncaric, Emina Torlak, Michael D. Ernst |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Correctness
Theoretical computer science Computer science 020207 software engineering 02 engineering and technology Data structure Computer Graphics and Computer-Aided Design Range (mathematics) Computer engineering 020204 information systems 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Implementation Software |
| Zdroj: | PLDI |
| ISSN: | 1558-1160 0362-1340 |
| DOI: | 10.1145/2980983.2908122 |
| Popis: | Many applications require specialized data structures not found in the standard libraries, but implementing new data structures by hand is tedious and error-prone. This paper presents a novel approach for synthesizing efficient implementations of complex collection data structures from high-level specifications that describe the desired retrieval operations. Our approach handles a wider range of data structures than previous work, including structures that maintain an order among their elements or have complex retrieval methods. We have prototyped our approach in a data structure synthesizer called Cozy. Four large, real-world case studies compare structures generated by Cozy against handwritten implementations in terms of correctness and performance. Structures synthesized by Cozy match the performance of handwritten data structures while avoiding human error. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|