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!

C code for determining the operating system

In the last days I have been busy trying to making our analysis program (written in a strange mixture of C, C++ and ITT IDL) work under Windows, Linux, Mac OS X and FreeBSD. I have discovered that a severe bottleneck was represented by the data transmission through a local socket. Under Linux and FreeBSD, sending ~500 packets of a few bytes each was taking ages to complete, while under Mac OS X the same task completed in a fraction of second. This is really strange, considering that we were using local sockets, i.e. communications between two tasks on the same machine.

After a little digging with Google, I discovered that the standard algorithm used by Linux and FreeBSD to send data through a socket can sometimes induce severe slowdowns. Luckly, there is a simple solution: call setsockopt and set TCP_NODELAY to 1. Doing this on our code made a performance boost of several orders of magnitude.

Since I wanted not to change things on those operating system that have never raised troubles (Mac OS X), I decided to put the call to setsockopt within an #ifdef…#endif block. But what macros must be checked to determine if we are compiling under Windows, Linux, FreeBSD or Mac OS X? It turned out that this information is not easy to find on the internet.

By Googling and using the clever trick suggested in this Wikipedia page (i.e. call gcc -dM -E - < /dev/null to discover which macros are automatically defined by the preprocessor), I have been able to find the following macros:

• FreeBSD defines __FreeBSD__ (at least FreeBSD 7.x);
• Under Linux you must check either __linux or __linux__;
• Windows defines _WIN32. (this was easy, as it is clearly specified in MSDN).

I have had no need so far to find this information for Mac OS X. I suppose that the macro to use is something like __darwin,__Darwin__ or whatever.

Update: (2011/05/17) Predef has nice tables containing the preprocessor macros defined by many compilers and operating systems. Very useful!

Remote "tar" backups via SSH

My first "real" entry to this blog is an easy method I have found this morning to perform a remote "tar" backup using SSH. It should be general enough to be applicable under any Unix system (I have tested it on Mac OS X 10.5 and Debian Lenny).

The problem I had was the following:

1. I had a lot of data (~ 33 Gb) on computer "foo" which wanted to back up before formatting the hard disk and installing FreeBSD 7.2;
2. There was however not enough room in computer "foo" to create the .tar file (just 13 Gb);
3. Thanks to a colleague, I had access to another computer "bar" with lot of free space (~750 Gb).

I solved this problem with the following command:

tar cvz -f - ./ | ssh bar "cat > \

  backup.tar.gz"

The "tar" process will write the .tar.gz file containing data from the "./" directory into the pipe. The "ssh" sends whatever is written into the pipe to the "bar" computer, where a "cat" command will save the data into "backup.tar.gz". This results in the .tar.gz file being written directly on the remote computer.