Linux Goodies

In Pursuit Of The Perfect O/S



A Comparison of Some Matrix vs Non-Matrix Computer Languages

A Comparison of Matrix vs Non-Matrix Languages

On the Head 2 Head web page I compared a number of matrix style math languages. In that article I compared their programming styles and speed. The speed test compared them with an imaging processing task that made use of their matrix manipulation abilities. The problem at hand was to align dozens of frames of some astronomical images to produce an optimal image. The problem wasn't purely vectorizable, in that some looping was necessary, but the looping times were swamped by the amount of math done in the matrix routines.

On this web page, I compare a few of the matrix languages with some non-matrix oriented languages, and the problem is one that again is not easily turned into a straightforward vector problem. In fact, this problem was such that the time spent doing the math didn't swamp the time it took the languages to do all of the required looping. The test turned up some surprises for me, and hopefully will surprise you too.

In this case, the languages compared were the following Matrix languages:

Perl PDL

and some non-matrix languages:

Linux C
Interpretive Chicken Scheme
Compiled Chicken Scheme
Forth 79 (author-constructed)

I thought this task would be an interesting problem because it put most of the languages outside of their comfort zone, that is the problem type area where they excel. Yet the task was a reasonable one. That is, the task was not contrived, but a task like many I've used many times in the past to generate test data.

The task in this case was a flight path generation program. The program uses some initial conditions, like position, acceleration, max G's in a turn, etc., and way-points. The way-points are simply locations that the hypothetical airplane is supposed to fly to. At each way-point, the airplane logic must make heading and altitude and perhaps speed adjustments to get to the next way-point. Of course these adjustments require changes in roll and pitch. It's these adjustments and how they affect one another that made the problem not easily vectorizable.

The program I've constructed is not particularly high-fidelity, but does exercise significant math in the solution, which must be done in an incremental way. Involved is also some coordinate transformation which involves some vector application.

So as with the Head to Head web page problem, there is necessary looping done even in the matrix oriented languages. But unlike the Head 2 Head web page problem, in this case the looping to math ratio puts the matrix languages a bit out of their element. Matrix languages are designed to work very fast on large matrices of data when the looping is all done in the internal matrix routines. That wasn't possible with this problem.

I threw in a mix of non-matrix languages to see how they would compare to the matrix languages, when the matrix language solutions had to be coded in a less matrix style. The mix I used included the venerable C language, the only language not at a disadvantage with this problem, and some popular interpretive languages.

I had to extend the way-point list to force the programs to compute several cycles of the flight path in order to get measurable times. In each case the programs computed position, velocity, and attitude once per second for a several hour pseudo-flight path. The resulting computational times are as follows:

Flight Path Generator Tests

Language Seconds
C 2
Gforth 4
Forth 79 7
Yorick 8
Scheme Compiled 20
Scheme Interpreter 76
Euler 90
Perl 324

Flight Path Speed Test Chart

The Result Conclusions

What are the surprises? Certainly not that C won this contest. As I mentioned before, C was in no particular disadvantage in this problem. It didn't need complex memory management, and for C it was just business as usual, read a bit of data, loop through some equations, and output the results. Quite a few equations, but nothing unusual for a C program. It scored big, taking only 2 seconds to compute a flight profile of some several hours.

But Perl taking over 5 minutes was a surprise. The PDL Perl extension was used to the degree possible, calculating a number of vectors during the run. But there was much programmatic looping, for which the PDL offered no help.

Euler was a bit of a disappointment, at 90 seconds. Euler is quite competitive when a problem can be vectorized, but in this case where it had to loop over equations Euler wasn't so fast. Clearly not as slow as Perl in this case, however.

I was surprised at the compiled Scheme. The Chicken Scheme interpreter did about what I'd expect, taking some 76 seconds to solve the problem. But the compiled Scheme, running over 3 times faster than the interpreter, was significantly slower than the Forth systems.

Yorick did a respectable job. Yorick is a matrix language, and its more competitive type of problem is a vectorizable one. In fact, if you check out the Head 2 Head web page, you'll see that it was the fastest language tested there as well, doing a mound of matrix manipulation about 3 times faster than any contenders. Remarkably, even on this problem not optimal for matrix oriented languages, Yorick did a respectable job.

The big surprise to me, aside from the slowness of Perl on this problem, was the speed of the Forth languages. The Forth79 program, as I mentioned, is one I wrote using a FIG Forth manual as a guide. But I wrote my version in C rather than assembly language so that I could have solid floating point support. I did do what I could to make the looping portion of my Forth compiler fast, and it competed quite well. In fact, my lowly Forth79 system with its pseudo-compiler out performed compiled Scheme by nearly a factor of 3.

Gforth did even better. I'm not surprised that it outperformed my home-grown Forth. It is honed by a team of experienced programmers to be fast, and they've done a heck of a job. The compiled C program only beat the Gforth program by a factor of 2.

What conclusions can one draw from this test? Not a lot, as a single test. But is is a test on a rather typical math program, not a contrived set of operations. It may show why in the general programming world, Forth still has some steam while Scheme remains mostly in universities as a teaching language. It may give one pause if they believe Forth is only good for real-time instrument control. I've used Forth for all kinds of work over the years, from the typical instrument control to data reduction to even some kinds of things one might use BASH for, as Forth is scriptable in the same way.

It also certainly shows why C is the backbone of operating systems, and many languages are built with it.

It also shows that the big strength of matrix languages is with problems that can be vectorized, meaning problems that can be expressed as a series of matrix equations, with little looping done in the interpreters themselves.

It shows that as amazing as Perl is, combining language elements from both conventional languages like C with the list processing languages like Scheme and Lisp, that it too has some areas where it doesn't shine. It's a text file manipulator deluxe, and a matrix math language as good as any other. But when forced to do math without much support from the PDL extension, it performed poorly.

What this test doesn't show is the style of the different languages, and some of them have distinctly different styles from typical mathematical languages like Fortran or the popular matrix languages. I selected a particular equation out of each program listing just to show the flavor.

C Language
dhead = fmin(fabs(dturn),fabs(Heading_Err)) * sign(Heading_Err);

Yorick Language
dhead = min(abs(dturn),abs(Heading_Err)) * sign(Heading_Err);

Euler Toolbox
dhead = min(abs(dturn),abs(HeadingErr)) * sign(HeadingErr);

Perl PDL
$dhead = fmin(abs($dturn),abs($Heading_Err)) * sign($Heading_Err);

dturn fabs    Heading_Err fabs    fmin    Heading_Err fsign   f*    f=> dhead

(set! dhead (*   (min (abs dturn)   (abs Heading_Err))   (sign Heading_Err)))

Notice that C, Yorick, Euler, and even Perl show equations in an algebraic form similar to how one might write an equation. Perl does have the sigils (dollar signs) on the variables to indicate their type, but is otherwise algebraic in notation.

Forth uses a post-fix notation, with variables and values entered first, followed by the respective operation(s). All long equations in any language are made clear with some extra spaces here and there. It helps even more if Forth and Scheme programs use extra spaces between variables to make them read better. In the Forth code, the f=> symbol near the end is the store operator. The f on the front of each operator in the Forth equation indicates floating point operation.

To me at least, Scheme offers the least obvious equation form. It's a pre-fix language, and each operation is preceded with a left parenthesis. Each left parenthsis is eventually closed with a corresponding right parenthesis. With things being rearranged to make use of this form, and with the multiple parentheses, I and many others find that a bit distracting. Others more used to the syntax seem to easly see through it.

Of course the difference between languages isn't just whether they are algebraic, pre-fix, or post-fix in nature. The languages have some more fundamental differences which make them better or worse for attacking specific problems.

Keep in mind this is just one test case. It won't tell you what language to use for your problem solving, but it when combined with the Head 2 Head comparison, does give some insight into where these languages excel -- and where they don't.