nklein software

In response to my earlier post about hidden memory allocations, Jason Cornez pointed out how to rework my loop so that Allegro wouldn’t need to allocate memory. The new structure avoids using the summing keyword in (loop …) and doesn’t use the return-value from (loop …).

Now, the Allegro moved up in the rankings. All of the implementations (except 32-bit Clozure) ran slightly faster with this version. Allegro improved the most here though as its allocation/garbage dropped to nothing.

CMUCL compiled with 30 Notes. I should look into those some time. It still ran quite fast though.

Allegro definitely liked this version better. It kept from allocating anything.

For comparison, I am including the previous runtimes here as well:

In the original version of my Optimizing Lisp Some More article, I did a bad comparison between SBCL and Clozure. SBCL supports two different ways to declare the arguments to a function. Clozure only supports one of those ways. As such, my declarations didn’t matter at all to Clozure.

I updated that post with new numbers after putting in both types of declarations. Clozure was much closer to SBCL. I then decided to expand the list to include CMUCL, Allegro (Personal), Lispworks (Personal), ECL, and CLISP. I failed to get GCL or ABCL up and running on my Mac, and Scieneer CL isn’t available for the Mac.

As it turns out, the Allegro and LispWorks versions that I have are heap limited. Thus, they spent a great deal of time cleaning up garbage. To try to even the playing field, I reworked the function to take the ret buffer as a third argument so that allocation is no longer inside the timing loop.

Here are the results in terms of total user time, non-GC time, and bytes allocated:

As you can see, I failed to keep most of the implementations from allocating things (especially, ECL). Intriguingly, the 32-bit Clozure allocates a bunch where the 64-bit Clozure doesn’t seem to do so. It looks like Allegro would be pretty competitive if it weren’t using all of this extra memory.

I’m not sure why any of them are allocating with this code. Do they allocate loop counters? loop sums? function parameters? I may delve into the assembly of some of them at a later time. But, at this point, I’m just going to focus on those that don’t cons when I’m not looking.

In the previous article, I showed a chunk of code for multiplying a vector by a matrix. Nikodemus Silvola, on the sbcl-help mailing list, recommended that I change the matrix to a one-dimensional array instead of a two dimensional array.

Doing that takes me from ten million iterations in 1.038 seconds to ten million iterations in 0.645 seconds. That brings me an overall improvement of 14x from the original, untyped code.

Thanks, all!

For completeness, here is the final code:

To test this code, I made a ring of 4096 random matrices and a ring of 4095 random vectors. Then, I cycled through each ring as I iterated.

Making a random matrix is simple enough.

Making a bunch of them into a ring takes slightly more effort (in the form of tail recursion), but not much.

Today, I spent a large chunk of the day trying optimize a very small chunk of code. The code takes a matrix with three rows and four columns. It multiplies it by a vector that has three rows (and a pretend fourth row that is set to one). Here is the code that I started from:

I can do four million iterations of this function in 4.113 seconds. As such, it doesn’t seem like it’s necessarily the highest priority to optimize. But, my Lisp optimizing fu is not so great. This, being a small function, seemed like a good case study.

Compiler optimization without any type declarations

First, we’ll just see how it does if we ask SBCL to optimize for speed and throw caution to the wind.

The compiler spits out 38 notes telling me all of the stuff it failed to optimize for me. Then, it runs four million iterations in 3.944 seconds.

Type declarations without compiler optimizations

So, what can we tackle by declaring the types of the variables and the intermediate values?

Now, I can do four million iterations in 0.344 seconds. That’s better by a factor of eleven.

Both compiler optimizations and type declarations

Now, if I turn on compiler optimizations and turn off compiler safety:

With that, I am up to 0.394 seconds for four million iterations. I’m not sure why the compiler optimization slows me down slightly. So, I think I am going to nuke the speed request at the moment and call it a day.

Other Lisp Implementations

Justin Grant pointed out in a comment below that Clozure expects the declarations of types to be inside the function instead of externally as I did using the (declaim (ftype …)). So, the numbers in the following paragraph are slightly skewed.

SBCL cleaned Clozure‘s clock. The fully typed and optimized version took 6.272 seconds with 32-bit Clozure while the untyped, unoptimized version took 6.405 seconds. The fully typed and optimized version took 2.029 seconds with 64-bit Clozure while the untyped, unoptimized version too 2.129 seconds. It is hard to say how much of that is overhead with the one to four million loop.

CLisp took 158.738 seconds for the fully typed and optimized version. I didn’t bother letting it run the others.

Here are the numbers for the Lisps that I have running on my Mac with ten million iterations:

Interesting tidbits from the above:

• For the no declarations case, Allegro says it allocated -1,549,934,592 other bytes. I am assuming that it just crossed over and it really meant 2,745,032,704.
• LispWorks did about 40% better when I selected Compile and Load from the File menu instead of typing (load (compile-file “tm.lisp”)) at the REPL.
• I tried, but failed, to get GCL and ABCL installed. I may have to try those again some other time.
• Except for CLISP and ECL, the implementations all allocated significantly more memory for the no-decls case. SBCL allocated ten times as much in the no-decls case. CLISP allocated the same in all cases. ECL allocated 20% less in the no-decls case.

Important Lessons

I ran into all sorts of compiler notes and warnings and errors while trying to optimize this code. I was trying to use (SVREF …) to reference into an array. SVREF means simple-vector reference. I am not allowed to use it on an array. I hadn’t realized before that in a simple-vector, the elements are required to have unspecified type. For a vector or a simple-array, you can specify the type of the elements. For a simple-vector, you cannot. Richard Krueter, on the sbcl-help mailing list, set me straight.

My other big stumbling block was this. The following two lines mean exactly the same thing (they both create an array of three zeros):

If I wanted a multidimensional array, I would need to use the second form there and put a list of numbers in where the three is. For a one-dimensional array, I can use either the length as a number or a list with the length as its only element.

On the other hand, the following two lines mean very different things:

The former means that foo is a three-dimensional array of single-precision floating point numbers with the length of each array dimension left unspecified. The latter means that foo is a one-dimensional array with three single-precision floating point elements.