| Title | Fast synthesis of fast collections |
| Publication Type | Conference Paper |
| Year of Publication | 2016 |
| Authors | Loncaric C, Torlak E, Ernst MD |
| Conference Name | PLDI 2016: Proceedings of the ACM SIGPLAN 2016 Conference on Programming Language Design and Implementation |
| Pagination | 355-368 |
| Date or Month Published | June |
| Conference Location | Santa Barbara, CA, USA |
| Abstract | 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. |
| Downloads | https://github.com/CozySynthesizer/cozy Cozy implementation
|
| Citation Key | LoncaricTE2016 |
