Storage Strategies for Collections in Dynamically Typed Languages

Dynamically typed language implementations often use more memory and execute slower than their statically typed cousins, in part because operations on collections of elements are unoptimised. This paper describes storage strategies, which dynamically optimise collections whose elements are instances of the same primitive type. We implement storage strategies in the PyPy virtual machine, giving a performance increase of 18 % on wide-ranging benchmarks of real Python programs. We show that storage strategies are simple to imple-ment, needing only 1500LoC in PyPy, and have applicability to a wide range of virtual machines. Categories and Subject Descriptors D.3.4 [Programming Languages]: Processors—run-time environments, code gen-eration, incremental compilers, interpreter