The Many Varieties of Supercompilation

When a human programmer is given the task of speeding up someone else’s code, there are two different approaches they can take. There’s the “local” approach, where the programmer looks at each little part of the program and tries to figure out a way to make it faster. And then there’s the “global” approach, where the programmer takes a step back and asks: “What is this program trying to accomplish anyway? What is this portion of the program trying to accomplish … what about that one?” In a global rewrite, parts of the program that were formerly separate may get merged together, things that were done using a very general approach may become much more specialized, and so forth. The global approach is more work, and requires more expertise and intelligence, but generally yields far superior results.

Now, what if it’s a piece of software, rather than a human programmer, that’s rewriting a piece of computer code for improved efficiency? The same distinction between local and global program optimization holds true. But, software being generally less intelligent than human beings (so far), here local optimization is the norm. Modern compilers perform all sorts of local optimizations, and in the case of Java there are special tools like HotSpot that carry out local optimization at run-time. But automated global program optimization has existed only in the ivory tower of academia. The problem is that, the more complicated a programming language is, the harder it is to globally optimize programs written in it. Academic computer scientists have the liberty to work with beautiful but commercially impractical programming languages such as LISP, Scheme, ML and Haskell – languages that, by and large, most working commercial programmers have never even heard of. Some interesting global program optimization software has been written for these languages. But for the vast mass of programmers writing the software that people actually use, in languages like C, C++, Java and Visual Basic, automatic global program optimization software has been out of reach.

The technical term “supercompilation” refers to a particularly powerful global program optimization technique invented by SuperCompilers, LLC co-founder Valentin Turchin in Russia in the early 1970’s. Supercompilation was introduced to the West in Turchin’s 1986 technical paper "The concept of a supercompiler" (ACM Transactions on Programming Languages and Systems, volume 8, pp.292-325), and since this time the concept has been avidly developed by computer scientists in Russia, America, Denmark and other nations. However, prior to the Java supercompilation project pursued at SuperCompilers, LLC, practical examples of supercompilation had been developed primarily for the Russian programming language Refal, a non-commercial language that is basically unknown in the Western world, even among academics.

Why did SuperCompilers, LLC choose Java for their first product? Because Java is complex enough to be commercially useful yet simple enough to be mathematically analyzable. Java is far more complex than LISP, Scheme and other academic languages, yet unlike C++ and C, it is just barely simple enough to make automatic global optimization a contemporary practical possibility. With the Java supercompiler, the worlds of academic programming language theory and real-world software engineering are at long last brought into alignment.

The main thrust of SuperCompilers, LLC’s work is a “static supercompiler,” which works like the magic black box described above – it takes in Java source, and it spits out faster Java source doing the same thing. Complementary to this, a “dynamic run-time supercompiler” is also under development. This one speeds up a Java program as it runs, making optimizations based on data that is only known at run-time. Maximum speed-up, of course, is obtained by running both of these components together.

 

© Copyright 1999-2005 SuperCompilers, LLC. ALL RIGHTS RESERVED.
 

Design: A2AStudios