Optimizations for Dynamic Collections
By: Joannah Nanjekye, David Bremner, Aleksandar Micic
Abstract
Languages that support dynamically evolving collections present a range of challenges in modern virtual machines and require sophisticated optimizations to address efficiency gaps. Collections in such languages dynamically evolve in size as well as the types of the elements they contain, affecting performance and memory efficiency due to expensive operations required for resizing and supporting heterogeneous object types. This paper presents two collection optimizations to address these costs: (1) a novel memory layout, type-based stores, storing primitives of heterogeneous collections unwrapped in contiguous storage areas; and (2) an allocation context-aware collection presizing technique, a profile-guided optimization that uses feedback from allocation sites and infers the calling context from the stack height to determine an optimal collection size. The proposed type-based stores technique is implemented in PyPy, a Python implementation built using the RPython framework for meta-tracing-JIT-based virtual machines. Additionally, a language-independent version of type-based stores is implemented in RPython and evaluated for Topaz (a Ruby implementation) and Pycket (a Racket implementation). Evaluation results show an overall performance improvement of 11.4% for Python benchmarks, with Ruby and Racket applications seeing improvements of up to 5% and 14%, respectively. The offline version of the allocation context-aware presizing technique applied to PyPy achieves a performance improvement of 11% and memory savings of up to 16% on average for the best median strategy, though it introduces an overhead of up to 25% when accessing and applying the profiled data.
Keywords
Collections, Optimizations, Heterogeneity, Resizing, Dynamic Languages
Cite as:
Joannah Nanjekye, David Bremner, Aleksandar Micic, “Optimizations for Dynamic Collections”, Journal of Object Technology, Volume 24, no. 1 ( 2025), pp. 1-27, doi:10.5381/jot.2025.24.01.a1.
DOI | BiBTeX | Tweet this | Post to CiteULike | Share on LinkedIn