Staged Static Techniques to Efficiently Implement Array Copy Semantics in a MATLAB JIT Compiler
Abstract
MATLAB has gained widespread acceptance among engineers and scientists.
Several aspects of the language such as dynamic loading and typing, safe
updates, and copy semantics for arrays contribute to its appeal, but at
the same time provide many challenges to the compiler and virtual
machine. One such problem, minimizing the number of copies and copy
checks for MATLAB programs has not received much attention. Existing
MATLAB systems rely on reference-counting schemes to create copies only
when a shared array representation is updated. This reduces array
copies, but increases the number of runtime checks. In addition, this
sort of reference-counted approach does not work in a garbage-collected
system.
In this paper we present a staged static analysis approach that does
not require reference counts, thus enabling a garbage-collected virtual
machine. Our approach eliminates both unneeded array copies and
does not require runtime checks. The first stage combines two
simple, yet fast, intraprocedural analyses to eliminate unnecessary
copies. The second stage is comprised of two analyses that
together determine whether a copy should be performed before an array is
updated: the first, necessary copy analysis, is a forward flow
analysis and determines the program points where array copies are required
while the second, copy placement analysis, is a backward analysis
that finds the optimal points to place copies, which also guarantee safe
array updates.
We have implemented our approach in the McVM JIT, which is part of a
garbage-collected virtual machine for MATLAB. Our results demonstrate
that there are significant overheads for both existing reference-counted and
naive copy-insertion approaches. We also show that our staged approach is
effective. In some cases the first stage is sufficient, but in many
cases the second stage is required. Overall, our approach required no
dynamic checks and successfully eliminated all unnecessary copies, for
our benchmark set.
Click here for the full technical report.
Benchmarks and the summary results of the copy analysis
|
|
# Copies |
|
# Array |
Lower Bound |
With Analyses |
| Benchmark |
Updates |
Aspect |
Octave |
Naive |
QC |
CA |
| adpt |
adaptive quadrature using Simpson's rule |
19624 |
0 |
0 |
12223 |
12223 |
0 |
| capr |
capacitance of a transmission line using finite difference and
Gauss-Seidel iteration |
9790800 |
10000 |
10000 |
40000 |
20000 |
10000 |
| clos |
transitive closure of a directed graph |
2954 |
0 |
0 |
2 |
2 |
0 |
| crni |
Crank-Nicholson solution to the one-dimensional heat equation |
21143907 |
4598 |
6898 |
11495 |
6897 |
4598 |
| dich |
Dirichlet solution to Laplace's equation |
6935292 |
0 |
0 |
0 |
0 |
0 |
| diff |
diffraction pattern calculator |
0 |
0 |
0 |
0 |
0 |
0 |
| fdtd |
3D FDTD of a hexahedral cavity with conducting walls |
803 |
0 |
0 |
5400 |
5400 |
0 |
| fft |
fast fourier transform |
44038144 |
1 |
1 |
2 |
2 |
1 |
| fiff |
finite-difference solution to the wave equation |
12243000 |
0 |
0 |
0 |
0 |
0 |
| mbrt |
mandelbrot set |
5929 |
0 |
0 |
0 |
0 |
0 |
| nb1d |
N-body problem coded using 1d arrays for the displacement vectors. |
55020 |
0 |
0 |
10984 |
10980 |
0 |
| nb3d |
N-body problem coded using 3d arrays for the displacement vectors. |
4878 |
0 |
0 |
5860 |
5858 |
0 |
| nfrc |
computes a newton fractal in the complex plane -2..2,-2i..2i |
12800 |
0 |
0 |
6400 |
6400 |
0 |
| trid |
Solve tridiagonal system of equations |
2998 |
2 |
2 |
5 |
2 |
2 |
|
Aspect for counting dynamic array updates and copies
|
