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 referencecounting 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 referencecounted approach does not work in a garbagecollected
system.
In this paper we present a staged static analysis approach that does
not require reference counts, thus enabling a garbagecollected 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
garbagecollected virtual machine for MATLAB. Our results demonstrate
that there are significant overheads for both existing referencecounted and
naive copyinsertion 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
GaussSeidel iteration 
9790800 
10000 
10000 
40000 
20000 
10000 
clos 
transitive closure of a directed graph 
2954 
0 
0 
2 
2 
0 
crni 
CrankNicholson solution to the onedimensional 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 
finitedifference solution to the wave equation 
12243000 
0 
0 
0 
0 
0 
mbrt 
mandelbrot set 
5929 
0 
0 
0 
0 
0 
nb1d 
Nbody problem coded using 1d arrays for the displacement vectors. 
55020 
0 
0 
10984 
10980 
0 
nb3d 
Nbody 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
