I was looking through some garnet infor the other day and found the
following in an FAQ :

    [12] Why the change to C++?

    <snip>

    * Speed: We spend 5 years and lots of effort optimizing our Lisp
      code, but it was still pretty slow on "conventional" machines.
      The initial version of the C++ version, with similar
      functionality, appears to be about THREE TIMES FASTER than the
      current Lisp version without any tuning at all.

When I look at lisp code versus C++, I really don't see how compiled
C++ can run 3x faster than compiled lisp.  But I have to believe that
the people on the garnet project knew what the hell they were doing so
this statement seems to be outrageous - (5 year) optimized lisp code
is 3x slower than the first try at C++ ?!

Can anybody elaborate on the FAQ statement ?

I'm just interested in performance issues. C++ is a mess and I really
don't see why an optimizing lisp compiler wouldn't be able to keep up
with an optimizing C++ compiler.

When it comes to OO sorts of things, I CAN see that CLOS introduces a
nasty amount of overhead as opposed to C++ where you just toss
function pointers around.

Any reasonable, insightful, comments ?

Is it really possible for code coming from one language to run slower
than code coming from another language? This is really a silly idea if
you think about it.

The problem is probably that the Lisp code was doing more work than
the C++ code. The percieved difference in speed may come from the
distribution of work; some people think the compiler should do it, and
other people think they have to do it.

If I were to write 300 lines of code in language x versus 1000 lines
of code in language z, I would like to think that the 1000 lines of
code was doing more work than the 300 lines of code. I don't know if
other people would feel similiar, this is just how I think I would
like to feel.

Consider the following C code.

[ I would show C++ but I don't have a C++ compiler - I saw `cout' being
shifted "Hello world" times to the left and stopped right there (I was
told that C++ was compatible with C, hence the assumption). ]

char
index_array (char *s, int i)
{
  return s [i];

(defun index-array (string index)
  (write (aref string index)))

(let ((i 1)
      (array (make-array 100)))
   (fill array 65)
  (index-array array i))

Both operations took about the same amount of code, and they yeild the
same result.

The lisp compilers I am familiar with generate _extremely_ efficient
code (from what I understand of how my machine works at least). My
experience is that C code seems to execute in less time because it
does less work, not because it can do the same work in less time.

The real question is probably one involving your value of time, but I
imagine people tend to get upset when thinking about this.

< When it comes to OO sorts of things, I CAN see that CLOS introduces a
< nasty amount of overhead as opposed to C++ where you just toss
< function pointers around.

a) The "first try" at C++ of course wasn't really a first try.  It had
   the experience of at least 5 years of Lisp optimization and usage
   of Garnet.  With that amount of experience with a system, any kind
   of complete rewrite is going to fare much better in terms of speed,
   since you already know many of the bottle-necks, and you know which
   seldomly-used features you can sacrifice to gain much in speed.
   Many of these optimizations are out of the question for normal
   maintenance, because they either break compatibility, and/or it
   would require too much work to rewrite large portions of your
   code-base.

b) C++ _forces_ you to micro-optimize most things, because you are
   directly involved in nearly all low-level decisions.  In writing
   new code, this often gobles up so much of your time, resources and
   attention, that it leads to micro-overoptimization, whilst
   macro-optimization, code quality, progress, maintainability,
   etc. suffer.

   When you are rewriting a well understood, stable toolkit, some of
   the downsides of this decrease, whereas advantages increase.

c) The C++ version is _very_ unlikely to be really comparable in terms
   of functionality, clarity or extendability.  For example I don't
   see any way they could have implemented their prototype-based
   object system on top of C++ in any kind of reasonable way.  Doesn't
   mean there is no way, just that I can't imagine one, which could
   just be my missing imagination again ;).  So most likely they will
   have switched to C++ built-in object-system, which of course
   changes things quite a bit.

Of course, not knowing the C++ version of Garnet, and not knowing
Garnet in-depth, all of my comments should be taken in perspective.
OTOH most of this is generic reasoning...

Regs, Pierre.

I agree with what you say here as well. I'll take your point about the
low level of C++ as an opportunity to point people to
http://www.elwood.com/alu/table/performance.htm#language, (and indeed,
the whole of that page).  As a teaser, I'll include here what I think
are the most important points about performance in Lisp versus other
languages -- points which I'd like to know that everyone who reads this
newsgroup understands (and I'm happy to think that practically all do):

"...
If it is easier and faster to program arbitrary applications in Lisp
than in some other languages, then, too, it is easier to program
inefficient programs in Lisp. ...
In Lisp, it is easy to obscure implementation details while making the
programmer's intent clear. This can lead to productive, clear, easily
maintained code, which may, sometimes, be inefficient.

In other languages, it is easy to obscure the programmer's intent while
making the
implementation details clear. This can lead to efficient code which may,
sometimes, be unclear, unproductive, or even incorrect."

Coming from a hardware background myself, I grew up learning the
importance of the prototype, and have always been aware of the truth
in the adage "Always throw the first one away".  I am a bit surprised
at how few programmers buy in to this truth, especially given how
easy it is to change software relative to hardware (yes, even C++)
[perhaps not as true as it once was, in this throw-the-old-chip-away
era, but it was certainly true 20 years ago; the equivalent of the
chip filled a room back then, and it was certainly not an option to
throw it away].

I believe that lisp's reputation for being slow comes about for
precisely this reason; it is so easy to prototype in lisp, and the
result looks so deceptively like the desired final results that it
is easy to just skip the step of rewriting it, and start heading
for production.  Thus, it is easy to ship prototype code.  And,
somewhat ironically, it is easy to write high-quality code using
a terrible algorithm (or, not knowing the problem space, the wrong
algorithm), so it is usually harder to recognize a prototype, or
for the developer to recognize that it must be re-written.  So a
lisp project may go into production for 3, 5, 10, or more years in
the prototype stage.

The LOOM project, btw., makes a similar statement about
their new "language" Stella, which can be compiled to
Lisp or C++. The C++ code runs ten times faster, they claim:

http://www.isi.edu/isd/LOOM/Stella/index.html

----

I remember the situation with MCL.
Years ago people started to develop big Lisp software in MCL
on 68k Macs. You really needed a high-end Mac (68040, lots of
memory) to get something done with these *big* (prototype)
software systems - and it was really expensive.

Then came the PowerPC. I got a machine with a PowerPC 603e.
It was slow, slow, slow. Two years later I got a new one.
*Ten* times faster -> Lisp screams.

There are only few excuses not to use Lisp nowadays.
Speed is not one of them.

Combine that with better GC in CMUCL, and you've probably coveredmost of the 3X performance
gap stated in previous posts.

----------------------------------------------------------------

An idea is a greater monument than a cathedral.

    John> I seem to remember that Garnet built using CLISP with Bruno
    John> Haible'shomebrew CLX is about twice as fast as using
    John> standard CLX.  I'm sure the optimized CLX implementation
    John> would be portable to CMUCL.

I'm pretty sure the the optimized CLX for CLISP is not portable.  It
was rewritten in "C" expressly for CLISP.  I think someone has used
the FFI in GCL to hook up directly to X.  That would be pretty fast, I
guess.

    John> Combine that with better GC in CMUCL, and you've probably
    John> coveredmost of the 3X performance gap stated in previous
    John> posts.

On x86, there's a gengc.  I guess it's good, but I don't know how
good.  I find Garnet to run fast enough on a 200 MHz x86 box.  It's
fine on a Sparc 20 too.  Well, at least the demos run reasonably
fast.  I don't have any "real" heavy-duty Garnet apps to test.

    Rainer> http://www.isi.edu/isd/LOOM/Stella/index.html

But aren't some of the things they claim also wrong:

        Common Lisp provides a very supportive environment for the
        development of symbolic processing applications (e.g.,
        ``intelligent'' applications). However, Common Lisp has
        several drawbacks: Its performance is slow (as compared to a
        C++ program); it does not interface well to tools and
        applications in commercial environments (e.g., to C++ and
        CORBA); and it fails to incorporate recent object system
        trends (e.g., collections, iterators, and parameterized
        types). As a result, customer demand and vendor support for
        Lisp is declining, creating yet another reason to abandon
        Lisp.

Lisp has CORBA right?  

I also think interfacing anything to C++ except C++ is quite hard, so
that's a moot point.  

Doesn't lisp have collections and iterators (of some sort)?

I'm not sure about "parameterized types".

Of course like any adage or truism, the one above is a generalization,
and one can always find circumstances in which the adage is false.
However, it is intended as a way to shake people out of an opposite
state of thinking.  Another way to put it is "Don't hang on to the
first thing you did."

As for the definition of "prototype", my dictionary says "1. An original
model on which something is patterned".  In other words, the first
time you build anything, it is by definition a prototype.  However,
I submit that lispers prototype constantly, and that every time you
type "(defun foo () ...)" to the prompt, you are prototyping something
that you _intend_ to throw away (otherwise you would have put it into
a file!).  This prototyping becomes so ingrained into lisp programmers
that they may not even realize they are doing it (or may find it hard
to explain how they can be so productive to a C++ programmer, who in
general doesn't have this instant-prototyping capability).

[I observe that programmers, myself included, tend to be overly
optimistic in the way they estimate times for a project; it is
not that we are bad planners - a bad planner might estimate two
weeks for a two month project and 4 months for a three-week
project; it is instead the case that we are consistently over-
optimistic.  And of course no manager wants to hear the bad news
regarding schedules; they always want to hear good news.  But if
they hear bad news from someone they know can and has done the job
on time in the past, they tend to be much happier than when they
hear good news from someone that they know they are going to have
to plan "slop" time for.  And for those programmers who gain the
reputation of getting work done on time, the subject of prototyping
should rarely even come up.]

Secondly, perhaps they were also evaluating on obsolete machines. I'm
running it with ACL/Linux on a 486 with 16MB and it is fast enough for
what I'm doing with it so any more modern machine shouldn't have too
many problems.

  since I recently said I don't believe in prototypes, let me clarify and
  expand on it: I don't think one should write software with the conscious
  intent to throw it away.  instead, you should be prepared for that
  outcome, but work to make it the real system.  after a while, you _may_
  find that certain areas of the application domain were underresearched
  and find it easier to start over, but people who work on software that is
  known to become junk get quite disillusioned, and managers never give
  them the resources they need to make the prototype useful to learn from.
  instead, the first _real_ version will be the prototype that they wanted
  the prototype to be: the one from which they learn what they were really
  trying to do, so the prototype is a waste of time and money.

  add to this that many a manager feels this way about paying for software
  that isn't going to be the real thing and associates bad things with
  "prototype".  since so many are quick to point out that Lisp is great for
  prototyping, the message is that Lisp is a great choice if you want to
  waste time and money.  I think it's the other way around: if you are free
  to make all sorts of changes to the design with little impact on the
  system, what you end up with has probably learned all there is to learn
  from the iterative process that otherwise would have involved several
  languages, teams, and project managers.

  my experience is that well-written Common Lisp is more space and time
  efficient than well-written C++, but not so with well-written C in which
  you basically hard-code every assumption and thereby win big.  enter a
  lot of dynamic memory, and C also loses to Common Lisp, not the least
  because malloc/free are hopelessly ineffecient in both time and space.

|       it does not interface well to tools and applications in commercial
|       environments (e.g., to C++ and CORBA);

  I'm sure this was true once.

|       and it fails to incorporate recent object system trends
|       (e.g., collections, iterators, and parameterized types).

  these are specific implementations of "inventions" required in C++
  because it doesn't have what people _actually_ need.

|       As a result, customer demand and vendor support for Lisp is
|       declining, creating yet another reason to abandon Lisp.

  I think "creating" here should be read literally, they literally had to
  create a reason to abandon Lisp...

| Lisp has CORBA right?  

  there's the ILU, and Allegro CL ORBlink.

| I also think interfacing anything to C++ except C++ is quite hard, so
| that's a moot point.

  well, Allegro CL does that, too.

| Doesn't lisp have collections and iterators (of some sort)?

  we have mapping functions, which are much more powerful than iterators.
  collections?  what's a list if _not_ a collection?

| I'm not sure about "parameterized types".

  I see STRING in (coerce <whatever> 'string) as a paremeterized type.

  there are still some valid reasons to reject Common Lisp.  I find it
  rather curious that people don't use them.

  um, no, not quite.  I don't believe it is possible to do anything right
  until you know what "right" means, and this is not available a priori,
  despite what all the lectures in programming methodology and systems
  design would have poor students believe.  (if it was, we would have had a
  perfect society, too -- law is nothing more than programming society, so
  if it were possible to plan for everything, it would have been worked out
  many millenia ago.  I'm amazed that people think large-scale experiments
  in top-down design like dictatorships and planned economies would fare
  any better in any other endeavor involving creative people.)  therefore,
  you have to go through various iterations, and your design must be
  prepared for this, but that is not to say that you should _not_ expect
  success, or actively prohibit it.

  the issue I want to raise is whether people should approach the first
  version with "let's try to get this right" vs "we're going to throw this
  one out, so let's not waste too much resources on it".  the whole point
  with wasting the first version is to waste _only_ the first version, at
  worst.  people who set out to do something that will be a waste in the
  eyes of managers who cannot understand why their employees do not know
  enough to get it right the first time, will _not_ learn all there is to
  learn and will _not_ ensure that only the first version gets wasted, but
  will waste version after version.

  now, if they do get he first version right, and don't need to waste it at
  all, that's a very commendable result, but if you only set out to
  "prototype", this is no longer an option, either by choice of language or
  tools or something else that everyone knows was intended to be wasted,
  and would feel bad if it were to go into production.  that's what I think
  is wrong about using specific languages to prototype things and talk
  about a language as "good for prototyping".  it is invariably understood
  as "not good for production code".  I have to fight this impression.

  in conclusion, it is hard enough work to it right the second time when
  you have all the data from the first try available if you should not also
  have to do it a third time because you weren't _allowed_ to go all the
  way in the first attempt.

| Another way to put it is "Don't hang on to the first thing you did."

  my argument is that the reverse is equally valid: don't _always_ throw
  out the first thing you did.

| However, I submit that lispers prototype constantly, and that every time
| you type "(defun foo () ...)" to the prompt, you are prototyping
| something that you _intend_ to throw away (otherwise you would have put
| it into a file!).

  ok, that's the gist of your disagreement.  I think intent to throw away
  is the bad part about prototyping.  throwing away is something you should
  be prepared to do without much concern, but you should strive to make it
  usable, too.  if you intend to throw it away, the threshold to keep it is
  set too high.  now, what if it actually does work the way you wanted it
  to?  do you still throw it away?  if you prototype in Lisp and write
  production code in C, you would have to, right?  that's bad.  not only
  because doing something you have already done over again is stifling, the
  problems in C are different from the problems in Lisp and you have to do
  a lot of redundant work.

| The world is full of programmers stuck on their own dinosaurs because
| they won't let go.

  well, letting go is as much a part of caring about something as not
  letting go.  sadly, our cultures are built by people who couldn't let go,
  so everything around us is shaped by an unhealthy conservatism, and
  because people are afraid of having to suffer as much pain every time
  they manage to get something to work somewhat right, we have a lot of
  stuff that were shaped by a trial-and-error process that stopped as soon
  as the errors were tolerably small.  had people been able to let go, and
  use their knowledge from what failed, perhaps we could move on.  in my
  view, the patent system was supposed to let inventors capitalize on the
  works of others and make _significant_ improvements, while the patent
  effectively forbade the meager insignificant improvements.  a wonderful
  mechanism that should be applauded and made much stronger, it has turned
  into a monster that stifles innovation by admitting overly broad and
  senseless patents, instead because the wrong kind of people approve
  patents.  this is just another example of how society is shaped by
  conservatives who have no clue _what_ they are conserving, only that
  change is bad.

| In which case you have already rewritten (at least parts of) your
| application several times over.  But to be free to do this rewriting, you
| have to have made a correct estimate of how long the project will take.
| If you factor in the prototyping (call it "learning curve", or "concept
| development") time, you will have the time to do this.

  ironically, you always have time to do that, despite what everyone says.
  the key is to get something to the point where it does not fail, and then
  you can change everything as long as it continues not to fail.  people
  always have time to improve things, and they embrace things get improved
  in oh so minor ways.

| But if they hear bad news from someone they know can and has done the job
| on time in the past, they tend to be much happier than when they hear
| good news from someone that they know they are going to have to plan
| "slop" time for.  And for those programmers who gain the reputation of
| getting work done on time, the subject of prototyping should rarely even
| come up.

  well, there's often a "fuzz factor" you can add to or multiply with what
  people say.  a good manager learns the fuzz factor and doesn't want to
  change it.  some programmers get all the big work done in the first few
  days and then spends a lot of time fixing minor bugs, while others tinker
  with fundamentals 95% of the time and whip up a marvelous piece of art in
  the last few days.  the key to managing is to understand what you deal
  with, and programmers are predictable _one_ at a time, even when they are
  (supposedly) part of a team.

  incidentally, getting something to work is child's play.  where you need
  the expertise is in not making it fail, or fail gracefully.  and I don't
  think a prototype that only shows how it works is useful at all, since
  you learn nothing about surviving the failure modes by having something
  that only "works".

  anyway, I like Common Lisp because I can write enough serious code in it
  to watch how it actually deals with a hostile world (specifically, socket
  code that distributes functionality across hundreds of computers over
  thousands of little stretches of cable and routers that people upgrade
  and add bogus routes to and all kinds of shit) and then rewrite it before
  the hostilities resulted in harming anything.  also, Allegro CL is the
  first environment I have used which allows me to use all I know and learn
  about the hostile world without writing tons and tons of code.  when
  something causes a crash only once a year, you ignore it in C because it
  might change your whole design and basically send you back to the drawing
  board for a year to deal with it, and then you suffer a crash once a
  year, so it isn't worth the costs.  it might take a week or a month to
  redesign to survive such a problem in Common Lisp, but you can actually
  offord to take care of it.  this means that the next time you have to
  deal with this kind of problem, the competent Common Lisp programmer gets
  it right, while the competent C programmer still doesn't know what it
  would take to solve that particular problem because he hasn't been there.

    Duane> In other words, the lisp version was a prototype.

    Duane> Coming from a hardware background myself, I grew up
    Duane> learning the importance of the prototype, and have always
    Duane> been aware of the truth in the adage "Always throw the
    Duane> first one away".  I am a bit surprised at how few
    Duane> programmers buy in to this truth, especially given how easy
    Duane> it is to change software relative to hardware (yes, even
    Duane> C++)

 You make some very good points, IMHO.  The fact that the C++ version
 was developed AFTER 5 years of tweaking lisp code had to have had a
 major impact.

 Along these lines, it's interesting that I haven't really seen any
 good guidelines for coding for speed in lisp or scheme.  Anybody have
 some goo d pointers to books or webpages ?

Brian

--

You can obviously create classes where the actual contents are in a
slot, or write functions that perform iterations on arrays beyond
vectors.
Still, it is difficult to say that CL has explicit and thorough support
for collections and iterations.  I agree with those saying that in CL
you do not need this as much as in other languanges due to its power and
flexibility, and it is often trivial to create collections atop of
classes, structures, arrays, hash tables and lists. It is not
show-stopper by any means.

Well, if you want the word of someone with VERY limited experience, I would
recommend Norvig's "Paradigms of Artificial Intelligence Programming."  He
has a couple of excellent chapters on efficiency issues.  Actually most of the
book could be considered something of a style guide, or Guide to Writing Good
Lisp, because of the way that Dr. Norvig takes complex problems (from the
AI community) and describes the process of writing solutions in Lisp.  I had
warm fuzzy feelings about Lisp before reading this book, but came away
feeling nearly evangelical about Lisp's place in the world.  Luckily my fine
sense of pragmatism and irony keeps me from going medieval on my Visual C++
and Visual Basic (shudder) fellow workers.

Not so sure about web pages, but if there is a page I would betcha that ALU
has one (http://www.elwoodcorp.com/alu/).

John Miller
mille...@enteract.com

  Norvig has already been mentioned, and Graham also includes a chapter on
  various aspects of efficiency.

  however, different things require different forms of attention in
  different implementations of Common Lisp, so you really need to profile
  your code to see where the hot spots are.

  no.

| If not, what have you meant by it?  To me, a parameterized type would be
| something like "vector of integers" or "list of bank transaction objects"
| where you parameterize LIST or VECTOR with your choice of element type.

  this entire issue is a joke on the explicit typing crowd.  by refusing to
  understand that lists and vectors and other generic collections shouldn't
  _have_ to be specialized on the type, they _invent_ a stupid need that
  smart people don't have.

  the whole parameterized type nonsense is a testament to bad language
  design.  it is completely devoid of meaning.

  incidentally, (make-array <dimensions> :element-type <type>) is your
  parameterized type if you didn't like my COERCE example, which I use to
  show these explicit typing doofuses who drop type information at runtime
  what they _really_ wanted, but didn't know how to ask for.  imagine a
  simple function that accepts a type _name_ as argument and tries its best
  to convert an object into that type.  it's template hell in C++.  the
  name of its types are _gone_ at runtime, for starters.

  if you want a list of bank transaction objects, just don't put anything
  else on it.  how hard can it be?  I fail to see the need to construct a
  bogus language construct just to make that _harder_.  if you want a typed
  container, define a class that has a type specifier and a sequence or
  whatever you want to hold them, and provide general functions to add
  things to it after having checked the type.  the problem is that this
  stuff is so seldom _needed_ in a language that remembers the types of its
  objects apart from whatever variable used to hold them.

| You can specialize methods on STRING, but not with something you create
| with DEFTYPE.

  if you're talking about CLOS methods, you're being disingenious.  CLOS
  was designed to dispatch on classes, not types.  if you don't like that,
  nothing whatsoever stops you from running down a TYPECASE or making a
  more general mechanism.  yes, you have to roll your own.  that's true for
  just about everything people want.  "I do not want what I haven't got"
  does not apply to programmers.  incidentally, PPRINT-DISPATCH has a nice
  type-dispatching system that does a lot more than CLOS dispatch does.

  just because something is a good thing to do when you regularly shoot
  yourself in the foot, doesn't mean it's a good thing to do if you can
  avoid shooting yourself in the foot.

  enough comparisons with C++.  I get sick to my stomach thinking about the
  talent wasted in inventing ways that braindamaged language can hurt less.

That said, strongly typed languages aren't a bad idea by themselves.
There are quite a few kinds of applications where, however, unlikely
you might think it is, you don't want to find out at runtime that
there is type mismatch. Also, there is some performance improvement
when the type-checking can be done at compile time. Of course, this
latter benefit is available in Lisp, so there is no dispute there.

I think the problem with strongly typed languages is that they are
really bad for iterative development, which is a very fast way to
work. It is really nice to work in Lisp where I don't have to have the
design completely correct before I can start development. There is a
certain point, however, as the design stabilizes, where the compile
time type-checking is useful to guarantee certain exceptions will not
occur. (This is the same idea behind exception specifications.)

It is possible to implement these things rather easily in Lisp. It
would be easy enough to check method or function invocations against
type specializers or declarations before compiling. It is also
straightforward to implement collections and iterators. In fact, I
think for mission critical systems, this is probably done routinely.
What is unfortunate, I suppose, is that none of this code has found
it's way into the public domain.

Or has it? =)