HL and HP Scheme

It seems that people still consider high level languages like Scheme and Lisp as specialty languages, suitable only for certain problem domains. Among the uninformed, Speed is often cited as a chief reason for Scheme being quite unusable. Apparently people have a kind of dual standard about programming languages, wherein they are convinced that they need to optimize their software as best as they can, yet they often use very slow software implementations to achieve their goals.

Java would be a prime example of this. Ruby, Python and PHP are some others. These are all useful tools in their own right, but if speed really were the only factor, none of these languages would reach the light of day. On modern computers, the processor speed and the run time are often the least important consideration. Developer cost and the time it takes to test and implement changes are often much more important. In this, Scheme excels. The high-level, abstract nature of Scheme, in addition to the interactive environments (REPLs) offered on many implementations, allows rapid prototyping and speedy development of serious programs.

However, once the program is developed, what if performance is an issue? What if someone honestly needs their software to perform faster and leaner than the competition for some high performance domain? Most people would immediately write Scheme as being too slow. However, is this really the case? Assuming that development time is still important, is it possible to achieve utopia through high performance programs that are fast and easy to develop and maintain? The answer is an emphatic, Yes! This article hopes to address some of the concerns of users who are afraid investing in Scheme will result in software that is too slow, and will not perform up to the standards they require.

I hope to convince my readers that Scheme is not just a special domain language, but that it is practical for use in high performance, rapid development environments that require and demand a lot from a language.

The First Issue

Before we get into the issue of run time performance, let’s reiterate that Development time and development cycle are the most important things to program development that a language can offer. In this aspect, there are numerous examples and articles explaining why Scheme is so useful as a prototyping tool. The interactive, interpreted nature of the initial development phase (and subsequent maintenance) of software development in Scheme make it a perfect tool for easily developing your software without strange and unnecessary restrictions (such as waiting for code to compile).

Now, what you all really want, Performance!

Despite the fact that most of the time performance is not nearly as important as people make it out to be, we still gotta admit, we all want to be able to put out speedy runtime stats and make our programs uber fast. Is Scheme up to the task?

If one looked at the language benchmark shootout, you might not think so. If you read something like the Ray Tracer Language Benchmarks you might be surprised to find out that Stalin Scheme is among the fastest implementations, period. It easily competes with C code, which surprises people pretty often that a high-level, completely unoptimized piece of code can match C code. Of course, the astute reader will immediately hit upon the catch: the compile times are enormous! If one were to read anything from these two benchmarks without knowing the full story, we might be lead to think that Scheme could only be made really fast by sacrificing huge development time in compiling for hours on end.

So, apparently we’re faced with a dilemma. How can we get high speed and the nice, rapid development environment that makes Scheme so appealing? Well, the first obvious solution is to develop your portable program in some other implementation than Stalin for the interactive part, and then do the final compilation on Stalin. This is all well and good, but it’s still not as pleasant as it could be. So, the question is, are there implementations that provide high performance code while still giving you access to a nice interactive development cycle? Yes, in a manner of speaking.

The good news is that there are a few implementations around that offer high performance code, a nice interactive environment, and all of it fits into a good all-in-one package! Of the top performers offering interactive environments, Chez Scheme usually takes top honors, with Gambit coming in after that. Both of these implementations are high performance implementations with good interactivity. Chez Scheme is particularly fast at the compilation stages.

Getting down and dirty…some real benchmarks.

Keep in mind that benchmarks are all relative, and cannot be trusted to provide a complete and accurate prediction of performance for every conceivable program. They are merely and index of how well certain implementations run certain programs. They are useful, however, to get some relative idea of how well things are going.

Implementations

To do these tests I am going to use three different compilers. GCC, Chez Scheme, and MIT Scheme. GCC is the de facto standard free software c compiler for UNIX systems, Chez Scheme is a commercial high performance scheme implementation, and MIT is a scheme implementation with an optimizing compiler.

The Code

I am going to be using some simple recursive function tests from the above benchmark shootout. I chose this basically because it was easy to implement, and I’m not really all that concerned with rigorous complete testing of all conceivable performance bottlenecks.

(recursive.zip) These files were designed to run on a Mac OS X machine with Chez Scheme installed. If you have Mac OS X and do not have Chez Scheme, you can still run the benchmarks, as the runtime environment, Petite Chez Scheme is available for free download. The recursive.so file is a pre-compiled file for Petite Chez Scheme on OS X.

Compilation time

Let’s first keep in mind that compilation is a step that does not even need to take place during the course of a Scheme program’s development until you are ready to distribute your application. Normally you just work from the source files as you go through an edit->run->debug cycle.

$ time make c-recursive

cc -pipe -Wall -O2 -fomit-frame-pointer recursive.c -o c-recursive

real    0m0.593s

user    0m0.078s

sys     0m0.058s

$ time make recursive.so

echo '(compile-file "recursive")' | scheme -q

real    0m0.194s

user    0m0.116s

sys     0m0.030s

$ time make recursive.com

echo '(cf "recursive.scm")' | mit-scheme --compiler --heap 6700

real    0m0.424s

user    0m0.107s

sys     0m0.056s

The first timing you see here is the compilation time of the C program. Remember that the C program must be compiled each and every time you want to make changes. The second timing is the compilation of the Chez Scheme file. The third timing is the compilation time for MIT Scheme.

These files are not really great indicators of compile time because they are so short. They are mostly here simply for the amusement of the reader. However, even at this point, it’s interesting to note that Chez Scheme compiles code very quickly. How does the compilation scale though?

To test this idea, I decided to use a set of code that was a bit bigger. While I can’t compare exact code footprints, I can compare things that are close. I started with my personal library directory of Scheme code, which contains about 900K of compilable files. As the comparison, I used the expat-2.0.0 code, which weighs in at about 560K.

Scheme Compile Times

$ du -sh .

936K    .

$ time echo '(compile-file "modules")' | scheme -q

compiling modules.ss with output to modules.so

real    0m1.548s

user    0m1.453s

sys     0m0.051s

$

Expat Compile Time

$ du -sh lib xmlwf/

464K    lib

100K    xmlwf/

$ time make

…

real    0m9.209s

user    0m7.696s

sys     0m1.422s

$

Here you can see that the Chez compiler is VERY fast. I’ll direct you to the SSAX Benchmark to get some interesting analysis of SSAX vs. Expat in Benchmarks. Otherwise, you can see here that as for compilation time, it appears that Chez Scheme scales very well in comparison to similar C code.

Run Time performance

So, you all really want to know how fast these programs run compared to one another. :-) Understandable. :-)

$ make run-benchmark

time echo y | mit-scheme --load recursive.com

…

real    0m14.627s

user    0m14.449s

sys     0m0.147s

time petite -q recursive.so

…

        4.67 real         4.62 user         0.02 sys

time ./c-recursive 11

…

        2.75 real         2.75 user         0.00 sys

$

So, if you compare these results to the results on the Benchmarks above, you see that in reality, MIT Scheme doesn’t do too poorly, and Chez Scheme does very well. Compared to many of the other languages, Chez Scheme is a very high performance beast, and if you compare the compile times, and the benefits of a rapid development cycle using Scheme, you’ll find that Scheme offers a lot of incentives to someone looking for high performance computing combined with the benefits of interactive, high-level development.

Redistribution, with or without modification, is permitted provided that the above copyright and these conditions remain with the article. This information is not guaranteed or warranted to be accurate, use at your own discretion and risk.