The Scheme of things/2

In one of my previous posts I compared Clojure with Python by implementing two identical versions of a program to solve problem 34 from Project Euler in both languages. My results showed that Clojure was able to be three times faster than Python when type hinting (TH) was enabled (even without TH Clojure was however faster than Python). My idea was then that any type-hinted (semi-)interpreted language like Clojure would have reached the same speed.

In the last month I have run some other tests, and I must say that my idea has changed. A number of Scheme/Common LISP implementation have proven to be even faster than Clojure, and this without type hints!

I am not going to provide my Common LISP and Scheme programs, as they are trivial conversions of the Clojure program I presented before. These are the compilers/interpreters I used to write and run my test programs:

Name	Version	Language	Timing
Ikarus	0.4 RC1	Scheme	14
Larceny	0.97	Scheme	15
Bigloo	3.5a	Scheme	16
Steel Bank CL	1.0.44	Common LISP	17
MZScheme (DrRacket)	5.0.1	Scheme	17
STklos	1.0	Scheme	43
CMU CL	20b	Common LISP	47
Clozure CL	1.5	Common LISP	62
Chicken	4.6.3	Scheme	93
Chicken	4.4.0	Scheme	102
CLISP	2.49	Common LISP	106
CPython (fast)	2.6.6	Python	135
CPython	2.6.6	Python	145
ECL	10.4.1	Common LISP	169

The "CPython (fast)" entry is a rewrite of my original Python program so that the body of solution does not call other Python functions:

sum ([num for num in xrange (10, max_n)
      if num == sum ([FAST_FACT[digit]
                      for digit in [int(x)
                                    for x in list (str (num))]])])

A few notes about these results:

• There is more than one order of magnitude between the slowest implementation (ECL) and the fastest (Ikarus Scheme);
• Compilers without TH (e.g. Ikarus, Larceny, Bigloo, SBCL) run much faster than Clojure with TH. I was really surprised!
• Avoiding function calls make CPython faster, but not much faster;
• The fastest program runs using Ikarus, a compiler in alpha stage that has been put on hiatus after the author (apparently) changed his job. What a pity! (Note however that Marco Maggi has forked Ikarus into Vicare, which seems to be actively developed.)
• While I had to change my Scheme program in order to make it runnable under various Scheme compilers/interpreters (nothing sensational, just one or two lines at the beginning), my Common LISP program ran unchanged under SBCL, ECL and CCL. One point for portability to Common LISP!

Here is a barchart of the results (click to zoom):

Update: After a suggestion by Water I included in my benchmarks also CLISP (and corrected the name) and CMU Lisp (which was mentioned in one of the pages at CLISP's site as being faster than CLISP – and indeed it is). In both cases I first compiled the program and then timed the execution of the bytecode. I have also added MZScheme, which I left out in the first version of this post. The table and the chart have been updated accordingly.

Clojure and FP - First impressions

This blog entry is to report my achievements with Clojure and Functional Programming (see my previous post).

What I do not like

The first thing that one faces when trying to use Clojure is the difficulty in installing it. The downloads page only lists a few zip files, without saying anything about how to use them. (Sure, there is a Readme file, but I would have like to know something more before downloading anything.) In comparison, the Downloads page of Scala is much better in shape, and a number of pre-built packages are provided. Moreover, Scala is included in Macports, while Clojure is not. Once the ZIP file has been uncompressed, the Readme file is extremely laconic: it just reports the command required to run/build Clojure. Since the REPL has no editing facilities (i.e. you cannot use Backspace/delete to modify what you have written, and there is no history), I would have expected some reference to jLine or rlwrap as these can really save you the day.

In general, Clojure shows its young age in a number of other spots. The documentation is quite sparse, and you often have to look at the source code of some function in order to understand its behavior. Many tools I regularly use for source code (e.g. Vim, Source-highlight and others) do not have native support for Clojure (although you can usually find something in the Web - I find VimClojure one of the best Vim plugins I have ever seen, the "rainbow parentheses" mode is incredibly useful!).

What I like

Being a LISP dialect, Clojure can be extremely elegant. Here is some code I wrote to solve problem 34 from Project Euler.

A few things worth to note:

• Clojure implements a large number of high-level data structures, like dictionaries. I used the latters in fast-fact, a dictionary whose keys are the 10 digits and whose values are the corresponding factorials.
• It is really easy to call Java functions like toString: just prepend them with a dot. No need to import modules to do this!
• Although Clojure is a dynamically typed language (like e.g. Python), it allows to specify the type of the input parameters for functions and let bindings. I have verified that this allows to dramatically increase the speed of the code (3x or 4x times).
• Like Python, Clojure allows to use docstrings. They can be accessed from the REPL through the doc function.

Python vs. Clojure

Since I am an avid Python user, I immediately rewrote the program in Python:

I tried to follow the same logic used in the Clojure program, i.e. using a dictionary for the first 10 factorials and getting the list of digits for a number by first converting it to a string (an alternative would be to repeatedly apply division and modulus 10). Then, using the Clojure time function and the IPython %time command, I was able to record the times used by each program. In order to get sounder values, I repeated each measurement till the timing did not change significatively any more.

Results are shown in the plot on the right. They look quite impressive: as shown by the following graph, type hints allow Clojure to be more than three times faster than Python. Even not using type hints would have allowed Clojure to be approximately 20% faster than Python.

Preliminary conclusions

Despite its young age and a few rough edges, my overall impression is extremely positive: Clojure is really nice to use and the number of features it provides are extremely interesting. Its speed is also remarkable.

Functional programming

Recently I had to work with an old numerical software written in Fortran77. Such program simulates the microwave radiation pattern of an emitter (like an horn or a waveguide). The program requires several minutes to compute a radiation pattern for all but the simplest configurations, so I started wondering how the computation might be accelerated (despite the fact that, being the software closed-source, the only way to go would be to rewrite it from scratch).

One way to get a significative speedup is to take advantage of multi-core architectures, as this seems so far the only way to ensure that performances will scale in the future. As it is well known, parallelizing an algorithm is not generally a trivial task. Rather, it often involves rethinking the problem from the ground up.

As parallelizing C/C++/Fortran code requires using either OpenMP (easy, but not feasible for complex tasks) or MPI (many features, but difficult to use), I started investigating some "new" approaches to parallelization. Then I found… functional programming!

Functional programming (opposed to imperative programming) is a way to write programs that concentrates on functions which work on immutable values. The point of having immutable values helps parallelization, as one does not need locks, mutexes and semaphores: this explains why, even if functional programming is a quite old concept, it has gained a renewed interest in the last few years. Microsoft is pushing its F# language (based on the very nice family of Caml languages), and other languages have been designed with multicore CPUs in mind. E.g. this post compares Clojure (see below) with Python with an explicit note on concurrency/parallelism (something Python is not very good at, see also the follow-up).

In the last weeks I started gathering some information about the most widely used functional languages. I started with OCaml, as it seems one of the oldest and widely-used languages. Although the INRIA compiler produces really fast code, it seems that some fundamental problems with the garbage collector prevent OCaml programs from taking benefit of multicore CPUs. Although there are attempts to solve this, OCaml does not seem ready for multicore yet. So I looked for another language to study. Haskell enjoys a very large community, but I do not really like it (but it seems to support concurrency pretty well…), and I avoided Erlang too (no specific reason, maybe it is its syntax that scares me).

Among the most interesting functional languages of the new generation, Scala and Clojure have caught my attention. Both run using the Java Virtual Machine (which, according to your taste, might or not be an advantage) and have a similar objective (exploiting functional programming for easy parallelization, see e.g. this page about Clojure), although they try to accomplish this using two different approaches: Scala is clearly derived from Java and ML, while Clojure is a simpler (and nicer) LISP. Both are moving targets (both languages seem to change pretty fast with each release) but already have a remarkable community.

I am studying Clojure with great interest, as it reminds me of my old days with Scheme. Although it seems that Scala often beats Clojure in performance (see The Computer Language Benchmarks Game, but take their results with a grain of salt), I find the syntax of the latter easier to understand. More details to come with the next posts!