I am a software engineer interested in the implementation of dynamic languages such as Python. My research during my PhD at the University of Glasgow and subsequently has been focussed on the engineering behind virtual machines for dynamic languages.

These virtual machines are large and complex, and the conventional tools, such as C compilers, are often inappropriate for building these machines. My PhD focussed on how to make better tools. My subsequent research has been focussed on ways to dynamically transform dynamic language code to a form more suitable for conventional tools. 

Current Work --- Bringing Trace-Based Optimisation to the CPython Virtual Machine

I am currently working on the HotPy (2) project to port improved versions of the optimisations used in the original HotPy project to the latest version of CPython.

In order to apply trace-based optimisations to a dynamic language it is useful to convert the high-level 'fat' bytecodes into a lower-level representation. This can be done in one of three ways:
  • At close the hardware level like PyPy or the GVMT (see below). This has been shown to work but requires complex tools.
  • By layering the dynamic language VM on top of a static language VM such as the JVM. This does not work well due to mismatches between the VMs.
  • Or, by translating the high-level 'fat' bytecodes into lower-level 'thin' bytecodes within the same VM. This approach has been used (in a limited fashion) in the TraceMonkey VM for Javascript and is the approach used for HotPy (2). 
HotPy and HotPy (2) are the only virtual machines, of which I am aware, which use tracing to perform optimisation within an interpreter, not merely as a precursor to JIT compilation.
(HotPy also includes a JIT compiler, but it can optimise without compiling)

Improving CPython

In order to be able trace and optimise bytecodes in the CPython virtual machine, some modifications need to be made. Some of these modifications are specific to HotPy but some would be beneficial to the main CPython distribution. I am currently working on the following improvements to CPython:

  • A new dictionary implementation, which splits dictionary tables into key arrays and values arrays. Doing this can save significant amounts of memory, typically reducing memory usage by about 10%. For that reason it is worth adding to CPython. This has included in Python 3.3.
  • Table driven binary operators. Binary operators, such as add, are implemented by dispatching first on the type of the left operand, then on the type of the right operand. This double dispatching can be eliminated for standard built-in types like integers and floats by using tables to lookup the operator function for this standard types, then falling back on the normal double dispatching. This is useful for HotPy as it will mean that the tracing interpreter does not have to expand every binary operator. It is less useful for CPython but it does result in 1-2% speedup and could potentially simplify the implementation by removing a lot of boilerplate code required to make the current dispatching technique work well. See here for the code.
  • Refactoring frame object, generator objects and the interpreter so that the structure of the implementation better reflects the semantics of generator objects. This is necessary for HotPy in order for the tracing interpreter to handle "yield" expressions. It is useful for CPython as it makes the code base smaller and more modular.

Previous Research --- Building Virtual Machines for Dynamic Languages

Virtual machines consist of many complex, interacting and interwoven parts. Object-oriented languages and even aspect-oriented languages cannot separate these parts. Tools are required. My research aims to demonstrate that using appropriate tools will allow the construction of better virtual machines with less effort.

To demonstrate the sorts of tools that are needed and how they are used, I have developed a toolkit for building virtual machines as well as a new virtual machine for Python. The toolkit handles the generation of interpreters and a compiler, as well as managing memory management, which makes the implementation of optimisers and compilers for dynamic languages such as Python much more feasible.

Using the toolkit to build the new virtual machine means that its implementation is simplified enough to be able to incorporate powerful optimisations which might otherwise be too time consuming. Combining these optimisations with the compilation ability provided by the toolkit further enhances the performance of the resulting virtual machine.

The Glasgow Virtual Machine Toolkit

The Glasgow Virtual Machine Toolkit (GVMT) allows easy construction of virtual machines. It handles garbage collection automatically, and builds interpreters and compilers from a common specification. The toolkit helps the rapid development of various sorts of interpreters, such as bytecode instrumentation and transformation passes, making the implementation of a high-performance virtual machine much easier.

You can download from it here. 

The HotPy Virtual Machine

The HotPy virtual machine is a high-performance virtual machine for Python. HotPy is a recursive acronym for:
  • HotPy
  • Optimising
  • Tracing
  • Python

The notable features of HotPy are:

  • It is built using the GVMT
  • It offers significantly improved performance by:
    • Tracing the bytecode to determine what to optimise and when.
    • Optimising the bytecode, using type information gathered at runtime.
    • Compiling the optimised bytecode using the GVMT generated compiler.
An overview of how it works can be found here. The HotPy can be downloaded from here. You will need the GVMT and antlr2.x (Not version 3) to build and run it. You will also need to modifiy the Makefile to suit your machine. Good luck. When HotPy has an integrated parser the need for antlr will go, so there is no plan to update to antlr3.

HotPy is no longer being developed, see HotPy (2).

Publications

Talks


Comments