CDR coding harmful.

[dekleer.pa@xerox.com]

DLA, says:

    1.  For all operations but RPLACD, operations on cdr-coded lists need be
    no slower than the equivalent operations on normally-coded lists.  On
    many architectures individual operations are slower because designers
    didn't think additional complexity was worth putting into hardware for
    specific operations.

    ...

Well you are telling us the full story:

RPLACD's into CDR-coded lists presumably generate invis pointers to full
cons cells.  This presumably has nasty consequences (its hard to tell
exactly of course because the Symbolics debugging tools make it hard to
tell exactly what the list structures you construct truely look like):

  (1) Constructing these invis pointers and consing is extremely slow.  By my crude
      measurements its at least 10x slower than a regular RPLACD.  There is this nasty
      function RPLACD-ESCAPE which always seems to show up with high percentages when
      I meter.

   (2) CDR'ing down this list will be slow, as invis pointers have to be chased.  So 
       CDR is slowed down.

   (3) Memory utilization is bad.  After a single RPLACD on a CDR coded list you've wasted 50% of 
       the space for that list element.

   (4) Question: Will GC pick up the unused fragments of cdr-coded lists?  If not, bad news.  I hope the implementation
       doesn't build long chances of invis pointers.  (I haven't checked, but I've seen other situations
       in which this happens).

I discovered these things the hard way.  The moral is, if you use
RPLACD, don't use CDR-coded lists ***AT ALL*** or only for trivialities.
And you have to read the manuals very carefully to determine what
CommonLisp functions return a cdr-coded list and which do not.  CONS
does not CDR-code, LIST does. I sped up one module by an order of
magnitude by replacing all occurences of (LIST <x>) by (CONS <x> NIL).
(Which is not so easy because many of the standard macros and functions
implicitly use LIST's not CONS's).

In general, I think CDR-coding is a crock, and not worth all the trouble
it generates for the implementor(you) and user(me) just to save the few
cons cells which take up a small percentage of the real and virtual
memory space.
-------