Concrete Type Inference for Code Optimization using Machine Learning with SMT Solving
Open Access
- 16 October 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 7 (OOPSLA2) , 773-800
Abstract
Despite the widespread popularity of dynamically typed languages such as Python, it is well known that they pose significant challenges to code optimization due to the lack of concrete type information. To overcome this limitation, many ahead-of-time optimizing compiler approaches for Python rely on programmers to provide optional type information as a prerequisite for extensive code optimization. Since few programmers provide this information, a large majority of Python applications are executed without the benefit of code optimization, thereby contributing collectively to a significant worldwide wastage of compute and energy resources. In this paper, we introduce a new approach to concrete type inference that is shown to be effective in enabling code optimization for dynamically typed languages, without requiring the programmer to provide any type information. We explore three kinds of type inference algorithms in our approach based on: 1) machine learning models including GPT-4, 2) constraint-based inference based on SMT solving, and 3) a combination of 1) and 2). Our approach then uses the output from type inference to generate multi-version code for a bounded number of concrete type options, while also including a catch-all untyped version for the case when no match is found. The typed versions are then amenable to code optimization. Experimental results show that the combined algorithm in 3) delivers far superior precision and performance than the separate algorithms for 1) and 2). The performance improvement due to type inference, in terms of geometric mean speedup across all benchmarks compared to standard Python, when using 3) is 26.4× with Numba as an AOT optimizing back-end and 62.2× with the Intrepydd optimizing compiler as a back-end. These vast performance improvements can have a significant impact on programmers’ productivity, while also reducing their applications’ use of compute and energy resources.Keywords
This publication has 23 references indexed in Scilit:
- SciPy 1.0: fundamental algorithms for scientific computing in PythonNature Methods, 2020
- NL2Type: Inferring JavaScript Function Types from Natural Language Information2019
- Deep learning type inference2018
- A Survey of Machine Learning for Big Code and NaturalnessACM Computing Surveys, 2018
- Probabilistic model for code with decision treesACM SIGPLAN Notices, 2016
- Neural Machine Translation of Rare Words with Subword Units2016
- Numba2015
- Z3: An Efficient SMT Solver2008
- Precise concrete type inference for object-oriented languages1994
- A theory of type polymorphism in programmingJournal of Computer and System Sciences, 1978