I'm looking for information on cdr-coding. Specifically do any current
LISP implementations for general purpose machines use cdr-coding?
If yes, has anyone published an assessment of the tradeoffs.
Refererences to cdr-coding papers are welcome. I have "A New List Compaction
Method" Li & Hudak S-P&E 1986 and presumably earlier useful papers
are in its reference list.
Andrew Taylor
In article <···@cluster.cs.su.oz>, ·······@cluster.cs.su.oz (Andrew Taylor) writes:
> I'm looking for information on cdr-coding.
> ... has anyone published an assessment of the tradeoffs.
A study I did in 1986 at LISP MACHINE INC showed CDR-coding saving about 5%
of the storage space in a working band. Except for their use in &REST
lists of procedures arguments (stack-allocated) there was no significant runtime
speed advantage. And since most use of &REST was actually a user-level use
of &KEY, I concluded that we could get rid of CDR-coding and increase
the capability of the LMI-LAMBDA in doing so. (The address space of the
machine would go up by a factor of 4, and immediate FIXNUM's could go from
25 bits to 27 bits).
The experimental single-cycle-per-instruction lisp processor that LMI
developed later in 1986/1987 had no CDR-coding. Instead it fetched data
in 64-bit chunks and used 32-bit pointers.
If CDR-coding is not so hot for specialized lisp processors I doubt it could
be of much value for general-purpose machines.
-gjc
The CDR-coding scheme used in AltoLisp, Interlisp-D, and now even in
Medley on Suns (a "current LISP implementation for general purpose
machines"?) has a better compression ratio (I believe the figure was
that CONS cells took an average of 36 bits), but that was because it
used an 8-bit CDR-code instead of the 2-bit ones found in the MIT-Lisp
machine descendents. Of course, the address space is limited to 24
bits; not an unreasonable limit when the scheme was designed.
--
Larry Masinter (········@parc.xerox.com)
Xerox Palo Alto Research Center (PARC)
3333 Coyote Hill Road; Palo Alto, CA USA 94304