On 3/18/2012 8:32 AM, Stavros Macrakis wrote:
> Re efficiency of numerical Lisp vs. C and Fortran....
Good explanation.
Some of these issues can be addressed by extensions to the ANSI Common
Lisp language. For
example, Allegro has a bunch of features (maybe SBCL etc have similar
stuff) like this:
"foreign" types which can correspond to anything in C, e.g. structs.
They can be addressed, changed, allocated,
allocated in static space (that is, not subject to being moved in a
copying garbage collection), and they
can also be garbage collected. An array allocated in foreign space
could be addressed in the same
way (and host the same aliasing problems) as in FORTRAN.
Using these features allows the Lisp compiler, at least in principle, to
generate the same code for
array accessing, arithmetic, etc as FORTRAN, I think.
I think that as a language definition issue, it would be impossible as
you say for Lisp to assume
that it can cache the address of a lisp array between function calls,
but some memory references
(e.g. the ones that are needed for indirectly referencing an array) are
likely to be in hardware
cache, and so they are negligible in cost.
One trick in making Lisp and FORTRAN run at the
same speed may be to slow them both down by allocating and using huge
arrays... so that the cost
of full memory accesses dominates everything, and the little indirection
stuff is just a blip. But
this would be something of a cooked-up benchmark. And no, I haven't
measured this.
RJF
>
> I have over the years done some detailed low-level analyses of the
> /theoretical /efficiency of the various languages, based on the
> run-time models they require -- and assuming that the compiler
> technology is equally good (which it may or may not be).
>
> For numerical routines which pass many arrays as parameters, Fortran
> has traditionally had an advantage over C because any two pointers in
> C can potentially point to the same thing (aka aliasing). That means
> that after the sequence *p1 = 1; *p2 = 2, it is possible for *p1 to be
> 1, and so every assignment to *var (which is how array parameters are
> accessed) must be saved to memory (not kept in a register). This is a
> significant overhead if the inner loop of your code accesses more than
> one array. Fortran takes care of this problem by saying that arrays
> passed by reference can be assumed not to overlap -- even if you pass
> the same array in two different parameters. I believe more recent
> versions of C allow you to declare the same thing.
>
> 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 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.
>
> 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?
>
> -s
>
> PS Of course there are other issues like calling sequences. Fateman
> did a performance test of Lisp vs. Fortran arithmetic speed in the
> 70's which was dominated by PDP-10 Fortran's very heavy procedure call
> sequence (save all registers across calls).
>
>