Type-Based Gradual Typing Performance Optimization
Open Access
- 2 January 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (POPL) , 2667-2699
Abstract
Gradual typing has emerged as a popular design point in programming languages, attracting significant interests from both academia and industry. Programmers in gradually typed languages are free to utilize static and dynamic typing as needed. To make such languages sound, runtime checks mediate the boundary of typed and untyped code. Unfortunately, such checks can incur significant runtime overhead on programs that heavily mix static and dynamic typing. To combat this overhead without necessitating changes to the underlying implementations of languages, we present discriminative typing . Discriminative typing works by optimistically inferring types for functions and implementing an optimized version of the function based on this type. To preserve safety it also implements an un-optimized version of the function based purely on the provided annotations. With two versions of each function in hand, discriminative typing translates programs so that the optimized functions are called as frequently as possible while also preserving program behaviors. We have implemented discriminative typing in Reticulated Python and have evaluated its performance compared to guarded Reticulated Python. Our results show that discriminative typing improves the performance across 95% of tested programs, when compared to Reticulated, and achieves more than 4× speedup in more than 56% of these programs. We also compare its performance against a previous optimization approach and find that discriminative typing improved performance across 93% of tested programs, with 30% of these programs receiving speedups between 4 to 25 times. Finally, our evaluation shows that discriminative typing remarkably reduces the overhead of gradual typing on many mixed type configurations of programs. In addition, we have implemented discriminative typing in Grift and evaluated its performance. Our evaluation demonstrations that DT significantly improves performance of Grift.Keywords
Funding Information
- NSF (ccf-1750886)
This publication has 55 references indexed in Scilit:
- Blame and coercion: together again for the first time2015
- Programming Strategies for Contextual Runtime Specialization2015
- Monotonic References for Efficient Gradual Typing2015
- Extending Type Inference to Variational ProgramsACM Transactions on Programming Languages and Systems, 2014
- The Choice CalculusACM Transactions on Software Engineering and Methodology, 2011
- Space-efficient gradual typingHigher-Order and Symbolic Computation, 2010
- Well-Typed Programs Can’t Be Blamed2009
- Specialization tools and techniques for systematic optimization of system softwareACM Transactions on Computer Systems, 2001
- The Cartesian Product Algorithm2000
- C and tccACM Transactions on Programming Languages and Systems, 1999