Re: Numeric efficiency in dylan (or lisp in general)

[Scott_Fahlman@SEF-PMAX.SLISP.CS.CMU.EDU]

I agree with Jonathan Backrach that Lisp can be quite competitive with C in
terms of numerical efficiency.  I spend a lot of my time writing neural-net
simulation code (very float-intensive, and it runs for hours) in CMU CL.
The last time we measured, it was 10%-20% slower than the same code
hand-translated to C by a grad student and run through a first-rate C
compiler on the same machine.  That's close enough to eliminate any desire
I might have to switch this work to C.

I think that Dylan (some widely available implementations, at least) must
aim for comparabale performance if it is to achieve the goal of attracting
people who now program in static languages.  Many people just won't move
over if you tell them their code will run more than 2x slower, regardless
of how nice the Dylan environment is for development.  Runtime efficiency
is more measurable, and thus more real to people, than productivity gains.
That may be irrational in the age of ever-faster machines, but that's how
it is.  I'm not sure what the magic number is.  For me, a penalty of 20%
doesn't matter, but for this neural net code a factor of 2 would matter.

One source of inefficiency is Lisp's (and Dylan's) dynamic typing, or
rather the lack of sufficient type info at compile time.  But I prefer to
think of Common Lisp as having "optional strong typing": You can say as
much or as little as you want about the type of each object and slot.  The
more you say, the better job the compiler can do.  If you just say that an
object is of type <object>, that provides no information -- fine unless
it's in a performance-critical stretch of code.

A second source of inefficiency is the lack of provision for type-tags in
most current architectures, at least in floating-point numbers.  Everyone
has decided that 32-bit and 64-bit floats are standard, and that leaves no
room for a type tag in a 32-bit or 64-bit machine.  Stealing some bits of
the number to use as a tag is not a good solution in general, since it is
inefficient (you have to keep masking off and restoring those tags) and it
leads to problems with the rounding that is build into a good FPU.  So, in
the general case, you have to "box" floating-point numbers and allocate
them on the heap.  But our Python compiler already does a very good job of
avoiding number-consing if you provide enough type info at compile time.

The final source of inefficiency is from the ability to redefine things on
the fly: functions, classes, etc.  This means that some extra cost is
incurred at the seams between redefinable objects, usually in the form of
an extra level of indirection.  It also means that cross-function
optimizations are impossible (or greatly reduced in effectiveness).  This
is where Dylan's "seal it and ship it" orientation is going to be
important.  At some point, you will state that you're done with redefining
things, and ask the compiler to produce a module that has all the seams
welded shut.  If you later want to change something, you throw out that
whole compiled module and go back to the source.

Yes, we need an excellent call out to C for other reasons, but we should
not give up on the goal of providing excellent numerical performance in
(some implemntations of) Dylan.  I'm sure it can be done, and without
severely damaging the beauty of the language for less demanding
programmers.  It's fine with me if we put the whole floating-point package
in a library or optional facility, as long as we standardize what it should
look like if it is around.

-- Scott
===========================================================================
Scott E. Fahlman
School of Computer Science
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213

Internet: sef+@cs.cmu.edu