self-hosting gc, narrowed
Thomas Bushnell, BSG
Ok, the discussion has been useful, but didn't get to the narrow
question I was asking. Here's my narrowing and specification of the
question, with much thanks to those who entertained the first version.
I'm interested in self-hosting GC. What I mean by that is fairly
specific.
"Self-hosting" I take to mean that the GC is written in Lisp/Scheme
itself, not in some other language. Some subsetting is tolerable, but
the prohibition of things like cons, creation of closures, and call/cc
is not a solution to the problem I'm posing.
primitives either;
The goal is to eliminate reliance on language processors for other
languages. That's why I say "self-hosting". Linux, for example, is a
self-hosting C implementation: the kernel, toolchain, shells, and
compiler, are all written in C, with no need for another language to
help out.
(Obviously that means that small amounts of assembly hooks are not a
problem; of course, any complete system will need those; if they are
kept to a small degree--NOT the entire GC--then they don't count as
"another language".)
This is not a project for some specific existing Lisp/Scheme system,
nor is it any kind of criticism of those systems. If a system is
"hosted", and runs on, say, a Linux kernel, then there's nothing wrong
with taking advantage of the existing C compiler on your GNU/Linux
system.
But consider the situation of, say, the oskit version of MzScheme.
Here we have an unhosted implementation, but alas, it can't compile
itself--it isn't self-hosting. Rather, it requires access to a *nix
box to compile and build the system.
There are many issues involved in making such a self-hosting
Lisp/Scheme system, obviously. The present question is concerned
specifically with the issue of GC. Writing such a GC certainly
requires adding suitable new primitives to your Lisp dialect; that's
not a problem.
The basic problem is that the GC, if written in Lisp/Scheme, will
itself be allocating memory. But GC is usually described as a
*separate* process from the mutator (whether the incremental or
concurrent or not). In the self-hosting case, however, the GC itself
*is* a mutator.
Some implementation strategies involve:
setting aside a special heap for the collector to use.
use stop-and-copy; the collector always allocates in the clean semi-heap.
There may be more. I'm interested in whatever historical practice has
done (that's why I asked about Genera and the MIT Lisp Machines; TI
too). I'm interested in whatever research or papers may exist.
Thomas
Joe Marshall
"Thomas Bushnell, BSG" <tb+u...@becket.net> wrote in message
news:87y9h24...@becket.becket.net...
>
> The basic problem is that the GC, if written in Lisp/Scheme, will
> itself be allocating memory. But GC is usually described as a
> *separate* process from the mutator (whether the incremental or
> concurrent or not). In the self-hosting case, however, the GC itself
> *is* a mutator.
This is not necessarily the case. It is fairly easy to write Lisp and
Scheme
code that either does not allocate temporary storage, only allocates
temporary storage in a provably stack-like manner, or allocates a bounded
amount of temporary storage from a statically allocated `pool'.
In any case, as I mentioned before, the GC *can* cons provided it
doesn't cons too much.
What is more interesting is writing the virtual memory and interrupt
system in Lisp.
> There may be more. I'm interested in whatever historical practice has
> done (that's why I asked about Genera and the MIT Lisp Machines; TI
> too). I'm interested in whatever research or papers may exist.
The LMI K-machine had no microcode; the Lisp was compiled
`down to the metal'. The GC was decoupled from allocation.
Just above the virtual memory abstraction was a `region' abstraction.
A `region' is a very large block of address space that is explicitly
managed. CONS would allocate out of some distinguished region,
and when it ran out of room, it would simply call to allocate another
region. The GC would run in a separate thread and monitor the growth
of the allocated space. When it decided to flip, it would select a region,
evacuate the live data from it, then return that region to free space.
Thomas Bushnell, BSG
> This is not necessarily the case. It is fairly easy to write Lisp and
> Scheme
> code that either does not allocate temporary storage, only allocates
> temporary storage in a provably stack-like manner, or allocates a bounded
> amount of temporary storage from a statically allocated `pool'.
You've ignored what was clearly said above about subsetting. I'm
interested in doing it *WITHOUT* such restrictions in the language.
> In any case, as I mentioned before, the GC *can* cons provided it
> doesn't cons too much.
So, that opens two problems: does it cons from the main heap? If so,
doesn't that impede certain kinds of GC algorithms? If it conses from
a different heap, how big of one can be used?
I'm looking for *research* or *experience*. I'm able to fill in the
obvious points myself.
> What is more interesting is writing the virtual memory and interrupt
> system in Lisp.
I'm not asking about "whatever is most interesting". I'm asking about
GC. I already have a pretty durn solid idea about how to write VM
systems and interrupt handling, and doing it in Lisp is not terribly
different from other languages.
> The LMI K-machine had no microcode; the Lisp was compiled
> `down to the metal'. The GC was decoupled from allocation.
> Just above the virtual memory abstraction was a `region' abstraction.
> A `region' is a very large block of address space that is explicitly
> managed. CONS would allocate out of some distinguished region,
> and when it ran out of room, it would simply call to allocate another
> region. The GC would run in a separate thread and monitor the growth
> of the allocated space. When it decided to flip, it would select a region,
> evacuate the live data from it, then return that region to free space.
Thanks--this is the kind of detail I'm looking for.
Is there any documentation or published descriptions available?
Christopher C. Stacy
Joe> The LMI K-machine had no microcode; the Lisp was
Joe> compiled `down to the metal'.
For the benefit of other folks who might not totally understand,
in general, what microcode is about: microcode might as well be metal,
and the distinction is mostly unimportant in the context of this discussion.
The Lisp compiler on these machines did not produce microcoded
programs -- the result of the compilation was a sequence of object
codes of "macro instructions", which are commonly referred to (on
Lisp Macines, and most other kinds of computers) simply as "instructions".
In other words, the compiler was like the compiler on other computers
and Lisp programs executed instructions (not micro instructions).
The fact that the instruction set is implemented in a micro-machine
rather than directly on transistors is totally irrelevant.
The Pentium is also a microcoded machine, but since the lowest level
you can reach down to is the x86 instruction set, nobody knows or cares.
(Well, actually, you can download microcode patches sometimes.
On the Lisp Machines that were microcoded, the system software
(including the GC) was written in normal instructions, with the
instruction set essentially being LISP.
"Writing microcode" means "implementing new instructions on the hardware".
The transistors don't implement instructions (or micro-instructions
for that matter), anyway. Each instruction (and therefore the GC)
is actually implemented using quantum states of electrons...
The reason for having writeable microcode stores, such as on most of
the Lisp Machine architectures, and for that matter on the DEC PDP-10
computer system, was so that you could change around the instruction set
A few other computers that use microcode include: IBM/360 (most models),
Honeywell Level 64, Burroughs B1700 (instructions for BASIC, FORTRAN,
COBOL), HP 2100 and 9800, Motorola 65C02 and 68000, the IBM RS/6000,
and the DEC VAX, and the DEC Alpha.
On machines with writable microcode, loading the microcode happens very
early on as part of bootloading the machine, before it is executing any
instructions. This is accomplished through special hardware or by using
a front-end processor. Some processors have their microcode stored in
some kind of ROM (in modern ones, on the CPU chip itself).
It is correct to say that the Lisp Machine microcode was part of the
garbage collector in the same way that it is proper to say that the
Pentium microcode is part of how you load a 16-bit word from main
storage into an HL register pair.
Microcode can play a role in garbage collection in the sense that regular
macro-instructions can be (micro)coded to participate in garbage collection.
For example, instructions can check which part of memory an object reference
points to, and maybe transport the object or update invisible pointers.
This does not require microcode, however; it's just work that the primitive
Lisp functions (or the instructions corresponding to them) have to do.
Read the standard GC literature for more info.
The thing you might be looking for is called "subprimitives", which are
macro instructions (just like ADD or MOVE or PUSH), but which are capable
of accessing memory at a lower abstraction level than normal Lisp functions.
For example, one subprimitive can look at the type-tag of an object (the bits
that say "instance" or "CDR-coded cons cell"), or move memory words
around using pointers, that sort of thing. Subprimitive functions are
called by programs just as ordinary functions, but they can do things
that get under the covers of the Lisp implementation. If your program
calls a subprimitive function, you can crash the system (by creating
illegal data structures that normal Lisp primitive functions will
trip over).
See my previous article in this newsgroup explaining how the Lisp
Machine GC is written in Lisp, uses subprimitives, also uses the
LOOP macro, and so forth, and also explains some of the Lisp Machine
instruction set and stuff. The GC is not written in straight Common Lisp,
because that lacks the subprimitives necessary to access the implementation.
I am not sure how it's done in Lisp on conventional architectures,
because GC typically involves transporting Lisp objects from one
memory location to another, and Common Lisp does not include
functions for directly hacking memory locations. I assume there
must be subprimitive functions in those Lisp implementations, too.
However, I would still say that the GC is written in Lisp.
(But not in ANSI Common Lisp without extensions.)
Maybe the Franz, Xanalys, CMUCL, and CLISP guys could chime in
here and explain what kind of functions are called by their GCs.
William D Clinger
> "Joe Marshall" <prunes...@attbi.com> writes:
>
> > This is not necessarily the case. It is fairly easy to write Lisp and
> > Scheme
> > code that either does not allocate temporary storage, only allocates
> > temporary storage in a provably stack-like manner, or allocates a bounded
> > amount of temporary storage from a statically allocated `pool'.
>
> You've ignored what was clearly said above about subsetting. I'm
> interested in doing it *WITHOUT* such restrictions in the language.
I think you'd get more useful answers to your question if you'd do
a better job of explaining _why_ you want to reject collectors that
are written in a subset of Scheme. In point of fact, most collectors
written in C or assembly language also go to great trouble to avoid
allocating storage during a collection, so I don't understand why
you object to doing that in Scheme.
Will
Thomas F. Burdick
> Maybe the Franz, Xanalys, CMUCL, and CLISP guys could chime in
> here and explain what kind of functions are called by their GCs.
[I'm not claiming to be one of the cmucl "guys", just a user] Well,
the CMUCL GC is written in C. It's got a grip of bootstrapping issues
as it is, I can't see the benefits of a GC in Lisp outweighing the
cost of adding to those. Perhaps some day the SBCL project will
result in a code base on which this would be less than horribly
painful :)
I'm working on a Lisp system that uses a GC written in C++. In the
long run, it will be possible to replace it with one written in Lisp,
which will hopefully allow us be more agile and adaptive to profiling
results in our GC development. The strategy for writing new GCs will
probably be to do initial development in Lisp, rewrite in
micro-performance-minded Lisp, and rewrite some parts in C++ and
assembly language. Of course, it might just not be worth it to
rewrite the GC.
We'll be able to do this because all[*] of the memory-allocating parts
of the runtime are written with allocation issues in mind: where they
allocate from can be controlled dynamically.
[*] This approach might change. In the end, maybe only some parts of
the runtime will support this -- meaning we'll be limited in what
parts of the language we can use in our GC -- or we might use some of
the bunch of other optimization ideas I have in my head for this. I'm
trying to believe my own rhetoric, though, and get it working first :)
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Thomas Bushnell, BSG
> I think you'd get more useful answers to your question if you'd do
> a better job of explaining _why_ you want to reject collectors that
> are written in a subset of Scheme. In point of fact, most collectors
> written in C or assembly language also go to great trouble to avoid
> allocating storage during a collection, so I don't understand why
> you object to doing that in Scheme.
One reason is that I don't want to impinge on the compiler. It might
well be that even if I don't call cons, the compiler might.
It might also be that the best way to express a particular compilation
is by manipulating some list, and I don't want to have to gunk up the
code in order to avoid calling cons.
In addition, a rule "you can't call cons" is very fragile, because you
also can't call any function that itself calls cons, which requires
you to keep track, for just about every generally useful function,
whether it calls cons or not. Now that's fragile, because every time
you change any function in your general library of functions, you
might be changing whether the GC routine can safely call it; that's
the kind of non-local effect that I'm loath to entertain.
So I don't mind writing by trying to minimize cons; sure, that's
fine. But prohibiting it is not too good. Similar comments apply to
call/cc, exception mechanisms, and the like.
Thomas
Pierre R. Mai
> The goal is to eliminate reliance on language processors for other
> languages. That's why I say "self-hosting". Linux, for example, is a
> self-hosting C implementation: the kernel, toolchain, shells, and
> compiler, are all written in C, with no need for another language to
> help out.
Since your definition prohibits sub-setting that e.g. disallows the
use of normal allocation primitives, Linux is _not_ self-hosting
according to your definition: You can't use the full ANSI C standard
library in the kernel, including the use of malloc.
Regs, Pierre.
--
Pierre R. Mai <pm...@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
Christopher Browne
> tb+u...@becket.net (Thomas Bushnell, BSG) writes:
>> The goal is to eliminate reliance on language processors for other
>> languages. That's why I say "self-hosting". Linux, for example,
>> is a self-hosting C implementation: the kernel, toolchain, shells,
>> and compiler, are all written in C, with no need for another
>> language to help out.
> Since your definition prohibits sub-setting that e.g. disallows the
> use of normal allocation primitives, Linux is _not_ self-hosting
> according to your definition: You can't use the full ANSI C standard
> library in the kernel, including the use of malloc.
It's a given that CONS can't call CONS, unless CONS represents a light
wrapper on top of MACHINE-CONS, which does the _real_ work...
But it seems entirely likely that big chunks of Lisp _could_
"self-host."
Garbage collection would be an interesting example.
Now, GC is doubtless going to use some components that go _beyond_
standard Lisp/Scheme, as standard Lisp/Scheme have _no_ functions
designed to directly access memory, and that's going to be what
MACHINE-CONS and GC are doing.
Flip side: It should be _fine_ for GC to CONS and generate collectable
garbage, so long as it's not doing so within the scope of the memory
it's working on.
Thus, for "CONSing GC," you just need to ensure that you have multiple
blocks of memory which you can:
a) collect independently, and
b) choose to CONS in, or perhaps more important, to _NOT_ CONS in.
A reasonable architecture probably involves at least 3 regions of
memory, at least two being distinct...
1. The one that you're collecting, REGION-1;
2. One (or more) into which objects can be thrown (e.g. - the goal
of GC might be to completely empty REGION-1, by moving objects
into other regions, thus eliminating any memory fragmentation);
3. One for the GC process to CONS into.
A slick thing might be for this region to be allocated newly at
the start of GC and then return it at the end, throwing its
contents away completely. That approach has the interesting
property that if you can be sure that GC won't do more than
(say) 1MB of CONSing, you could reserve a permanent fixed buffer
of 1MB for the purpose, and be certain you'll never run out of
memory to the point of being unable to garbage collect.
This has implications that can't be expressed in standard R5RS or ANSI
CL. That's not because they're not expressive enough, but rather
because the implications have to do with lower level details, most
notably the logic of how memory is allocated, which is something which
the standards do not directly address.
--
(reverse (concatenate 'string "gro.mca@" "enworbbc"))
http://www.ntlug.org/~cbbrowne/linuxxian.html
PASCAL is not a language. It was an experiment combining the
flexibilty of C with that of a drug-crazed penguin. It is also the
'language' of choice of many CS professors who aren't up to handling
REAL programming. Hence, it is not a language.
Thomas Bushnell, BSG
> tb+u...@becket.net (Thomas Bushnell, BSG) writes:
>
> > The goal is to eliminate reliance on language processors for other
> > languages. That's why I say "self-hosting". Linux, for example, is a
> > self-hosting C implementation: the kernel, toolchain, shells, and
> > compiler, are all written in C, with no need for another language to
> > help out.
>
> Since your definition prohibits sub-setting that e.g. disallows the
> use of normal allocation primitives, Linux is _not_ self-hosting
> according to your definition: You can't use the full ANSI C standard
> library in the kernel, including the use of malloc.
The point here isn't to be pedantic. I'm interested in a rather
specific problem, not posing some idle question, nor looking for
foolish attempts to start arguments. I think the question I'm
investigating is fairly clear, but if it isn't, I'm happy to keep
clarifying. So far, for all the people posting rather pointless
comments, and at least two secondary flame wars, I've gotten only a
very single one (1) useful pointer, and my request for follow up
information has so far not merited any response.
I'm not against subsetting as a strategy--if *necessary*. But just
saying "self-hosting GC is easy if you subset" (which is certainly
true)--is not really productive. I gave, in a different message, some
of the reasons why subsetting is dangerous.
C does not depend on dynamic memory allocation to nearly the degree as
good Scheme or Lisp code, which is one reason that the usual malloc
implementation in C can easily avoid allocating memory.
Scheme compilers often allocate memory for other reasons than direct
calls to cons, C compilers never do, for example.
Thomas
Joe Marshall
> "Joe Marshall" <prunes...@attbi.com> writes:
>
> > This is not necessarily the case. It is fairly easy to write Lisp and
> > Scheme
> > code that either does not allocate temporary storage, only allocates
> > temporary storage in a provably stack-like manner, or allocates a
bounded
> > amount of temporary storage from a statically allocated `pool'.
>
> You've ignored what was clearly said above about subsetting. I'm
> interested in doing it *WITHOUT* such restrictions in the language.
I was rebutting this particular statement: ``The basic problem is
that the GC, if written in Lisp/Scheme, will itself be allocating memory.''
This is incorrect on two counts:
1. A GC written in Lisp or Scheme will not necessarily be
allocating memory.
and
2. Allocation of memory by the GC is not a problem, let alone
the `basic' one. In fact, a copying GC can allocate quite
a bit of memory.
Now, in regards to subsetting, what you said was this:
``Some subsetting is tolerable, but the prohibition
of things like cons, creation of closures, and call/cc
is not a solution to the problem I'm posing.''
I guess I don't understand what you mean by subsetting.
If you have lexical closures, cons, and call/cc, you have
essentially everything.
> > In any case, as I mentioned before, the GC *can* cons provided it
> > doesn't cons too much.
>
> So, that opens two problems: does it cons from the main heap? If so,
> doesn't that impede certain kinds of GC algorithms? If it conses from
> a different heap, how big of one can be used?
Two problems?
Yes, it conses from the main heap. All GC algorithms have variants
that allow the GC to CONS, so it should not impede the algorithm.
The answer to the last question depends on the amount of memory
available to the process.
> I'm looking for *research* or *experience*. I'm able to fill in the
> obvious points myself.
If you are implying that I have neither researched the problem nor
have experience in it, you are mistaken.
> > What is more interesting is writing the virtual memory and interrupt
> > system in Lisp.
>
> I'm not asking about "whatever is most interesting". I'm asking about
> GC. I already have a pretty durn solid idea about how to write VM
> systems and interrupt handling, and doing it in Lisp is not terribly
> different from other languages.
Having written VM, interrupt handling, and GC in Lisp, I have come
to the conclusion that GC is the easiest of the three. But I will
defer to your `durn solid ideas'.
> > The LMI K-machine had no microcode; the Lisp was compiled
> > `down to the metal'. The GC was decoupled from allocation.
> > Just above the virtual memory abstraction was a `region' abstraction.
> > A `region' is a very large block of address space that is explicitly
> > managed. CONS would allocate out of some distinguished region,
> > and when it ran out of room, it would simply call to allocate another
> > region. The GC would run in a separate thread and monitor the growth
> > of the allocated space. When it decided to flip, it would select a
region,
> > evacuate the live data from it, then return that region to free space.
>
> Thanks--this is the kind of detail I'm looking for.
>
> Is there any documentation or published descriptions available?
Start with this:
http://fare.tunes.org/tmp/emergent/kmachine.htm
There is no documentation on the VM, interrupt system, or GC
because I haven't written it down.
~jrm
Thomas Bushnell, BSG
> A slick thing might be for this region to be allocated newly at
> the start of GC and then return it at the end, throwing its
> contents away completely. That approach has the interesting
> property that if you can be sure that GC won't do more than
> (say) 1MB of CONSing, you could reserve a permanent fixed buffer
> of 1MB for the purpose, and be certain you'll never run out of
> memory to the point of being unable to garbage collect.
So one problem with this is computing the amount of memory needed.
Normal computations of space complexity are not apropos here, because
normal computations assume that GC is happening... That is, a normal
computation of space complexity counts the total number of *live*
cells. The bound we need for this is different: the total number of
*allocations* is what needs to fit in that 1 MB.
Consider, for example, a compiler which did one allocation per-tail
call (but quickly dropped the only pointer to the cell). Such a
compiler has the necessary proper tail recursion property, because at
most one cell is live from the tail recursion. However, if we are
counting total allocations, such a strategy might pile rather up a
bunch.
Obviously any sane compiler doesn't allocate a cell per
tail-recursion, but that example is enough to demonstrate the point.
A standard binary tree traversal, for a tree with N nodes, has space
complexity of ln(n). But if you are using lisp lists to hold the
stack in the normal way, the total number of allocations is order N.
Now, of course, you could put the stack in an array instead of a list,
and then only need order ln(n). But that's the kind of disruption of
ordinarily sane code that I want to avoid--that's the whole point.
Thomas
Joe Marshall
> ces...@qnci.net (William D Clinger) writes:
>
> In addition, a rule "you can't call cons" is very fragile, because you
> also can't call any function that itself calls cons, which requires
> you to keep track, for just about every generally useful function,
> whether it calls cons or not. Now that's fragile, because every time
> you change any function in your general library of functions, you
> might be changing whether the GC routine can safely call it; that's
> the kind of non-local effect that I'm loath to entertain.
There is a very robust way of enforcing the rule `you cannot call
cons'. Simply do not make it available in the environment. You
cannot call it because it is undefined. You cannot accidentally
call something that calls it because those functions are not
defined until CONS is.
> So I don't mind writing by trying to minimize cons; sure, that's
> fine. But prohibiting it is not too good. Similar comments apply to
> call/cc, exception mechanisms, and the like.
I think it is obvious that you cannot expect to implement a particular
feature starting from the assumption that the feature is already
available. If CONS, CALL/CC, etc. are not primitive forms that your
compiler can handle, you need to implement them in the primitives that
you *do* have. And whatever implementation you come up with cannot
assume the full language.
Joe Marshall
>
> C does not depend on dynamic memory allocation to nearly the degree as
> good Scheme or Lisp code, which is one reason that the usual malloc
> implementation in C can easily avoid allocating memory.
When you call malloc in C, you will dynamically allocate memory.
>
> Scheme compilers often allocate memory for other reasons than direct
> calls to cons, C compilers never do, for example.
C has a large set of unenforced rules and restrictions that
you *must* follow in order for the compiler to create correct
code. These restrictions allow the compiler to assume that
the code cannot `implicitly' cons.
C is *already* the non-consing subset (of an undefined C-like
language that has no restriction on lifetimes of automatic
variables).
Thomas Bushnell, BSG
> This is incorrect on two counts:
> 1. A GC written in Lisp or Scheme will not necessarily be
> allocating memory.
If the compiler generates hidden memory allocations, then anything is
going to be allocating memory. And I don't want to restrict the
compiler against such a strategy when it's the right thing for
compiling code well. (Consider that executing a lambda special form
must often allocate memory; consider also that good Scheme programs
execute lambda forms *constantly*.)
If it's *obliged* to avoid allocations, then I can't call *any*
library function without knowing whether it does memory allocations or
not, and suddenly the correctness of my algorithm is dependent on each
such function's continuing not to allocate. Even ordinary integer
arithmetic is suddenly off limits.
Suddenly I'm not allowed to use (lambda ...); I'm not allowed to use
map. Do I need to pay very close attention to stack depth now? Is
for-each going to be dangerous?
Of *course* I could write the GC in a dialect of Scheme pruned down to
have no more features than FORTRAN. But that's not really the point.
I keep saying it's not the point, and people keep saying "hey, you can
do GC in a subsetted language". Well duh. FORTRAN is Turing
complete. That's not the point.
> I guess I don't understand what you mean by subsetting.
> If you have lexical closures, cons, and call/cc, you have
> essentially everything.
Yep! And I need that; it's part of writing good Scheme code.
Subsetting is establishing a rule like "the GC isn't allowed to use
function FOO" where FOO is a normal constant thing in decent Scheme
programming--like lambda, cons, and call/cc.
> If you are implying that I have neither researched the problem nor
> have experience in it, you are mistaken.
No, but I'm looking for the *research*. I really want pointers to
specifics. Can you point me at an article that addresses the topic?
Implementation details? People who have written about it? I don't
want a freaking tutorial, I know wtf I'm doing. I'm asking for a
research pointer.
> Having written VM, interrupt handling, and GC in Lisp, I have come
> to the conclusion that GC is the easiest of the three. But I will
> defer to your `durn solid ideas'.
I didn't say GC was harder than the others. Ever. I said I know how
to write VM systems and interrupt handlers. VM systems and interrupt
handlers are generally more complex than garbage collectors. But I
*know* how to do those well. I even know how to do GC (in general)
well. Hence, I'm asking a very targeted question, about the
particular thing I'm wondering about.
Thomas
Thomas Bushnell, BSG
> There is a very robust way of enforcing the rule `you cannot call
> cons'. Simply do not make it available in the environment. You
> cannot call it because it is undefined. You cannot accidentally
> call something that calls it because those functions are not
> defined until CONS is.
Huh? Not in Scheme, at least. Scheme implementations differ on how
to do environment manipulation (except for simple extension).
Suppose, however that we have a special form:
(munge-environment (drops) forms ...)
which executes the forms with the symbols named in 'drops' omitted
from the environment. Then the following certainly has cons
unavailable, but still calls cons:
(munge-environment (cons)
(map some-procedure some-list))
The reason, of course, is that map gets cons from the lexical context
in scope when it was defined.
> I think it is obvious that you cannot expect to implement a particular
> feature starting from the assumption that the feature is already
> available. If CONS, CALL/CC, etc. are not primitive forms that your
> compiler can handle, you need to implement them in the primitives that
> you *do* have. And whatever implementation you come up with cannot
> assume the full language.
Cons need not call gc. Cons, obviously, cannot be implemented in
terms of cons. But gc can be (and really, should be) thought about
more-or-less uncoupled with the mutator. It's not something that cons
calls (in reasonably mature systems).
Most sane compilers know cons quite directly, of course. But they
don't call gc, something else does, "off line" from the main executing
thread, even if the thread stops while gc runs.
Thomas
Thomas Bushnell, BSG
> > C does not depend on dynamic memory allocation to nearly the degree as
> > good Scheme or Lisp code, which is one reason that the usual malloc
> > implementation in C can easily avoid allocating memory.
>
> When you call malloc in C, you will dynamically allocate memory.
But the usual malloc *implementation* does not. Or rather, it calls
sbrk (or some such), which allocates raw heap pages. The point is
that malloc is not recursive, and neither is cons, of course.
However, gc != cons. It's perfectly reasonable for me to want gc to
call cons; that's nothing at all like saying that cons can't call
cons.
Thomas
Joe Marshall
> "Joe Marshall" <prunes...@attbi.com> writes:
>
> > There is a very robust way of enforcing the rule `you cannot call
> > cons'. Simply do not make it available in the environment. You
> > cannot call it because it is undefined. You cannot accidentally
> > call something that calls it because those functions are not
> > defined until CONS is.
>
> Huh? Not in Scheme, at least. Scheme implementations differ on how
> to do environment manipulation (except for simple extension).
> Suppose, however that we have a special form:
>
> (munge-environment (drops) forms ...)
>
> which executes the forms with the symbols named in 'drops' omitted
> from the environment. Then the following certainly has cons
> unavailable, but still calls cons:
>
> (munge-environment (cons)
> (map some-procedure some-list))
>
> The reason, of course, is that map gets cons from the lexical context
> in scope when it was defined.
Er, yes, but that isn't how to do it --- it doesn't work.
The run-time library of your system should be `stratified', with
each `layer' depending only on those layers below it. Now Scheme
doesn't define a package or module system that enforces this,
so you'll have to `roll your own'. At the very lowest level,
you *only* have those primitive procedures that the compiler
can generate inline code for. At another level, you'll add
CONS and MAP.
> > I think it is obvious that you cannot expect to implement a particular
> > feature starting from the assumption that the feature is already
> > available. If CONS, CALL/CC, etc. are not primitive forms that your
> > compiler can handle, you need to implement them in the primitives that
> > you *do* have. And whatever implementation you come up with cannot
> > assume the full language.
>
> Cons need not call gc. Cons, obviously, cannot be implemented in
> terms of cons. But gc can be (and really, should be) thought about
> more-or-less uncoupled with the mutator. It's not something that cons
> calls (in reasonably mature systems).
I agree that CONS shouldn't bottom out to the GC, but I've seen more
`mature' systems that do it that way than not.
> Most sane compilers know cons quite directly, of course. But they
> don't call gc, something else does, "off line" from the main executing
> thread, even if the thread stops while gc runs.
They do, do they? News to me.
Thomas Bushnell, BSG
> The run-time library of your system should be `stratified', with
> each `layer' depending only on those layers below it. Now Scheme
> doesn't define a package or module system that enforces this,
> so you'll have to `roll your own'. At the very lowest level,
> you *only* have those primitive procedures that the compiler
> can generate inline code for. At another level, you'll add
> CONS and MAP.
Well sure, duh, that's basic OS design, nothing weird there.
However, none of that requires GC to be anywhere near the "lowest"
level. And indeed, there are plenty of reasons not to want it to be
in a low level, since, after all, one usually wants to keep as little
as possible in the lowest levels.
> I agree that CONS shouldn't bottom out to the GC, but I've seen more
> `mature' systems that do it that way than not.
Well, maybe I'm building more into "mature" than I should. ;)
I think (without much evidence, however) that the best compiler
strategies do allocation from "private" (per-thread) arenas, and when
they run out, they just get another arena. At worst, they block if
there are no arenas available.
Timing GC is managed entirely separately (though coordinated in the
obvious ways).
That seems a much happier method.
For a quick-and-cheap lisp one usually just has cons bottom out to
calling some mark-and-sweep.
> > Most sane compilers know cons quite directly, of course. But they
> > don't call gc, something else does, "off line" from the main executing
> > thread, even if the thread stops while gc runs.
> They do, do they? News to me.
Well, yeah, I think so. It's common to inline cons, I think, and
allocate from private arenas. At least, my Scheme-compiler-whiz
friends tell me that. (If you are in a bytecoded or compile-to-C sort
of system, then certainly something else might be considered normal or
sane.)
Thomas
Joe Marshall
> "Joe Marshall" <prunes...@attbi.com> writes:
>
> > This is incorrect on two counts:
> > 1. A GC written in Lisp or Scheme will not necessarily be
> > allocating memory.
>
> If the compiler generates hidden memory allocations, then anything is
> going to be allocating memory.
I don't understand this line of reasoning. Are you saying ``If a
compiler *always* generates code that allocates from the heap, then
*all* code such generated will allocate from the heap.''? That is
an uninteresting tautology about an uninteresting compiler.
Outside of that interpretation, I fail to see how this negates
my statement that a GC will not necessarily CONS. Certainly an
arbitrary piece of code *may* cons, but that is not the same as
saying `no GC can be written that does *not* cons'.
> And I don't want to restrict the
> compiler against such a strategy when it's the right thing for
> compiling code well. (Consider that executing a lambda special form
> must often allocate memory; consider also that good Scheme programs
> execute lambda forms *constantly*.)
>
> If it's *obliged* to avoid allocations, then I can't call *any*
> library function without knowing whether it does memory allocations or
> not, and suddenly the correctness of my algorithm is dependent on each
> such function's continuing not to allocate.
This is correct. But as an implementor, you ought to know which
functions cons and which ones do not. In fact, the partitioning
of the implementation into a non-consing and a consing set is one
of the first design decisions.
> Even ordinary integer arithmetic is suddenly off limits.
`Generic' arithmetic, yes. Fixnum arithmetic ought to be just fine.
> Suddenly I'm not allowed to use (lambda ...);
Only if such use requires consing a closure. `Downward funargs'
and lambda's with no free variables do not require run-time allocation
of storage.
> Do I need to pay very close attention to stack depth now?
Unless your hardware supports arbitrary stack depth, yes.
Perhaps you will wish to provide a nicer way of dealing with
stack overflow. If so, the code that implements this will have
to be *very careful* not to overflow itself, but the code above
this level of abstraction can ignore it.
> Is for-each going to be dangerous?
You're the implementor, you tell me. In my experience, for-each
can be implemented completely in-line, and it requires no temporary
storage.
> Of *course* I could write the GC in a dialect of Scheme pruned down to
> have no more features than FORTRAN. But that's not really the point.
> I keep saying it's not the point, and people keep saying "hey, you can
> do GC in a subsetted language". Well duh. FORTRAN is Turing
> complete. That's not the point.
What *is* the point, then? Do you want to write the GC for a
scheme implementation using only R5RS Scheme? Sorry, you are SOL.
Do you want to write a GC in Lisp using techniques that people have
been using for the past 30 years? Well, they use a restricted
subset of the language.
> > I guess I don't understand what you mean by subsetting.
> > If you have lexical closures, cons, and call/cc, you have
> > essentially everything.
>
> Yep! And I need that; it's part of writing good Scheme code.
Catch-22. If lexical closures, cons, and call/cc are available,
you need not implement them. If they are not available, you *cannot*
use them to implement themselves.
> Subsetting is establishing a rule like "the GC isn't allowed to use
> function FOO" where FOO is a normal constant thing in decent Scheme
> programming--like lambda, cons, and call/cc.
In one breath you say `Some subsetting is tolerable, but
the prohibition of things like cons, creation of closures, and call/cc
is not a solution to the problem I'm posing.'
A `subset' that allows CONS, lexical closures, and call/cc is
no subset whatsoever.
> > If you are implying that I have neither researched the problem nor
> > have experience in it, you are mistaken.
>
> No, but I'm looking for the *research*. I really want pointers to
> specifics. Can you point me at an article that addresses the topic?
Nope. I know of no such articles.
> Implementation details?
See the microcode for the Lisp Machine.
> People who have written about it?
I don't recall any articles being written about the
details of the stratification of the architecture.
> I didn't say GC was harder than the others. Ever. I said I know how
> to write VM systems and interrupt handlers. VM systems and interrupt
> handlers are generally more complex than garbage collectors. But I
> *know* how to do those well. I even know how to do GC (in general)
> well. Hence, I'm asking a very targeted question, about the
> particular thing I'm wondering about.
Well, then you should know that CONSing during GC is not an issue.
Joe Marshall
>
> However, none of that requires GC to be anywhere near the "lowest"
> level. And indeed, there are plenty of reasons not to want it to be
> in a low level, since, after all, one usually wants to keep as little
> as possible in the lowest levels.
Yep. So what's the problem?
Thomas Bushnell, BSG
> I don't understand this line of reasoning. Are you saying ``If a
> compiler *always* generates code that allocates from the heap, then
> *all* code such generated will allocate from the heap.''? That is
> an uninteresting tautology about an uninteresting compiler.
I'm saying that I don't want to have to constrain the compiler in
significant ways.
> Outside of that interpretation, I fail to see how this negates
> my statement that a GC will not necessarily CONS. Certainly an
> arbitrary piece of code *may* cons, but that is not the same as
> saying `no GC can be written that does *not* cons'.
Right. Of course you can write a GC that does not cons. I keep
saying so, and you keep trying to prove it to me for some reason.
I can also write a GC that never uses identifiers that include the
letter E. But why should I?
Moreover, keeping all cons out of the GC is a pain, it requires citing
the GC way low in the call-graph, for no particular reason--that is,
if there are good strategies for allowing GC to have full use of the
language facilities.
Yes, it's possible to write a GC that avoids cons. Yes, it's possible
to write a GC that avoids cons. Yes, I know. Please stop trying to
prove it to me. I know it's true.
My question is: what are the strategies in use (now, or historically,
or in research) for writing a GC that does *not* have such a
restriction?
> > Suddenly I'm not allowed to use (lambda ...);
>
> Only if such use requires consing a closure. `Downward funargs'
> and lambda's with no free variables do not require run-time allocation
> of storage.
You're telling me things that I know perfectly well. If you read what
I wrote *carefully* you see that I said that *some* lambda's require
allocation.
> Unless your hardware supports arbitrary stack depth, yes.
> Perhaps you will wish to provide a nicer way of dealing with
> stack overflow. If so, the code that implements this will have
> to be *very careful* not to overflow itself, but the code above
> this level of abstraction can ignore it.
Right. Of course. This is boilerplate OS design.
But why should the GC have to have the restrictions incumbent on the
lowest levels of the OS?
> What *is* the point, then?
How many times do I have to say it?
I'm asking about experience writing GC's that have essentially full
access to the language facilities (say, arbitrary lambda, cons, and
call/cc). I keep saying that's the point, and you keep trying to
prove to me that it's not necessary to have such access.
I'm saying "tell me about P" and you keep saying "not Q! not Q". I
*know* it can be done by subsetting the language. That's *PATENTLY
OBVIOUS*. I'm asking about the *harder* problem, what are the
efficient/sensible ways of doing so without subsetting the language in
such a radical degree.
> Do you want to write the GC for a
> scheme implementation using only R5RS Scheme?
No, I've said this for a bajillion times, of course you can't do it
using only the standard language facilities, at the least you have to
*add* memory peek/poke in some way. That's *PATENTLY OBVIOUS*.
But saying "you have to add new primitives to do it" (which is
obvious) is not the same thing as saying "you have to exclude certain
other primitives to do it" (which is not obvious, and is the point I'm
talking about).
> Do you want to write a GC in Lisp using techniques that people have
> been using for the past 30 years? Well, they use a restricted
> subset of the language.
Right. But was that necessary? Or just the easiest thing? Do they
have any experience doing it without a restriction on the language?
I keep saying this, I feel like I'm repeating myself endlessly, and
you keep misunderstanding. I don't know whether that's my fault or
not, but I don't know how much clearer I can be.
> > > I guess I don't understand what you mean by subsetting.
> > > If you have lexical closures, cons, and call/cc, you have
> > > essentially everything.
> >
> > Yep! And I need that; it's part of writing good Scheme code.
>
> Catch-22. If lexical closures, cons, and call/cc are available,
> you need not implement them. If they are not available, you *cannot*
> use them to implement themselves.
You are not talking to some undergraduate CS student who barely
understands how the world works.
gc != {lexical closures, cons, call/cc}. It's *PATENTLY OBVIOUS* that
you can't implement cons in cons. But that doesn't mean at all that
you can't implement GC using cons. GC is something that need not live
anywhere near the bottom layers of the system; my question is
precisely about the (possibly harder) case where it is *not*, but
instead has full access to language facilities.
> > Subsetting is establishing a rule like "the GC isn't allowed to use
> > function FOO" where FOO is a normal constant thing in decent Scheme
> > programming--like lambda, cons, and call/cc.
>
> In one breath you say `Some subsetting is tolerable, but
> the prohibition of things like cons, creation of closures, and call/cc
> is not a solution to the problem I'm posing.'
>
> A `subset' that allows CONS, lexical closures, and call/cc is
> no subset whatsoever.
Yes, precisely. As a response to my question, I'm willing to allow
subsets that don't seriously impede the normal language facilities,
but not anything "important". I keep saying that, but you keep
ignoring it, for some reason.
> See the microcode for the Lisp Machine.
Where is it available?
> Well, then you should know that CONSing during GC is not an issue.
So lots of systems have a GC that does memory allocation or not?
Thomas Bushnell, BSG
Many stop-the-world GC algorithms have the property that the heap is
in a "sane" state only at the beginning and end of the collection, but
during the collection, the heap is not in such a "sane" state. Most
any stop-the-world algorithm assumes that no mutations happen during
collection. So if the collector calls cons, and those cells come from
the normal arena; if the collector mutates data structures shared with
the rest of the system; etc; then it seems clear that a simple
mark-sweep implementation will fail rather spectacularly.
So do people have experience having the collector allocate out of a
different heap? Of what size? (See my other post on the difference
between space complexity and total-number-of-allocations for why
that's not necessarily a trivial problem.)
Etc.
Bill Richter
> Right. Of course you can write a GC that does not cons. I keep
> saying so, and you keep trying to prove it to me for some reason.
Thomas, I think maybe you're running into some hostility that was
generated by Tom Lord, who ran a number of rude-sounding threads like
"What were they smoking?". Why not write an article about what your
real purpose is? Is this about Hurd? How is the Hurd coming along
anyway? Is this a guile problem? Inquiring minds want to know :)
--
Bill
<http://www.math.nwu.edu/~richter>
Joe Marshall
> "Joe Marshall" <prunes...@attbi.com> writes:
>
> > "Thomas Bushnell, BSG" <tb+u...@becket.net> wrote in message
> > news:874rjor...@becket.becket.net...
> > >
> > > However, none of that requires GC to be anywhere near the "lowest"
> > > level. And indeed, there are plenty of reasons not to want it to be
> > > in a low level, since, after all, one usually wants to keep as little
> > > as possible in the lowest levels.
> >
> > Yep. So what's the problem?
>
> Many stop-the-world GC algorithms have the property that the heap is
> in a "sane" state only at the beginning and end of the collection, but
> during the collection, the heap is not in such a "sane" state. Most
> any stop-the-world algorithm assumes that no mutations happen during
> collection. So if the collector calls cons, and those cells come from
> the normal arena; if the collector mutates data structures shared with
> the rest of the system; etc; then it seems clear that a simple
> mark-sweep implementation will fail rather spectacularly.
Mutation != allocation. Most stop-the-world GC algorithms assume that
you will not be moving an object from `space to be scavenged' to
`space that has been scavenged' without scavenging the object
thus moved (indeed, that is what the write barrier prevents in
those GCs that run concurrently). But this is not the same as disallowing
creation of new objects.
If you are using a copying GC, simply have the GC allocate in the
to-space. If you are using mark/sweep, make sure the newly consed
objects are marked.
> So do people have experience having the collector allocate out of a
> different heap? Of what size? (See my other post on the difference
> between space complexity and total-number-of-allocations for why
> that's not necessarily a trivial problem.)
First of all, if the GC allocates a byte for every byte it collects,
then it is easy to see that garbage collection becomes a useless
operation.
Second, if the GC retains *every* object (i.e., nothing seems to
be garbage), then the amount of storage you need at the end of a
flip will be the amount at the beginning plus the amount the GC
allocated. By the first point, this will be strictly less than
twice the current amount of storage.
Thomas Bushnell, BSG
Ah well, Tom Lord does do that. I'm not him. :) But I understand
perfectly if people have left-over hostility about that.
It's neither about the Hurd nor guile.
Guile is a fairly ordinary hosted implementation of Scheme; I'm
certainly a guile fan, but not because I think it will replace heavy
duty Lisp or Scheme systems. Guile of course is wedded to C, and its
gc is written in C--as it should be, I think. Guile is "just" an
extension language; it's no more a "real big Scheme system" than Emacs
is a "real big Lisp system". From the standpoint of language theory,
Guile has only two contributions that I can think of (and I'm not sure
how really significant they are): One is the need for a seriously
robust and flexible foreign function interface. The other is the
"translate other languages into Scheme" idea. The first of these is
still awkward and Guile is still figuring it out. The latter is as
yet totally unproven. (Though I am actually working on a
Python->Scheme translator for the FSF as the first such project.)
The Hurd is a "standard" kernel/processes system. I think it's cool
(duh!) but I have no particular axe to grind; if someone doesn't think
it's cool, they're free to ignore it. The project is moving forward
swimmingly, with a Debian GNU/Hurd release in process. We have a nice
crowd of people doing development and improvement; some are really
motivated. I'm pleased with it at present, though (obviously) I wish
I had been able to get things moving with more alacrity--it's been in
the works for rather a *long* time now.
So if my interests here are not Hurd- or Guile-related, what are they?
Well, it's connected to a project M-DEL fantasy M-DEL idea for a new
OS (called Sky), which is a dream of myself and a few friends. In
Sky, we are motivated by three coordinate goals:
1) A passion for single-address space safe language systems (like
Smalltalk, Lisp, etc, etc). After flirting with Self and then Java
(eek!) we've settled on Scheme. Of course, we'll have rather more
functions than your average Scheme system--the library will end up
as rich as Common Lisp. One reason for Scheme over Lisp is that we
want to do things *right*; we do not want to settle for "good
enough" or "this is what everyone else does". Common Lisp has
many, many historical artifacts that we just don't want to be
saddled with.
2) A desire to have a *good* user interface rather that the windowing
crap we have now. (It was good at the time, but we know more about
user interfaces than when Xerox PARC came up with the current
paradigm.) Among other things, we are enchanted by Jef Raskin's
book "The Humane Interface". We want a zooming interface, an
"objects on canvas with good searching" rather than traditional
filesystems and such [with buzzwords like "persistent object
store"], and so forth.
3) We are disgusted by the number of times the *very same problem* is
coded a bajillion times on an existing system. Raskin counts more
than a *dozen* different text editors on a typical desktop GUI.
Most of these are little toy editors for filling in forms and such,
and there should instead be *one* editor, which knows how to edit
everything with a single uniform command set. Guess how many times
the average GNU/Linux system implements command line argument
parsing--a task that is really a *total* waste, contributing
nothing to the overall system. We believe this is an artifact of
the "shell and separate processes" structure of most systems.
4) We want to do something fun and cool, and what passes for fun and
cool in operating systems and user interfaces at present does *not*
impress us. The problem with the Hurd is that it's just another
way of implementing Posix (plus some really nifty other bits too,
don't get me wrong). But Posix is the bug.
I freely confess that this may all be pie in the Sky. Pun intended.
But I enjoy thinking about it when I'm tired with my day job (teaching
and studying philosophy) and I enjoy writing code and planning and
designing, and I hope it will come to something real. I have no
particular rush either.
If this interests you, great; if you think it's misguided or you want
us to design something else, well, we aren't looking for the old
LispOS mailing list. We care not at all for snipes like "that's a
waste of time" or "you're doing this all wrong".
We have a wiki describing things at present:
Thomas Bushnell, BSG
> Mutation != allocation. Most stop-the-world GC algorithms assume that
> you will not be moving an object from `space to be scavenged' to
> `space that has been scavenged' without scavenging the object
> thus moved (indeed, that is what the write barrier prevents in
> those GCs that run concurrently). But this is not the same as disallowing
> creation of new objects.
Yes, that's a good point. Thanks for making it.
However, lots of GCs also do mutation, at least, for registering and
maintaining statistics. Obviously, however, there are plenty of hacks
to make that work; it's nothing seriously pervasive.
It's not too much of an imposition to tell the GC can avoid mutating
any previously existing objects (except a few in carefully controlled
ways). I'm thinking about issues of sizing the area the gc allocates
from, for example--something I'm not sure how to think correctly
about. (I understand space complexity well, but I understand
total-number-of-allocations a fair bit less.)
> If you are using a copying GC, simply have the GC allocate in the
> to-space. If you are using mark/sweep, make sure the newly consed
> objects are marked.
In the latter case, that requires some kind of tweak to cons to notice
whether one is in the gc or not. That's not awful, but depending on
how you do it, it might have performance implications, no?
> > So do people have experience having the collector allocate out of a
> > different heap? Of what size? (See my other post on the difference
> > between space complexity and total-number-of-allocations for why
> > that's not necessarily a trivial problem.)
>
> First of all, if the GC allocates a byte for every byte it collects,
> then it is easy to see that garbage collection becomes a useless
> operation.
Indeed.
> Second, if the GC retains *every* object (i.e., nothing seems to
> be garbage), then the amount of storage you need at the end of a
> flip will be the amount at the beginning plus the amount the GC
> allocated. By the first point, this will be strictly less than
> twice the current amount of storage.
Ah, thanks, that's a good argument there for that method of counting.
Joe Marshall
> "Joe Marshall" <prunes...@attbi.com> writes:
>
> > I don't understand this line of reasoning. Are you saying ``If a
> > compiler *always* generates code that allocates from the heap, then
> > *all* code such generated will allocate from the heap.''? That is
> > an uninteresting tautology about an uninteresting compiler.
>
> I'm saying that I don't want to have to constrain the compiler in
> significant ways.
In other words, at all.
> > Outside of that interpretation, I fail to see how this negates
> > my statement that a GC will not necessarily CONS. Certainly an
> > arbitrary piece of code *may* cons, but that is not the same as
> > saying `no GC can be written that does *not* cons'.
>
> Right. Of course you can write a GC that does not cons. I keep
> saying so, and you keep trying to prove it to me for some reason.
>
> I can also write a GC that never uses identifiers that include the
> letter E. But why should I?
Notwithstanding any prejudice you may have against the letter E,
you seem to believe that there is an issue with allowing the GC to
CONS. If you write a GC that does not CONS, you don't have to
deal with this issue. That should be reason enough.
> Moreover, keeping all cons out of the GC is a pain, it requires citing
> the GC way low in the call-graph, for no particular reason--that is,
> if there are good strategies for allowing GC to have full use of the
> language facilities.
>
> Yes, it's possible to write a GC that avoids cons. Yes, it's possible
> to write a GC that avoids cons. Yes, I know. Please stop trying to
> prove it to me. I know it's true.
>
> My question is: what are the strategies in use (now, or historically,
> or in research) for writing a GC that does *not* have such a
> restriction?
Any GC that runs concurrently allows the `mutator' process to
allocate storage. The cons cells don't know who allocated them, so
the GC ought to be able to allocate as well.
A replicating GC works by duplicating the heap *before* the flip.
You should know these things.
> > > Suddenly I'm not allowed to use (lambda ...);
> >
> > Only if such use requires consing a closure. `Downward funargs'
> > and lambda's with no free variables do not require run-time allocation
> > of storage.
>
> You're telling me things that I know perfectly well. If you read what
> I wrote *carefully* you see that I said that *some* lambda's require
> allocation.
You wrote `Suddenly I'm not allowed to use (lambda ...);'
I was rebutting that argument by saying that there are many cases
where you could indeed use lambda.
> > Unless your hardware supports arbitrary stack depth, yes.
> > Perhaps you will wish to provide a nicer way of dealing with
> > stack overflow. If so, the code that implements this will have
> > to be *very careful* not to overflow itself, but the code above
> > this level of abstraction can ignore it.
>
> Right. Of course. This is boilerplate OS design.
>
> But why should the GC have to have the restrictions incumbent on the
> lowest levels of the OS?
It doesn't. However, since the system will (eventually) come to halt
if the GC does not run, and since the GC *must* synchronize with *every*
other process, it *does* have a distinguished place in the system.
Not at the lowest level, but it will have a need to reach down to
that lowest level.
> > What *is* the point, then?
>
> How many times do I have to say it?
>
> I'm asking about experience writing GC's that have essentially full
> access to the language facilities (say, arbitrary lambda, cons, and
> call/cc). I keep saying that's the point, and you keep trying to
> prove to me that it's not necessary to have such access.
The `full language' allows you to create arbitrary lambdas, conses,
and continuations in any amount. However, as should be obvious, the
GC *must* cons strictly less than it collects. Therefore, *you have already
lost* in that you cannot exploit the full power of the language.
In addition, the code that transports/marks or whatever the smallest
unit of storage *must not* allocate as much as it traverses. Since
storage is quantized, and we're postulating about the smallest
unit, there is therefore some part of the core algorithm that *cannot*
be allowed to allocate storage.
Thus whether you have access to arbitrary lambda, cons, or call/cc
is moot: there are sections of code in which you may not use them.
> I'm saying "tell me about P" and you keep saying "not Q! not Q". I
> *know* it can be done by subsetting the language. That's *PATENTLY
> OBVIOUS*. I'm asking about the *harder* problem, what are the
> efficient/sensible ways of doing so without subsetting the language in
> such a radical degree.
I've been trying to tell you. You have essentially 3 options:
1. Write the GC in an implementation language that does not cons.
(like C or assembler)
2. Write the GC in a lisp-like restricted language that does not
cons. (like pre-scheme)
3. Write the GC in `full lisp', but be careful not to cons (either
implicitly or explicitly).
In my experience, option 3 works just fine. If you can arrange for
your compiler to warn if you have written code that implicitly conses,
so much the better.
But you needn't take my word for it. Try it yourself.
> > Do you want to write the GC for a
> > scheme implementation using only R5RS Scheme?
>
> No, I've said this for a bajillion times, of course you can't do it
> using only the standard language facilities, at the least you have to
> *add* memory peek/poke in some way. That's *PATENTLY OBVIOUS*.
>
> But saying "you have to add new primitives to do it" (which is
> obvious) is not the same thing as saying "you have to exclude certain
> other primitives to do it" (which is not obvious, and is the point I'm
> talking about).
I'm saying that you don't *have* to exclude any primitive a priori,
but that there are certain things you ought to watch out for.
> > Do you want to write a GC in Lisp using techniques that people have
> > been using for the past 30 years? Well, they use a restricted
> > subset of the language.
>
> Right. But was that necessary?
Yes. The GC must not cons more than it collects, therefore you must
restrict use of consing code. Eliminating it altogether is not hard,
and most have chosen to do just that. However, most GC's should be
able to tolerate a `small' amount of consing.
> Or just the easiest thing?
Since other low-level parts of the system *require* you to work in
a restricted subset, it is pretty easy to just code the GC in that
subset as well.
> Do they
> have any experience doing it without a restriction on the language?
Part of the GC I wrote for the K machine used a lexical closure
near the end of the flip. This closure would be consed in `to-space'
(along with any other consing the mutator was doing).
As I mentioned above, the inner loops cannot be allowed to cons.
> I keep saying this, I feel like I'm repeating myself endlessly, and
> you keep misunderstanding. I don't know whether that's my fault or
> not, but I don't know how much clearer I can be.
>
> > > > I guess I don't understand what you mean by subsetting.
> > > > If you have lexical closures, cons, and call/cc, you have
> > > > essentially everything.
> > >
> > > Yep! And I need that; it's part of writing good Scheme code.
> >
> > Catch-22. If lexical closures, cons, and call/cc are available,
> > you need not implement them. If they are not available, you *cannot*
> > use them to implement themselves.
>
> You are not talking to some undergraduate CS student who barely
> understands how the world works.
>
> gc != {lexical closures, cons, call/cc}. It's *PATENTLY OBVIOUS* that
> you can't implement cons in cons. But that doesn't mean at all that
> you can't implement GC using cons. GC is something that need not live
> anywhere near the bottom layers of the system; my question is
> precisely about the (possibly harder) case where it is *not*, but
> instead has full access to language facilities.
And your question is what? Can it be done? The answer is yes.
Can it do arbitrary consing? The answer is no. Can it do `some'
consing? Yes.
> > See the microcode for the Lisp Machine.
>
> Where is it available?
First, get yourself a Lisp machine....
>
> > Well, then you should know that CONSing during GC is not an issue.
>
> So lots of systems have a GC that does memory allocation or not?
Any system with a copying or replicating GC certainly conses while
collecting. Any system that allows concurrent GC will allow consing
by the GC itself. I don't know what constitutes `lots', but it
shouldn't be hard to find numerous examples where the GC *can*
allocate memory, should it desire to.
Joe Marshall
"Joe Marshall" <prunes...@attbi.com> wrote in message
news:SzVi8.11416$44.27...@typhoon.ne.ipsvc.net...
A small error here:
> Mutation != allocation. Most stop-the-world GC algorithms assume that
> you will not be moving an object from `space to be scavenged' to
> `space that has been scavenged' without scavenging the object
> thus moved (indeed, that is what the write barrier prevents in
> those GCs that run concurrently).
It is the *read* barrier that prevents this, not the *write* barrier.
Sorry for any confusion.
Christopher C. Stacy
Thomas> The point here isn't to be pedantic. I'm interested in a rather
Thomas> specific problem, not posing some idle question, nor looking for
Thomas> foolish attempts to start arguments. I think the question I'm
Thomas> investigating is fairly clear, but if it isn't, I'm happy to keep
Thomas> clarifying. So far, for all the people posting rather pointless
Thomas> comments, and at least two secondary flame wars, I've gotten only a
Thomas> very single one (1) useful pointer, and my request for follow up
Thomas> information has so far not merited any response.
As one of the responders whom you seem be dismissing,
let me say that I don't understand what problem you
are trying to solve, and I'm not alone.
Are you actually implementing a Lisp system, or is this just
some academic exercise. Your line of questioning tends to
elicit a "What are you _really_ trying to do?" response,
which should suggest that you're not being clear, or not
understanding any of the answers that are being given to you.
First, have you read the copious literature on automatic storage
management? If you have not read up on GCs, just go to Google
and hunt around. Also, Xanalys has a web site all about it.
(Franz might have something, too.) Also there are lots of books.
Assuming you are up on the basics, do you have a specific
question about how to accomplish some particular algorithm?
You need to think it through in the same way that you would any
program - in this case, identify the data that you will be
operating on and what operations you need to do to it.
That will lead you to following the conclusion, which has
already been explained here several times in various ways.
Lisp, by definition, does not allow you to know (much less
manipulate) its own implementation. You're not allowed to
know how the GC works, except possibly in an abstract sense,
because the GC by definition does things that are not possible
to do in Lisp. In Lisp you are not allowed to _know_ how cons
cells or any other data types are implemented in memory.
You can not reference memory directly, and so can't look see to
see if it contains some kind of kind of forwarding pointer, nor
can you make any pointer of any kind. There are no Lisp functions
that will allow you to know where a Lisp object is located in
memory, nor anything that will let you move memory around.
In fact, you are not allowed to know about or allocate or free or
acccess or manipulate _memory_ at all, in any way.
You certainly can't perform memory management.
All that you have available to program with are the Lisp object
abstractions, which are well-defined in terms of the Lisp language
functions (sometimes by, "...is not defined", and which do not
knowlingly correspond to anything in the underlying implementation.
This is fundamentally different from, say, C, in which you are given
access to the memory model of the machine (eg. you know that there
are storage locations, can make pointers to those locations, etc.)
Your question seems the same as asking, "How in C can I use only
the C language dynamically allocate memory and manipulate hardware
page maps without using any pointers or calling any library or
system routines, and how do I guarantee that other code written by
someone else will not interfere with my doing so?"
Most Lisp systems are written mostly in Lisp. But the question
you seem to be asking is: "How can I implement the part of the
Lisp system that I am not allowed to know how to implement?"
The answer is obviously: YOU CAN'T -- not without functions and
knowledge that access the underlying implementation, thereby
violating the fundamentals of Lisp data abstraction.
Some Lisp systems provide those kinds of functions, which are
sometimes called "subprimitives" and are not "legal" for use by
ordinary Lisp programs. In such cases, the garbage collector
can be carefully implemented in that superset of Lisp.
The implementation of any automatic storage system has to be
carefully done. The answer to, "How can I implement the GC in a
totally free way, where I can call any function and do anything
I feel like", is, as has been stated several times, "YOU CAN'T
AND BY THE WAY THAT'S TRUE REGARDLESS OF WE"RE TALKING ABOUT LISP."
Questions like if or how you are allowed to CONS during garbage
collection depends entirely on the memory model of the system,
how the primitive functions in the language have been _implemented_
to interact with GC, and exactly how the GC algorithm works.
You can only call the functions that make sense to safely call
in the context of the particular GC algorithm as already designed
into those functions. You have already been given several answers
explaining how in such systems consing may be permitted.
(In particular, by segregating memory into seperate areas.)
Whether GC conses doesn't have anything to do with the language
that anything is implemented in.
If the above doesn't answer your question, you're going to need to
start over and ask a different question, rather than just repeating
your question, telling us that you think you're being clear but for
some reason we don't get it, and labelling all the helpful advice
you have been getting as "pointless" or "flaming". My suggestion
is to start out such a question by explaining in more detail exactly
what you are trying to do, and perhaps say why anyone should care,
rather than by asking a patently self-contradictory question.
Thomas Bushnell, BSG
> In other words, at all.
Hehe; it's a matter of goals. Sure, some restrictions might be
inevitable. But the goal is to minimize the restrictions as much as
possible. There are various reasons, but here's one:
For compiling "ordinary code", the code the compiler generates should
have full access to everything the runtime can provide. There's no
reason for marking anything off-bounds a priori; if the compiler
writer says "hey, if I do this weird thing xyz, I can get that kind of
function to run 5% faster"--and I want them to be able to say that.
However, if gc must be compiled in a special mode, obeying special
restrictions, then that part of the compiler--the part responsible for
the gc-code-limitations--will be *much* less tested than the rest of
the compiler, since it is only use to compile that one thing.
In the case of things like interrupt handlers, I'm pretty confident
there is *no* way to avoid this problem; interrupt handlers and the
compiler simply *must* understand each other, and that's the way it
goes. But it's much less clear to me that the compiler must specially
understand the kind of code the gc uses. (This is of course an
entirely different question from the compiler's need to understand the
*memory*model* the gc uses.)
> Notwithstanding any prejudice you may have against the letter E,
> you seem to believe that there is an issue with allowing the GC to
> CONS. If you write a GC that does not CONS, you don't have to
> deal with this issue. That should be reason enough.
If there's no way to avoid it, then I'll bite the bullet. But saying
"hey, the bullet is yummy" just isn't true. I don't *want* to write
in a cons-free subset unless I *must* write in a cons-free subset.
> It doesn't. However, since the system will (eventually) come to halt
> if the GC does not run, and since the GC *must* synchronize with *every*
> other process, it *does* have a distinguished place in the system.
> Not at the lowest level, but it will have a need to reach down to
> that lowest level.
It may need to stop-the-world, indeed, but that's a fairly easy thing
to do--stopping the world is already the sort of thing any system has
to support (in order to shutdown cleanly, at the very least). :)
> The `full language' allows you to create arbitrary lambdas, conses,
> and continuations in any amount. However, as should be obvious, the
> GC *must* cons strictly less than it collects.
Yes, this is true. But that's not a horrible thing to worry about.
Like I said, I don't mind a strategy of minimizing cons calls; that
doesn't bug me. I'm just bothered by a need to have *no* conses.
> Thus whether you have access to arbitrary lambda, cons, or call/cc
> is moot: there are sections of code in which you may not use them.
Of course; that's quite well taken. But the set of things done while
the world is stopped (assuming for the moment a stop-the-world
approach) is more than just the bottom level operation of the gc.
> I've been trying to tell you. You have essentially 3 options:
> 1. Write the GC in an implementation language that does not cons.
> (like C or assembler)
> 2. Write the GC in a lisp-like restricted language that does not
> cons. (like pre-scheme)
> 3. Write the GC in `full lisp', but be careful not to cons (either
> implicitly or explicitly).
Or option 4:
Write the GC in the full language, but have some idea *how much* you
are consing, keeping it below the theoretical limitation. So how does
one keep track well?
> But you needn't take my word for it. Try it yourself.
I'm really *not* looking for a big discussion on either newsgroup
here. I know, that seems bizarre, but my real desire is for pointers
to research and implementations that I can read about and study.
> And your question is what? Can it be done? The answer is yes.
> Can it do arbitrary consing? The answer is no. Can it do `some'
> consing? Yes.
Right. But that wasn't the question. I pretty much *knew* the answer
to those questions. My question is:
Can you point me to research and implementations that I can study?
> First, get yourself a Lisp machine....
*Sigh*. If only I could. :(
> Any system with a copying or replicating GC certainly conses while
> collecting. Any system that allows concurrent GC will allow consing
> by the GC itself. I don't know what constitutes `lots', but it
> shouldn't be hard to find numerous examples where the GC *can*
> allocate memory, should it desire to.
So, um which of the three options above is this?
Thomas
Thomas Bushnell, BSG
> Are you actually implementing a Lisp system, or is this just
> some academic exercise. Your line of questioning tends to
> elicit a "What are you _really_ trying to do?" response,
> which should suggest that you're not being clear, or not
> understanding any of the answers that are being given to you.
It's to understand the problem space, with implementation in mind.
> First, have you read the copious literature on automatic storage
> management? If you have not read up on GCs, just go to Google
> and hunt around. Also, Xanalys has a web site all about it.
> (Franz might have something, too.) Also there are lots of books.
Unfortunately, the particular problem I'm asking about is *not*
generally addressed. I have read the basics, and the advanced
literature also. I'm really not a newbie.
So your little lesson on "why Lisp is different from C", is rather
pointless (a little tedious, actually).
> The answer is obviously: YOU CAN'T -- not without functions and
> knowledge that access the underlying implementation, thereby
> violating the fundamentals of Lisp data abstraction.
Um, that you write this indicates that you have totally ignored what I
said. I already *KNOW* this perfectly well. Quoting myself, I said:
"Of course I was taking for granted the existence of suitable
peek/poke primitives" and "Having special peek/poke primitives is
certainly necessary...but not sufficient."
> The implementation of any automatic storage system has to be
> carefully done.
Duh.
> Questions like if or how you are allowed to CONS during garbage
> collection depends entirely on the memory model of the system,
> how the primitive functions in the language have been _implemented_
> to interact with GC, and exactly how the GC algorithm works.
Right, hence, these are questions that can't be answered in the
abstract. Which is why I asked for people who might know pointers to
research or specific implementations, and the way these problems might
have been addressed in them.
A sample answer to the question is something like:
"Alyssa P. Hacker addressed this in her paper `Managing concurrently
allocating garbage collection', though she only addressed Baker-style
incremental collection."
Or
"The FooCorp LispBox had a clever gc technique; we had most of the
language available, but we had to prohibit certain kinds of closures.
You can read about it in the internals manual on page NNN; we wrote
down some of our thoughts about to fix the problem with those kinds of
closures too."
Or
"This is an open area for research, but has not been widely
investigated because of the paucity of live bare-metal implementations
since the demise of the major lisp machine vendors."
Thomas
Christopher C. Stacy
Thomas> Right, hence, these are questions that can't be answered in the
Thomas> abstract. Which is why I asked for people who might know pointers to
Thomas> research or specific implementations, and the way these problems might
Thomas> have been addressed in them.
I typed in "garbage collector" to Google and all the standard references
came up, for example all the Baker papers, and you can find out all the
books that way, also. One bibliography that came up was cross-indexed
by programming language. I also suggested Xanalys, which has an
entire web site devoted to the subject.
William D Clinger
in any other language for that matter, including C and assembly
language), without any restrictions concerning the use of features
or library routines that might allocate storage during garbage
collection, is an open area for research, but one that has not
been widely investigated because it is generally regarded as a
poor way to construct a garbage collector.
The reason for this is elementary: The collector's performance
matters most when the mutator's data fill most of the available
storage, leaving little storage available to the collector.
Will
Thomas Bushnell, BSG
None of them talk about the self-hosting problem. Not a one.
Thomas F. Burdick
> Christopher Browne <cbbr...@acm.org> writes:
>
> > A slick thing might be for this region to be allocated newly at
> > the start of GC and then return it at the end, throwing its
> > contents away completely. That approach has the interesting
> > property that if you can be sure that GC won't do more than
> > (say) 1MB of CONSing, you could reserve a permanent fixed buffer
> > of 1MB for the purpose, and be certain you'll never run out of
> > memory to the point of being unable to garbage collect.
>
> So one problem with this is computing the amount of memory needed.
Yes. I've said it before, but I'll say it again: this is *not* a
language issue. Garbage collectors are a funny problem domain. This
is something you must take into account when writing GCs in *any*
language. The more you rely on automatic memory management *inside* a
GC, the more you need to very carefully arrange things so that they
will work.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Thomas Bushnell, BSG
> Yes. I've said it before, but I'll say it again: this is *not* a
> language issue. Garbage collectors are a funny problem domain. This
> is something you must take into account when writing GCs in *any*
> language. The more you rely on automatic memory management *inside* a
> GC, the more you need to very carefully arrange things so that they
> will work.
Agreed, it's not a language issue--or rather, it's an issue for any
language which makes heavy use of dynamically allocated memory and
relies on GC to clean its dynamic memory.
Rahul Jain
> cst...@theworld.com (Christopher C. Stacy) writes:
> > I typed in "garbage collector" to Google and all the standard references
> > came up
> None of them talk about the self-hosting problem. Not a one.
Maybe that's because there wasn't anything significant to talk about?
--
-> -/ - Rahul Jain - \- <-
-> -\ http://linux.rice.edu/~rahul -=- mailto:rj...@techie.com /- <-
-> -/ "Structure is nothing if it is all you got. Skeletons spook \- <-
-> -\ people if [they] try to walk around on their own. I really /- <-
-> -/ wonder why XML does not." -- Erik Naggum, comp.lang.lisp \- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
(c)1996-2002, All rights reserved. Disclaimer available upon request.
Thomas Bushnell, BSG
> tb+u...@becket.net (Thomas Bushnell, BSG) writes:
>
> > cst...@theworld.com (Christopher C. Stacy) writes:
> > > I typed in "garbage collector" to Google and all the standard references
> > > came up
>
> > None of them talk about the self-hosting problem. Not a one.
>
> Maybe that's because there wasn't anything significant to talk about?
Perhaps so, but Chistopher Stacy's suggestion that a trivial web
search would find what I'm looking for indicates that either his goal
is to belittle me, or alternatively (and more likely) that he didn't
understand what I'm looking for.
Thomas
Jeffrey Siegal
> > I typed in "garbage collector" to Google and all the standard references
> > came up, for example all the Baker papers, and you can find out all the
> > books that way, also. One bibliography that came up was cross-indexed
> > by programming language. I also suggested Xanalys, which has an
> > entire web site devoted to the subject.
>
> None of them talk about the self-hosting problem. Not a one.
And you know this because you carefully reviewed all 121,000 web
references (not including groups references)?
> Perhaps so, but Chistopher Stacy's suggestion that a trivial web
> search would find what I'm looking for indicates that either his goal
> is to belittle me
Please grow up.
Thomas Bushnell, BSG
> "Thomas Bushnell, BSG" wrote:
> > > I typed in "garbage collector" to Google and all the standard references
> > > came up, for example all the Baker papers, and you can find out all the
> > > books that way, also. One bibliography that came up was cross-indexed
> > > by programming language. I also suggested Xanalys, which has an
> > > entire web site devoted to the subject.
> >
> > None of them talk about the self-hosting problem. Not a one.
>
> And you know this because you carefully reviewed all 121,000 web
> references (not including groups references)?
Um, I checked the first several. Baker doesn't talk about it, and the
standard references (which, of course, I'm already familiar with)
don't talk about it either.
> > Perhaps so, but Chistopher Stacy's suggestion that a trivial web
> > search would find what I'm looking for indicates that either his goal
> > is to belittle me
>
> Please grow up.
Well, what *is* his goal? His message demonstrates a passionate
conviction that I must be a blithering fool. I guess that's the
standard procedure for some people on Usenet; it is disgusting,
however.
Rahul Jain
> Jeffrey Siegal <j...@quiotix.com> writes:
>
> > "Thomas Bushnell, BSG" wrote:
> > > Perhaps so, but Chistopher Stacy's suggestion that a trivial web
> > > search would find what I'm looking for indicates that either his
> > > goal is to belittle me
> > Please grow up.
I think that was a little harsh, but is essentially what I was going
to say.
> Well, what *is* his goal? His message demonstrates a passionate
> conviction that I must be a blithering fool.
If it's any help, I'm coming close to a similar conclusion as he seems
me to be (which is not that you're a blithering fool).
> I guess that's the standard procedure for some people on Usenet; it
> is disgusting, however.
It's standard procedure for one to apply some thought to a problem
before complaining about problems that don't exist. That way, you
won't complain about them.
Where exactly do you see the need for lots of consing in the inner
loop of the GC? If you're talking about something unconventional,
PLEASE MAKE THAT CLEAR so that people won't make the assumption that
you're just complaining that a solved problem's solution doesn't
exist.
Jeffrey Siegal
> Well, what *is* his goal? His message demonstrates a passionate
> conviction that I must be a blithering fool. I guess that's the
> standard procedure for some people on Usenet; it is disgusting,
> however.
Here's a hint: Anyone can post to Usenet, but no one can force anyone
else to read his or her posts.
If you want people to read your messages, stick with discussing relevant
issues. If you want to engage in petty name calling, you're going to
lose the audience you probably want (though you might pick up an
audience of people who want to engage in flame wars with you).
Thomas Bushnell, BSG
> It's standard procedure for one to apply some thought to a problem
> before complaining about problems that don't exist. That way, you
> won't complain about them.
Gee, I did.
> Where exactly do you see the need for lots of consing in the inner
> loop of the GC? If you're talking about something unconventional,
> PLEASE MAKE THAT CLEAR so that people won't make the assumption that
> you're just complaining that a solved problem's solution doesn't
> exist.
Oh, I don't think the inner loop needs any consing at all for any
normal algorithms.
Thomas Bushnell, BSG
> If you want people to read your messages, stick with discussing relevant
> issues. If you want to engage in petty name calling, you're going to
> lose the audience you probably want (though you might pick up an
> audience of people who want to engage in flame wars with you).
I agree. But I didn't engage in name calling, I said that I thought
his goal was to belittle me. I got that guess from his long
discussion of "why Lisp is different from C".
Regardless, I was carried away given the venom of attacks from some on
comp.lang.lisp, and my reply was more out of anger than any kind of
reasoned response.
David Rush
> itself be allocating memory. But GC is usually described as a
> *separate* process from the mutator (whether the incremental or
> concurrent or not). In the self-hosting case, however, the GC itself
> *is* a mutator.
But a mutator of what?
> Some implementation strategies involve:
>
> setting aside a special heap for the collector to use.
As I have conducted my gedanken experiments on how to build
GC-friendly OSes this has generally been the way that I have
followed. In particular, if your entire OS memory-management is
GC-driven, per-process memory protection boundaries become rather less
relevant...in fact GC becomes a system service so it is entirely
reasonable for it to run "in the kernel". So you quickly get to an
architecture where the collector has it's own storage areas in which
to work.
This begs the question of how the collector's memory gets managed, but
that doesn't trouble me unduly. Collectors have fairly unique memory
menagement patterns, coming up with an adequate ad-hoc solution
doesn't strike me as a huge problem.
> use stop-and-copy; the collector always allocates in the clean semi-heap.
IIRC (it's been a few years), you don't have to "stop" in order to
"copy". ISTR at least one incremental copying collector in the Garbage
Collection book (which is at a different desk). Most copying
collectors only use memory from the regions under management, so the
problem pretty much disappears in this case, too.
Caveat lector: it's late and my memory of these things hasn't been
refreshed too recently...
david rush
--
Gnus is a fashion statement. Emacs is clothing. Everyone else is
running around naked.
-- Jonadab the Unsightly One (on gnu.emacs.gnus)
Erik Naggum
| Regardless, I was carried away given the venom of attacks from some on
| comp.lang.lisp, and my reply was more out of anger than any kind of
| reasoned response.
Well, do not post when under the influence of emotions -- it only gets
you into trouble. Remember that just because you do, does not mean that
anybody else does. Also, do not interpret harshness as hostility, that
only causes hostility because you start attacking someone who is not
attacking you. The ability to be harsh without hostility is not foreign
to the American culture, so there is no cultural excuse here, either.
Emotions that overflow into your treatment of unrelated people are out of
control. Admitting to such lack of control is not particularly smart.
///
--
In a fight against something, the fight has value, victory has none.
In a fight for something, the fight is a loss, victory merely relief.
David Rush
>
> > This is not necessarily the case. It is fairly easy to write Lisp and
> > Scheme
> > code that either does not allocate temporary storage, only allocates
> > temporary storage in a provably stack-like manner, or allocates a bounded
> > amount of temporary storage from a statically allocated `pool'.
>
> You've ignored what was clearly said above about subsetting. I'm
> interested in doing it *WITHOUT* such restrictions in the language.
No he didn't. It's not about subsetting. It's about what operations
can be performed with the system in an inconsistent state. Even in C
there are restrictions on the safe operations during periods of system
instability. Collectors written in C don't allocate from the managed
heap (at least not via the interface available outside the
collector). The only way to avoid such restrictions is to have some
other stable environment running which can operate on the unstable
one. From what you have said so far, I don't get the implressions that
you would consider that to be a self-hosting solution.
david rush
--
There is only one computer program, and we're all just writing
pieces of it.
-- Thant Tessman (on comp.lang.scheme)
Pierre R. Mai
Furthermore it seems to me that any solution that allows the GC to use
the full language is going to be more complicated and error-prone than
implementing the GC in a restricted subset, so that for the uncertain
convenience of being able to use the full language in the GC, you have
to include lots of code complicated code in your implementation,
solely for that convenience.
That doesn't seem like a sensible trade-off at all, unless ideological
considerations are more important than cost-of-implementation and
cost-of-maintenance.
Regs, Pierre.
--
Pierre R. Mai <pm...@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
Ray Dillinger
>
> "Joe Marshall" <prunes...@attbi.com> writes:
>
> Moreover, keeping all cons out of the GC is a pain, it requires citing
> the GC way low in the call-graph, for no particular reason--that is,
> if there are good strategies for allowing GC to have full use of the
> language facilities.
> Yes, it's possible to write a GC that avoids cons. Yes, it's possible
> to write a GC that avoids cons. Yes, I know. Please stop trying to
> prove it to me. I know it's true.
Right. It's possible to design an efficient GC. We're
all puzzled because you seem to want an inefficient one
and nobody can figure out why. What can you do with a
consing GC that you cannot do with a non-consing GC?
Why is this "problem" worth solving?
> My question is: what are the strategies in use (now, or historically,
> or in research) for writing a GC that does *not* have such a
> restriction?
No one has ever found a use for such strategies, as far
as I know. I do not think that they exist.
> But why should the GC have to have the restrictions incumbent on the
> lowest levels of the OS?
Well, GC is in fact a function of the lowest levels of
a lispy OS. On OSes without GC, it's usually part of the
runtime environment that simulates a lispy OS for the
program's sake. Or depending on your compiler it may be
statically linked into the program itself, but that's not
because it's part of the program the user defined - GC is
never even called by the user's code.
As an OS function, the programmer never has to write it
or customize it, at all - nor even explicitly call it.
So there's really not much point in making it a "friendly
environment to program in" - it's part of what the language
implementor does to make the *rest* of the world a friendly
environment to program in.
It looks a lot like it has the restrictions incumbent on
the lowest levels of the OS because it's one of the
functions of the lowest levels of the OS. Nobody has
ever come up with a convincing reason why it ought not
be, so that's pretty much how lisp programmers think of
it.
> > What *is* the point, then?
>
> How many times do I have to say it?
>
> I'm asking about experience writing GC's that have essentially full
> access to the language facilities (say, arbitrary lambda, cons, and
> call/cc). I keep saying that's the point, and you keep trying to
> prove to me that it's not necessary to have such access.
There is no such experience because no one has ever
found it to be worthwhile to pursue. People keep asking
you why you'd want such facilities to be available in the
GC, and you keep saying "that's not the point! I just
want them!". Without some idea what problem you're trying
to solve, or at least a representative problem that such
facilities could be used to solve, you can't expect much
interest in making or having those facilities available.
Bear
Sander Vesik
> "Joe Marshall" <prunes...@attbi.com> writes:
>
>> cons'. Simply do not make it available in the environment. You
>> cannot call it because it is undefined. You cannot accidentally
>> call something that calls it because those functions are not
>> defined until CONS is.
>
> Huh? Not in Scheme, at least. Scheme implementations differ on how
> to do environment manipulation (except for simple extension).
> Suppose, however that we have a special form:
>
> (munge-environment (drops) forms ...)
>
> which executes the forms with the symbols named in 'drops' omitted
> from the environment. Then the following certainly has cons
> unavailable, but still calls cons:
>
> (munge-environment (cons)
> (map some-procedure some-list))
>
> The reason, of course, is that map gets cons from the lexical context
> in scope when it was defined.
Then you need to define the other library functions in a similarily
constrained environment. But the best way is probably to define it
in an environment where cons has been redefined to use storage from
a separate, static area and have it be explicitly freed by the
GC code.
>
>> I think it is obvious that you cannot expect to implement a particular
>> feature starting from the assumption that the feature is already
>> available. If CONS, CALL/CC, etc. are not primitive forms that your
>> compiler can handle, you need to implement them in the primitives that
>> you *do* have. And whatever implementation you come up with cannot
>> assume the full language.
>
> Cons need not call gc. Cons, obviously, cannot be implemented in
> terms of cons. But gc can be (and really, should be) thought about
> more-or-less uncoupled with the mutator. It's not something that cons
> calls (in reasonably mature systems).
You can implement cons in terms of make-vector. Now, having implemented
cons so, ou then have to implement the make-vector that still cannot be
done without going "outside" the language.
>
> Most sane compilers know cons quite directly, of course. But they
> don't call gc, something else does, "off line" from the main executing
> thread, even if the thread stops while gc runs.
So in that case, cons doesn't call gc but something else calls gc
(and suspends cons) if cons runs out of memory. Wouldn't it be far
easier to have cons call gc if needed?
>
> Thomas
--
Sander
+++ Out of cheese error +++
Sander Vesik
> "Joe Marshall" <prunes...@attbi.com> writes:
>
>> > good Scheme or Lisp code, which is one reason that the usual malloc
>> > implementation in C can easily avoid allocating memory.
>>
>> When you call malloc in C, you will dynamically allocate memory.
>
> But the usual malloc *implementation* does not. Or rather, it calls
> sbrk (or some such), which allocates raw heap pages. The point is
> that malloc is not recursive, and neither is cons, of course.
>
> However, gc != cons. It's perfectly reasonable for me to want gc to
> call cons; that's nothing at all like saying that cons can't call
> cons.
Only if you write your own local copy of cons.
Sander Vesik
> "Joe Marshall" <prunes...@attbi.com> writes:
>
>> each `layer' depending only on those layers below it. Now Scheme
>> doesn't define a package or module system that enforces this,
>> so you'll have to `roll your own'. At the very lowest level,
>> you *only* have those primitive procedures that the compiler
>> can generate inline code for. At another level, you'll add
>> CONS and MAP.
>
> Well sure, duh, that's basic OS design, nothing weird there.
>
> However, none of that requires GC to be anywhere near the "lowest"
> level. And indeed, there are plenty of reasons not to want it to be
> in a low level, since, after all, one usually wants to keep as little
> as possible in the lowest levels.
One also wants everything to be on the "correct" level. Which in case of
GC is low and is even lower for the actual allocator.
>
>> I agree that CONS shouldn't bottom out to the GC, but I've seen more
>> `mature' systems that do it that way than not.
>
> Well, maybe I'm building more into "mature" than I should. ;)
>
> I think (without much evidence, however) that the best compiler
> strategies do allocation from "private" (per-thread) arenas, and when
> they run out, they just get another arena. At worst, they block if
> there are no arenas available.
This can lead to unwanted amounts of fragmentation very easily if
data is accessed from more than one thread.
>
> Timing GC is managed entirely separately (though coordinated in the
> obvious ways).
>
> That seems a much happier method.
>
> For a quick-and-cheap lisp one usually just has cons bottom out to
> calling some mark-and-sweep.
>
>> > Most sane compilers know cons quite directly, of course. But they
>> > don't call gc, something else does, "off line" from the main executing
>> > thread, even if the thread stops while gc runs.
>
>> They do, do they? News to me.
>
> Well, yeah, I think so. It's common to inline cons, I think, and
> allocate from private arenas. At least, my Scheme-compiler-whiz
> friends tell me that. (If you are in a bytecoded or compile-to-C sort
> of system, then certainly something else might be considered normal or
> sane.)
Using bytecodes or compiling to C mostly covers scheme implemenations,
leaving aside larcenery (sp? sorry, never used it).
Thomas Bushnell, BSG
> tb+u...@becket.net (Thomas Bushnell, BSG) writes:
> > The basic problem is that the GC, if written in Lisp/Scheme, will
> > itself be allocating memory. But GC is usually described as a
> > *separate* process from the mutator (whether the incremental or
> > concurrent or not). In the self-hosting case, however, the GC itself
> > *is* a mutator.
>
> But a mutator of what?
At the very least, of the data structures and variables it maintains
to keep track of where it is in the GC.
> > use stop-and-copy; the collector always allocates in the clean semi-heap.
>
> IIRC (it's been a few years), you don't have to "stop" in order to
> "copy". ISTR at least one incremental copying collector in the Garbage
> Collection book (which is at a different desk). Most copying
> collectors only use memory from the regions under management, so the
> problem pretty much disappears in this case, too.
Yes, I know, I was using stop-and-copy as one example. I'm well aware
of all the various gc algorithms out there (except maybe for really
weird things). My expertise is at about the level of, say, the Jones
and Lin book.
Thomas Bushnell, BSG
> > Most sane compilers know cons quite directly, of course. But they
> > don't call gc, something else does, "off line" from the main executing
> > thread, even if the thread stops while gc runs.
>
> So in that case, cons doesn't call gc but something else calls gc
> (and suspends cons) if cons runs out of memory. Wouldn't it be far
> easier to have cons call gc if needed?
The reasons involve things like:
You want cons to be able to run really fast, and not need to do a
check and branch like this every time.
You don't want gc to run on the same execution stack as the user's
process.
So the sort of strategy I'm thinking of for cons is something like:
Each thread has an allocation arena, given by the system, and the
compiler is allowed to take bits of it as it pleases (in order) from
front to back to allocate objects.
The page after the allocation arena is marked out-of-bounds by the
VM hardware, so that once the compiler crosses that line, the system
gets control and can give the thread a new allocation area and
resume.
This requires knowing how the compiler tracks the current allocation
pointer in the arena (say, by dedicating a specific register to it,
dunno) but otherwise nicely decouples the two.
In this way, cons (and friends) can run really fast, because the "am I
out of memory" check is done automatically by the hardware.
GC is a separate task entirely, whose job is to make sure that there
are always enough pages hanging around so that faulting threads can
get one.
Thomas
Thomas Bushnell, BSG
> Right. It's possible to design an efficient GC. We're
> all puzzled because you seem to want an inefficient one
> and nobody can figure out why. What can you do with a
> consing GC that you cannot do with a non-consing GC?
> Why is this "problem" worth solving?
The inner loop isn't going to be able to do cons. But there is more
to the gc thread (assuming it has a "thread") than running the inner
loop.
> > My question is: what are the strategies in use (now, or historically,
> > or in research) for writing a GC that does *not* have such a
> > restriction?
>
> No one has ever found a use for such strategies, as far
> as I know. I do not think that they exist.
So the weird thing is that some people have said "it's trivial" and
some have said "it's impossible", and somewhere in between the truth
must lie.
Thomas Bushnell, BSG
> The only way to avoid such restrictions is to have some
> other stable environment running which can operate on the unstable
> one. From what you have said so far, I don't get the implressions that
> you would consider that to be a self-hosting solution.
Of course that's self-hosting. The queries with solutions like "the
gc runs on a secondary heap" involve things like sizing the secondary
heap, how it gets cleaned, if it leaves live objects on the secondary
heap, how and when do they get transferred to the main heap when gc is
through, etc.
Thomas
Thomas Bushnell, BSG
> This can lead to unwanted amounts of fragmentation very easily if
> data is accessed from more than one thread.
Most data is not accessed from more than one-thread, of course.
But you are right that this is a worry. So my idea for that problem
(which is really quite vague at this point) is to use a generational
copy scheme, which moves data into global heaps and gets (hopefully
better) locality for such data.
One issue that vexes me is that incremental generational collectors
(at least, as presented in Jones and Lin) are a somewhat untravelled
water. So I'm not sure what the Right Thing is.
> Using bytecodes or compiling to C mostly covers scheme implemenations,
> leaving aside larcenery (sp? sorry, never used it).
I want to compile to machine code. (Actually, MIT Scheme compiles to
machine code.)
David Rush
> > The only way to avoid such restrictions is to have some
> > other stable environment running which can operate on the unstable
> > one. From what you have said so far, I don't get the implressions that
> > you would consider that to be a self-hosting solution.
>
> Of course that's self-hosting.
OK.
> The queries with solutions like "the
> gc runs on a secondary heap" involve things like sizing the secondary
> heap, how it gets cleaned, if it leaves live objects on the secondary
> heap, how and when do they get transferred to the main heap when gc is
> through, etc.
Most of which are of equivalent computational complexity to the
problem of collecting the garbage in the first place. It really makes
much more sense to use one of the algorithms which operate entirely
within the (primary) managed heap since you are not then duplicating
the work (once to work out the constraints and once to do the work).
IMNSHO, at least.
david rush
-----BEGIN GEEK CODE BLOCK-----
Version 3.12
GCS d? s-: a C++$ ULSAH+++$ P+(---) L++ E+++ W+(--) N++ K w(---) O++@
PS+++(--) PE(++) Y+ PGP !tv b+++ DI++ D+(--) e*(+++>+++) h---- r+++
z++++
-----END GEEK CODE BLOCK-----
David Rush
> > Right. It's possible to design an efficient GC. We're
> > all puzzled because you seem to want an inefficient one
> > and nobody can figure out why. What can you do with a
> > consing GC that you cannot do with a non-consing GC?
> > Why is this "problem" worth solving?
<chop mode='context-abusing'/>
> So the weird thing is that some people have said "it's trivial" and
> some have said "it's impossible", and somewhere in between the truth
> must lie.
I think that the difference between the 'trivial' and 'impossible'
answers lies in the problem definition. Personally, I can't see why
you want to make the problem any harder than the trivial solutions.
david rush
--
Finding a needle in a haystack is a lot easier if you burn down the
haystack and scan the ashes with a metal detector.
-- the Silicon Valley Tarot
Sander Vesik
>> management? If you have not read up on GCs, just go to Google
>> and hunt around. Also, Xanalys has a web site all about it.
>> (Franz might have something, too.) Also there are lots of books.
>
> Unfortunately, the particular problem I'm asking about is *not*
> generally addressed. I have read the basics, and the advanced
> literature also. I'm really not a newbie.
>
> So your little lesson on "why Lisp is different from C", is rather
> pointless (a little tedious, actually).
You have sufficently demonstrated that whatever seraches/reading you
did didn't touch on say fortran and fortran based systems and similar
and how people managed/coped with it there. The situation seeming
to be the opposite doesn't make it irrelevant.
>
>> The answer is obviously: YOU CAN'T -- not without functions and
>> knowledge that access the underlying implementation, thereby
>> violating the fundamentals of Lisp data abstraction.
>
> Um, that you write this indicates that you have totally ignored what I
> said. I already *KNOW* this perfectly well. Quoting myself, I said:
> "Of course I was taking for granted the existence of suitable
> peek/poke primitives" and "Having special peek/poke primitives is
> certainly necessary...but not sufficient."
Actually, no you don't - you already have the needed operations in
scheme. They are called vector-ref and vector-set!
> "This is an open area for research, but has not been widely
> investigated because of the paucity of live bare-metal implementations
> since the demise of the major lisp machine vendors."
Bare metal did not become less available (unless it has to have some
really specific attributes) with the lisp machines going away. People
just became more convinient and moved to hosted environments.
Ray Dillinger
"Thomas Bushnell, BSG" wrote:
>
> Ray Dillinger <be...@sonic.net> writes:
>
> > > My question is: what are the strategies in use (now, or historically,
> > > or in research) for writing a GC that does *not* have such a
> > > restriction?
> >
> > No one has ever found a use for such strategies, as far
> > as I know. I do not think that they exist.
>
> So the weird thing is that some people have said "it's trivial" and
> some have said "it's impossible", and somewhere in between the truth
> must lie.
I don't think it's impossible. I just don't think anyone's ever
found it worth doing -- and people have to have done it to create
the information you want help finding. It may be entirely possible
or even trivial to create a GC that itself creates floating garbage.
But since no one has ever wanted to do it, it may be impossible to
find the kind of information you want to find about it.
Classically (on early LISP systems) the Garbage Collector got
called when the system was literally out of memory. If it had
allocated memory AT ALL, then it couldn't have run. On later
systems, the easiest way to assure that the system wouldn't run
out of memory unnecessarily has continued to be having a GC that
does not allocate, so, since non-allocating collectors had already
been built, no one has had a reason to try and produce one that
does allocation.
Ray
---
"Memory is like an orgasm. It's a lot better if you don't have
to fake it." -- Seymour Cray (on virtual memory)
Sander Vesik
>
>> > Most sane compilers know cons quite directly, of course. But they
>> > don't call gc, something else does, "off line" from the main executing
>> > thread, even if the thread stops while gc runs.
>>
>> So in that case, cons doesn't call gc but something else calls gc
>> (and suspends cons) if cons runs out of memory. Wouldn't it be far
>> easier to have cons call gc if needed?
>
> The reasons involve things like:
>
> You want cons to be able to run really fast, and not need to do a
> check and branch like this every time.
This is a simple arithmetic check against a high-watermark, I doubt it
would have a significant cost. Especially if you can inline.
>
> You don't want gc to run on the same execution stack as the user's
> process.
Why? Oh, and 'does it uncesessarily burden debugging'?
>
> So the sort of strategy I'm thinking of for cons is something like:
>
> Each thread has an allocation arena, given by the system, and the
> compiler is allowed to take bits of it as it pleases (in order) from
> front to back to allocate objects.
So this would be the static allocation area, as the compiler cannot
predict runtime. Probably a very small area.
>
> The page after the allocation arena is marked out-of-bounds by the
> VM hardware, so that once the compiler crosses that line, the system
> gets control and can give the thread a new allocation area and
> resume.
By compiler you surely mean "the runtime system"?
>
> This requires knowing how the compiler tracks the current allocation
> pointer in the arena (say, by dedicating a specific register to it,
> dunno) but otherwise nicely decouples the two.
No, you don't need to know how the runtime/compiler stores the current
highest pointer - you just allocate that page (and possibly a couple
of more) on the request.
>
> In this way, cons (and friends) can run really fast, because the "am I
> out of memory" check is done automatically by the hardware.
>
> GC is a separate task entirely, whose job is to make sure that there
> are always enough pages hanging around so that faulting threads can
> get one.
>
This assumes that faulting on "need more memory" is cheaper than a simple
check. It may be for bytecodes, not necessarily for compiled (and memory
intensive) code.
IMVHO having cons be fast, low-level but stupid is not the interesting
thing to solve. Having fast primitives does not necessarily automaticly
give you a fast system - the interesting thing is to make the code, not
the primitives it uses, fast. An allocator and GC pair that was smart
about memory hierarchy but required more instructions to run would be a
win - even if it was not so good on micro-benchmarks.
Sander Vesik
>
>> This can lead to unwanted amounts of fragmentation very easily if
>> data is accessed from more than one thread.
>
> Most data is not accessed from more than one-thread, of course.
>
> But you are right that this is a worry. So my idea for that problem
> (which is really quite vague at this point) is to use a generational
> copy scheme, which moves data into global heaps and gets (hopefully
> better) locality for such data.
And destroys the locality in another sense of the word due to copying?
Joe Marshall
"David Rush" <ku...@bellsouth.net> wrote in message
news:okfsn78...@bellsouth.net...
> IIRC (it's been a few years), you don't have to "stop" in order to
> "copy". ISTR at least one incremental copying collector in the Garbage
> Collection book (which is at a different desk).
While it is true that you don't *have* to stop in order to copy,
it is much more difficult. It seems to be more common to use
a generational GC to keep the `stop' time down to a very small
amount.
Stefan Monnier <foo@acm.com>
> So the weird thing is that some people have said "it's trivial" and
> some have said "it's impossible", and somewhere in between the truth
> must lie.
I think the problem is that it's trivial from the point of view of the
compiler that compiles the GC code. But it's very difficult from the point
of view of the coder who has to convince himself (and others) that the
code is correct.
Stefan
Thomas Bushnell, BSG
> Actually, no you don't - you already have the needed operations in
> scheme. They are called vector-ref and vector-set!
Sure, if the system hands me a vector representing the memory arena.
Which is a pretty clever strategy, and very Schemey. Thanks for the
suggestion, I like it!
> > "This is an open area for research, but has not been widely
> > investigated because of the paucity of live bare-metal implementations
> > since the demise of the major lisp machine vendors."
>
> Bare metal did not become less available (unless it has to have some
> really specific attributes) with the lisp machines going away. People
> just became more convinient and moved to hosted environments.
Bare metal is not less available. But bare-metal implementations are
less available.
Thomas Bushnell, BSG
> This is a simple arithmetic check against a high-watermark, I doubt it
> would have a significant cost. Especially if you can inline.
I'm not so sure of that. You might be right. But I don't want the
memory model to constrain the compiler against doing things faster, if
it turns out that the check is expensive.
> > You don't want gc to run on the same execution stack as the user's
> > process.
> Why? Oh, and 'does it uncesessarily burden debugging'?
Several reasons: the user's process might have lower permissions, so
that you want to do the gc in a process that has more
permissions. This of course depends on the permission model.
> > So the sort of strategy I'm thinking of for cons is something like:
> >
> > Each thread has an allocation arena, given by the system, and the
> > compiler is allowed to take bits of it as it pleases (in order) from
> > front to back to allocate objects.
>
> So this would be the static allocation area, as the compiler cannot
> predict runtime. Probably a very small area.
By "the compiler" I mean "the code the compiler generates"; sorry for
needless confusion.
> > This requires knowing how the compiler tracks the current allocation
> > pointer in the arena (say, by dedicating a specific register to it,
> > dunno) but otherwise nicely decouples the two.
>
> No, you don't need to know how the runtime/compiler stores the current
> highest pointer - you just allocate that page (and possibly a couple
> of more) on the request.
That works if you can guarantee that the heap will be growing "in
order"; if all the threads are sharing the same address space, then
that might be more trouble than its worth, and might interact poorly
with other constraints on the paging system.
I'd rather decouple things as much as possible, which means I'd like
to allow the gc the freedom to tell the thread where its new
allocation area is, in case the next page isn't actually available for
the task.
> This assumes that faulting on "need more memory" is cheaper than a simple
> check. It may be for bytecodes, not necessarily for compiled (and memory
> intensive) code.
Faulting on need-more-memory can be really really fast, actually, if
the VM system is designed with it in mind. If allocation areas are
handed out in 512K chunks, for example, and a cons holds eight bytes,
and all the allocations are conses, then allocating the full 512K
would require 65,536 checks, at at least two instructions each, for a
total of 131,072 instructions. Good page fault algorithms could trap
the fault, detect it's the fastpath case, and return with a new arena
in under 100 instructions.
> IMVHO having cons be fast, low-level but stupid is not the interesting
> thing to solve. Having fast primitives does not necessarily automaticly
> give you a fast system - the interesting thing is to make the code, not
> the primitives it uses, fast. An allocator and GC pair that was smart
> about memory hierarchy but required more instructions to run would be a
> win - even if it was not so good on micro-benchmarks.
Yes, certainly. I think it's important to make the whole damn thing
fast, and since this one is so easy to get right, I'll do it.
Thomas
Sander Vesik
>
>> This is a simple arithmetic check against a high-watermark, I doubt it
>> would have a significant cost. Especially if you can inline.
>
> I'm not so sure of that. You might be right. But I don't want the
> memory model to constrain the compiler against doing things faster, if
> it turns out that the check is expensive.
cons is not something that should get called often, almost definately
not by other library functions.
>
>> > You don't want gc to run on the same execution stack as the user's
>> > process.
>
>> Why? Oh, and 'does it uncesessarily burden debugging'?
>
> Several reasons: the user's process might have lower permissions, so
> that you want to do the gc in a process that has more
> permissions. This of course depends on the permission model.
How can a process have so low permissionsit can't do its own garbage
collection? I'm definately missing something in the architecture here...
>
>> > So the sort of strategy I'm thinking of for cons is something like:
>> >
>> > Each thread has an allocation arena, given by the system, and the
>> > compiler is allowed to take bits of it as it pleases (in order) from
>> > front to back to allocate objects.
>>
>> So this would be the static allocation area, as the compiler cannot
>> predict runtime. Probably a very small area.
>
> By "the compiler" I mean "the code the compiler generates"; sorry for
> needless confusion.
>
>> > This requires knowing how the compiler tracks the current allocation
>> > pointer in the arena (say, by dedicating a specific register to it,
>> > dunno) but otherwise nicely decouples the two.
>>
>> No, you don't need to know how the runtime/compiler stores the current
>> highest pointer - you just allocate that page (and possibly a couple
>> of more) on the request.
>
> That works if you can guarantee that the heap will be growing "in
> order"; if all the threads are sharing the same address space, then
> that might be more trouble than its worth, and might interact poorly
> with other constraints on the paging system.
>
> I'd rather decouple things as much as possible, which means I'd like
> to allow the gc the freedom to tell the thread where its new
> allocation area is, in case the next page isn't actually available for
> the task.
Why is decoupling everything a design goal for you?
>
>> This assumes that faulting on "need more memory" is cheaper than a simple
>> check. It may be for bytecodes, not necessarily for compiled (and memory
>> intensive) code.
>
> Faulting on need-more-memory can be really really fast, actually, if
> the VM system is designed with it in mind. If allocation areas are
> handed out in 512K chunks, for example, and a cons holds eight bytes,
> and all the allocations are conses, then allocating the full 512K
> would require 65,536 checks, at at least two instructions each, for a
> total of 131,072 instructions. Good page fault algorithms could trap
> the fault, detect it's the fastpath case, and return with a new arena
> in under 100 instructions.
I can't think of any excuse for using the function 'cons' like that.
I can't think of any reasonable case where you would in fact be using
a pattern like that unless you were "by hand" in-place building huge
lists - and that is probably done best in some other way.
>
>> IMVHO having cons be fast, low-level but stupid is not the interesting
>> thing to solve. Having fast primitives does not necessarily automaticly
>> give you a fast system - the interesting thing is to make the code, not
>> the primitives it uses, fast. An allocator and GC pair that was smart
>> about memory hierarchy but required more instructions to run would be a
>> win - even if it was not so good on micro-benchmarks.
>
> Yes, certainly. I think it's important to make the whole damn thing
> fast, and since this one is so easy to get right, I'll do it.
No, this one is not easy to get right, its hard.
Thomas Bushnell, BSG
> How can a process have so low permissionsit can't do its own garbage
> collection? I'm definately missing something in the architecture here...
An ordinary *thread* in a single-address space system better not have
permission to do gc, or it can screw the one global heap used by
all the other threads beloning to all the other users.
I'm doing OS design here; this is not about hosted implementations
running on Unix.
> Why is decoupling everything a design goal for you?
Because it leads to more robust software in the long-term.
> I can't think of any excuse for using the function 'cons' like that.
> I can't think of any reasonable case where you would in fact be using
> a pattern like that unless you were "by hand" in-place building huge
> lists - and that is probably done best in some other way.
What? I'm talking about the overhead of doing 32K conses. That
overhead is, using your technique, something like 131,072
instructions. In my technique, it's about 100.
If you aren't going to do that many conses, ever, then it would be
far better to skip gc *entirely*, and just use up the memory. I'm
assuming that you do do enough allocation to actually need gc and
memory management techniques at all.
> No, this one is not easy to get right, its hard.
I'm an OS designer. It's really easy for me to get it right. Writing
page manipulations and vm code is my bread and butter.
Thomas
Joe Marshall
"Sander Vesik" <san...@haldjas.folklore.ee> wrote in message
news:10160260...@haldjas.folklore.ee...
>
> cons is not something that should get called often, almost definately
> not by other library functions.
Why not? When the GC is correctly tuned, the cost of consing
temporary structure is virtually negligable.
> How can a process have so low permissionsit can't do its own garbage
> collection? I'm definately missing something in the architecture here...
Imagine that the OS needs to allocate storage for some operation it
does on behalf of the user process. The OS cannot trust the user
process to leave the storage alone, so it puts it where the user
can't manipulate it.
Now suppose this structure contains a pointer to a user structure.
If the user wishes to garbage collect, he must update the pointer,
yet he doesn't have permission to.
> Thomas Bushnell, BSG wrote
> > Faulting on need-more-memory can be really really fast, actually, if
> > the VM system is designed with it in mind. If allocation areas are
> > handed out in 512K chunks, for example, and a cons holds eight bytes,
> > and all the allocations are conses, then allocating the full 512K
> > would require 65,536 checks, at at least two instructions each, for a
> > total of 131,072 instructions. Good page fault algorithms could trap
> > the fault, detect it's the fastpath case, and return with a new arena
> > in under 100 instructions.
>
> I can't think of any excuse for using the function 'cons' like that.
> I can't think of any reasonable case where you would in fact be using
> a pattern like that unless you were "by hand" in-place building huge
> lists - and that is probably done best in some other way.
While I tend to doubt that the processor can take a fault like this
in less than 100 instructions (well the *count* may be less, but I bet
the execution time isn't), I have seen lots of cases where fast consing
is used.
> No, this one is not easy to get right, its hard.
I'd agree with this.
> Sander
>
> +++ Out of cheese error +++
(call-with-sufficient-cheese (lambda () (write-signature "~jrm")))
Sander Vesik
>
>> How can a process have so low permissionsit can't do its own garbage
>> collection? I'm definately missing something in the architecture here...
>
> An ordinary *thread* in a single-address space system better not have
> permission to do gc, or it can screw the one global heap used by
> all the other threads beloning to all the other users.
>
> I'm doing OS design here; this is not about hosted implementations
> running on Unix.
Ah, ok, so you would have a "non-proccess based" system. Or rather,
a system where processes would be represented as threads?
>> I can't think of any excuse for using the function 'cons' like that.
>> I can't think of any reasonable case where you would in fact be using
>> a pattern like that unless you were "by hand" in-place building huge
>> lists - and that is probably done best in some other way.
>
> What? I'm talking about the overhead of doing 32K conses. That
> overhead is, using your technique, something like 131,072
> instructions. In my technique, it's about 100.
>
> If you aren't going to do that many conses, ever, then it would be
> far better to skip gc *entirely*, and just use up the memory. I'm
> assuming that you do do enough allocation to actually need gc and
> memory management techniques at all.
Here we go again. "memory allocation" != cons. cons is one consumer of
memory allocation and does it in rather bad (small quantity, no
usable info about lifetime/type, etc.) one at that. Oh, and causes a
gazillion small fragmenting memory allocations to happen.
>
>> No, this one is not easy to get right, its hard.
>
> I'm an OS designer. It's really easy for me to get it right. Writing
> page manipulations and vm code is my bread and butter.
But thats not the part you need to get right - the part is doing
allocations and garbage collection while staying cache friendly.
Provided you get page colouring right its almost completely in the
noise area.
Sander Vesik
>
> "Sander Vesik" <san...@haldjas.folklore.ee> wrote in message
> news:10160260...@haldjas.folklore.ee...
>>
>> cons is not something that should get called often, almost definately
>> not by other library functions.
>
> Why not? When the GC is correctly tuned, the cost of consing
> temporary structure is virtually negligable.
But does the code actually cons or just need to (re)allocate memory?
The more you operate on memory in bulk the, esp if it happens in
"good" patterns the better for the memory hierarchy and the faster
the code will run. zone, slab and other more advanced allocators that
give you fast, pre-initalised cache-friendly memory have been around
for ages now - and these need to have something more than an anonymous
cons to give you any benefit.
>
>> How can a process have so low permissionsit can't do its own garbage
>> collection? I'm definately missing something in the architecture here...
>
> Imagine that the OS needs to allocate storage for some operation it
> does on behalf of the user process. The OS cannot trust the user
> process to leave the storage alone, so it puts it where the user
> can't manipulate it.
>
> Now suppose this structure contains a pointer to a user structure.
> If the user wishes to garbage collect, he must update the pointer,
> yet he doesn't have permission to.
>
Actually, if the OS cannot trust (but needs to), then allowing for pointers
outside of that area is a bug. Because the user can then effectively
change the data dispite the fact that the OS supposedly secured it.
So it effectively needs to either:
* suspend the process
* copy the data
>
>> Thomas Bushnell, BSG wrote
>> > Faulting on need-more-memory can be really really fast, actually, if
>> > the VM system is designed with it in mind. If allocation areas are
>> > handed out in 512K chunks, for example, and a cons holds eight bytes,
>> > and all the allocations are conses, then allocating the full 512K
>> > would require 65,536 checks, at at least two instructions each, for a
>> > total of 131,072 instructions. Good page fault algorithms could trap
>> > the fault, detect it's the fastpath case, and return with a new arena
>> > in under 100 instructions.
>>
>> I can't think of any excuse for using the function 'cons' like that.
>> I can't think of any reasonable case where you would in fact be using
>> a pattern like that unless you were "by hand" in-place building huge
>> lists - and that is probably done best in some other way.
>
> While I tend to doubt that the processor can take a fault like this
> in less than 100 instructions (well the *count* may be less, but I bet
> the execution time isn't), I have seen lots of cases where fast consing
> is used.
A L2 cache miss may well cost more than 100 cycles...
>
>> No, this one is not easy to get right, its hard.
>
> I'd agree with this.
>
>> Sander
>>
>> +++ Out of cheese error +++
>
> (call-with-sufficient-cheese (lambda () (write-signature "~jrm")))
>
>
>
--
Thomas Bushnell, BSG
> Actually, if the OS cannot trust (but needs to), then allowing for pointers
> outside of that area is a bug. Because the user can then effectively
> change the data dispite the fact that the OS supposedly secured it.
No, no, you don't really understand the permission model. The OS
*knows* that the user can "change the data", and that's not harmful at
all, as long as the OS exercises proper care when reading it.
Thomas Bushnell, BSG
> While I tend to doubt that the processor can take a fault like this
> in less than 100 instructions (well the *count* may be less, but I bet
> the execution time isn't), I have seen lots of cases where fast consing
> is used.
IIRC, the Utah Flux group executed a syscall trap in a total of less
than a hundred exceptions, and that was doing some message passing
too.
I'm not talking about doing this on Unix; geez, if you have to go
through the kernel, the signal code, user interrupt handlers, and all
the rest, it's a pain.
> > No, this one is not easy to get right, its hard.
>
> I'd agree with this.
Um, if you've ever written a page-fault handler, it's a really trivial
case.
Thomas Bushnell, BSG
> Ah, ok, so you would have a "non-proccess based" system. Or rather,
> a system where processes would be represented as threads?
Yes, absolutely.
Sander Vesik
How can I understand a permission model that has not been presented? 8-)
Thomas Bushnell, BSG
Here's the real clincher.
The gc needs access to primitives that can destroy the memory model of
the system if misused.
If everyone is sharing memory, then the gc is able to hose everybody.
Accordingly, the gc must be privileged.
Joe Marshall
"Thomas Bushnell, BSG" <tb+u...@becket.net> wrote in message
news:87henkq...@becket.becket.net...
> "Joe Marshall" <prunes...@attbi.com> writes:
>
> > While I tend to doubt that the processor can take a fault like this
> > in less than 100 instructions (well the *count* may be less, but I bet
> > the execution time isn't), I have seen lots of cases where fast consing
> > is used.
>
> IIRC, the Utah Flux group executed a syscall trap in a total of less
> than a hundred exceptions, and that was doing some message passing
> too.
>
> I'm not talking about doing this on Unix; geez, if you have to go
> through the kernel, the signal code, user interrupt handlers, and all
> the rest, it's a pain.
I was speculating that the time it took between the processor issuing
a write to the non-existant page until the processor was executing
the code that created the page would be quite high.
Thomas Bushnell, BSG
> I was speculating that the time it took between the processor issuing
> a write to the non-existant page until the processor was executing
> the code that created the page would be quite high.
VM ain't really that slow these days. It can be high, but it's
certainly not on the order of 125,000 instructions, which is what it
costs to execute two extra instructions per cons.
Daniel C. Wang
> If everyone is sharing memory, then the gc is able to hose everybody.
>
> Accordingly, the gc must be privileged.
Not if you're type system can gurantee your GC is type-preserving.
http://www.cs.princeton.edu/~danwang/Papers/tpsrvgc/
http://flint.cs.yale.edu/flint/publications/gc.html
http://ncstrl.cs.princeton.edu/expand.php?id=TR-640-01
Extending the proof that the GC is value preserving is still an open
question, but I think within the realm of "standard" type systems.
Ji-Yong D. Chung
"Thomas Bushnell, BSG" <tb+u...@becket.net> wrote in message
news:878z8xn...@becket.becket.net...
> Sander Vesik <san...@haldjas.folklore.ee> writes:
>
> > This can lead to unwanted amounts of fragmentation very easily if
> > data is accessed from more than one thread.
> ...
> But you are right that this is a worry. So my idea for that problem
> (which is really quite vague at this point) is to use a generational
> copy scheme, which moves data into global heaps and gets (hopefully
> better) locality for such data.
When you implement a generational collector, each arena
will have a finite size. Thus, if your overall heap size is 1 meg,
and each arena is 300k (assuming you have approximately 3
generations). Each arena is further partitioned for
each "native Scheme object" type.
So, you will end up with many small heaps.
In such cases, if your nursery allocates a relatively large
object (i.e., vector of very large dimension), it will not
be possible to promote that object to the next generation
(during a collection), because the available to-space in the
next generation will not be sufficient.
There are two ways to deal with the problem -- (1)
introduce big objects and/or (2) use expandable arenas.
Either case, it is a pain in the neck.
=====================
You might consider BIBOP.
Personally, I have found Kent Dybvig's paged memory
to be useful in this regard.
Rahul Jain
> When you implement a generational collector, each arena will have a
> finite size. Thus, if your overall heap size is 1 meg, and each
> arena is 300k (assuming you have approximately 3 generations). Each
> arena is further partitioned for each "native Scheme object" type.
WHY?? No Lisp implementation I know of does such a crazy thing. I
never knew there were people who wanted to make their implementations
that bad.
> So, you will end up with many small heaps.
If that were the case, how on earth would any reasonable
implementations of any garbage-collected, strongly-typed language
exist?
> In such cases, if your nursery allocates a relatively large
> object (i.e., vector of very large dimension), it will not
> be possible to promote that object to the next generation
> (during a collection), because the available to-space in the
> next generation will not be sufficient.
You could collect the next generation, too...
>
> There are two ways to deal with the problem -- (1)
> introduce big objects
I assume that means promoting the object to an older generation or
allocating it outside of the generations. This is the typical
strategy.
> and/or (2) use expandable arenas.
> Either case, it is a pain in the neck.
It is?
--
-> -/ - Rahul Jain - \- <-
-> -\ http://linux.rice.edu/~rahul -=- mailto:rj...@techie.com /- <-
-> -/ "Structure is nothing if it is all you got. Skeletons spook \- <-
-> -\ people if [they] try to walk around on their own. I really /- <-
-> -/ wonder why XML does not." -- Erik Naggum, comp.lang.lisp \- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
(c)1996-2002, All rights reserved. Disclaimer available upon request.
Ji-Yong D. Chung
"Rahul Jain" <rj...@sid-1129.sid.rice.edu> wrote in message
news:87663xw...@photino.sid.rice.edu...
> "Ji-Yong D. Chung" <virtua...@erols.com> writes:
>
> > When you implement a generational collector, each arena will have a
> > finite size. Thus, if your overall heap size is 1 meg, and each
> > arena is 300k (assuming you have approximately 3 generations). Each
> > arena is further partitioned for each "native Scheme object" type.
>
> WHY?? No Lisp implementation I know of does such a crazy thing. I
> never knew there were people who wanted to make their implementations
> that bad.
Actually, I have made an error in using the term "arena." I meant
that each generation is further partitioned into arenas.
If I remember right, SML/NJ (correct me here, as I am walking on
thin ice!!!), I think partitions heap as I said. I thought the collector
for Larceny did the same. It has been a while since I looked at
their source code, though.
BIBOP maps each object type into different arenas.
In my implementation, I did not further partition each
arena -- I did not use traditional BIBOP object mapping scheme.
> > So, you will end up with many small heaps.
>
> If that were the case, how on earth would any reasonable
> implementations of any garbage-collected, strongly-typed language
> exist?
Without specifics, this is not really answerable. Also,
I am rather ignorant on the topic of using generational gc for
strongly typed language.
> > In such cases, if your nursery allocates a relatively large
> > object (i.e., vector of very large dimension), it will not
> > be possible to promote that object to the next generation
> > (during a collection), because the available to-space in the
> > next generation will not be sufficient.
>
> You could collect the next generation, too...
That would not work -- because the maximum
to-space is bound by the size of the arena.
> >
> > There are two ways to deal with the problem -- (1)
> > introduce big objects
>
> I assume that means promoting the object to an older generation or
> allocating it outside of the generations. This is the typical
> strategy.
Yes.
> > and/or (2) use expandable arenas.
> > Either case, it is a pain in the neck.
>
> It is?
Big objects are pain in the neck, because these
objects need to be treated specially. They need to be
scanned for pointers, after "normal collection." Furthermore,
it can introduce heap fragmentation. (I have read that, _in practice_,
fragmentation is not really a problem for Chez Scheme or
Larceny -- but, at least, it is an issue one needs to think about).
Having expandable arenas are pain in the neck, because
this means one has to make arenas of different sizes. This
also means keeping track of extra parameters for computing
available heap space for promotion. When the arena sizes
are identical, one can calculate the available promotion space
based on simple algorithms.
Take for example the following algorithm for computing available
arena space for promotion: first, collect _within_ the same
generation, doing a simple transfer of objects from from-space
to to-space. If objects survive twice, we promote.
The preceding algorithm is inefficient, because it copies
objects at least once prior to copying for promotion..
In any case, there are additional problems with
expandable arenas -- I am not saying they are very
difficult to implement. It is just that, IMHO, one loses
a lot of design elegance and introduces unnecessary
complexity.
Rahul Jain
> Hi
> "Rahul Jain" <rj...@sid-1129.sid.rice.edu> wrote in message
> news:87663xw...@photino.sid.rice.edu...
> > "Ji-Yong D. Chung" <virtua...@erols.com> writes:
> > > When you implement a generational collector, each arena will have a
> > > finite size. Thus, if your overall heap size is 1 meg, and each
> > > arena is 300k (assuming you have approximately 3 generations). Each
> > > arena is further partitioned for each "native Scheme object" type.
> > WHY?? No Lisp implementation I know of does such a crazy thing. I
> > never knew there were people who wanted to make their implementations
> > that bad.
> Actually, I have made an error in using the term "arena." I meant
> that each generation is further partitioned into arenas.
I understood what you were saying even though the terminology may have
not been what I was used to. It was the partitioning of the
generations by type that I don't understand.
> If I remember right, SML/NJ (correct me here, as I am walking on
> thin ice!!!), I think partitions heap as I said. I thought the collector
> for Larceny did the same. It has been a while since I looked at
> their source code, though.
That's a really strange way to do things. I can't imagine what the
material gain would be. Maybe a few bits on the fixnum type?
> Without specifics, this is not really answerable. Also,
> I am rather ignorant on the topic of using generational gc for
> strongly typed language.
Typically, the way I understand Lisp GCs work is that each object has
type information in its header, which allows the GC to know how large
the object is and whether (and where) it contains references to other
objects.
> Big objects are pain in the neck, because these
> objects need to be treated specially. They need to be
> scanned for pointers, after "normal collection." Furthermore,
> it can introduce heap fragmentation. (I have read that, _in practice_,
> fragmentation is not really a problem for Chez Scheme or
> Larceny -- but, at least, it is an issue one needs to think about).
it's true that you have to make special considerations for such
objects. If there are enough of them to cause a problem, you're
probably using the wrong gc (settings) for your application.
> In any case, there are additional problems with
> expandable arenas -- I am not saying they are very
> difficult to implement. It is just that, IMHO, one loses
> a lot of design elegance and introduces unnecessary
> complexity.
Yes, I'd have to agree with this now. Expandable arenas are really a
waste of effort, since it would be easier to just have them fit some
fixed portion of memory space, and map only what it needed for the
current generation size. I suppose this is effectively "expandable" in
that the generation does not chew up more VM than the generation's
size, and the generations can grow to some size that is fixed by the
implementation's choice of VM layout.
Jeffrey Siegal
> > If I remember right, SML/NJ (correct me here, as I am walking on
> > thin ice!!!), I think partitions heap as I said. I thought the collector
> > for Larceny did the same. It has been a while since I looked at
> > their source code, though.
>
> That's a really strange way to do things. I can't imagine what the
> material gain would be. Maybe a few bits on the fixnum type?
It eliminates the need for a separate tag (which is only a few bits in a
langauge with few types) on every object, not just fixnums.
Erik Naggum
| It eliminates the need for a separate tag (which is only a few bits in a
| langauge with few types) on every object, not just fixnums.
I have wondered about this, so maybe you can help me understand. When
you allocate objects from type-specific arenas, how many types do you do
this for? Does a user-defined class hierarchy get their own arena for
each class? How do you get the type of the object? (I think one would
either have type information at the beginning of the page or use the page
number as some kind of index into a table, or use virtual memory address
space to sort of have tag bits in the upper address bits.) This would
save space compared to using type information in the object itself, but
it seems the pages would have to be fairly large to make sure the type
information would be in an active cache line. However, this approach
seems to me to work well only if you do not use the type information all
the time, because the memory accesses required to obtain the type would
be fairly expensive compared to extracting low-end bits. I have read
about BIBOP long ago, but I did not find an explanation of how you mad
back from page to type or for which types this was employed.
///
--
In a fight against something, the fight has value, victory has none.
In a fight for something, the fight is a loss, victory merely relief.
Jeffrey Siegal
>
> * Jeffrey Siegal <j...@quiotix.com>
> | It eliminates the need for a separate tag (which is only a few bits in a
> | langauge with few types) on every object, not just fixnums.
>
> I have wondered about this, so maybe you can help me understand. When
> you allocate objects from type-specific arenas, how many types do you do
> this for?
Were I implementing such a system, I would probably do it for every
type, but not in the first GC generation. I would size the arenas based
on previous collections, on the theory that usage has some measure of
stability.
> Does a user-defined class hierarchy get their own arena for
> each class? How do you get the type of the object? (I think one would
> either have type information at the beginning of the page or use the page
> number as some kind of index into a table, or use virtual memory address
> space to sort of have tag bits in the upper address bits.)
Agreed.
> This would
> save space compared to using type information in the object itself, but
> it seems the pages would have to be fairly large to make sure the type
> information would be in an active cache line. However, this approach
> seems to me to work well only if you do not use the type information all
> the time, because the memory accesses required to obtain the type would
> be fairly expensive compared to extracting low-end bits.
This would of course depend on the size and relative speed of cache,
etc., but I suspect that you would get more from being able to store
more objects in cache than you would lose by occasionally having a cache
miss when looking up types. Keep in mind that with type inference, you
can often determine types at compile type, but unless you can type-infer
the entire program, you still need to store types in memory. A more
compact representation in memory will still yield a benefit in terms of
increased cache hit rate even in this case, and in this case it is a
pure gain, since there is no need to reference the types at all.
Matthias Blume
> * Jeffrey Siegal <j...@quiotix.com>
> | It eliminates the need for a separate tag (which is only a few bits in a
> | langauge with few types) on every object, not just fixnums.
>
> I have wondered about this, so maybe you can help me understand. When
> you allocate objects from type-specific arenas, how many types do you do
> this for? Does a user-defined class hierarchy get their own arena for
> each class? How do you get the type of the object? (I think one would
> either have type information at the beginning of the page or use the page
> number as some kind of index into a table, or use virtual memory address
> space to sort of have tag bits in the upper address bits.)
You snipped the a relevant part of the discussion leading up to this, namely that
this scheme is being used by SML/NJ -- an implementation of a statically typed language.
The BIBOP allocation scheme worries about "representation types" only: Everything that
looks (in memory) like a cons cell is allocated in the cons arena. The BIBOP is not
sufficient to answer the question "which high-level type does this value belong to",
but since it is only used so the GC can do its tracing, such a question never comes
up.
Matthias
Erik Naggum
| You snipped the a relevant part of the discussion leading up to this,
| namely that this scheme is being used by SML/NJ -- an implementation of a
| statically typed language.
Yes, I did, as is common when discussing things on USENET -- we do not
generally post multimegabyte messages to keep all the context -- but you
imply that I had not understood that. Please refrain from such dirty
tactics. You have not helped answer my question, either.
Duane Rettig
> * Jeffrey Siegal <j...@quiotix.com>
> | It eliminates the need for a separate tag (which is only a few bits in a
> | langauge with few types) on every object, not just fixnums.
>
> I have wondered about this, so maybe you can help me understand. When
> you allocate objects from type-specific arenas, how many types do you do
> this for? Does a user-defined class hierarchy get their own arena for
> each class? How do you get the type of the object? (I think one would
> either have type information at the beginning of the page or use the page
> number as some kind of index into a table, or use virtual memory address
> space to sort of have tag bits in the upper address bits.) This would
> save space compared to using type information in the object itself, but
> it seems the pages would have to be fairly large to make sure the type
> information would be in an active cache line. However, this approach
> seems to me to work well only if you do not use the type information all
> the time, because the memory accesses required to obtain the type would
> be fairly expensive compared to extracting low-end bits. I have read
> about BIBOP long ago, but I did not find an explanation of how you mad
> back from page to type or for which types this was employed.
FranzLisp used this bibop method. The way they (UCB students) and we
(Franz Inc) did it was to preallocate an array of 8-bit typecodes, one
for each allocation page, and then assign each entry in the array which
corresponded to the new page being allocated. The "types" were really
only implementational types; any composite types would be allocated
based on the 8-bit type code associated with the object. And FranzLisp
didn't have CLOS, so that meta-type structure didn't exist. Flavors
covered that time period, but flavors classes were not discriminated
with that low-level mechanism. Think of the typing being equivalent
to the 8-bit "other" type codes that are currently stored in the header
of each object in CL implementations when they are not determined by
their tag (i.e. when they have a tag of "other").
In FranzLisp's bibop, to get from any address to its type. you hash on
the address. Suppose the allocation page size is 8 kbytes. Then to
get an index into the typetable vector, you shift the address of your
object right 13 bits, and use that to index into your type vector.
Since it was a byte vector, it needed no other shifts to account for
element width.
Obviously, when we created Allegro CL (called ExCL at the time), we
changed the basic philosophy of typing, partly due to the number of
instructions and memory references it took to get the type of an object.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 du...@Franz.COM (internet)
Thomas Bushnell, BSG
> * Matthias Blume
> | You snipped the a relevant part of the discussion leading up to this,
> | namely that this scheme is being used by SML/NJ -- an implementation of a
> | statically typed language.
>
> Yes, I did, as is common when discussing things on USENET -- we do not
> generally post multimegabyte messages to keep all the context -- but you
> imply that I had not understood that. Please refrain from such dirty
> tactics. You have not helped answer my question, either.
I think Matthias' point is that in a statically typed language, you
don't need to detect types at runtime, or something like that.
(Except in GC, where the costs you point out are not so severe.)
At least, that's what I took Matthias to be saying.
Erik Naggum
| I think Matthias' point is that in a statically typed language, you
| don't need to detect types at runtime, or something like that.
| (Except in GC, where the costs you point out are not so severe.)
|
| At least, that's what I took Matthias to be saying.
Let me repeat what I actually wrote:
However, this approach seems to me to work well only if you do not use
the type information all the time
which I think any reasonably smart reader would understand implied that
(1) I had already figured out that it works best for statically typed
languages that do little dynamic typing, and (2) wondered about the
design in a language that did have dynamic typing, where is also used.
So what was Matthias saying? Nothing. One does not need to post an
article to say nothing. Posting an article to say nothing is rude.
Rahul Jain
> Keep in mind that with type inference, you can often determine types
> at compile type, but unless you can type-infer the entire program,
> you still need to store types in memory.
It seems this strategy will only work for static languages, then. In
Lisp, functions and types can be redefined on the fly, changing the
time-dependent assumptions of the compiler.
Jeffrey Siegal
> > Keep in mind that with type inference, you can often determine types
> > at compile type, but unless you can type-infer the entire program,
> > you still need to store types in memory.
>
> It seems this strategy will only work for static languages, then. In
> Lisp, functions and types can be redefined on the fly, changing the
> time-dependent assumptions of the compiler.
That was precisely my point about still needing to store types in
memory, even if they often won't be used. Type inference can work even
in a dynamic language for some pieces of code, due to lexical scope and
declarations, but since usually it can't work for the whole program,
types must be stored, somehow, in memory, even when they often will not
be used in performance-critical code (because this code will often make
use of the above techniques to allow a compiler to optimize).
However, even in the fully-general case of code which always checks
types at run time, it isn't clear that storing type by arena would not
be faster today. Given the extreme spread between cache speed and main
memory speed, compared to only a few years ago, it can sense to do a lot
of work to get more objects to fit in cache (effectively making the
cache larger).
Rahul Jain
> That was precisely my point about still needing to store types in
> memory, even if they often won't be used.
So why not place the type tag in the low bits rather than the high bits?
> However, even in the fully-general case of code which always checks
> types at run time, it isn't clear that storing type by arena would not
> be faster today. Given the extreme spread between cache speed and main
> memory speed, compared to only a few years ago, it can sense to do a lot
> of work to get more objects to fit in cache (effectively making the
> cache larger).
This would mean that you don't want to spread objects all over the
memory space. You're more likely to have more objects in cache if
objects are more densely pcked in memory.
Actually, this scheme would completely destroy the idea of a fixnum,
since there would be "holes" all over the fixnum space which coincide
with where the arenas are...
Jeffrey Siegal
> > That was precisely my point about still needing to store types in
> > memory, even if they often won't be used.
>
> So why not place the type tag in the low bits rather than the high bits?
In fact the low few bits probably should be used for tags, since they're
otherwise useless given that objects will always be aligned.
However, there are only a few usable low bits. To encode a more than a
few primitive types, you need more. Probably the low bits can be used
to encode primitive types and arenas can be used to encode user defined
types.
> > However, even in the fully-general case of code which always checks
> > types at run time, it isn't clear that storing type by arena would not
> > be faster today. Given the extreme spread between cache speed and main
> > memory speed, compared to only a few years ago, it can sense to do a lot
> > of work to get more objects to fit in cache (effectively making the
> > cache larger).
>
> This would mean that you don't want to spread objects all over the
> memory space. You're more likely to have more objects in cache if
> objects are more densely pcked in memory.
Cache lines aren't that large. As long as you aren't dealing with one
each from a zillion different types, which I rather doubt is the usual
case, locality should be fine.
> Actually, this scheme would completely destroy the idea of a fixnum,
> since there would be "holes" all over the fixnum space which coincide
> with where the arenas are...
Fixnums can have a unique tag in the low-order bits.
Rahul Jain
> Rahul Jain wrote:
> > > That was precisely my point about still needing to store types in
> > > memory, even if they often won't be used.
> >
> > So why not place the type tag in the low bits rather than the high bits?
>
> In fact the low few bits probably should be used for tags, since they're
> otherwise useless given that objects will always be aligned.
>
> However, there are only a few usable low bits. To encode a more than a
> few primitive types, you need more. Probably the low bits can be used
> to encode primitive types and arenas can be used to encode user defined
> types.
The way most lisp implementations do it is to have "headers" on object
to indicate what type it is. There are often so many different
user-defined types (and builtin types) that you'd need hundreds of
arenas.
From debian's cmucl 3.0.9 without loading any other code,
* (inspect (find-class t))
#<BUILT-IN-CLASS T (read-only) {28000A65}> is a structure.
6. SUBCLASSES: #<EQ hash table, 478 entries {280C3695}>
That would require at LEAST 400 arenas. Way too much fragmentation for
real use.
> > This would mean that you don't want to spread objects all over the
> > memory space. You're more likely to have more objects in cache if
> > objects are more densely pcked in memory.
>
> Cache lines aren't that large. As long as you aren't dealing with one
> each from a zillion different types, which I rather doubt is the usual
> case, locality should be fine.
Well, lisp systems make good use of user-defined types. When you
actually load an application, that number can increase
dramatically. E.g., I estimate that DefDoc (my vaporware document
processing system) will define at least 100 types, allowing for
another 100 or so to be generated dynamically at runtime without
explicit defintion.
> > Actually, this scheme would completely destroy the idea of a fixnum,
> > since there would be "holes" all over the fixnum space which coincide
> > with where the arenas are...
>
> Fixnums can have a unique tag in the low-order bits.
How is that guaranteed to be unique and not intersect with the arena
segments?
Jeffrey Siegal
> That would require at LEAST 400 arenas. Way too much fragmentation for
> real use.
That depends how large the arenas are and also how much overall benefit
is realized by using them. I don't believe you can say "way too much
fragmentation" without actually measuring, or at least modeling, both
the costs and benefits.
> > > Actually, this scheme would completely destroy the idea of a fixnum,
> > > since there would be "holes" all over the fixnum space which coincide
> > > with where the arenas are...
> >
> > Fixnums can have a unique tag in the low-order bits.
>
> How is that guaranteed to be unique and not intersect with the arena
> segments?
Because objects stored in segments are always aligned, so their
low-order bits can be a constant. Fixnums can be tagged in their low
order bits using a distinct constant.
Matthias Blume
> * Matthias Blume
> | You snipped the a relevant part of the discussion leading up to this,
> | namely that this scheme is being used by SML/NJ -- an implementation of a
> | statically typed language.
>
> Yes, I did, as is common when discussing things on USENET -- we do not
> generally post multimegabyte messages to keep all the context -- but you
> imply that I had not understood that.
I did not imply any such thing, at least not intentionally. I merely
said that you did (snip), and as you say yourself, that is a fact.
> Please refrain from such dirty tactics.
You are hallucinating. No tactics, dirty or clean. (What would be the point?)
> You have not helped answer my question, either.
I am truly sorry about that.
Matthias