Dynamic languages, such as JavaScript, Python, Lua and Ruby, are increasingly popular amongst programmers at large, and virtual machine technology is constantly evolving to keep pace. This seminar aims to show both the gritty details and the high-level ideas of implementing VM's for dynamic languages. It is being taught by Gregor Richards.

The course grade breakdown is: 50% projects, 25% presentation, 25% final. The final will be an project for each student or group of two students. There is no precise structure to the final project: Each student or group will discuss project ideas with the instructor until one is agreed upon. Typical projects would be to extend SDyn or write a paper on a relevant topic. The instructor's expectation for group projects will be double that of his expectation for individual projects.

Schedule

Projects will be due on February 8th, March 1st and March 15th, with the final project due on the final day of class. Each project will be assigned well before the due date of the previous, and all required course material covered well before as well.

In most of March and April, students will present papers. The schedule is as follows:

DatePresentations
03-15 Adhityaa Chandrasekar. Presenting Idle Time Garbage Collection Scheduling.
Minghua Fan. Presenting Adaptive Scanning Reduces Sweep Time for the Lisp2 Mark-Compact Garbage Collector.
Damien Masson. Presenting Detailed Heap Profiling.
Andrew Beach. Presenting Efficient and Thread-Safe Objects for Dynamically-Typed Languages.
03-22 Qian Liang. Presenting Prioritized Garbage Collection: Explicit GC Support for Software Caches.
Aimilios Tsalapatis. Makalu: Fast Recoverable Allocation of Non-volatile Memory.
Michael Brooks. Safe Transferable Regions.
Jinshan Gu. Ryū: Fast Float-to-String Conversion.
03-29 Stan Gurtler. Virtual Machine Warmup Blows Hot and Cold.
Yang Tian Zi. Putting in All the Stops: Execution Control for JavaScript.
Jakub Kuderski. Simple and Effective Type Check Removal through Lazy Basic Block Versioning.
Krishna Teja Reddy Vemula. Interprocedural Type Specialization of JavaScript Programs Without Type Analysis.
04-05 Sagar Kulkarni. Design and Evaluation of Gradual Typing for Python.
Qingnan Duan. Accelerating Dynamically-Typed Languages on Heterogeneous Platforms Using Guards Optimization.
Ankith Prabhu. Python Interpreter Performance Deconstructed.
Final remarks

Before then, we'll do standard lectures, with a heavier weight on JIT-related material at the beginning and on GC-related material at the end.

Reference Material

I will be using a mix of slides and other forms of presentation, and will post files here shortly after they're presented in class.

DateResources
01-11Slides
Live JIT demo
01-18Slides
01-22Slides
Speculation ossification example
02-01Slides
Inline limit example
02-08Slides
02-15Slides
03-01Slides
03-08Slides

Resources

Students are expected to present a paper. A list of suggested papers is here.

To explore “the gritty details”, this course will use a simple dynamic language implementation called SDyn. As a JIT, SDyn is not intrinsically portable: At present, it works on x86_64 Unix only. Slightly specialized versions of SDyn will be provided for the projects. SDyn is available here. How SDyn works will be discussed in class.

Projects

This course has three software implementation projects, accounting collectively for 50% of the grade, each with equal weight. Yes, this means the actual percentage value of each project is an awkward 16.66 repeating%.

Project 1: Inline caching

The first project is to implement inline caching, as discussed in class, in SDyn. It is due on February 8th. A patch, sdyn-1.3-inline-cache-scaffolding.diff.gz, which adds the scaffolding to implement inline caching, is provided . Alternatively you may download sdyn-1.3-w-inline-cache-scaffolding.tar.gz, which is sdyn 1.3 with the patch preapplied.

Project requirements document

A brief explanation of the inline caching scaffolding patch: For each cacheable access site, the JIT creates a SDyn_InlineCache object. An SDyn_InlineCache* is passed to each function which accesses members of objects. You must define SDyn_InlineCache in h/sdyn/value.h , and use it in the relevant functions in value.c to implement caching of object shapes.

Project 2: Speculation

The second project is to implement speculation and specialization over function arguments in SDyn. It is due on March 1st. A patch, sdyn-1.3-speculation-scaffolding.diff.gz, which adds the scaffolding to implement speculation, is provided. Alternatively you may download sdyn-1.3-w-speculation-scaffolding.tar.gz, which is sdyn 1.3 with the patch preapplied.

Project requirements document

Please note that the scaffolding patch also includes the implementation of RECORD and a fix to the implementation of SPECULATE. Please read h/sdyn/nodex.h for descriptions of these operations.

Project 3: Mark-and-Sweep GC

The third project will be to replace the good generational garbage collector in GGGGC with a much-inferior mark-and-sweep one. Why would you do this? ... well, because I said so, I guess. It is due on March 15th. Due to some bugs in previous versions, it must be based on SDyn 1.4. No further patch is necessary and no scaffolding is provided.

Project requirements document