Elamur Research⌕
☰
home / papers / 2010 / Optimizing MATLAB through just-in-time specialization

Optimizing MATLAB through just-in-time specialization

Paper · 2010 · Maxime Chevalier-Boisvert, Laurie Hendren and Clark Verbrugge

Summary

Matlab is popular with scientists, but its dynamic, implicitly typed semantics make it hard to compile into fast code. Variables change type and size at run time, scalars are treated as 1×1 arrays, and code is loaded incrementally, so whole-program static compilation is impractical. The authors present McVM, an open virtual machine for Matlab that pairs a simple AST interpreter with a JIT compiler built on LLVM. Any construct the JIT cannot yet handle is delegated back to the interpreter. The central idea is to compile a separate version of a function for each distinct combination of argument types seen at call time. A lightweight type and shape inference analysis, combining eight simple abstractions, pushes these argument types through the function body and guides code generation. The specializing JIT was compared with MathWorks Matlab, GNU Octave, the McFor static compiler and McVM without specialization. It was faster than Octave by up to three orders of magnitude and sometimes faster than the commercial system. This shows that coarse, function-level online specialization is a practical way to speed up dynamic scientific languages.

Key points

  • McVM uses a mixed-mode design. The McLab front-end produces a shared AST for both the interpreter and the JIT. The JIT lowers code to a RISC-like SSA form, and LLVM then generates machine code.
  • Run-time libraries include ATLAS, BLAS and LAPACK for matrix operations and the Boehm collector for garbage collection.
  • Functions are cloned and specialized per call signature (argument types). The inference combines 8 abstractions, such as overall type, scalar vs. 2D matrix, and shape.
  • When execution falls back to the interpreter, live register variables are written to memory. Functions that never need the interpreter pay no extra cost.
  • Future work targets speculative, heuristic type guessing, because conservative merging lets "unknown" types spread and erode the results of inference.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelf 1The field of science this work belongs to (OpenAlex fields).Mathematics · 233 works

Cite

Cite as Maxime Chevalier-Boisvert, Laurie Hendren and Clark Verbrugge. 2010. Optimizing MATLAB through just-in-time specialization. Compiler Construction (CC) 2010, LNCS 6011.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{chevalierboisvert2010optimizing,
  title = {{Optimizing MATLAB through just-in-time specialization}},
  author = {Maxime Chevalier-Boisvert, Laurie Hendren and Clark Verbrugge},
  booktitle = {Compiler Construction (CC) 2010, LNCS 6011},
  year = {2010},
  url = {https://www.sable.mcgill.ca/mclab/publications/}
}

References

27 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Lattner, C.: LLVM: An Infrastructure for Multi-Stage Optimization. Master’s thesis, Comp. Sci. Dept., U. of Illinois at Urbana-Champaign (Dec 2002) find
  2. Boehm, H., Spertus, M.: Transparent programmer-directed garbage collection for C++ (2007) find
  3. Biggar, P., de Vries, E., Gregg, D.: A practical solution for scripting language compilers. In: SAC ’09, ACM (2009) 1916–1923 find
  4. Almási, G., Padua, D.: MaJIC: compiling MATLAB for speed and responsiveness. In: PLDI ’02, ACM (2002) 294–303 find
  5. Elphick, D., Leuschel, M., Cox, S.: Partial evaluation of MATLAB. In: GPCE ’03, Springer-Verlag (2003) 344–363 find
  6. Derose, L., Rose, L.D., Gallivan, K., Gallivan, K., Gallopoulos, E., Gallopoulos, E., Marsolf, B., Marsolf, B., Padua, D., Padua, D.: FALCON: A MATLAB interactive restructuring compiler. In: LCPC ’95, Springer-Verlag (1995) 269–288 find
  7. Birkbeck, N., Levesque, J., Amaral, J.N.: A dimension abstraction approach to vectorization in matlab. In: CGO ’07, IEEE Computer Society (2007) 115–130 Maxime Chevalier-Boisvert, Laurie Hendren, Clark Verbrugge find
  8. Joisha, P.G., Banerjee, P.: A translator system for the MATLAB language: Research articles. Softw. Pract. Exper. 37(5) (2007) 535–578 find
  9. Rose, L.D., Padua, D.: A MATLAB to Fortran 90 translator and its effectiveness. In: ICS ’96, ACM (1996) 309–316 find
  10. Joisha, P.G., Banerjee, P.: An algebraic array shape inference system for MATLAB R . ACM Trans. Program. Lang. Syst. 28(5) (2006) 848–907 find
  11. Haldar, M., Nayak, A., Kanhere, A., Joisha, P., Shenoy, N., Choudhary, A., Banerjee, P.: Match virtual machine: An adaptive runtime system to execute MATLAB in parallel. In: ICPP2000. (2000) 145–152 find
  12. Jones, N.D., Gomard, C.K., Sestoft, P.: Partial evaluation and automatic program generation. Prentice-Hall, Inc. (1993) find
  13. Cooper, K.D., Hall, M.W., Kennedy, K.: Procedure cloning. In: Computer Languages. (1992) 96–105 find
  14. Chauhan, A., McCosh, C., Kennedy, K., Hanson, R.: Automatic type-driven library generation for telescoping languages. In: SC ’03. Volume 1. (1917) 58113–695 find
  15. Chambers, C., Ungar, D.: Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language. SIGPLAN Not. 24(7) (1989) 146–160 find
  16. Kennedy, A., Syme, D.: Design and implementation of generics for the .NET Common Language Runtime. In: PLDI ’01, ACM New York, NY, USA (2001) 1–12 find
  17. Shankar, A., Sastry, S.S., Bodı́k, R., Smith, J.E.: Runtime specialization with optimistic heap analysis. SIGPLAN Not. 40(10) (2005) 327–343 find
  18. Schultz, U., Consel, C.: Automatic program specialization for Java. ACM Trans. Program. Lang. Syst. 25(4) (2003) 452–499 find
  19. Rigo, A.: Representation-based just-in-time specialization and the Psyco prototype for Python. In: PEPM ’04, ACM (2004) 15–26 find
  20. Carette, J., Kucera, M.: Partial evaluation of Maple. In: PEPM ’07, ACM (2007) 41–50 find
  21. Gal, A., Eich, B., Shaver, M., Anderson, D., Mandelin, D., Haghighat, M.R., Kaplan, B., Hoare, G., Zbarsky, B., Orendorff, J., Ruderman, J., Smith, E.W., Reitmaier, R., Bebenita, M., Chang, M., Franz, M.: Trace-based just-in-time type specialization for dynamic languages. In: PLDI ’09, ACM (2009) 46… find
  22. Duggan, D., Bent, F.: Explaining type inference. In: Science of Computer Programming. (1996) 37–83 find
  23. Bacon, D.F., Sweeney, P.F.: Fast static analysis of C++ virtual function calls. In: OOPSLA ’96, ACM (1996) 324–341 find
  24. Tip, F., Palsberg, J.: Scalable propagation-based call graph construction algorithms. In: OOPSLA ’00, ACM (2000) 281–293 find
  25. Singer, J.: Sparse bidirectional data flow analysis as a basis for type inference. In: Web proceedings of the Applied Semantics Workshop. (2004) find
  26. Joisha, P.G., Banerjee, P.: Correctly detecting intrinsic type errors in typeless languages such as MATLAB. In: APL ’01, ACM (2001) 7–21 find
  27. Furr, M., An, J.h.D., Foster, J.S., Hicks, M.: Static type inference for Ruby. In: SAC ’09, ACM (2009) 1859–1866 find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/boisvert-2010-optimizing-matlab-through-just-time/