Paul Biggar (Research)

Compilers and Scripting Languages

Design and Implementation of an Ahead-of-time Compiler for PHP
Paul Biggar
PhD Dissertation

Abstract

In recent years the importance of dynamic scripting languages—such as PHP, Python, Ruby and Javascript—has grown as they are used for an increasing amount of software development. Scripting languages provide high-level language features, a fast compile-modify-test environment for rapid prototyping, strong integration with database and web development systems, and extensive standard libraries. PHP powers many of the most popular web applications such as Facebook, Wikipedia and Yahoo. In general, there is a trend towards writing an increasing amount of an application in a scripting language rather than in a traditional programming language, not least to avoid the complexity of crossing between languages.

Despite their increasing popularity, most scripting language implementations remain interpreted. Typically, these implementations are slow, between one and two orders of magnitude slower than C. Improving the performance of scripting language implementations would be of significant benefit, however many of the features of scripting languages make them difficult to compile ahead of time. In this dissertation we argue that ahead-of-time compilation of scripting languages is both possible and valuable. We present phc, an ahead-of-time compiler for the PHP language. We describe the design and implementation of the compiler, and identify specific challenges in the design of a compiler for a dynamic scripting language.

We determine that there are three important features of scripting languages that are difficult to compile or reimplement. Since scripting languages are defined primarily through the semantics of their original implementations, they often change semantics between releases. They provide C APIs, used both for foreign-function interfaces and to write third-party extensions. These APIs typically have tight integration with the original implementation, and are used to provide large standard libraries, which are difficult to re-use, and costly to reimplement. Finally, they support run-time code generation. These features make the important goal of correctness difficult to achieve for compilers and reimplementations.

We present a technique to support these features in our ahead-of-time compiler for PHP. Our technique uses the original PHP implementation through the provided PHP C API, both in our compiler, and in our generated code. We support all of these important scripting language features, particularly focusing on the correctness of compiled programs. Additionally, our approach allows us to automatically support limited future language changes. We present a discussion and performance evaluation of this technique, which we show increases the execution speed of PHP programs by 1.55x in our benchmarks. In order to improve this performance, static analysis and optimization are required.

However, static analysis of scripting languages such as PHP is difficult due to the features found in these languages. These features include dynamic typing with implicit type conversions, dynamic aliasing, implicit object and array creation, and overloading of simple operators. We find that as a result, simple analysis techniques such as SSA and def-use chains are not straightforward to use, and that a single unconstrained variable can ruin our analysis. We describe the challenging semantics of PHP, and a static analyser to model them. Our analysis combines alias analysis, type-inference and constant-propagation for PHP, computing results that are essential for other analyses and optimizations. Our empirical results show that our analysis is capable of determining that almost all program variables are unaliased, and that dynamic types for over 60% of variables can be statically determined by our analysis.

How not to Design a Scripting Language
Paul Biggar
StackOverflow London, October 28, 2009

One Representation to Rule Them All
(Combining analyses on SSA with On-Demand SSA Construction)
Paul Biggar and David Gregg
PLDI '09 FIT Session (June 2009)

Summary

The authors sketch an algorithm for constructing an SSA intermediate representation while performing analysis that typically preceded SSA construction. The goal is to combine the benefits of SSA (sparse representation) with costly analysis so that the analysis is positively impacted (faster, more precise).

On the use of SSA with scripting languages
Paul Biggar and David Gregg
Static Single-Assignment Form Seminar (April 2009)

Summary

Constructing SSA form for static languages is a well-studied problem. Techniques exist to handle all of the most common features of static languages, and these solutions have been tried and tested in production level compilers for many years.

In our study of optimizing dynamic scripting languages, specifically PHP, we find this is not the case. The information required to build SSA form—that is, some conservatively complete set of unaliased scalars, and the locations of their uses and definitions—is not available directly from the program source, and can not be derived from a simple analysis. Instead, we find a litany of features whose presence must be ruled out, or heavily analysed, in order to obtain a non-pessimistic estimate.

Scripting languages commonly feature run-time code generation, built-in functions, and variable-variables, all of which may alter arbitrary unnamed variables. Less common—but still possible—features include the existence of object handlers which have the ability to alter any part of the program state, most dangerously a function's local symbol-table.

Ruling out the presence of these features requires precise, inter-procedural, whole-program analysis. We discuss the futility of the pessimistic solution, the analyses required to provide a precise SSA form, and how the presence of variables of unknown types affect the precision of SSA.

Compiling and Optimizing Scripting Languages
Paul Biggar and David Gregg
Various talks (March 2009)

Abstract

A Practical Solution for Scripting Language Compilers
Paul Biggar, Edsko de Vries and David Gregg
SAC '09: ACM Symposium on Applied Computing (2009), (March 2009)

Abstract

Although scripting languages are becoming increasingly popular, even mature scripting language implementations remain interpreted. Several compilers and reimplementations have been attempted, generally focusing on performance.

Based on our survey of these reimplementations, we determine that there are three important features of scripting languages that are difficult to compile or reimplement. Since scripting languages are defined primarily through the semantics of their original implementations, they often change semantics between releases. They provide large standard libraries, which are difficult to re-use, and costly to reimplement. They provide C APIs, used both for foreign-function-interfaces and to write third-party extensions. These APIs typically have tight integration with the original implementation. Finally, they support run-time code generation. These features make the important goal of correctness difficult to achieve.

We present a technique to support these features in an ahead-of-time compiler for PHP. Our technique uses the original PHP implementation through the provided C API, both in our compiler, and in our generated code. We support all of these important scripting language features, particularly focusing on the correctness of compiled programs. Additionally, our approach allows us to automatically support limited future language changes. We present a discussion and performance evaluation of this technique, which has not previously been published.

Sorting

An Experimental Study of Sorting and Branch Prediction
Paul Biggar, Nicholas Nash, Kevin Williams and David Gregg
ACM Journal of Experimental Algorithmics, Volume 12 (June 2008)

Abstract

Sorting is one of the most important and well-studied problems in computer science. Many good algorithms are known which offer various trade-offs in efficiency, simplicity, memory use, and other factors. However, these algorithms do not take into account features of modern computer architectures that significantly influence performance. Caches and branch predictors are two such features and, while there has been a significant amount of research into the cache performance of general purpose sorting algorithms, there has been little research on their branch prediction properties. In this paper, we empirically examine the behavior of the branches in all the most common sorting algorithms. We also consider the interaction of cache optimization on the predictability of the branches in these algorithms. We find insertion sort to have the fewest branch mispredictions of any comparison-based sorting algorithm, that bubble and shaker sort operate in a fashion that makes their branches highly unpredictable, that the unpredictability of shellsort's branches improves its caching behavior and that several cache optimizations have little effect on mergesort's branch mispredictions. We find also that optimizations to quicksort, for example the choice of pivot, have a strong influence on the predictability of its branches. We point out a simple way of removing branch instructions from a classic heapsort implementation and also show that unrolling a loop in a cache-optimized heapsort implementation improves the predicitability of its branches. Finally, we note that when sorting random data two-level adaptive branch predictors are usually no better than simpler bimodal predictors. This is despite the fact that two-level adaptive predictors are almost always superior to bimodal predictors, in general.

Sorting in the Presence of Branch Prediction and Caches
Paul Biggar and David Gregg
(Technical Report TCD-CS-2005-57 - August, 2005)
(Revision 1 - January, 2007)

Abstract

Sorting is one of the most important and studied problems in computer science. Many good algorithms exist which offer various trade-offs in efficiency, simplicity and memory use. However most of these algorithms were discovered decades ago at a time when computer architectures were much simpler than today. Branch prediction and cache memories are two developments in computer architecture that have a particularly large impact on the performance of sorting algorithms.

This report describes a study of the behaviour of sorting algorithms on branch predictors and caches. Our work on branch prediction is almost entirely new, and finds a number of important results. In particular we show that insertion sort causes the fewest branch mispredictions of any comparison-based algorithm, that optimizations - such as the choice of the pivot in quicksort - can have a large impact on the predictability of branches, and that advanced two-level branch predictors are usually worse at predicting branches in sorting algorithms than simpler branch predictors. In many cases it is possible to draw links between classical theoretical analyses of algorithms and their branch prediction behaviour.

The other main work described in this report is an analysis of the behaviour of sorting algorithms on modern caches. Over the last decade there has been considerable interest in optimizing sorting algorithms to reduce the number of cache misses. We experimentally study the cache performance of both classical sorting algorithms, and a variety of cache-optimized algorithms proposed by LaMarca and Ladner. Our experiments cover a much wider range of algorithms than other work, including the O(N²) sorts, radixsort and shellsort, all within a single framework. We discover a number of new results, particularly relating to the branch prediction behaviour of cache-optimized sorts.

We also developed a number of other improvements to the algorithms, such as removing the need for a sentinel in classical heapsort. Overall, we found that a cache-optimized radixsort was the fastest sort in our study; the absence of comparison branches means that the algorithm causes almost no branch mispredictions.

Work in progress (comments welcome)

A Practical Solution for Scripting Language Compilers
Paul Biggar, Edsko de Vries and David Gregg
Journal version, in submission

Abstract

Although scripting languages are becoming increasingly popular, even mature scripting language implementations remain interpreted. Several compilers and reimplementations have been attempted, generally focusing on performance.

Based on our survey of these reimplementations, we determine that there are three important features of scripting languages that are difficult to compile or reimplement. Since scripting languages are defined primarily through the semantics of their original implementations, they often change semantics between releases. They provide large standard libraries, which are difficult to re-use, and costly to reimplement. They provide C APIs, used both for foreign-function-interfaces and to write third-party extensions. These APIs typically have tight integration with the original implementation. Finally, they support run-time code generation. These features make the important goal of correctness difficult to achieve.

We present a technique to support these features in an ahead-of-time compiler for PHP. Our technique uses the original PHP implementation through the provided C API, both in our compiler, and in our generated code. We support all of these important scripting language features, particularly focusing on the correctness of compiled programs. Additionally, our approach allows us to automatically support limited future language changes. We present a discussion and performance evaluation of this technique, which has not previously been published.

Static Analysis of Dynamic Scripting Languages
Paul Biggar and David Gregg
In Submission

Abstract

Scripting languages, such as PHP, are among the most widely used and fastest growing programming languages, particularly for web applications. Static analysis is an important tool for detecting security flaws, finding bugs, and improving compilation of programs. However, static analysis of scripting languages is difficult due to features found in languages such as PHP. These features include run-time code generation, dynamic weak typing, dynamic aliasing, implicit object and array creation, and overloading of simple operators. We find that as a result, simple analysis techniques such as SSA and def-use chains are not straight-forward to use, and that a single unconstrained variable can ruin our analysis. In this paper we describe a static analyser for PHP, and show how classical static analysis techniques can be extended to analyse PHP. In particular our analysis combines alias analysis, type-inference and constant-propagation for PHP, computing results that are essential for other analyses and optimizations. We find that this combination of techniques allows the generation of meaningful and useful results from our static analysis.