Repr Types: One Abstraction to Rule Them All
<|reference_start|>Repr Types: One Abstraction to Rule Them All: The choice of how to represent an abstract type can have a major impact on the performance of a program, yet mainstream compilers cannot perform optimizations at such a high level. When dealing with optimizations of data type representations, an important feature is having extensible representation-flexible data types; the ability for a programmer to add new abstract types and operations, as well as concrete implementations of these, without modifying the compiler or a previously defined library. Many research projects support high-level optimizations through static analysis, instrumentation, or benchmarking, but they are all restricted in at least one aspect of extensibility.   This paper presents a new approach to representation-flexible data types without such restrictions and which still finds efficient optimizations. Our approach centers around a single built-in type $\texttt{repr}$ and function overloading with cost annotations for operation implementations. We evaluate our approach (i) by defining a universal collection type as a library, a single type for all conventional collections, and (ii) by designing and implementing a representation-flexible graph library. Programs using $\texttt{repr}$ types are typically faster than programs with idiomatic representation choices -- sometimes dramatically so -- as long as the compiler finds good implementations for all operations. Our compiler performs the analysis efficiently by finding optimized solutions quickly and by reusing previous results to avoid recomputations.<|reference_end|>
@article{palmkvist2024repr,
    title={Repr Types: One Abstraction to Rule Them All},
    author={Viktor Palmkvist, Anders {AA}gren Thun'e, Elias Castegren, David
  Broman},
    journal={arXiv preprint arXiv:2409.07950},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.07950},
    primaryClass={cs.PL cs.PF}
}