Dynamic adaptive optimizations in JIT compiler for R

• Thesis title in English: Dynamic adaptive optimizations in JIT compiler for R
• Academic year of topic announcement: 2014/2015
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Distributed and Dependable Systems (32-KDSS)
• Supervisor: doc. RNDr. Pavel Parízek, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 07.10.2014
• Date of assignment: 22.10.2014
• Confirmed by Study dept. on: 20.11.2014

Guidelines

R is a scripting language widely used in statistics, big data processing, and for general scientific computing.
It supports various mathematical operations and techniques for data analysis (including graphics), but the current implementation of the R virtual machine has limited performance.
TinyR is a research project whose goal is to investigate possible approaches to dynamic adaptive optimizations inside a just-in-time compiler for a subset of the R language.

The focus of this work will be on the inference and usage of assumptions about values of program variables. When the just-in-time compiler knows that a variable has a particular value, it can perform more aggressive optimizations of code fragments that involve the given variable. However, sometimes the inferred assumptions may be invalid and the virtual machine has to discard the optimized code.

Specific tasks include:
1) Defining the list of possibly useful types of assumptions based on initial experiments.
2) Design and implementation of a dynamic analysis for precise identification of assumptions that are useful in program optimization.
3) Implementing a simple framework that will enable the virtual machine to save inferred assumptions and use them later in future runs of the same program.
4) Evaluation of the proposed approach on several benchmark programs.

The main challenge is to design an algorithm for recognizing the useful assumptions on-the-fly during program execution.

References

1. The R project. http://www.r-project.org/
2. T. Kalibera, P. Maj, F. Morandat, and J. Vitek. A Fast Abstract Syntax Tree Interpreter for R. VEE 2014.
3. F. Morandat, B. Hill, L. Osvald, and J. Vitek. Evaluating the Design of the R Language - Objects and Functions for Data Analysis. ECOOP 2012.
4. F. Nielson, H.R. Nielson, and C. Hankin. Principles of Program Analysis. Springer, 1999.