Interpreters Part I : Language & Runtime comparison

At SourceProbe, we are building fast and powerful code search tools. Our query engine uses a sort of mini-language to express the query. We are planning to add another internal language to our system, to provide even more precise results for your searches. Both of these rely on fast and efficient interpreters.

Interpreters are very common in software. In fact, large systems tend to develop interpreter like functionality, whether intentional or not (Greenspun’s rule). Outside of programming languages, they are also typically found in system emulators and any system which wants to add programmability.

So lets see what it takes to build an interpreter, and make it fast. In this first post, we’ll focus primarily on the languages we’ll use in future posts. Next we’ll build a few simple interpreters, and then explore techniques and tricks to make them fly.

Languages

For this investigation, we have selected a few programming languages to explore.

• C : Compiled and non-garbage collected. This give us a baseline performance number to compare against, a sort of optimal performance for a given technique.
• Python : Interpreted and garbage collected. Python is easy to read and write, and gives us a clean reference implementation before porting to other languages. And as a scripting language, its performance is similar to many languages people use frequently.
• Common Lisp (CL) : A highly flexible language which can be interpreted or compiled. We’ll be leveraging some Common Lisp features more heavily in later posts. We’ll be using SBCL, a Common Lisp system with a high-performance compiler.
• Scheme : A simpler Lispy language. Originally used as an intermediate goal to ease porting to CL. We’ve decided to include it as performance was better than expected. We’re using chicken-scheme.

Language Version Info

If you would like more information on the tools used in this series, you can expand this section.

$ g++ --version
g++ (Debian 10.2.1-6) 10.2.1 20210110
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ python3 --version
Python 3.11.2

$ sbcl --version
SBCL 2.4.0.40-016fa7e01

$ csc -version
CHICKEN
(c) 2008-2021, The CHICKEN Team
(c) 2000-2007, Felix L. Winkelmann
Version 5.3.0 (rev e31bbee5)
linux-unix-gnu-x86-64 [ 64bit dload ptables ]

Implementing a Mandelbrot renderer

To start off our investigation, we will implement a Mandelbrot renderer in each of these languages. We have selected this as it uses a good mix of language features, particularly branching and looping. Yet it is also simple enough that a few implementations can be completed in an afternoon.

The Mandelbrot renderer performs some calculation for each x/y cell in the image. At each point, the formula is iterated. The value at each point is based on the number of steps before the formula diverges.

The renderer was initially written in Python, then translated by hand to each of the other languages. Care was taken to ensure that the implementation should be performing similar work, and no inefficiencies are introduced. The Scheme and CL implementations are both tail-recursive, and both platforms support the Tail-Call Optimization.

Results

The table below captures the performance of each implementation. A few of these rows involve different settings which are worth mentioning:

• C (script) : A shebang has been added to the file to allow running it directly like a script. Runtime includes compilation time as well as running the resulting binary. Though C is rarely used this way, the results are interesting since it includes parsing and interpreting, just as with scripting languages. mentions
• C (O3) : Highest safe optimization level for GCC. A standards compliant C program will run correctly and quickly with these settings.
• Lisp/Scheme Compiled: Both SBCL and chickenscheme can generate native binaries for your programs. For chickenscheme, all you need to do is pass the file to the compiler. For SBCL, a lisp script is linked which invokes the compiler.

Conclusion:

The total running time, even for the slowest setups, is quite low. Unfortunately, this means running time can be dominated by higher startup times or other one-time costs.

A longer running program would more accurately characterize the performance of these compilers. Next up we will be building a simple programming language interpretter, and run a familiar program in our resulting interpreters.