Collection data structures in standard libraries of programming languages are designed to excel for the average case by carefully balancing memory footprint and runtime performance. These implicit design decisions and hard-coded trade-offs do constrain users from using an optimal variant for a given problem. Although a wide range of specialized collections is available for the Java Virtual Machine (JVM), they introduce yet another dependency and complicate user adoption by requiring specific Application Program Interfaces (APIs) incompatible with the standard library. A product line for collection data structures would relieve library designers from optimizing for the general case. Furthermore, a product line allows evolving the potentially large code base of a collection family efficiently. The challenge is to find a small core framework for collection data structures which covers all variations without exhaustively listing them, while supporting good performance at the same time. We claim that the concept of Array Mapped Tries (AMTs) embodies a high degree of commonality in the sub-domain of immutable collection data structures. AMTs are flexible enough to cover most of the variability, while minimizing code bloat in the generator and the generated code. We implemented a Data Structure Code Generator (DSCG) that emits immutable collections based on an AMT skeleton foundation. The generated data structures outperform competitive handoptimized implementations, and the generator still allows for customization towards specific workloads.

Additional Metadata
Keywords Code generation, Hash trie, Immutability, Performance, Persistent data structure, Software product line
Persistent URL dx.doi.org/10.1145/2993236.2993251
Conference ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences
Citation
Steindorfer, M.J, & Vinju, J.J. (2016). Towards a software product line of trie-based collections. In GPCE 2016 - Proceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences, co-located with SPLASH 2016 (pp. 168–172). doi:10.1145/2993236.2993251