Staged Static Techniques to Efficiently Implement Array Copy Semantics in a MATLAB JIT Compiler

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