On 3/18/12 8:32 AM, Stavros Macrakis wrote:
>
> Lisp doesn't allow array parameters to be aliased, but when the same
> array is passed in two parameters, it has the same problem, so it must
> write array assignments into memory. Also, Lisp supports dynamic
> array resizing and (possibly relocating) garbage collection. This
> means that array references are double indirections (the intermediate
> cell can be changed by relocation). The actual array address can of
> course
For the one lisp I'm really familiar with (cmucl), 1D specialized arrays
don't have this problem. But all other arrays types have this issue.
> be cached in many cases, but the compiler can't assume that it is
> stable across function calls-- in the sequence ar[1]<-1; b<-cons(...);
> ar[2]<-2, the compiler cannot assume that the address of ar remains
> the same. I don't know of any way around this, but I am certainly not
> aware of all Lisp implementations' tricks.
>
For cmucl, this isn't a problem because the GC knows how to collect
items in registers. So if ar is in a register, you call some routine
which causes GC, and ar moves, the GC will update the value in the
register so it now has the correct new address of ar. So nothing needed
by the compiler.
> Now, how much overhead can you expect from all this? I would think
> that in the very worst case, we're talking about a factor of 2, and
> not a factor of 10, but I have not measured it. Has anyone?
>
While Michel rightly complains about how slow colnew (translated by
f2cl) is, it is not so simplistic as blaming lisp. The slowness comes
from several areas. One major factor was the need to call from Lisp
back into Maxima to compute the various functions and the need of
marshalling the lisp arrays to and from Maxima lists. There's also the
issue with array access and how f2cl (and lisp) has to handle Fortran's
array slicing, which runs into the issue you mention above. But these
are not the only issues. The translation itself is much slower than
fortran because I've run some of the demo programs from colnew and they
are quite a bit slower than fortran.
I've been too lazy to track this down, but several years ago, I worked
with Richard Fateman on a paper. As part of the work, we took Brent's
mpfun package in Fortran and converted it to Lisp via f2cl. The test
was computing pi to thousands of digits. Lisp was much slower (10x?).
This was partly due to the translation, but mostly due to the fact that
Fortran could assume things didn't overflow (or you didn't care), but
Lisp couldn't. So the bottle neck was in truncating floats to
integers. Fortran assumes the result fits in a fortran integer. Lisp
had to assume a bignum. With a few careful declarations, we got lisp
down to around 2x slower, maybe less. Some further optimizations in
inlining simple (lisp) functions got it down more. This helped a lot
too. And finally fixing the very badly converted print function (which
used to take minutes or hours to print out 10000 digits of pi) made the
test program quite reasonable compared to Fortran.
I don't know colnew could be made to be only 2x slower, but there is
certainly room for improvement, but it certainly can't be as fast as the
Fortran version, even if we called out directly to the Fortran code,
simply because there are a lot of calls back into Maxima, which is slow.
Ray