A simple question: Is cdr-coding used in modern lisp system? If so,
why? If not, why not?
Thanks in advance for any help,
Robert
--
Robert Virding Tel: +46 (0)8 719 95 28
Computer Science Laboratory Email: ··@erix.ericsson.se
Ericsson Telecom AB
S-126 25 �LVSJ�, SWEDEN
WWW: http://www.ericsson.se/cslab/~rv
"Folk s�ger att jag inte bryr mig om n�gonting, men det skiter jag i".
In article <············@news.du.etx.ericsson.se> ··@erix.ericsson.se
(Robert Virding) writes:
>
> A simple question: Is cdr-coding used in modern lisp system? If so,
> why? If not, why not?
>
> Thanks in advance for any help,
>
Yes, cdr-coding was (is) used on the Symbolics. But it was built into the
machine addressable word.
My guess is that you would not see cdr-coding in standard Von Neumann style
CPU Lisp implementations a lot because the two bit cdr code would have to be
included in the address space of a machine addressable word. If at the top
the word it would eliminate 3/4 of the potential memory, which is not so bad
on large word sizes. If at the bottom of the word it would require all lisp
objects to be on 4 byte boundaries. In either case a masking operation is
required to get the actual address for every reference.
--
William P. Vrotney - ·······@netcom.com
William Paul Vrotney wrote:
>
> In article <············@news.du.etx.ericsson.se> ··@erix.ericsson.se
> (Robert Virding) writes:
>
> >
> > A simple question: Is cdr-coding used in modern lisp system? If so,
> > why? If not, why not?
> >
> > Thanks in advance for any help,
> >
>
> Yes, cdr-coding was (is) used on the Symbolics. But it was built into the
> machine addressable word.
>
> My guess is that you would not see cdr-coding in standard Von Neumann style
> CPU Lisp implementations a lot because the two bit cdr code would have to be
> included in the address space of a machine addressable word. If at the top
> the word it would eliminate 3/4 of the potential memory, which is not so bad
> on large word sizes. If at the bottom of the word it would require all lisp
> objects to be on 4 byte boundaries. In either case a masking operation is
> required to get the actual address for every reference.
>
> --
>
> William P. Vrotney - ·······@netcom.com
Yes, Symbolics used it, because with the special dedicated tag
architecture, recgonizing a regular CDR from a "compressed CDR" was very
quick.
VAX Lisp (running on general purpose Vaxes) did not use CDR coding,
because it would change a CDR function call from a one-instruction
address jump to a somewhat complex subroutine call. This would have
degraded the overall system performance.
Basically, for general architecture, CDR coding is a tradeoff between
space and speed.
--
_________________________________________________________________
|David D. Lowry |
|Attorney at Law (or at Play) ···@dbrc.com |
|Dike, Bronstein, Roberts & Cushman LLP www.dbrc.com |
|Boston, Mass. (617) 523-3400 |
| |
|CLOS > C++ * 10^2 |
|_______________________________________________________________|
William Paul Vrotney <·······@netcom.com> wrote:
>My guess is that you would not see cdr-coding in standard Von Neumann
>style CPU Lisp implementations a lot because the two bit cdr code
>would have to be included in the address space of a machine
>addressable word. If at the top the word it would eliminate 3/4 of
>the potential memory, which is not so bad on large word sizes. If at
>the bottom of the word it would require all lisp objects to be on 4
>byte boundaries. In either case a masking operation is required to
>get the actual address for every reference.
Actually, I use cdr-coding in the runtime system for Cyc. It makes a
big difference in memory requirements and locality when you have tens
of millions of cons cells. The system assumes a byte-addressed
machine and that all objects are word-aligned (four bytes on 32-bit
machines, eight on 64-bitters). That is not a bad assumption for the
foreseeable future, and you don't want to have non-aligned objects for
performance reasons anyway.
That leaves two or three bits free at the low end for cdr-codes. I
use the usual cdr-normal, cdr-next, and cdr-nil values, plus a
cdr-forward value for cdr-next cells that have been RPLACD'ed. The
garbage collector and various list functions coalesce cdr-normal and
cdr-forward cells into cdr-next ones when they can.
It is a bit painful to have to mask out the low bits on dereferencing
a pointer from a cons on machines that do not have a load instruction
that ignores the low bits, but, if you are going to be bouncing around
the address space anyway, that is down in the noise.
IIRC, the 68K MCL implementation had a cool trick where type tags were
stored in the low-order bits, and pointers to objects were adjusted
downwards so that you could just dereference the pointer + tag.
--David Gadbois
In article <············@news.du.etx.ericsson.se>, ··@erix.ericsson.se (Robert Virding) writes:
>>
>> A simple question: Is cdr-coding used in modern lisp system? If so,
>> why? If not, why not?
>>
Cdr-coding saves space essentially by representing lists internally as arrays.
The space savings can be significant if a large percentage of data are lists,
as in the "old days" when source code was represented in memory as lists.
This isn't really true today, it's all compiled, and source code is kept in files.
It requires hardware support to be really efficient, since the CDR operation
must work differently for the two types of list representations.
Supporting cdr-coding would also "throw out" the fast non-type-checked CDR
operations that are currently possible when high-speed, low-safety declarations
are being used, since the programmer could not specify, or may even know,
what type of list is being CDR'd to declare it.
However, a non-CommonLisp alternative is to make all lists cdr-coded,
and also make them read-only! This is a big win for a parallel, distributed
system, and also appropriate for a persistent object system as well,
since read-only means lists can be copied at will, and cdr-coding makes
the data more compact in memory and to transfer.
-Kelly Murray ···@franz.com http://www.franz.com
In article <············@sparky.franz.com>, ···@franz.com wrote:
> However, a non-CommonLisp alternative is to make all lists cdr-coded,
> and also make them read-only! This is a big win for a parallel, distributed
> system, and also appropriate for a persistent object system as well,
> since read-only means lists can be copied at will, and cdr-coding makes
> the data more compact in memory and to transfer.
Of course, if such lists are allowed to 'share tails', then some of them
cannot be cdr-coded...