Vectorizer tool speeds up Python NumPy loops by rewriting them into fast array operations
Vectorizer: Vectorizing NumPy Programs with Shape-Guided Rewrite
Computation and LanguageSoftware Engineering
Summary
Programming with NumPy can be tricky when turning slow loops into faster array-based commands because it involves careful handling of shapes and data. The authors created a tool called Vectorizer that automatically rewrites explicit loops over arrays into efficient vectorized operations by analyzing the shape and flow of the data. Their approach works inside out and follows safe rewrite rules to keep the program correct and fast. They tested it on 150 real examples and made almost all faster by more than 70 times on average, with very little time needed to perform the rewriting.
NumPyvectorizationarray programmingbroadcastingloop rewritingshape analysissource-to-source transformationdataflow analysisPythonscientific computing
Authors
Jingqian Liu, Xiaoyu Liu, Yuepeng Wang
Abstract
NumPy is a widely used Python library for numerical scientific computing, known for its declarative APIs and its optimized implementations. However, writing efficient NumPy programs, which often entails using vectorized array operations instead of explicit Python loops, may not be straightforward. This can be difficult for programmers who are accustomed to imperative array traversal, especially when vectorized API invocations require careful reasoning about shapes, broadcasting, and advanced indexing. This paper presents a rewrite-based approach for vectorizing Numpy programs with explicit loops over array data. Our approach vectorizes loops from the inside out, using array shapes and dataflow analysis to guide a source-to-source transformation that replaces loop bodies with vectorized statements. Following a set of rewrite rules that are correct by construction, our approach is consistently fast. We have implemented the approach as a tool called Vectorizer and evaluated it on 150 benchmarks collected from prior work and Stack Overflow. The evaluation shows that Vectorizer vectorizes 142 of the 150 benchmarks directly and 2 more after minor changes to the original benchmarks, with only 0.53 seconds on average to rewrite each one. The resulting programs are, on average, 74.83x faster than the original loop-based implementations.