Re efficiency of numerical Lisp vs. C and Fortran....
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).
On Sun, Mar 18, 2012 at 11:05, Richard Fateman <fateman at eecs.berkeley.edu>wrote:
> On 3/18/2012 3:54 AM, Michel Talon wrote:
>
>> Akshay Srinivasan wrote:
>>
>>> On 03/18/2012 02:20 AM, Richard Fateman wrote:
>>>
>>>> You mention AD (automatic differentiation). Have you seen this?
>>>>
>>>> http://www.cs.berkeley.edu/~**fateman/papers/overload-AD.pdf<http://www.cs.berkeley.edu/~fateman/papers/overload-AD.pdf>;
>>>>
>>>>
>>>> Yes, well sort of, I remember that I didn't read the paper completely
>>> or try the source code though.
>>>
>>> I think the trouble is, as it is now, I don't think I can rely on
>>> Maxima for doing efficient numerical calculations, and there really
>>> isn't a very usable lisp alternative for something like NumPy,
>>> although Matlisp comes close.
>>>
>> Are you saying that NumPy is efficient? Or that you like its user
> interface? Or its scope?
> The efficiency of numerical calculations in Lisp is heavily dependent on
> the particular
> implementation. CMU-CL or SBCL, among the free lisps, should be pretty
> good.
>
>
> Indeed, from my experience with colnew, i don't think that Common Lisp
>> may really be used for extensive numerical computations, contrary to what
>> is claimed by lisp evangelists.
>>
> With GCL? Also, there is a certain loss inherent in the f2cl, if that was
> used. For example,
> the result of a fortran call by reference is mimicked by a multiple-value
> return, and there may
> be other issues too.
>
> Knowing how well NumPy works, i think
>> like you that the solution is to allow convenient translation of the
>> numerical
>> intensive work from maxima to Fortran or C, automatic compilation of this
>> code
>> and linking in the maxima process.
>>
> This has been a long-time traditional way of dealing with the issue.
> Actually, C was traditionally
> less favored compared to FORTRAN because the optimization of FORTRAN was
> more
> sophisticated (e.g. loop unrolling, code motion, common subexpression
> optimization....).
> Either C has got this kind of stuff too, or no one cares. Consider the
> possibility that, if you
> are not wedded to portability, you can generate assembler (from lisp
> directly)!
>
>
> Automatic translation can be helped by
>> primitive programs like fortran (or my cgrind), but also by more
>> sophisticated
>> ones like contrib/gentran.
>>
> Yep, original Gentran and related stuff is decades old.
>
> Dan Stanger has recently contributed work to
>> gentran so i think it works now on recent Maxima, at least up to producing
>> fortran code. As far as i remember some work is still needed for
>> producing C
>> code. If you are interested it should not be difficult to do: by
>> comparing an
>> old version of gentran and a recent one you will see what Dan
>> has done to make fortran generation work. Basically the point is that
>> gentran
>> has been written for old versions of lisp, and needs some adaptation to
>> work
>> with sbcl, cmucl, etc. gentran is *very* sophisticated, it can translate
>> whole
>> maxima programs to fortran programs (resp C) including the logical flow
>> operators, etc. so i think that with some polishing and testing, you have
>> here
>> a tool which is as least as sophisticated as anything existing for python.
>> Arranging things so that gcc is invoked on the code produced from within
>> lisp
>> is probably trivial. Arranging that the object can be linked into maxima
>> is
>> perhaps less trivial, this has to do with foreign function interface in
>> lisp,
>> which apparently may have variations from lisp to lisp.
>> Unfortunately there
>> are several Common Lisp variants, with differences in the non normalized
>> parts
>> of the language, but fortunately it seems that sbcl emerges as the only
>> widely
>> used variant, at least in the free software world, which may help creating
>> equivalents of NumPy working with sbcl.
>>
> There is some attempt, CFFI, which I have not used myself, to standardize
> foreign function interfaces.
> My understanding is the GCL doesn't allow this. If SBCL truly runs on
> Windows, (for which there
> seems to be some issues), that would help. I personally solve these
> issues by not
> using "several Common Lisp variants" but only one.
>
>
>
>>
>>
>>
>>
>> Ray and I have been incorporating new stuff into Matlisp though,
>>> hopefully that will mature into something that I'd be happy using.
>>>
>> Great! I'm a fan of Matlisp, at least in principle; I haven't used it
> myself :)
>
>>
>>> Akshay
>>>
>>
> ______________________________**_________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/**mailman/listinfo/maxima<http://www.math.utexas.edu/mailman/listinfo/maxima>;
>