Re: following up on speed

[Ken Anderson <address@hidden>]

At 04:32 PM 7/18/2002, Michael Vanier wrote:
>...
>Parenthetically, I gather that one trick lisp programmers use a lot is to
>rewrite code to minimize allocations (consing), but that this is typically
>done as an optimization after the code is working.  Maybe some of the lisp
>gurus on the list can comment further on this.

Yes.  Paul Graham mentioned that Arc would have a profiler to help in this 
kind of optimization, and i have used Lisp profilers very 
effectively.  While you can often improve things after the code is written, 
it helps to have started with a good design.

We have had a Lisp program used for military transportation planning since 
1990.  Various phases of its operation have been profiled and optimized 
over the years.  Optimizations include

- reorganizing database access to go to the database less often and for 
more data
- reshaping objects.  For example, on 96 field object only had small 
subsets of fields actually used in a particular instance, so we squeezed 
out all the unused fields.
- Adding declarations, usually to avoid float consing.

Here are two papers that describe the profiling and optimization of 3 Lisp 
programs and compares them to their C counterparts:

http://openmap.bbn.com/~kanderso/performance/postscript/courage-in-profiles-ppt.ps 
(slides only, sorry)

http://openmap.bbn.com/~kanderso/performance/postscript/courage-in-profiles-ppt.ps

The papers are concerned with overall performance rather than comparing GC.
However, in one case, consing was reduced by a factor of 40 in the Lisp 
version.  Ultimately, it was 8 times faster than the C version which spent 
30% of its time in malloc/free while the Lisp version only spent 13% in 
cons/GC.

Getting the declarations write can be tricky.  While the compiler can 
suggest that declarations are possible, it would be nice if it could put 
them in for you!

>However, I agree with you that it's often more difficult to understand the
>exact execution model in languages with GC (or any high level language for
>that matter) than it is with C.  I think this is a large part of the
>attraction of C for many programmers; no matter how hard it is to get
>things working, you know that (in theory) you can understand how everything
>works right down to the machine level if you need to, something which is
>pretty hard to do in most high-level languages.  That's the price you pay.

See Bently, Kernighan and VanWyk, "An elementary C cost model", Unix 
Review, 9,2,p.38-48.  When they asked their friends to rank order the 
performance of code fragments, they got wildly different estimates, and 
their friends are C experts!  On todays machines my guess is that even in C 
it can be hard to predict what the effect of a change will be.

I certainly agree that higher level languages make understanding 
performance more difficult.  In Lisp, you never know what optimizations are 
being done unless you disassemble the code.  In Java, you can't even do 
that.  Even though i can see the byte codes i don't know what HotSpot will 
do with them.
I wish i could!

k