Fast synthesis of fast collections

Download: PDF, slides (PDF), Cozy implementation.

“Fast synthesis of fast collections” by Calvin Loncaric, Emina Torlak, and Michael D. Ernst. In PLDI 2016: Proceedings of the ACM SIGPLAN 2016 Conference on Programming Language Design and Implementation, (Santa Barbara, CA, USA), June 2016, pp. 355-368.


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.

Download: PDF, slides (PDF), Cozy implementation.

BibTeX entry:

   author = {Calvin Loncaric and Emina Torlak and Michael D. Ernst},
   title = {Fast synthesis of fast collections},
   booktitle = {PLDI 2016: Proceedings of the {ACM} {SIGPLAN} 2016
	Conference on Programming Language Design and Implementation},
   pages = {355-368},
   address = {Santa Barbara, CA, USA},
   month = jun,
   year = {2016}

(This webpage was created with bibtex2web.)

Back to Michael Ernst's publications.