Hi there,
In many texts "cons" is explained to be implemented as linked list.
Is it possible to create Ansi compatible Lisp where "cdr"
would just return index to the "remaining values" and where
finding last value(s) does not mean traversing the whole structure.
Is support for lists with unlimited size compulsory
for Ansi compatible Lisp Interpreter to exist?
This came into my my mind when reading about Linux v2.6 scheduler
where the selection time does not depend on total number
of the processes?
-pekka-
On Jul 5, 12:23 pm, Pekka Niiranen <··············@pp5.inet.fi> wrote:
> In many texts "cons" is explained to be implemented as linked list.
It would be more accurate to say that a linked list may be implemented
using CONS.
CONS doesn't have anything to do with lists by itself. Imagine a CONS
implementation in C:
struct cons {
void* car;
void* cdr;
};
That's pretty much it. You can use CONS to implement a linked list,
and this is how linked lists are commonly implemented in Lisps. But
you are also welcome to implement your own linked list with different
properties. For example, your linked list could have a "tail
pointer" (so that you can find the end in constant time) or be doubly
linked instead of singly linked.
CONS's simplicity also means that it is very general. If you try to
force CONS to be only for linked lists, and then include a "tail
pointer" to find the end in constant time, then you won't be able to
use CONS (easily) to implement more general linked structures like
trees (there are multiple tails) or circular structures (there's no
tail). However, you can use CONS to implement your own kind of list
that has the properties you want.
mfh
On Jul 5, 3:23 pm, Pekka Niiranen <··············@pp5.inet.fi> wrote:
> Hi there,
>
> In many texts "cons" is explained to be implemented as linked list.
>
> Is it possible to create Ansi compatible Lisp where "cdr"
> would just return index to the "remaining values" and where
> finding last value(s) does not mean traversing the whole structure.
> Is support for lists with unlimited size compulsory
> for Ansi compatible Lisp Interpreter to exist?
>
> This came into my my mind when reading about Linux v2.6 scheduler
> where the selection time does not depend on total number
> of the processes?
>
> -pekka-
Your question is posed in a slightly offbeat way, but the answer is
"sort of." The semantics of "cons" is always a cell containing 2
pointers. You can form any kind of graph with such cells, not just
lists, so in general there is no way to use an array rep for conses
(as has already been said).
There is however an old and well-known optimization of simple lists of
conses called "cdr coding." When an implementation can detect that a
cons structure is just a list of conses jointed by cdr pointers, it
can substitute an array consisting entirely of "car" pointers. Codrs
are repaced by adjacency in the cdr-coded list. This can save space
and time. However it adds significant complexity as well, and in some
cases it causes additional copying that actually wastes time. All the
cons-handling primitives have to be able to accept these cdr-coded
lists and do the right thing. I don't think they're often used in CL
implementations because CL already offers vectors and arrays. The
burden is on the programmer to pick the data structure that's best for
a given app.
In article <························@q75g2000hsh.googlegroups.com>,
Gene <············@gmail.com> wrote:
> There is however an old and well-known optimization of simple lists of
> conses called "cdr coding." When an implementation can detect that a
> cons structure is just a list of conses jointed by cdr pointers, it
> can substitute an array consisting entirely of "car" pointers. Codrs
> are repaced by adjacency in the cdr-coded list. This can save space
> and time. However it adds significant complexity as well, and in some
> cases it causes additional copying that actually wastes time. All the
> cons-handling primitives have to be able to accept these cdr-coded
> lists and do the right thing. I don't think they're often used in CL
> implementations because CL already offers vectors and arrays. The
> burden is on the programmer to pick the data structure that's best for
> a given app.
AFAIK, cdr coding has only been used on Lisp Machines -- they're
recognized by the hardware/microcode to avoid performance impact.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
From: Kent M Pitman
Subject: Re: Newbie question about "cons"?
Date:
Message-ID: <uejjmjf27.fsf@nhplace.com>
Barry Margolin <······@alum.mit.edu> writes:
> In article <························@q75g2000hsh.googlegroups.com>,
> Gene <············@gmail.com> wrote:
>
> > There is however an old and well-known optimization of simple lists of
> > conses called "cdr coding." When an implementation can detect that a
> > cons structure is just a list of conses jointed by cdr pointers, it
> > can substitute an array consisting entirely of "car" pointers. Codrs
> > are repaced by adjacency in the cdr-coded list. This can save space
> > and time. However it adds significant complexity as well, and in some
> > cases it causes additional copying that actually wastes time. All the
> > cons-handling primitives have to be able to accept these cdr-coded
> > lists and do the right thing. I don't think they're often used in CL
> > implementations because CL already offers vectors and arrays. The
> > burden is on the programmer to pick the data structure that's best for
> > a given app.
>
> AFAIK, cdr coding has only been used on Lisp Machines -- they're
> recognized by the hardware/microcode to avoid performance impact.
First, it's worth noting that cdr coding would NOT solve the problem
of indexed access. CDR-coding ALLOWS lists to have cells allocated
one after another, however it does not REQUIRE it, and consequently for
the Lispm you still had to cdr down the list to get to the nth element
just in case one of the cells was not a cdr-next.
Second, as to the performance impact, Barry's right about the fact
that hardware support is probably important, but I don't think you can
say, as Gene suggests, that CL's vectors and arrays are the reasons
not to use cdr-coded lists. The LispM had vectors and arrays in more
kinds than CL had [several big omissions, one I mention below, but two
other missing things are: conformally displaced arrays and arrays with
array leaders]. The reason for not having them is simply that they're
no good if they aren't fast enough, and it's hard to make them fast on
so-called "stock hardware" (what we used to call non-Lispm hardware),
especially in the presence of RPLACD (the correct handling of which
introduces a need for forwarding pointers in some cases).
I'm not the best person to describe this, but I'm pretty sure the
above summary is wrong, so consider this my stab at fixing it. I'm
open to being corrected as needed...
Cdr coding requires no "detection" at all. It's done entirely by the
allocation operator itself, which lays out memory in the way it
anticipates will be good. It uses 2-bit codes to denote the cdr. The
codes have four possible values, which I think are: cdr-nil [the cdr
is NIL, so don't look for it], cdr-next [the next cell is the cdr],
cdr-normal [the next cell points to the cdr], and cdr-error [don't
take the cdr of this, it's not cdr-able].
(list x y z) would create words that looked like this, where the words
were mostly just one pointer plus two bits of another. I don't recall
Lispm word sizes, and I think there were stray bits doing other things,
but ignoring that, if you had n bit pointers to memory, for example,
it would take n+2 bits minimum to represent a cdr-coded cons:
[ full-pointer-to-x | cdr-next ]
[ full-pointer-to-y | cdr-next ]
[ full-pointer-to-z | cdr-nil ]
(list* x y z nil) would create words that looked like (I think):
[ full-pointer-to-x | cdr-next ]
[ full-pointer-to-y | cdr-next ]
[ full-pointer-to-z | cdr-normal ]
[ full-pointer-to-nil | cdr-error ]
(cons x y) would do
[ full-pointer-to-x | cdr-normal ]
[ full-pointer-to-y | cdr-error ]
(cons x (cons y (cons z nil))) would do what I imagine was like this,
though I never really paid a lot to how cdr-normal was laid out, I just
knew it made enough room somehow:
[ full-pointer-to-x | cdr-normal ]
[ pointer-to-next | cdr-error ]
[ full-pointer-to-y | cdr-normal ]
[ pointer-to-next | cdr-error ]
[ full-pointer-to-z | cdr-normal ]
[ full-pointer-to-nil | cdr-error ]
Doing this would mean that you could always use cons or list* to
make initial room for doing rplacd, and you would tend to use list when
you weren't planning to rplacd. [See notes below about what happened
if you were planning to.]
And it goes without saying, but I'll say it anyway, that
(cons x (cons y nil)) was not the same as (list* x y nil) and not
the same as (list x y) in terms of how it laid out memory, and how
it consumed memory, even though at the level of car and cdr it was
always identical.
There WAS a datatype on the LispMachine (in Zetalisp, not in Common
Lisp) which was a combination array/list, that had some name like
ART-Q-LIST or some such thing, I think. You could access the array
elements directly via AREF or you could do an access operation,
bizarrely called something like G-L-P (which I think stood for
get-list-pointer), if I recall right, that gave back a list-tagged
pointer to the array's data as a list, so you could cdr down it.
It may have been an error to try to RPLACD the elements of such
a structure.
(In general, other than this situation, RPLACD was handled even in
densely packed cdr-coded lists, I think by using some sort of
body-forward cell that allowed you to move the cons to another place
and then have that place contain the changed cdr. In effect, this
meant that RPLACD cons'd, which was counter to the intuition of some
people, but was "due justice" to people who hated side effects and
wanted people who wrote them to pay dearly. ;) It might be the garbage
collector would eventually fix up these body forward pointers, but the
rest of the memory system would track through them as if they weren't
there. I think there were several kinds of forwarding pointers,
including gc forwarding pointers, that were done that way.
That's what I recall anyway. I didn't have my LispM spun up to check
this so I'm working from a different kind of memory. Plus I never
programmed this stuff in the first place--it just happened mostly
invisibly--so I could have had a misconception and never noticed. All
one really had to know was to make sure to use cons or list* rather
than list in order to create rplacd-able cells in some cases, and the
rest just didn't matter... and even then it was fault tolerant.
Someone who has one handy might correct me if I made a mistake on
this. But enough with the disclaimers. My main point really was just
to correct the misunderstanding that cdr-coding implied indexed
access. I'm pretty sure I got at least that part right.
And, as an aside, nreverse is fun with cdr-coding. I'll leave that
for someone else to remark about.
In article <·············@nhplace.com>,
Kent M Pitman <······@nhplace.com> wrote:
> Second, as to the performance impact, Barry's right about the fact
> that hardware support is probably important, but I don't think you can
> say, as Gene suggests, that CL's vectors and arrays are the reasons
> not to use cdr-coded lists. The LispM had vectors and arrays in more
> kinds than CL had [several big omissions, one I mention below, but two
> other missing things are: conformally displaced arrays and arrays with
> array leaders]. The reason for not having them is simply that they're
> no good if they aren't fast enough, and it's hard to make them fast on
> so-called "stock hardware" (what we used to call non-Lispm hardware),
> especially in the presence of RPLACD (the correct handling of which
> introduces a need for forwarding pointers in some cases).
I suspect the main benefit of cdr-coding was not that you could treat
them as vectors -- you couldn't, as Kent pointed out.
The main benefit was that they used half as much memory -- if a list is
fully cdr-coded, it uses one pointer per element rather than two. When
the LispM's were first developed, RAM was very expensive, and disk
access (for paging) was very slow. And applications that take advantage
of Lisp's power typically are very memory-hungry. So a built-in
mechanism that could automatically halve the memory use of some common
data structures was very useful.
Now, memory is cheap, and the engineering tradeoffs are different.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
In article <····························@comcast.dca.giganews.com>,
Barry Margolin <······@alum.mit.edu> wrote:
> In article <·············@nhplace.com>,
> Kent M Pitman <······@nhplace.com> wrote:
>
> > Second, as to the performance impact, Barry's right about the fact
> > that hardware support is probably important, but I don't think you can
> > say, as Gene suggests, that CL's vectors and arrays are the reasons
> > not to use cdr-coded lists. The LispM had vectors and arrays in more
> > kinds than CL had [several big omissions, one I mention below, but two
> > other missing things are: conformally displaced arrays and arrays with
> > array leaders]. The reason for not having them is simply that they're
> > no good if they aren't fast enough, and it's hard to make them fast on
> > so-called "stock hardware" (what we used to call non-Lispm hardware),
> > especially in the presence of RPLACD (the correct handling of which
> > introduces a need for forwarding pointers in some cases).
>
> I suspect the main benefit of cdr-coding was not that you could treat
> them as vectors -- you couldn't, as Kent pointed out.
>
> The main benefit was that they used half as much memory -- if a list is
> fully cdr-coded, it uses one pointer per element rather than two. When
> the LispM's were first developed, RAM was very expensive, and disk
> access (for paging) was very slow. And applications that take advantage
> of Lisp's power typically are very memory-hungry. So a built-in
> mechanism that could automatically halve the memory use of some common
> data structures was very useful.
>
> Now, memory is cheap, and the engineering tradeoffs are different.
It also improves locality. Which is very important in
a virtual memory based system with much more disk memory
than RAM. With modern processors and a hierarchy of
memory (1st-3rd level caches, RAM, disk caches, ...)
it still might have a little use. Though I haven't
seen anybody using it lately...
Genera has a Optimize World command which can be used
to rearrange objects more optimally in the Lisp image.
Commands like these (could) give an opportunity to also
to rearrange normal lists into cdr-coded lists.
Often it is not that a single optimization is a huge win,
I guess often it is the sum of a lot of small optimizations.
--
http://lispm.dyndns.org
On Jul 8, 12:47 pm, Rainer Joswig <······@lisp.de> wrote:
>
> It also improves locality. Which is very important in
> a virtual memory based system with much more disk memory
> than RAM. With modern processors and a hierarchy of
> memory (1st-3rd level caches, RAM, disk caches, ...)
> it still might have a little use. Though I haven't
> seen anybody using it lately...
I don't think the idea of a VM system as being a way of using cheap,
abundant disk as a way of making it look like there's more memory than
there is is really very interesting now - most of the machines I deal
with (which, OK, are not your average PC) have much more physical
memory than swap space. Even on desktop/laptop boxes I'd assume the
common approach is to simply throw enough memory at the system.
Of course this does not invalidate the locality argument, since
locality within main memory is now extremely important. Copying GCs
ought to help ensure that, I think. How well they actually do I'm not
sure.
--tim
Tim Bradshaw <··········@tfeb.org> writes:
> On Jul 8, 12:47 pm, Rainer Joswig <······@lisp.de> wrote:
>
> >
> > It also improves locality. Which is very important in
> > a virtual memory based system with much more disk memory
> > than RAM. With modern processors and a hierarchy of
> > memory (1st-3rd level caches, RAM, disk caches, ...)
> > it still might have a little use. Though I haven't
> > seen anybody using it lately...
>
> I don't think the idea of a VM system as being a way of using cheap,
> abundant disk as a way of making it look like there's more memory than
> there is is really very interesting now -
Did this ever actually work? I think the story goes
something like this:
Think of a machine with several interactive users.
If you don't have virtual memory you have to swap whole
programs in and out. Imagine you have 10MB of RAM and a
typical program takes 2MB. You can comfortably support 5
users. More than that and you use the disk and performance
goes downhill very fast.
If you do have VM and the typical program has a 1/2 MB
working set you can support 20 users. What makes this go is
that the programs remain in their working sets. The other 1 1/2
MB is barely used. If program strays outside its working set
the machine has to go to disk and takes an enourmous
performance hit.
So VM was a very important technology. It made machines 4
times as powerful but not much more expensive. However it
was mostly about not swapping totally unused stuff in and
out when you changed users. Disk was still too slow for
virtual memory to be useful with bits that you actually
used.
I think this is relevant to the history of Lisp. Purchasers
of AI workstations thought of VM as magic that let them run
a 3MB expert system written in Lisp on a 2MB work
station. The performance gap between disk and RAM is just
too big. Any program that makes non-trivial use of pages
outside the working set is just too slow, and Lisp got the
blame when the culprit was Virtual Memory Mysticism.
I never studied this stuff and I think that it was mostly
before my time, so I might be getting it horribly wrong, but
my claim is that VM worked because there was a lot of "never
used" code that real memory systems used to swap when
changing users.
Alan Crowe
Edinburgh
Scotland
From: Kent M Pitman
Subject: Re: Newbie question about "cons"?
Date:
Message-ID: <u644uvi3w.fsf@nhplace.com>
Alan Crowe <····@cawtech.freeserve.co.uk> writes:
>
> I think this is relevant to the history of Lisp. Purchasers
> of AI workstations thought of VM as magic that let them run
> a 3MB expert system written in Lisp on a 2MB work
> station. The performance gap between disk and RAM is just
> too big. Any program that makes non-trivial use of pages
> outside the working set is just too slow, and Lisp got the
> blame when the culprit was Virtual Memory Mysticism.
Well, I think it has lingering resonance because it relates to one of
the most fundamental issues of all computer science: which parts of
the low-level truth to reveal and which to hide. (Those not familiar
with this should See Gabriel and his "Worse is Better" paper for a
detailing of this.) Even today, you find situations where there are
mega-large databases of facts that can't all be "in memory" at once.
Sometimes one creates abstractions that hide this. They can range
from lazy evaluation (which just lets you think they are and tries to
hide it) to mapping operations (which segment operations into
chunkable steps that perhaps a compiler or memory manager can reason
about implementing differently than appears) to other language
operations that force the user to implicitly reveal the intent to pipe
stuff through a bit at a time (Unix pipe and its friends like sed
being an obvious example). These things are all paradigms for saying
"let's do this a little at a time" and the designers of this paradigm
ultimately know that there are locality issues no matter what you do.
In fact, the choice of lists vs arrays in languages, something near
and dear to all of our hearts, often hinges on the issue of locality.
Locality is a property of the universe, not of a language. Languages
can hide it, they can try to exploit it as a benefit, or they can
present it as a burden (leaving it to the user to sort out). Each of
these has advantages and disadvantages. It is the business of languages
to sort that out.
Some people would like to use a single language to solve all problems.
Those people are more susceptible to memory management hiding probably
because they want a single virtual world model. Some people prefer to
use targeted languages for targeted problems, in order to maximize the
control of assumptions about the processor itself, but often at the
expense of abstraction. The problem is often that "arbitrary" stuff
gets lost in between--for example, they may have the same or better
functional capabilities, but they may be lacking familiar syntax. Or
even just compatible syntax, so that it's easy to call back and forth.
The marketing concept of "one-stop shopping" is in play here, and VM's
offer that, by not splitting your programming task into two unrelated
abstractions--one for operating on a small amount of data and one for
shuttling data in and out of that small place.
Almost all programming pre 1980 or so was about being clever about
wedging data into a small space, and very little forward motion
happened, I think, in many fronts until we had large address space,
when the shoehorning of stuff into overtight spaces could become a
secondary activity, not a primary one. When I first heard of Moore's
Law, I recall thinking "I hope we don't lose the ability to manage
memory well in the interim, because while it's cool to have all that
memory, when we run out, we may have to learn some hard lessons all
over again about how to conserve."
The global ecological crisis is a similar situation, actually. People
struggled for resources for a long time. Then suddenly, with the
opening of the world market, resources seemed free. Now as we
approach the upper bound, we have to learn to live on less, as we did
before. Because it was all an illusion. Until we have workign space
flight, the world really is just as finite as it seemed before. We
had a one-time free pass to not having to think about it, and in that
time we needed to learn wisdom, not carelessness. I hope in both
cases we can overcome the vacation from wisdom.
Kent M Pitman wrote:
> Almost all programming pre 1980 or so was about being clever about
> wedging data into a small space, and very little forward motion
> happened, I think, in many fronts until we had large address space,
> when the shoehorning of stuff into overtight spaces could become a
> secondary activity, not a primary one. When I first heard of Moore's
> Law, I recall thinking "I hope we don't lose the ability to manage
> memory well in the interim, because while it's cool to have all that
> memory, when we run out, we may have to learn some hard lessons all
> over again about how to conserve."
>
> The global ecological crisis is a similar situation, actually. People
> struggled for resources for a long time. Then suddenly, with the
> opening of the world market, resources seemed free. Now as we
> approach the upper bound, we have to learn to live on less, as we did
> before. Because it was all an illusion. Until we have workign space
> flight, the world really is just as finite as it seemed before. We
> had a one-time free pass to not having to think about it, and in that
> time we needed to learn wisdom, not carelessness. I hope in both
> cases we can overcome the vacation from wisdom.
Tragically, that passage is too long to fit in a sig.
-- JK
On Jul 8, 4:17 pm, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
>
> Did this ever actually work? I think the story goes
> something like this:
I think it worked better than it does now, because I think the latency
between disk and processor has widened. It may also be that for
little machines the bandwidth gap has widened, but I think that for
big machines it's still the case that you want an I/O system that can
saturate the processor(s), more-or-less, for most applications.
An alternative view would be to say that, actually, it's never worked
better than it does now. I find it rather amusing when talking to
various old-OS fantasists who will go endlessly on about how Unix
makes this huge distinction between files and memory when it really
all ought to be a seamless whole, clearly not actually realising that
at least one major Unix went through a phase of making so little
distinction that it became hard to work out when the machine was short
of memory, because the mechanisms for file access and anonymous memory
access were identical: you could no longer distinguish between I/O
load and memory pressure, because actually, they were the same thing.
Ultimately this turned out to be a problem because the system tended
to make poor decisions about what to evict from memory when under
pressure, resulting in an initial change to prioritising pages mapped
to (I think) non-executable files, aonymous memory, then finally
executable files in that order, and then later to another change which
uses a different page-evicting technique for pages caching (non-
executable?) files.
So, actually, systems like that can be regarded, I think, as among the
most aggressive VM systems ever seen.
--tim
Tim Bradshaw <··········@tfeb.org> writes:
> On Jul 8, 4:17 pm, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
>
> >
> > Did this ever actually work? I think the story goes
> > something like this:
>
> I think it worked better than it does now, because I think the latency
> between disk and processor has widened. It may also be that for
> little machines the bandwidth gap has widened, but I think that for
> big machines it's still the case that you want an I/O system that can
> saturate the processor(s), more-or-less, for most applications.
>
I was turning over my earlier post in my mind and found
myself getting further and further away from this kind of
technical perspective. I realised that I was claiming that
VM working for one lot of programs, because they had good
locality, but not for a different group of programs, which
had bad locality, but what drives locality?
I think there is a sociological perspective from which VM
worked because it solved a social problem.
Hypothesis: Once upon a time, before virtual memory, there
were small programs and large programs and they all had poor
locality. The programmers working on large programs had to
control memory consumption. If their programs became large
they would no longer fit. Programmers working on small
programs added bells and whistles and the programs became
medium sized.
This was not a problem for developers. Their small/medium
programs still fitted in physical memory with a comfortable
margin.
This was a problem for system administrators. Their job was
to provide a computing service so that many users could run
small programs interactively using as few expensive
mainframe computers as possible. The growth from small to
medium memory usage was hurting the number of users a big
machine could support.
The social factor was that system administrators had no
leverage with developers, they just had to cope with bloated
small/medium programs as best they could.
VM provided a technical fix for the social problem. Since
they were really small programs, bloated to medium size with
bells and whistles, they had good locality. Usually they
only needed a little memory to get on with their original
job. So VM worked well, despite the huge latency of going to
disk.
When people tried to run large programs on small
machines/work stations, expecting VM to fix the lack of
physical memory, they were disappointed. The core reason was
that programmers writing larger programs had a direct
interest in the memory consumption of large programs. They
had to run! So the large programs had never experienced
irresponsible bloating and didn't have the artifically
enhanced locality of a medium sized program with a small
program living inside it. VM worked poorly due to the
sbsence of the social problem which VM solved.
Alan Crowe
Edinburgh
Scotland
On Jul 10, 11:01 am, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
> I was turning over my earlier post in my mind and found
> myself getting further and further away from this kind of
> technical perspective. I realised that I was claiming that
> VM working for one lot of programs, because they had good
> locality, but not for a different group of programs, which
> had bad locality, but what drives locality?
>
One problem is that "locality" isn't a really good term. Consider an
application which walks, once, forwards through an enormous address
space. Does it have good locality? I don't think it does. But it is
terribly friendly to your average VM system, so long as it's backed
with decent I/O.
--tim
In article <························@57g2000hsv.googlegroups.com>,
Tim Bradshaw <··········@tfeb.org> wrote:
> On Jul 10, 11:01 am, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
>
> > I was turning over my earlier post in my mind and found
> > myself getting further and further away from this kind of
> > technical perspective. I realised that I was claiming that
> > VM working for one lot of programs, because they had good
> > locality, but not for a different group of programs, which
> > had bad locality, but what drives locality?
> >
>
> One problem is that "locality" isn't a really good term. Consider an
> application which walks, once, forwards through an enormous address
> space. Does it have good locality? I don't think it does. But it is
> terribly friendly to your average VM system, so long as it's backed
> with decent I/O.
Why do you say it has bad locality? Suppose you have 1KB memory pages,
and you step through it 1 byte at a time. 99.9% of the time you'll hit
the same page as the previous access, which is pretty good locality.
And the access pattern easily allows for prefetching. It's not as good
as staying entirely on the same memory page, but it's as good as you can
get if your working set doesn't fit in one page.
Contrast it with an application that accesses addresses randomly. In
this case, if the working set is N pages, the chance that access I and
access I+1 will be on the same page is 1/N. The worst case, though, is
an application that accesses address X, X+P, X+2P, etc. where P is the
page size; in this case, you stay on the same page 0% of the time
(although if the pattern is consistent like this, you may be able to
supply a hint to the VM system, allowing it to prefetch so you don't
have to wait for the next page -- random access prevents any sort of
prefetching).
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
On Jul 12, 12:50 am, Barry Margolin <······@alum.mit.edu> wrote:
> Why do you say it has bad locality? Suppose you have 1KB memory pages,
> and you step through it 1 byte at a time. 99.9% of the time you'll hit
> the same page as the previous access, which is pretty good locality.
> And the access pattern easily allows for prefetching. It's not as good
> as staying entirely on the same memory page, but it's as good as you can
> get if your working set doesn't fit in one page.
>
> Contrast it with an application that accesses addresses randomly. In
> this case, if the working set is N pages, the chance that access I and
> access I+1 will be on the same page is 1/N. The worst case, though, is
> an application that accesses address X, X+P, X+2P, etc. where P is the
> page size; in this case, you stay on the same page 0% of the time
> (although if the pattern is consistent like this, you may be able to
> supply a hint to the VM system, allowing it to prefetch so you don't
> have to wait for the next page -- random access prevents any sort of
> prefetching).
Well, it obviously depends on your definition of "locality": mine was
probably wrong. And I think I was probably thinking of something more
like working set, although even then that's wrong. What I actually
meant was that you can write programs which chew chew through a huge
amount of address space (far more than physical memory) and yet have
performance that is almost incredibly good on decent HW (programs like
this can be good at the processor-does-not-stall level I think, if the
memory and I/O is up to it), if the program matches the assumptions
made by the VM/cache system, or can be made to.
(An interesting thing to try is to take such a program and modify it
to walk *backwards*. No change in locality or workign set but you can
see dramatic changes in performance...)
--tim
In article <························@m3g2000hsh.googlegroups.com>,
Tim Bradshaw <··········@tfeb.org> wrote:
> (An interesting thing to try is to take such a program and modify it
> to walk *backwards*. No change in locality or workign set but you can
> see dramatic changes in performance...)
That's probably an indication that the VM's prefetch algorithm assumes
forward stepping (it queues page N+1 after fetching page N), and doesn't
try to detect backward stepping.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
On Jul 14, 2:06 am, Barry Margolin <······@alum.mit.edu> wrote:
>
> That's probably an indication that the VM's prefetch algorithm assumes
> forward stepping (it queues page N+1 after fetching page N), and doesn't
> try to detect backward stepping.
>
Also I have a suspicion that disks do this too though this seems less
plausible.
But really my point was that there's an intimate relation between the
performance of code and how well it sits on the VM system, from cache
down to disk, and how well it sits may nit be immediately obvious
(though, OK, "walk uniformly through memory in increasing address
order" is pretty likely to be good).
--tim
Gene wrote:
> On Jul 5, 3:23 pm, Pekka Niiranen <··············@pp5.inet.fi> wrote:
>> Hi there,
>>
>> In many texts "cons" is explained to be implemented as linked list.
>>
>> Is it possible to create Ansi compatible Lisp where "cdr"
>> would just return index to the "remaining values" and where
>> finding last value(s) does not mean traversing the whole structure.
>> Is support for lists with unlimited size compulsory
>> for Ansi compatible Lisp Interpreter to exist?
>>
>> This came into my my mind when reading about Linux v2.6 scheduler
>> where the selection time does not depend on total number
>> of the processes?
>>
>> -pekka-
>
> Your question is posed in a slightly offbeat way, but the answer is
> "sort of." The semantics of "cons" is always a cell containing 2
> pointers. You can form any kind of graph with such cells, not just
> lists, so in general there is no way to use an array rep for conses
> (as has already been said).
One of the mid-80s introductions to Lisp (Touretzky?) posited a nice
thought-experiment to do this with two arrays: the first array holds all
the cars in your universe, the second array holds all the cdrs. It takes
a moment to wrap one's head around the idea, but then it becomes kinda
sweet. (I had an idea of building a machine that actually implemented a
memory model like this, but a real computer architect brought me to my
senses.) Of course, unless you continually perform some bizarre analogy
of sorting it has nothing to offer the original poster.
paul
Paul Wallich <··@panix.com> wrote:
+---------------
| One of the mid-80s introductions to Lisp (Touretzky?) posited a nice
| thought-experiment to do this with two arrays: the first array holds all
| the cars in your universe, the second array holds all the cdrs.
+---------------
Uh... This is how people did list processing in Fortran
in the late 1960's and early 1970's. Sometimes they even
used three arrays -- VALUE (car), NEXT (cdr), and PREV --
to get doubly-linked lists.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Nils M Holm
Subject: Re: Newbie question about "cons"?
Date:
Message-ID: <f6nsis$js1$1@online.de>
Paul Wallich <··@panix.com> wrote:
> One of the mid-80s introductions to Lisp (Touretzky?) posited a nice
> thought-experiment to do this with two arrays: the first array holds all
> the cars in your universe, the second array holds all the cdrs. It takes
> a moment to wrap one's head around the idea, but then it becomes kinda
> sweet. [...]
Without having read the introduction you are refering to, this was the
first idea I had when implementing my first LISP interpreter. I even
recycled the idea recently when implementing Scheme 9 from Empty Space[1],
because it is simple and rather easy to explain. Another nice thing
about this approach is that you keep indices to the arrays rather than
pointers in the car and cdr fields, so you can save your workspace by
just saving the arrays (and some meta information).
[1] http://t3x.org/bits/s9fes/
--
Nils M Holm <n m h @ t 3 x . o r g> -- http://t3x.org/nmh/
On 2007-07-05 21:23:19 +0200, Pekka Niiranen <··············@pp5.inet.fi> said:
> Hi there,
>
> In many texts "cons" is explained to be implemented as linked list.
>
> Is it possible to create Ansi compatible Lisp where "cdr"
> would just return index to the "remaining values" and where
> finding last value(s) does not mean traversing the whole structure.
> Is support for lists with unlimited size compulsory
> for Ansi compatible Lisp Interpreter to exist?
>
> This came into my my mind when reading about Linux v2.6 scheduler
> where the selection time does not depend on total number
> of the processes?
I'd say you want an array. Luckily Common Lisp has arrays.
>
> -pekka-
--
http://lispm.dyndns.org/
Pekka Niiranen <··············@pp5.inet.fi> writes:
> Is it possible to create Ansi compatible Lisp where "cdr"
> would just return index to the "remaining values" and where
> finding last value(s) does not mean traversing the whole structure.
This is too expensive, both in time and space.
The problem is that lists are mutable (you can insert an item in the
middle of a list), and that you can keep references to cons cells in
the middle of a list (and therefore share the tail between several
lists).
Therefore, if you tried to use vectors to implement lists, a lot of
operations that can be done very quickly would require a lot more time
and memory. And I don't mean O(f(length of the list)), but rather
O(f(number of objects in memory)).
That said, if you have a specific situation where you need to optimize
some operation that with lisp list takes O(n), you can build your own
abstract data type, or use another type than lisp lists (eg vectors,
hash-tables, etc).
For example, if you want to optimize length and appending a element to
the end of a list, you could use:
(defstruct mylist length head tail)
(defun mylist (&rest items)
(let ((items (copy-list items)))
(make-mylist :length (length items)
:head items
:tail (last items))))
(defun mylist-add-item (mylist item)
(if (zerop (mylist-length mylist))
(setf (mylist-head mylist) (list item)
(mylist-tail mylist) (mylist-head mylist)
(mylist-length mylist) 1)
(setf (cdr (mylist-tail mylist)) (cons item nil)
(mylist-tail mylist) (cdr (mylist-tail mylist))
(mylist-length mylist) (1+ (mylist-length mylist))))
mylist)
etc...
> Is support for lists with unlimited size compulsory
> for Ansi compatible Lisp Interpreter to exist?
Yes.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
From: Kent M Pitman
Subject: Re: Newbie question about "cons"?
Date:
Message-ID: <uir8yjk1c.fsf@nhplace.com>
Pascal Bourguignon <···@informatimago.com> writes:
> > Is support for lists with unlimited size compulsory
> > for Ansi compatible Lisp Interpreter to exist?
>
> Yes.
Well, sort of. See STORAGE-CONDITION.
That's not to say that I think the typical user, shopping for an
implementation, would look very long at an implementation that
had a bound. But there could be specialized cases where they do.
For that matter, CL could conceivably run in situations where the
total amount of memory was quite small, such that bounding your
list size was the least of your problems.
The matter of resource limitations are really beyond the scope of the
language definition.
But, anyway, it doesn't matter, because the question of list size is
not the issue in the original question. The fact of the time to find
the end is not made O(1) just by agreeing to make the n in O(n)
smaller. If that were true, we could declare all algorithms that had
some O(f(n)) to be O(1) if f(n) was just a function of memory size,
since all memory is finite in size.
On Jul 5, 9:23 pm, Pekka Niiranen <··············@pp5.inet.fi> wrote:
> Hi there,
>
> In many texts "cons" is explained to be implemented as linked list.
>
> Is it possible to create Ansi compatible Lisp where "cdr"
> would just return index to the "remaining values" and where
> finding last value(s) does not mean traversing the whole structure.
> Is support for lists with unlimited size compulsory
> for Ansi compatible Lisp Interpreter to exist?
>
> This came into my my mind when reading about Linux v2.6 scheduler
> where the selection time does not depend on total number
> of the processes?
>
> -pekka-
You question is little weird, do you need to find last value from the
first value of the list that's easy involving a chain like structure,
or you need to access any value from any value that sounds that you
need array. To keep things short, arrays support random access as
their elements are contigous block of memory that's why inserting
elements at other side except the end is expensive you need to move
all the elements to new place, (c++ vector). Than there is a list that
supports inserting elements at any place, lisp lists are single linked
meaning that you don't know where the element is unless you travel
whole chain of links. To implement what you ask you need cons cell
that has a value and a link to all elements in the list. The
disadvantages of this implementation should be obvious, huge size of
the cons cell and fixing all links to all cons cells whenever elements
gets added or deleted. I suggest to read chapter 2 of touretzky gentle
intro (available for free as pdf) to get idea what am I talking
about. Dave explains far better than I do.