2024/09/12 by Viktor Palmkvist, Anders Ågren Thuné, Palmkvist, Viktor +5
Computer Science · #D.3.3 #D.4.8 #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Performance (cs.PF) #Programming Languages (cs.PL)
paper · pdf · doi:10.48550/arxiv.2409.07950
openalex publication_date 2024/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 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.