I've read the GC FAQ but that's basically all I know about garbage
collection. What I noticed is that some CL implementations on some
platforms have conservative GC while others have precise GC. I
understand that conservative GC may keep objects alive (infinitely?)
that are otherwise garbage. My questions are:
1. Does this have any consequences in practice or are these just
theoretical issues? I'm currently working on an application that is
supposed to sit behind a webpage and run for a very long time -
maybe months or years. Do I have to worry if my GC is conservative?
2. And, _if_ I have to worry, are there any identifiable - maybe
degenerated - usage patterns which will lead to accumulated garbage
or can this happen with arbitrary data/programs?
3. Do I have any (implementation-dependent) options to get rid of this
garbage or will I have to restart the application from time to time
(provided there _is_ accumulated garbage).
4. And, out of curiosity - is there any reason to use conservative GC
if it tends to "leak" memory? Is precise GC slower or
harder/impossible to implement - maybe on certain platforms?
Thanks in advance,
Edi.
Edi Weitz <···@agharta.de> wrote in message news:<··············@bird.agharta.de>...
> I've read the GC FAQ but that's basically all I know about garbage
> collection. What I noticed is that some CL implementations on some
> platforms have conservative GC while others have precise GC. I
> understand that conservative GC may keep objects alive (infinitely?)
> that are otherwise garbage. My questions are:
>
> 1. Does this have any consequences in practice or are these just
> theoretical issues?
It has consequences in practice. It means that the GC algorithm is
incorrect, so that the application potentially contains memory leaks.
This type of GC is only useful as a safety net to try to plug memory
leaks in software that otherwise manages its own deallocation.
> I'm currently working on an application that is
> supposed to sit behind a webpage and run for a very long time -
> maybe months or years. Do I have to worry if my GC is conservative?
Yes.
> 2. And, _if_ I have to worry, are there any identifiable - maybe
> degenerated - usage patterns which will lead to accumulated garbage
> or can this happen with arbitrary data/programs?
Conservative garbage collection means that the collector cannot be
sure whether some word of storage is a pointer or not, because it
could just be some scalar value of a non-pointer type which looks like
a pointer. How likely is it that your program will contain such scalar
values somewhere in its live data, and contain them long enough? How
many angels can stand on the head of a pin?
Just one such a scalar value could masquerade as the last remaining
reference to a complex object containing references through which a
large amount of data is accessible.
> 4. And, out of curiosity - is there any reason to use conservative GC
> if it tends to "leak" memory? Is precise GC slower or
> harder/impossible to implement - maybe on certain platforms?
It's harder to implement under some programming languages, like C and
C++. An object in C is just a piece of storage, whose type is known
implicitly by the expression which refers to it. On, say, a typical 32
bit platform, it's impossible to tell, by looking at it, whether a
four byte object is a pointer or integer, or an IEEE short float, a
char [4] array, a struct of two short ints and so forth. Secondly,
garbage collectors ``slid under'' existing language implementations
have to work with their existing allocation strategies. The compiler
uses the stack in a certain way for locals, and so you have to work
with that, etc.
In a language designed for, and implemented with GC from the start,
you don't have this problem. Not only are objects tagged with a type
field, so you know exactly whether you are looking at a literal object
or a reference, but you have total control over their allocation
strategy in the first place. For instance you can use a dedicated pool
purely for cons cells, where consequently you don't have to deal with
fragmentation, all objects being of equal size.
>>>>> "Edi" == Edi Weitz <···@agharta.de> writes:
Edi> 1. Does this have any consequences in practice or are these just
Edi> theoretical issues? I'm currently working on an application that is
Edi> supposed to sit behind a webpage and run for a very long time -
Edi> maybe months or years. Do I have to worry if my GC is conservative?
The XEmacs folks use a precise GC for this reason. But I have not
heard of that actually happening.
Edi> 2. And, _if_ I have to worry, are there any identifiable - maybe
Edi> degenerated - usage patterns which will lead to accumulated garbage
Edi> or can this happen with arbitrary data/programs?
Somewhere in the cmucl-imp archives is a small program that causes
cmucl/x86 with it's generational conservative gc to leak huge amounts
of memory as long as the function is running. When the function
finishes, the memory is eventually released. cmucl/sparc, which uses
a precise copying gc, doesn't have ths problem.
Edi> 4. And, out of curiosity - is there any reason to use conservative GC
Edi> if it tends to "leak" memory? Is precise GC slower or
Edi> harder/impossible to implement - maybe on certain platforms?
At least for cmucl, the x86 port uses conservative gc because there
aren't enough registers to partition into descriptor (pointers to lisp
objects) and non-descriptor (machine ints, fixnums, characters, etc.)
registers, so gc is conservative because the gc doesn't know what kind
of object is in the register.
Ray
Raymond Toy <···@rtp.ericsson.se> writes:
> At least for cmucl, the x86 port uses conservative gc because there
> aren't enough registers to partition into descriptor (pointers to lisp
> objects) and non-descriptor (machine ints, fixnums, characters, etc.)
> registers, so gc is conservative because the gc doesn't know what kind
> of object is in the register.
It's not quite as bad as it sounds, really. The registers must be
scavenged conservatively for the aforementioned reason: ditto the
stack, because we share it with C so it may have foreign frames,
signal handler contexts, etc, on it.
Lisp space (dynamic heap, static space, etc) on the other hand is full
of appropriately tagged objects, and can be scavenged exactly.
So, yes, a partly-conservative GC is still a conservative GC, but I
wouldn't want to leave people under the impression that we don't use
the tag/header information in the places where we _can_ rely on it.
(I guess we could get closer to exactness by doing magic in the
call-into-c glue, and using alternate signal stacks for all signals,
but historically some of the CMUCL targets have struggled with their
support for signal delivery on alternate stacks, so the current
approach is probably a bit more portable)
-dan
--
http://www.cliki.net/ - Link farm for free CL-on-Unix resources
Daniel Barlow <···@telent.net> writes:
> It's not quite as bad as it sounds, really. The registers must be
> scavenged conservatively for the aforementioned reason: ditto the
> stack, because we share it with C so it may have foreign frames,
> signal handler contexts, etc, on it.
We handle the mix of data on the stack in Allegro CL by dividing stacks
into blocks of Lisp frames and blocks of non-lisp frames, and by dividing
individual Lisp frames into Lisp slots and non-lisp slots (for immediate
float values, for example, and for stack-allocated arrays of specialized
element-types). The stack walker for the GC skips non-lisp frames
entirely, and skips the non-lisp slots in Lisp frames as well.
> (I guess we could get closer to exactness by doing magic in the
> call-into-c glue, and using alternate signal stacks for all signals,
> but historically some of the CMUCL targets have struggled with their
> support for signal delivery on alternate stacks, so the current
> approach is probably a bit more portable)
We handle this in Allegro CL by not allowing the signal handler
to call any lisp code. Instead, it vectors off to other code which
is similar to the interrupt code, but which was compiled by the
lisp compiler and thus has known internal structure.
I wrote and presented a paper at the 1999 LUGM, available as
ftp://ftp.franz.com/pub/duane/break.ps - it is in fact about
instruction-level stepping, but section 2.1 goes into how the
signal handlers operate.
Once data on the stack is known as lisp or non-lisp, the GC can be
precise.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Martin Hirzel has performed some interesting studies about these issues.
His homepage is at http://csel.cs.colorado.edu/~hirzel/ - perhaps you
can find some answers in his publications, or contact him directly.
Edi Weitz wrote:
> I've read the GC FAQ but that's basically all I know about garbage
> collection. What I noticed is that some CL implementations on some
> platforms have conservative GC while others have precise GC. I
> understand that conservative GC may keep objects alive (infinitely?)
> that are otherwise garbage. My questions are:
>
> 1. Does this have any consequences in practice or are these just
> theoretical issues? I'm currently working on an application that is
> supposed to sit behind a webpage and run for a very long time -
> maybe months or years. Do I have to worry if my GC is conservative?
As far as I understand, these are mostly theoretical issues. It can be
shown that precise gc doesn't buy you much whereas for example liveness
analysis is worthwhile.
> 3. Do I have any (implementation-dependent) options to get rid of this
> garbage or will I have to restart the application from time to time
> (provided there _is_ accumulated garbage).
Martin told me about an interesting technique: When you change the start
addresses of the memory pages you have allocated every now and then, you
can be pretty sure that you won't run into memory leaks at all. MMUs
allow you to do this with virtually no cost. However, I don't know the
exact details and I don't know if this has ever been used in
"real-world" systems.
> 4. And, out of curiosity - is there any reason to use conservative GC
> if it tends to "leak" memory? Is precise GC slower or
> harder/impossible to implement - maybe on certain platforms?
One of the most widely used gcs - the Boehm gc - is conservative. So it
doesn't seem to be a problem in general.
But please beware: I am not more than an informed outsider wrt to this
topic.
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Pascal Costanza <········@web.de> wrote in message news:<············@f1node01.rhrz.uni-bonn.de>...
> One of the most widely used gcs - the Boehm gc - is conservative. So it
> doesn't seem to be a problem in general.
Wide use doesn't prove anything, because crap software written in C
and C++, chock full of crashes and memory leaks, with no garbage
collector under it, also achieves wide use nevertheless.
If Boehm fails to plug all the memory leaks in a program, nobody will
care in practice. They are just happy that the code crashes less, and
doesn't appear to leak as much.
The reason Boehm is widely used is because it's one of the few choices
available to C programmers. It's not chosen because it's conservative,
but in spite of that limitation, which can be rationalized away.
>>>>> "Kaz" == Kaz Kylheku <···@ashi.footprints.net> writes:
Kaz> Pascal Costanza <········@web.de> wrote in message
Kaz> news:<············@f1node01.rhrz.uni-bonn.de>...
>> One of the most widely used gcs - the Boehm gc - is
>> conservative. So it doesn't seem to be a problem in general.
Kaz> Wide use doesn't prove anything, because crap software
Kaz> written in C and C++, chock full of crashes and memory leaks,
Kaz> with no garbage collector under it, also achieves wide use
Kaz> nevertheless.
Agreed, but Boehm's GC is still quite remarkable in my opinion.
Kaz> If Boehm fails to plug all the memory leaks in a program,
Kaz> nobody will care in practice. They are just happy that the
Kaz> code crashes less, and doesn't appear to leak as much.
Agreed.
Kaz> The reason Boehm is widely used is because it's one of the
Kaz> few choices available to C programmers. It's not chosen
Kaz> because it's conservative, but in spite of that limitation,
Kaz> which can be rationalized away.
I will argument it differently. The main advantage of *conservative*
GC for *plain C* programmers is that such a GC does not hurt their
coding habits. Basically, it permit to just replace malloc and forget
about free. This is why conservative GC is prefered by C coders.
Precise GC can be written for C (there are several such GC -like in
Ocaml or Xemacs-, usually in implementations of other languages, which
can be used by C code carefully embedded and coded for the
application). But by definition any precise GC requires full knowledge
about all pointers. This is not achievable in plain C (without
programmer cooperation). So any precise GC for C *requires* some
strict coding guidelines and style - which means hurting plain C coder
habits. Automatic detection of all pointers is intractable in the
general case (pointer arithmetic or encryption) and not very used for
C.
<shameless_plug>
Among some of the precise garbage collectors for C, there is qish
(written by me) - see http://starynkevitch.net/Basile/qishintro.html
and download it there (or from http://freshmeat.net/projects/qish
where you can subscribe to new announcements). The documentation is
poorly written (but all useful information is inside), but the
software is there (opensource, under LGPL license). Qish contains a
precise generational copying GC (with fixed finalized objects) which
should be usable in various C applications (provided you follow some
very strict coding guidelines). I think Qish is usable in
applications where a precise GC is needed before start of
coding. (replacing a conservative GC in an existing program by a
precise one like Qish is a significant task, since the coding style
should be followed everywhere).
</shameless_plug>
I also think (like many others) that having a GC change the
programming style you have. And the need of a precise GC is rarely
explicited at design phase.
regards
--
Basile STARYNKEVITCH http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net
alias: basile<at>tunes<dot>org
8, rue de la Fa�encerie, 92340 Bourg La Reine, France
On 09 Jan 2003 21:30:45 +0100, Basile STARYNKEVITCH
<·········@SPAM+starynkevitch.net.invalid> wrote:
>Precise GC can be written for C (there are several such GC -like in
>Ocaml or Xemacs-, usually in implementations of other languages, which
>can be used by C code carefully embedded and coded for the
>application). But by definition any precise GC requires full knowledge
>about all pointers. This is not achievable in plain C (without
>programmer cooperation). So any precise GC for C *requires* some
>strict coding guidelines and style - which means hurting plain C coder
>habits. Automatic detection of all pointers is intractable in the
>general case (pointer arithmetic or encryption) and not very used for
It seems like you are saying you can implement a garbage collector in C for a
language that is implemented in C, which is quite a bit different than
implementing a garbage collector *for* C such as Boehm.
In my experience, only a conservative collector will work for C, generally,
unless you also can control the code generation. Using a disciplined coding
style may work for a particular compiler, with optimizations off. However,
different compilers, or changes to the compiler, can easily mess it up. The
compiler generates pointers that the garbage collector does not know about and
which can trip up the collector.
>Among some of the precise garbage collectors for C, there is qish
>(written by me) - see http://starynkevitch.net/Basile/qishintro.html
>and download it there (or from http://freshmeat.net/projects/qish
>where you can subscribe to new announcements). The documentation is
>poorly written (but all useful information is inside), but the
>software is there (opensource, under LGPL license). Qish contains a
>precise generational copying GC (with fixed finalized objects) which
>should be usable in various C applications (provided you follow some
>very strict coding guidelines). I think Qish is usable in
>applications where a precise GC is needed before start of
>coding. (replacing a conservative GC in an existing program by a
>precise one like Qish is a significant task, since the coding style
>should be followed everywhere).
So I am interested in how you can workaround code generation issues. Are you
able to prevent the code generator from ever interfering with your collector? I
see from you web site that things such as interior pointers (pointers into heap
blocks) are disallowed. However, I have found some C and C++ compilers generate
these without me asking for them. For example, you say you can't use multiple
inheritance. This is just an example of something the code generator is doing
because it can (by the language definition). There would probably be other
things it thinks it can do which are not so easily avoided by programming.
I think your collector looks very nice and I am sure will be useful in a variety
of situations. I have found a conservative collector works quite well, as an
alternative, and does not require any change to C/C++ semantics.
Roger Corman
Corman Technologies
www.cormanlisp.com
·····@corman.net (Roger Corman) writes:
> On 09 Jan 2003 21:30:45 +0100, Basile STARYNKEVITCH
> <·········@SPAM+starynkevitch.net.invalid> wrote:
>
> >Precise GC can be written for C (there are several such GC -like in
> >Ocaml or Xemacs-, usually in implementations of other languages, which
> >can be used by C code carefully embedded and coded for the
> >application). But by definition any precise GC requires full knowledge
> >about all pointers. This is not achievable in plain C (without
> >programmer cooperation). So any precise GC for C *requires* some
> >strict coding guidelines and style - which means hurting plain C coder
> >habits. Automatic detection of all pointers is intractable in the
> >general case (pointer arithmetic or encryption) and not very used for
>
> It seems like you are saying you can implement a garbage collector in C for a
> language that is implemented in C, which is quite a bit different than
> implementing a garbage collector *for* C such as Boehm.
It's pretty easy to write C code that doesn't work with Boehm. For
instance, if you store data in pointers, you can lose. So I disagree
that Boehm is a solution for C in general. You must adhere to style
restrictions to use it safely.
For example, I used to work on a C program that took advantage of the
fact that the rightmost two bits in a pointer are zero. The program
would store some data in these two bits, and mask it off to
dereference the pointer. This will cause problems for the Boehm gc.
-russ
Hello!
Russell McManus <···············@yahoo.com> wrote:
>[...]
>For example, I used to work on a C program that took advantage of the
>fact that the rightmost two bits in a pointer are zero. The program
>would store some data in these two bits, and mask it off to
>dereference the pointer. This will cause problems for the Boehm gc.
IIRC there's a mode of Boehm's GC that also recognizes interior
pointers (i.e. for an allocated block of size n at address a, any
value from a up to and including a+n) as references to a block.
This should also cover your example.
You could of course mask off pointers by doing things like
((foo *) ((unsigned long) some_pointer ^ 0x12345678ul)) and
unmasking them before dereference. But this looks sick.
Kind regards,
Hannah.
In article <··············@thelonious.dyndns.org>,
Russell McManus <···············@yahoo.com> wrote:
> It's pretty easy to write C code that doesn't work with Boehm. For
> instance, if you store data in pointers, you can lose. So I disagree
> that Boehm is a solution for C in general. You must adhere to style
> restrictions to use it safely.
>
> For example, I used to work on a C program that took advantage of the
> fact that the rightmost two bits in a pointer are zero. The program
> would store some data in these two bits, and mask it off to
> dereference the pointer. This will cause problems for the Boehm gc.
I think you will find that is not a valid C program, according to the
ANSI standard. Of course it will work most places, but that's just luck
(or nonportable platform-specific knowledge).
-- Bruce
In article <···························@copper.ipg.tsnz.net>,
Bruce Hoult <·····@hoult.org> wrote:
>In article <··············@thelonious.dyndns.org>,
> Russell McManus <···············@yahoo.com> wrote:
>
>> It's pretty easy to write C code that doesn't work with Boehm. For
>> instance, if you store data in pointers, you can lose. So I disagree
>> that Boehm is a solution for C in general. You must adhere to style
>> restrictions to use it safely.
>>
>> For example, I used to work on a C program that took advantage of the
>> fact that the rightmost two bits in a pointer are zero. The program
>> would store some data in these two bits, and mask it off to
>> dereference the pointer. This will cause problems for the Boehm gc.
>
>I think you will find that is not a valid C program, according to the
>ANSI standard. Of course it will work most places, but that's just luck
>(or nonportable platform-specific knowledge).
Of course "the fact that the rightmost two bits in a pointer are zero" is
platform-specific knowledge. Just about anyone who fiddles with the bits
of a pointer knows it's not portable.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin <······@genuity.net> writes:
> Of course "the fact that the rightmost two bits in a pointer are
> zero" is platform-specific knowledge.
nowadays, is there anything except for Cray and MS-DOS where this
isn't true?
--
Perhaps it IS a good day to die; I say we ship it!
-- Klingon Programmer
Michael Livshin <······@cmm.kakpryg.net> writes:
> Barry Margolin <······@genuity.net> writes:
>
> > Of course "the fact that the rightmost two bits in a pointer are
> > zero" is platform-specific knowledge.
>
> nowadays, is there anything except for Cray and MS-DOS where this
> isn't true?
x86 in general is byte-addressable, isn't it?
Gabe Garza
In article <··············@ix.netcom.com>,
Gabe Garza <·······@ix.netcom.com> wrote:
> Michael Livshin <······@cmm.kakpryg.net> writes:
>
> > Barry Margolin <······@genuity.net> writes:
> >
> > > Of course "the fact that the rightmost two bits in a pointer are
> > > zero" is platform-specific knowledge.
> >
> > nowadays, is there anything except for Cray and MS-DOS where this
> > isn't true?
>
> x86 in general is byte-addressable, isn't it?
Yes, and so is PowerPC.
Some particular implementation of malloc() might [1] return objects that
are always aligned to 4 byte boundaries (or bigger), but they don't have
to.
-- Bruce
[1] ok, all the ones I've seen recently.
Bruce Hoult <·····@hoult.org> writes:
> In article <··············@ix.netcom.com>,
> Gabe Garza <·······@ix.netcom.com> wrote:
>
>> Michael Livshin <······@cmm.kakpryg.net> writes:
>>
>> > Barry Margolin <······@genuity.net> writes:
>> >
>> > > Of course "the fact that the rightmost two bits in a pointer are
>> > > zero" is platform-specific knowledge.
>> >
>> > nowadays, is there anything except for Cray and MS-DOS where this
>> > isn't true?
>>
>> x86 in general is byte-addressable, isn't it?
>
> Yes, and so is PowerPC.
you mean you can always take an unaligned address and access the value
that sits there transparently by dereferincing a pointer to intptr_t?
I didn't know that...
and nobody in their right mind would assume availability of the 2
rightmost bits of a _char_ pointer, would they?
> Some particular implementation of malloc() might [1] return objects that
> are always aligned to 4 byte boundaries (or bigger), but they don't have
> to.
>
> [1] ok, all the ones I've seen recently.
same here.
--
The only thing better than TV with the sound off is Radio with the sound
off.
-- Dave Moon
Michael Livshin <······@cmm.kakpryg.net> writes:
> you mean you can always take an unaligned address and access the value
> that sits there transparently by dereferincing a pointer to intptr_t?
>
> I didn't know that...
>
> and nobody in their right mind would assume availability of the 2
> rightmost bits of a _char_ pointer, would they?
>
They used tio say: "All the world's a vax!"
#:Andreas
--
Wherever I lay my .emacs, there�s my $HOME.
In article <··············@laredo.verisity.com.cmm>,
Michael Livshin <······@cmm.kakpryg.net> wrote:
> Bruce Hoult <·····@hoult.org> writes:
>
> > In article <··············@ix.netcom.com>,
> > Gabe Garza <·······@ix.netcom.com> wrote:
> >
> >> Michael Livshin <······@cmm.kakpryg.net> writes:
> >>
> >> > Barry Margolin <······@genuity.net> writes:
> >> >
> >> > > Of course "the fact that the rightmost two bits in a pointer are
> >> > > zero" is platform-specific knowledge.
> >> >
> >> > nowadays, is there anything except for Cray and MS-DOS where this
> >> > isn't true?
> >>
> >> x86 in general is byte-addressable, isn't it?
> >
> > Yes, and so is PowerPC.
>
> you mean you can always take an unaligned address and access the value
> that sits there transparently by dereferincing a pointer to intptr_t?
>
> I didn't know that...
Yes.
On PowerPC you can access anything at any old unaligned address. If the
object falls entirely within a cache block (generally 32 bytes) then
there is no penalty. If it crosses a cache block boundary there is
something like a 1-cycle penalty, If it crosses a 4 Kbyte page boundary
then there is a slightly bigger penalty (but it's fixed up in hardware
on the chips I've looked at). If it crosses a 256 Mbyte segment
boundary then there is a trap to the OS, which can fix it up in software.
Apple insisted on this in PowerPC because they needed to run old 68k
software, whether recompiled (with the binary-compatable alignment) or
emulated.
-- Bruce
Bruce Hoult wrote:
> On PowerPC you can access anything at any old unaligned address.
Which I find annoying, since being able to trap on unaligned
accesses is really useful for implementing Lisp -- car and cdr
stay safe even at high optimization/low safety.
Paul
"Paul F. Dietz" <·····@dls.net> writes:
> Bruce Hoult wrote:
>
>> On PowerPC you can access anything at any old unaligned address.
>
> Which I find annoying, since being able to trap on unaligned
> accesses is really useful for implementing Lisp -- car and cdr
> stay safe even at high optimization/low safety.
trapping on unaligned access is useful for many more things. I've
come to *really* appreciate this feature recently while porting some
"legacy" code to 64 bits.
it's pretty scary how slippery is the path of relying on
machine/OS-level checking, come to think about it. and how similar it
is to the way police states are born and then sustain and strengthen
themselves. now that's getting _really_ offtopic, though.
--
Being really good at C++ is like being really good at using rocks to
sharpen sticks.
-- Thant Tessman
Bruce Hoult <·····@hoult.org> writes:
>> x86 in general is byte-addressable, isn't it?
>
> Yes, and so is PowerPC.
>
> Some particular implementation of malloc() might [1] return objects that
> are always aligned to 4 byte boundaries (or bigger), but they don't have
> to.
For calloc() and malloc(), the value returned is a pointer to the allo-
cated memory, which is suitably aligned for any kind of variable, or
NULL if the request fails.
(Taken from a Linux man page). If this requirement isn't in ANSI C, I
will be very surprised.
It doesn't invalidate your general point, of course, - even if
malloc() returns 32-bit-aligned pointers, that doesn't stop you from
using e.g. pointer arithmetic to create valid pointers that aren't.
-dan
--
http://www.cliki.net/ - Link farm for free CL-on-Unix resources
Daniel Barlow <···@telent.net> writes:
>
> For calloc() and malloc(), the value returned is a pointer to the allo-
> cated memory, which is suitably aligned for any kind of variable, or
> NULL if the request fails.
>
> (Taken from a Linux man page). If this requirement isn't in ANSI C, I
> will be very surprised.
It is, but some processors or ABIs don't have alignment requirements
so the suitably aligned could be vacuously true. In some cases the
alignment requirement is a speed issue and either the processor or the
run time environment makes unaligned access work. This mode could be
selected if you asked for optimising size above speed.
--
People don't bore me. I like people. - Really? All of them? - All of them. -
Even the creepy ones? - Nobody's creepy from the inside, Hazel. Some of them
are sad, and some of them hurt, and some of them think they're the only real
thing in the whole world. But they're not creepy. -- Hazel and Death
In article <··············@noetbook.telent.net>,
Daniel Barlow <···@telent.net> wrote:
> Bruce Hoult <·····@hoult.org> writes:
>
> >> x86 in general is byte-addressable, isn't it?
> >
> > Yes, and so is PowerPC.
> >
> > Some particular implementation of malloc() might [1] return objects that
> > are always aligned to 4 byte boundaries (or bigger), but they don't have
> > to.
>
> For calloc() and malloc(), the value returned is a pointer to the allo-
> cated memory, which is suitably aligned for any kind of variable, or
> NULL if the request fails.
>
> (Taken from a Linux man page). If this requirement isn't in ANSI C, I
> will be very surprised.
But what does "suitably aligned" mean? On x86 and PowerPC suitably
aligned can mean "totally unaligned" as the penalty for doing so is
quite small. On SPARC and MIPS and so forth you get a bus error if you
try to access a 2 or 4 or 8 byte value at, say, an odd address, but x86
and PowerPC don't do that.
-- Bruce
Bruce Hoult <·····@hoult.org> writes:
> In article <··············@thelonious.dyndns.org>,
> Russell McManus <···············@yahoo.com> wrote:
>
> > It's pretty easy to write C code that doesn't work with Boehm. For
> > instance, if you store data in pointers, you can lose. So I disagree
> > that Boehm is a solution for C in general. You must adhere to style
> > restrictions to use it safely.
> >
> > For example, I used to work on a C program that took advantage of the
> > fact that the rightmost two bits in a pointer are zero. The program
> > would store some data in these two bits, and mask it off to
> > dereference the pointer. This will cause problems for the Boehm gc.
>
> I think you will find that is not a valid C program, according to the
> ANSI standard. Of course it will work most places, but that's just luck
> (or nonportable platform-specific knowledge).
True. But all the C programmers I have worked with over ten years
don't restrict themselves to only what's ANSI. Sticking to pure ANSI
C is a considerable style restriction to the average C programmer in
my book.
But of course others may have different experience.
-russ
"Russell McManus" <···············@yahoo.com> wrote in message ···················@thelonious.dyndns.org...
>
> True. But all the C programmers I have worked with over ten years
> don't restrict themselves to only what's ANSI. Sticking to pure ANSI
> C is a considerable style restriction to the average C programmer in
> my book.
>
> But of course others may have different experience.
>
I try to make at least the main part of the code I write to be ANSI
conforming and package the non-conforming stuff into platform specific
libraries with identical interfaces. The old space saving tricks went
out of my toolbox the second memory limits went over 64K. They become
a maintenance nightmares very quickly, they complicate what should be
simple algorithms, and they are easy to forget when writing a section
of code that doesn't require the trick but has to support it.
One project I worked on wasted at least two man weeks tracking down
errors caused by a programmer inserting a non-standard dummy record at
the start of a data file to save himself some additional coding in one
routine. Everytime the product had capabilities added to it, code had
to be inserted to skip that record, compounded with the fact that the
algorithms were shared with products that didn't have the 'cute' trick,
team members just HAD to pay attention to which program they were adding
the new code to. Heh heh, I bet you can guess how well that worked.
The time required to eliminate the problem went up with each new addition
made a fix less and less attractive before doing the scheduled rewrite
for the next major version. It was, in fact, never done until the complete
rewrite.
--
Geoff
In article <··············@thelonious.dyndns.org>,
Russell McManus <···············@yahoo.com> writes:
> ...
> True. But all the C programmers I have worked with over ten years
> don't restrict themselves to only what's ANSI. Sticking to pure ANSI
> C is a considerable style restriction to the average C programmer in
> my book.
if they do that, they make sure that their code runs only in a
specific environment and is not portable to other environments. it's
probably ok if the assumption that the code won't be needed is made
explicit and correct.
> But of course others may have different experience.
i have seen lots of code like that several times. the first time when
C started to make inroads outside the unix/pdp11 environment (when all
code was compiled with the ritchie compiler), the second time when
dos/win<3.x programmers had to get used to 32 bit environments.
fortunately, some programmers seem to have learned their lessons, so
lately it seems not quite so common
hs
--
men are born ignorant, not stupid; they are made stupid by education
Bertrand Russel
From: Tim Bradshaw
Subject: Re: Conservative vs. precise GC
Date:
Message-ID: <ey3znq54wti.fsf@cley.com>
* Russell McManus wrote:
> True. But all the C programmers I have worked with over ten years
> don't restrict themselves to only what's ANSI. Sticking to pure ANSI
> C is a considerable style restriction to the average C programmer in
> my book.
It's kind of amusing that one of the features of the famous `all the
world's a VAX' syndrome was precisely the assumption that a data type
of any size could begin at any byte address in memory, and the machine
was byte addressed. But now that is so long ago (a whole, what, 12
years?) that people happily assume its opposite (is the opposite even
*true* on x86, or is it compiler-dependent?).
--tim
Tim Bradshaw <···@cley.com> writes:
> * Russell McManus wrote:
>
> > True. But all the C programmers I have worked with over ten years
> > don't restrict themselves to only what's ANSI. Sticking to pure ANSI
> > C is a considerable style restriction to the average C programmer in
> > my book.
>
> It's kind of amusing that one of the features of the famous `all the
> world's a VAX' syndrome was precisely the assumption that a data type
> of any size could begin at any byte address in memory, and the machine
> was byte addressed. But now that is so long ago (a whole, what, 12
> years?) that people happily assume its opposite (is the opposite even
> *true* on x86, or is it compiler-dependent?).
Generally its architecture-dependent. MIPS and PowerPC both want 32
bit aligned memory references (at least in 32 bit mode), only handling
byte-wise access by runtime bit shifting judo supplied by the C
compiler. Up until the 286 or even 386, x86 processors could directly
operate on odd addresses, though somewhat slower than they could on
even addresses. I've not crawled through modern x86 C code recently,
so can't comment on how it tends to be done nowadays.
In the same vein, struct field alignment to take advantage (or at
least to avoid disadvantage) of such architectural quirks has been
common for quite a while.
Gregm
Greg Menke <··········@toadmail.com> writes:
> Tim Bradshaw <···@cley.com> writes:
>
> > * Russell McManus wrote:
> >
> > > True. But all the C programmers I have worked with over ten years
> > > don't restrict themselves to only what's ANSI. Sticking to pure ANSI
> > > C is a considerable style restriction to the average C programmer in
> > > my book.
> >
> > It's kind of amusing that one of the features of the famous `all the
> > world's a VAX' syndrome was precisely the assumption that a data type
> > of any size could begin at any byte address in memory, and the machine
> > was byte addressed. But now that is so long ago (a whole, what, 12
> > years?) that people happily assume its opposite (is the opposite even
> > *true* on x86, or is it compiler-dependent?).
>
> Generally its architecture-dependent. MIPS and PowerPC both want 32
> bit aligned memory references (at least in 32 bit mode), only handling
> byte-wise access by runtime bit shifting judo supplied by the C
> compiler. Up until the 286 or even 386, x86 processors could directly
> operate on odd addresses, though somewhat slower than they could on
> even addresses. I've not crawled through modern x86 C code recently,
> so can't comment on how it tends to be done nowadays.
>
> In the same vein, struct field alignment to take advantage (or at
> least to avoid disadvantage) of such architectural quirks has been
> common for quite a while.
>
> Gregm
In anycase, whether the byte reordering is done by the hardware or by
the software, accessing a value crossing boundary of memory words
takes more time (and more silicium, either specific or using general
register). That's why it's more efficient to align data structures to
avoid such accesses. We have already so slow memories, (needed two
level of caches before getting to the registers!)...
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
There is a fault in reality. Do not adjust your minds. -- Salman Rushdie
Greg Menke <··········@toadmail.com> writes:
> Up until the 286 or even 386, x86 processors could directly
> operate on odd addresses, though somewhat slower than they could on
> even addresses.
They can still do that; Intel tries to keep the chips compatible.
There are now some flags for making misaligned accesses cause
exceptions instead, but toggling a flag on each library call may
be cumbersome.
Tim Bradshaw <···@cley.com> writes:
> * Russell McManus wrote:
>
> > True. But all the C programmers I have worked with over ten years
> > don't restrict themselves to only what's ANSI. Sticking to pure ANSI
> > C is a considerable style restriction to the average C programmer in
> > my book.
>
> It's kind of amusing that one of the features of the famous `all the
> world's a VAX' syndrome was precisely the assumption that a data type
> of any size could begin at any byte address in memory, and the machine
> was byte addressed. But now that is so long ago (a whole, what, 12
> years?) that people happily assume its opposite (is the opposite even
> *true* on x86, or is it compiler-dependent?).
From my memories of doing assembler coding on x86 (though this is
quite a way back, so it may be coloured by time), you can indeed load
a 16-bit value from memory from an odd address and I would be
surprised if you can't do the same with a 32-bit value (or possibly
even a 64-bit value).
A quick bit of testing gives (nasty icky C follows):
#include <stdio.h>
#define doprint(TYPE, FORMAT) printf(#TYPE " " FORMAT "\tsize %d\n", * (TYPE *) cp, sizeof(TYPE))
int main (void)
{
char payload[16];
int n;
char *cp;
for (n=0; n<16; n++) payload[n] = n;
cp = payload;
doprint(char, "%hhd");
doprint(short, "%hd");
doprint(int, "%d");
doprint(long, "%ld");
doprint(long long, "%lld");
printf("Bumping cp one step\n");
cp++;
doprint(char, "%hhd");
doprint(short, "%hd");
doprint(int, "%d");
doprint(long, "%ld");
doprint(long long, "%lld");
}
char 0 size 1
short 256 size 2
int 50462976 size 4
long 50462976 size 4
long long 506097522914230528 size 8
Bumping cp one step
char 1 size 1
short 513 size 2
int 67305985 size 4
long 67305985 size 4
long long 578437695752307201 size 8
If anyone is interested, I can also paste the assembler output, but
from what I can see, the "before cp++" and "after cp++" looks
identical. So, on a Pentium III (running Debian) it seems to work.
//Ingvar
--
When the SysAdmin answers the phone politely, say "sorry", hang up and
run awaaaaay!
Informal advice to users at Karolinska Institutet, 1993-1994
>>>>> "Roger" == Roger Corman <·····@corman.net> writes:
Roger> On 09 Jan 2003 21:30:45 +0100, Basile STARYNKEVITCH
Roger> <·········@SPAM+starynkevitch.net.invalid> wrote:
Citing me (Basile)
Basile>> Precise GC can be written for C (there are several such GC
Basile>> -like in Ocaml or Xemacs-, usually in implementations of other
Basile>> languages, which can be used by C code carefully embedded and
Basile>> coded for the application). But by definition any precise GC
Basile>> requires full knowledge about all pointers. This is not
Basile>> achievable in plain C (without programmer cooperation). So any
Basile>> precise GC for C *requires* some strict coding guidelines and
Basile>> style - which means hurting plain C coder habits. Automatic
Basile>> detection of all pointers is intractable in the general case
Basile>> (pointer arithmetic or encryption) and not very used for
Roger> It seems like you are saying you can implement a garbage
Roger> collector in C for a language that is implemented in C,
Roger> which is quite a bit different than implementing a garbage
Roger> collector *for* C such as Boehm.
Well, I sort of agree, but (even leaving my Qish aside) both Ocaml &
Xemacs garbage collector and runtime systems are *designed* to be able
to extend Ocaml or Xemacs with any routine coded in C, provided it
does follow some coding guidelines. So in a contrieved sense, they can
also be viewed as providing GC for some particular style of C
programming.
Roger> In my experience, only a conservative collector will work
Roger> for C, generally, unless you also can control the code
Roger> generation. Using a disciplined coding style may work for a
Roger> particular compiler, with optimizations off. However,
Roger> different compilers, or changes to the compiler, can easily
Roger> mess it up. The compiler generates pointers that the
Roger> garbage collector does not know about and which can trip up
Roger> the collector.
Yes, there is an old Boehm's? paper on this issue.
Basile>> Among some of the precise garbage collectors for C, there is
Basile>> qish (written by me) - see
Basile>> http://starynkevitch.net/Basile/qishintro.html and download it
Basile>> there (or from http://freshmeat.net/projects/qish where you can
Basile>> subscribe to new announcements). The documentation is poorly
Basile>> written (but all useful information is inside), but the
Basile>> software is there (opensource, under LGPL license). Qish
Basile>> contains a precise generational copying GC (with fixed
Basile>> finalized objects) which should be usable in various C
Basile>> applications (provided you follow some very strict coding
Basile>> guidelines). I think Qish is usable in applications where a
Basile>> precise GC is needed before start of coding. (replacing a
Basile>> conservative GC in an existing program by a precise one like
Basile>> Qish is a significant task, since the coding style should be
Basile>> followed everywhere).
Roger> So I am interested in how you can workaround code
Roger> generation issues. Are you able to prevent the code
Roger> generator from ever interfering with your collector? I see
Roger> from you web site that things such as interior pointers
Roger> (pointers into heap blocks) are disallowed. However, I have
Roger> found some C and C++ compilers generate these without me
Roger> asking for them. For example, you say you can't use
Roger> multiple inheritance. This is just an example of something
Roger> the code generator is doing because it can (by the language
Roger> definition). There would probably be other things it thinks
Roger> it can do which are not so easily avoided by programming.
I agree, but in Qish, you have to use (at specific places) in your
code some volatile pointers. I carefully read the C spec a year ago on
volatile keyword, and it is my understanding that using it make the
compiler aware that it cannot use above tricks.
Also, (both in Qish and in Ocaml runtime) garbage collection can only
occur at specific safe places (for instance, GC cannot occur in signal
handlers) and a C compiler cannot optimize as you suggest.
Roger> I think your collector looks very nice and I am sure will
Roger> be useful in a variety of situations. I have found a
Roger> conservative collector works quite well, as an alternative,
Roger> and does not require any change to C/C++ semantics.
I'm not sure Qish require changes to C semantics. It does require
careful use of volatile pointers. Which in my understanding not a
change in C semantics.
I do agree that the semantic of volatile is ill defined in C. In
practice, several common compilers seems to understand it in a nearly
common way.
For example, I believe that Xemacs (and also Ocaml) is compiled on
many different compilers and still works!
Regards.
--
Basile STARYNKEVITCH http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net
alias: basile<at>tunes<dot>org
8, rue de la Fa�encerie, 92340 Bourg La Reine, France
From: Nils Goesche
Subject: Re: Conservative vs. precise GC
Date:
Message-ID: <lyfzs1jc5m.fsf@cartan.de>
Basile STARYNKEVITCH <·········@SPAM+starynkevitch.net.invalid> writes:
> >>>>> "Roger" == Roger Corman <·····@corman.net> writes:
>
> Roger> It seems like you are saying you can implement a garbage
> Roger> collector in C for a language that is implemented in C,
> Roger> which is quite a bit different than implementing a
> Roger> garbage collector *for* C such as Boehm.
>
> Well, I sort of agree, but (even leaving my Qish aside) both Ocaml &
> Xemacs garbage collector and runtime systems are *designed* to be
> able to extend Ocaml or Xemacs with any routine coded in C, provided
> it does follow some coding guidelines. So in a contrieved sense,
> they can also be viewed as providing GC for some particular style of
> C programming.
Do you mean OCaml's FFI? Where you have to call something like
`register_global_root� to make C cooperate with the garbage collector?
I don't know, but somehow I don't think it is right calling that
``providing GC for ... C programming��. This is something you'd never
do in normal C programming; to me, it looks more like writing OCaml
code in Assembly, if you know what I mean ... as if you write C code
knowing that it will compile to the same machine code as the OCaml
code you'd normally write instead or some such (metaphorically
speaking).
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
>>>>> "Nils" == Nils Goesche <······@cartan.de> writes:
Nils> Basile STARYNKEVITCH
Nils> <·········@SPAM+starynkevitch.net.invalid> writes:
>> >>>>> "Roger" == Roger Corman <·····@corman.net> writes:
>>
Roger> It seems like you are saying you can implement a garbage
Roger> collector in C for a language that is implemented in C,
Roger> which is quite a bit different than implementing a garbage
Roger> collector *for* C such as Boehm.
Basile>> Well, I sort of agree, but (even leaving my Qish aside) both
Basile>> Ocaml & Xemacs garbage collector and runtime systems are
Basile>> *designed* to be able to extend Ocaml or Xemacs with any
Basile>> routine coded in C, provided it does follow some coding
Basile>> guidelines. So in a contrieved sense, they can also be viewed
Basile>> as providing GC for some particular style of C programming.
Nils> Do you mean OCaml's FFI? Where you have to call something
Nils> like `register_global_root' to make C cooperate with the
Nils> garbage collector?
Yes, I mean Ocaml's foreign function interface. But you seldom need to
call `register_global_root' (because global pointer values are not
that useful!) and most of the time passing all pointers as arguments
and calling the macros like CAMLparam2 ... is enough.
Nils> I don't know, but somehow I don't think it is right calling
Nils> that ``providing GC for ... C programming''. This is
Nils> something you'd never do in normal C programming;
Agreed, that is why I wrote "in a contrieved sense". But it does
happen that some people do write code of significant size in C using
Ocaml's GC, so that is why I wrote that it sometimes "provides GC".
Of course, people are writing such C code because they want to
integrate it into (i.e. call from) Ocaml code.
I think that the good practice (either when coding for Ocaml bytecode
machine or when coding for Xemacs) is to first code in the high level
(ie Ocaml or Xemacs elisp) language and then to optimize by recoding
in C.
Of course, when you can afford coding only in Ocaml it is much better.
--
Basile STARYNKEVITCH http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net
alias: basile<at>tunes<dot>org
8, rue de la Fa�encerie, 92340 Bourg La Reine, France
Basile STARYNKEVITCH <·········@SPAM+starynkevitch.net.invalid> wrote:
+---------------
| Among some of the precise garbage collectors for C, there is qish
| (written by me) - see http://starynkevitch.net/Basile/qishintro.html
| [which] contains a precise generational copying GC (with fixed
| finalized objects) which should be usable in various C applications
| (provided you follow some very strict coding guidelines).
+---------------
See <URL:http://www.informatik.uni-bremen.de/~net/elk> for the "Extension
Language Toolkit" a.k.a. "Elk", a dialect of Scheme. Elk was written in C,
and Elk-3.0 [1995] contains a precise garbage collector -- actually, *two*
of them (compile time option): a classic Cheney twin-arena copying collector,
and a generational/copying GC. From "doc/cprog/cprog.ms":
At the time Elk was designed [1987], conservative GC was still in
its infancy and sufficient experience did not exist. For this reason,
and because of the implied risks on certain machine architectures,
the inherent portability problems, and the inability to precisely
determine the actual memory utilization, a traditional [that is,
precise --rpw3] GC strategy was chosen for Elk.
Like Qish, Elk required considerable discipline on the part of the
programmer writing extensions in C, but did provide some handy macros
and utilities to make life easier. E.g., here's some code (loc. cit.)
for a sample vector NREVERSE, showing how to use the GC support calls:
Object p_vector_reverse(Object vec) {
Object ret;
int i, j;
GC_Node;
GC_Link(vec);
Check_Type(vec, T_Vector);
ret = Make_Vector(VECTOR(vec)->size, False);
for (i = 0, j = VECTOR(vec)->size; --j >= 0; i++)
VECTOR(ret)->data[i] = VECTOR(vec)->data[j];
GC_Unlink;
return ret;
}
If you *never* do any GC allocation in your routine [and never call
any subroutines which do] you don't need to do this, but if you do,
you need to declare a local "GC_Node". Then use "GC_Link(foo)" to flag
"foo" as naming a place that is (temporarily) added to the root set.
[There's also "GC_Node2/GC_Link2(x,y)", 3, 4, etc., if you need to
protect more than one variable per call.] Then be sure to call "GC_Unlink"
before returning. That's pretty much it. (Not *too* painful, eh?)
Each "Object" subtype needs to provide a handful of callbacks for the GC
so an object of that type can been scanned. This removes any restriction
on the exact format of objects (i.e., an object can freely intermix
GC'd sub-objects and raw bits), since it's the object-type callbacks
that actually scan that type, not the core GC.
I've written code in other environments using the Elk model (with a
dirt-simple copying collector written from scratch), and it's really
not too painful if, as Basile notes, the decision to use a precise
collector is made up front. Conversely, retrofitting code using a
conservative collector [such as Boehm's] to be "safe" with a precise
collector is fraught with danger, mainly due to simple clerical
errors -- overlooking a data/control flow path somewhere that needed
a "GC protect" in it.
-Rob
p.s. For the terminally curious, this code:
Object p_vector_reverse(Object x, Object y, Object z) {
Object ret;
GC_Node3;
GC_Link3(x, y, z);
...something that does allocation...
ret = ...some result... ;
GC_Unlink;
return ret;
}
expands into this [approximately, the actual code was slightly worse!]:
Object p_vector_reverse(Object x, Object y, Object z) {
Object ret;
Object *node[5];
extern Object *GC_List;
node[1] = 3; /* #pointers in this node */
node[2] = &x;
node[3] = &y;
node[4] = &z;
node[0] = GC_List; /* save existing roots */
GC_List = &node; /* add node to root set */
...something that does allocation...
ret = ...some result... ;
GC_List = node[0]; /* remove from root set */
return ret;
}
-----
Rob Warnock, PP-ASEL-IA <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Nils Goesche
Subject: Re: Conservative vs. precise GC
Date:
Message-ID: <ly4r8il4hi.fsf@cartan.de>
Edi Weitz <···@agharta.de> writes:
> I've read the GC FAQ but that's basically all I know about garbage
> collection.
I am not an expert either, but I think you will find useful
information in chapter 8 of LispWorks' ``User Guide��, which should
answer all of your questions (if I understood them correctly).
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
Edi Weitz <···@agharta.de> writes:
> I've read the GC FAQ but that's basically all I know about garbage
> collection.
Consider looking as well at
http://www.franz.com/support/documentation/6.2/doc/gc.htm
> What I noticed is that some CL implementations on some
> platforms have conservative GC while others have precise GC.
Hopefully, most CL's implement precise GCs, rather than conservative
GCs. Lisp objects tend to be tagged, and so the only reason I can think
of offhand for not using precise GC is on non-lisp data.
Perhaps any CL implementations you are noticing which use conservative
GC are the ones which compile down to C?
Or, perhaps there is some confusion about whether a generational GC
system is precise or conservative? (My own opinion is that if a
generational GC has a full-gc capability, all objects are still
managed and this will eventually be collected if/when dead, and thus
it is a precise GC. However, I've never seen this defined before,
and in fact have only ever seen conservative-GC mentioned in non-CL
contexts - I'd be interested in any links to the contrary).
> I
> understand that conservative GC may keep objects alive (infinitely?)
> that are otherwise garbage. My questions are:
[ ... ]
I'll leave these questions alone; I admit strong bias against any
GC algorithm which doesn't take full advantage of the data-typing
made available by the language for which it is implemented. I.e.,
in CL, there are no excuses to use conservative GC.
[Note that I don't have the same view of conservative GC for C
and similar languages; it is effectively the only possibility,
unless you want to invoke Greenspun and reinvent tagged pointers _and_
lock out all other normal C programming in such a C program... ]
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Duane Rettig wrote:
> Hopefully, most CL's implement precise GCs, rather than conservative
> GCs. Lisp objects tend to be tagged, and so the only reason I can think
> of offhand for not using precise GC is on non-lisp data.
I am curious - what do you think about the possibility that tag
inspection might incur some overhead that is perhaps not justified?
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Pascal Costanza <········@web.de> writes:
> Duane Rettig wrote:
>
> > Hopefully, most CL's implement precise GCs, rather than conservative
> > GCs. Lisp objects tend to be tagged, and so the only reason I can think
> > of offhand for not using precise GC is on non-lisp data.
>
> I am curious - what do you think about the possibility that tag
> inspection might incur some overhead that is perhaps not justified?
It is not a question of tagging incurring overhead. It is a question of
tagging allowing guarantees to the GC about what it can expect in any
particular slot it is examining. If such guarantees can be made, then
they should be made, and the GC can proceed with confidence that what
it is looking at really is a valid object, and not just random bits.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
In article <············@f1node01.rhrz.uni-bonn.de>,
Pascal Costanza <········@web.de> wrote:
>Duane Rettig wrote:
>
>> Hopefully, most CL's implement precise GCs, rather than conservative
>> GCs. Lisp objects tend to be tagged, and so the only reason I can think
>> of offhand for not using precise GC is on non-lisp data.
>
>I am curious - what do you think about the possibility that tag
>inspection might incur some overhead that is perhaps not justified?
That overhead is most likely outweighed by the fact that it doesn't waste
any time scanning memory that isn't part of any objects at all.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Duane Rettig <·····@franz.com> writes:
> Edi Weitz <···@agharta.de> writes:
>
> > I've read the GC FAQ but that's basically all I know about garbage
> > collection.
>
> Consider looking as well at
>
> http://www.franz.com/support/documentation/6.2/doc/gc.htm
>
> > What I noticed is that some CL implementations on some
> > platforms have conservative GC while others have precise GC.
>
> Hopefully, most CL's implement precise GCs, rather than conservative
> GCs. Lisp objects tend to be tagged, and so the only reason I can think
> of offhand for not using precise GC is on non-lisp data.
>
> Perhaps any CL implementations you are noticing which use conservative
> GC are the ones which compile down to C?
ECL uses Boehm-Weiser AFAIK and compiles down to C, but that's
definitely not true for CMUCL and SCL (see below).
> Or, perhaps there is some confusion about whether a generational GC
> system is precise or conservative? (My own opinion is that if a
> generational GC has a full-gc capability, all objects are still
> managed and this will eventually be collected if/when dead, and thus
> it is a precise GC.
CMUCL on x86 uses "a generational conservative garbage collector":
<http://www.cons.org/cmucl/platforms.html>
I also recall that the GC function on CMUCL has a :FULL keyword
parameter. So, er, does that mean CMUCL/x86 might eventually leak
memory or not? I'm confused...
> However, I've never seen this defined before, and in fact have only
> ever seen conservative-GC mentioned in non-CL contexts - I'd be
> interested in any links to the contrary).
See CMUCL above. Also, SCL on x86 uses "a conservative garbage
collector". They specifically mention that "objects that might
otherwise be garbage may be kept alive":
<http://www.scieneer.com/scl/doc/x86-linux>
Edi.
From: Nils Goesche
Subject: Re: Conservative vs. precise GC
Date:
Message-ID: <lysmw2jj8d.fsf@cartan.de>
Edi Weitz <···@agharta.de> writes:
> CMUCL on x86 uses "a generational conservative garbage collector":
>
> <http://www.cons.org/cmucl/platforms.html>
>
> I also recall that the GC function on CMUCL has a :FULL keyword
> parameter. So, er, does that mean CMUCL/x86 might eventually leak
> memory or not? I'm confused...
If /this/ is your main problem, whether you might have a memory leak
or not, then it doesn't matter at all whether the GC is conservative
or not. The /generational/ garbage collectors can leak memory under
certain circumstances. If they do, you have to tweak them until they
don't (for your program). Chapter 8 of the LispWorks User Manual
describes in detail how to do that for LispWorks; you can do similar
things on other implementations. (Another thing you could do would be
to make a full GC once a day or some such).
The reason generational garbage collectors are used despite of this is
that they are fast -- simply because they don't have to look at all
generations all the time -- and some generations are not scanned by
default at all. If, for some strange reason, objects are regularly
promoted to generations that are not scanned by default, you have a
memory leak. In this case you should tweak the GC in such a way that
this doesn't happen anymore.
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
Nils Goesche <······@cartan.de> writes:
> Edi Weitz <···@agharta.de> writes:
>
> > CMUCL on x86 uses "a generational conservative garbage collector":
> >
> > <http://www.cons.org/cmucl/platforms.html>
> >
> > I also recall that the GC function on CMUCL has a :FULL keyword
> > parameter. So, er, does that mean CMUCL/x86 might eventually leak
> > memory or not? I'm confused...
>
> If /this/ is your main problem, whether you might have a memory leak
> or not, then it doesn't matter at all whether the GC is conservative
> or not. The /generational/ garbage collectors can leak memory under
> certain circumstances. If they do, you have to tweak them until they
> don't (for your program). Chapter 8 of the LispWorks User Manual
> describes in detail how to do that for LispWorks; you can do similar
> things on other implementations. (Another thing you could do would be
> to make a full GC once a day or some such).
My problem would be a memory leak that I can't prevent from happening
from within the Lisp program. Invoking, e.g., a full GC once per night
would be fine.
It looks to me that we're using two different notions of "memory leak"
in this thread: The first notion talks about memory that is not
reclaimed by the normal, automatic, default GC of your Lisp while the
second notion talks about memory that isn't reclaimed (i.e. _can't_ be
reclaimed) no matter how you tune your Lisp's GC.
I admit that the first form of memory leak might be unnerving but I
was more concerned about the second form - i.e. something I can't
fight against even if I'm aware of it. My understanding of what I've
read was that conservative GC can lead to the second form of memory
leaks. From your posting above (first sentence) it looks like my
understanding was wrong.
Thanks,
Edi.
Edi Weitz <···@agharta.de> writes:
> Nils Goesche <······@cartan.de> writes:
>
> > Edi Weitz <···@agharta.de> writes:
> >
> > > CMUCL on x86 uses "a generational conservative garbage collector":
> > >
> > > <http://www.cons.org/cmucl/platforms.html>
> > >
> > > I also recall that the GC function on CMUCL has a :FULL keyword
> > > parameter. So, er, does that mean CMUCL/x86 might eventually leak
> > > memory or not? I'm confused...
> >
> > If /this/ is your main problem, whether you might have a memory leak
> > or not, then it doesn't matter at all whether the GC is conservative
> > or not. The /generational/ garbage collectors can leak memory under
> > certain circumstances. If they do, you have to tweak them until they
> > don't (for your program). Chapter 8 of the LispWorks User Manual
> > describes in detail how to do that for LispWorks; you can do similar
> > things on other implementations. (Another thing you could do would be
> > to make a full GC once a day or some such).
>
> My problem would be a memory leak that I can't prevent from happening
> from within the Lisp program. Invoking, e.g., a full GC once per night
> would be fine.
>
> It looks to me that we're using two different notions of "memory leak"
> in this thread: The first notion talks about memory that is not
> reclaimed by the normal, automatic, default GC of your Lisp while the
> second notion talks about memory that isn't reclaimed (i.e. _can't_ be
> reclaimed) no matter how you tune your Lisp's GC.
Of various definitions of "memory leak" I've seen, most have at least
three components, including something similar to each of the following
three phrases:
"an error in the program"
"a failure to reclaim discarded memory"
"an eventual abnormal termination of the program"
Your first notion fits the second component and possibly the first
(depending on what the user's expectations were). It may not fit
the third component, depending upon whether the lisp either has an
automatic full-gc that occurs before giving up and dying, or else
it provides the capability, with a storage-condition, to manually
or programmatically cause the full gc.
Your second notion of "memory leak" certainly fits all three components.
Certainly, aside from the third component, the first notion could be
considered to be a "local memory leak" (to coin a phrase), since
a full gc might take too long to be acceptable for the application.
In reality, the second component has a hidden meaning (usually its
cause) that is "failure to discard memory" - If the memory is not
discarded, it cannot be reclaimed. In C, this translates to forgetting
to call free() on a memory object. In Lisp, it means continuing to
reference the object.
However, there is an assumption in the phrase "failure to discard
memory", and that is that in a correct program every memory object that
has been allocated will be discarded. This is in reality very seldom
the case. How often have you looked at a C program which does a lot
of mallocs, performs its task, and then simply calls exit()? Is it
an incorrect program? Of course not. I suppose that you could
consider exit() to be a poor-man's gc for malloc, but bear with me;
I'm taking this somewhere...
Now consider the technique of resource management; instead of program
code discarding a memory object, giving it back causes the object to
be saved for later use. This becomes a "failure to discard memory",
but it is not really a failure, because it is intentional.
As a practical example of why this matters, we had a period of time
when we were debugging memory leaks in CLIM, especially in malloc
space. At the time we were using our own pd implementation of
malloc, and we instrumented it to allow us to examine blocks that
had been allocated but not yet freed. (I was the one who instrumented
malloc for the developer who did the leak-plugging). He found many
leaks having to do with X11 implementations, some because we were
not properly free()ing sub-structures, and some were in fact X bugs
(either due to the particular X11 vendor, or to general bugs in X's
resource management). However, the most interesting aspect of this
search was how hard it was to identify that a leak existed: when
you run for several minutes, exercising utilities, putting up new
windows, and then looking at the still-malloc'd blocks, were these
still allocated because they were leaked, or because X had stuffed
them into resource lists? The program eventually tended to reach
steady state, but even that was tenative, since other resources could
be filled as more functionality was exercised.
> I admit that the first form of memory leak might be unnerving but I
> was more concerned about the second form - i.e. something I can't
> fight against even if I'm aware of it. My understanding of what I've
> read was that conservative GC can lead to the second form of memory
> leaks. From your posting above (first sentence) it looks like my
> understanding was wrong.
From what Raymond Toy said elsewhere in this thread, you were not
wrong - it seems CMUCL on x86 does have a conservative-gc, and thus
(I surmise) might leak memory under certain circumstances, under your
second notion of memory leak.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
From: Nils Goesche
Subject: Re: Conservative vs. precise GC
Date:
Message-ID: <lyk7hejcj7.fsf@cartan.de>
Duane Rettig <·····@franz.com> writes:
> Edi Weitz <···@agharta.de> writes:
>
> > I admit that the first form of memory leak might be unnerving but
> > I was more concerned about the second form - i.e. something I
> > can't fight against even if I'm aware of it. My understanding of
> > what I've read was that conservative GC can lead to the second
> > form of memory leaks. From your posting above (first sentence) it
> > looks like my understanding was wrong.
>
> From what Raymond Toy said elsewhere in this thread, you were not
> wrong - it seems CMUCL on x86 does have a conservative-gc, and thus
> (I surmise) might leak memory under certain circumstances, under
> your second notion of memory leak.
Aargh, after some googling it looks as if I goofed -- somehow, I
seemed to remember that a ``conservative GC�� is one that doesn't move
objects around when collecting. Apparently, that was wrong. Sorry
for any confusion caused.
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
From: Christopher C. Stacy
Subject: Re: Conservative vs. precise GC
Date:
Message-ID: <u1y3mdo0w.fsf@dtpq.com>
>>>>> On 09 Jan 2003 21:25:48 +0100, Nils Goesche ("Nils") writes:
Nils> Aargh, after some googling it looks as if I goofed -- somehow, I
Nils> seemed to remember that a ``conservative GC�� is one that doesn't move
Nils> objects around when collecting.
It doesn't know precisely when it is looking at an object reference,
so it can't go moving objects around -- that candidate pointer might
not have been an object reference.
Nils Goesche <······@cartan.de> writes:
> Duane Rettig <·····@franz.com> writes:
>
> > Edi Weitz <···@agharta.de> writes:
> >
> > > I admit that the first form of memory leak might be unnerving but
> > > I was more concerned about the second form - i.e. something I
> > > can't fight against even if I'm aware of it. My understanding of
> > > what I've read was that conservative GC can lead to the second
> > > form of memory leaks. From your posting above (first sentence) it
> > > looks like my understanding was wrong.
> >
> > From what Raymond Toy said elsewhere in this thread, you were not
> > wrong - it seems CMUCL on x86 does have a conservative-gc, and thus
> > (I surmise) might leak memory under certain circumstances, under
> > your second notion of memory leak.
>
> Aargh, after some googling it looks as if I goofed -- somehow, I
> seemed to remember that a ``conservative GC�� is one that doesn't move
> objects around when collecting. Apparently, that was wrong. Sorry
> for any confusion caused.
Heh - yup, that would be "in place" vs "copying". Of course, it
probably is true that most conservative GC's are in-place, and I
think it's very likely that all generational gcs have some copying
component within, but the two pairs really are disjoint. I would
make a _guess_ that CMUCL on x86, which purports to be conservative
and generational, is nonetheless copying. Raymond?
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
In article <·············@beta.franz.com>,
Duane Rettig <·····@franz.com> wrote:
>Heh - yup, that would be "in place" vs "copying". Of course, it
>probably is true that most conservative GC's are in-place,
I think it's practically guaranteed. A conservative GC can't tell what's a
real pointer and what is just something that *might* be a pointer. So it
certainly can't update these "maybe" pointers -- if they're not actually
pointers then you've just corrupted ordinary data.
> and I
>think it's very likely that all generational gcs have some copying
>component within, but the two pairs really are disjoint.
Again, it seems like the correlation should be quite high. If each
generation is a region of memory, you presumably need to copy from one
generation to the next higher one.
On the other hand, I suppose you could perform an in-place sweep of a
generation, and then add its memory to the pool of pages that are part of
generation N+1. But it doesn't seem like this would actually get you any
memory back, since new allocations are always done in the lowest
generation. So all the unused space in these higher generations would end
up being wasted.
> I would
>make a _guess_ that CMUCL on x86, which purports to be conservative
>and generational, is nonetheless copying. Raymond?
I think some of the messages mentioned that it has both a precise and
conservative GC. It seems like it's a many-way hybrid.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin wrote:
> I think it's practically guaranteed. A conservative GC can't tell what's a
> real pointer and what is just something that *might* be a pointer. So it
> certainly can't update these "maybe" pointers -- if they're not actually
> pointers then you've just corrupted ordinary data.
There are 'mostly copying' collectors in which some subset of the
objects can be understood by the collector. Data in those objects
are never 'maybe' pointers; the collector knows what they are.
Objects pointed to only by definite pointers can be moved.
As I understand it, this idea is patented, with the US patent
expiring in 2007(?).
Paul
Paul Dietz <············@motorola.com> wrote:
>Barry Margolin wrote:
+---------------
| There are 'mostly copying' collectors in which some subset of the
| objects can be understood by the collector. Data in those objects
| are never 'maybe' pointers; the collector knows what they are.
| Objects pointed to only by definite pointers can be moved.
|
| As I understand it, this idea is patented, with the US patent
| expiring in 2007(?).
+---------------
Are you thinking of Joel Bartlett's mostly-copying collector?
<URL:http://www.research.compaq.com/wrl/techreports/abstracts/88.2.html>
Joel F. Bartlett, "Compacting Garbage Collection with Ambiguous Roots"
Compaq Western Research (formerly DECWRL) Research Report 88/2,
February 1988
This paper introduces a copying garbage collection algorithm which
is able to compact most of the accessible storage in the heap without
having an explicitly defined set of pointers that contain the roots
of all accessible storage. Using "hints" found in the processor's
registers and stack, the algorithm is able to divide heap allocated
objects into two groups: those that might be referenced by a pointer
in the stack or registers, and those that are not. The objects which
might be referenced are left in place, and the other objects are
copied into a more compact representation.
This was written [in 1987?] for his "Scheme2C" compiler. The core code
appears as "Appendix I" of the paper. I didn't know that it was patented,
though...
-Rob
-----
Rob Warnock, PP-ASEL-IA <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> | As I understand it, this idea is patented, with the US patent
> | expiring in 2007(?).
>
> Are you thinking of Joel Bartlett's mostly-copying collector?
Yes: US Patent 4907151, granted March 6, 1990.
Paul
Barry Margolin <······@genuity.net> writes:
> In article <·············@beta.franz.com>,
> Duane Rettig <·····@franz.com> wrote:
>
>> I would make a _guess_ that CMUCL on
>>x86, which purports to be conservative and generational, is
>>nonetheless copying. Raymond?
>
> I think some of the messages mentioned that it has both a precise
> and conservative GC. It seems like it's a many-way hybrid.
no, it's of the so-called "mostly-copying" variety. "conservative"
(i.e. uncertain) pointers "pin" objects in place. for space
consumption reasons a whole page stays in place if it contains even
one pinned object.
the rest is copied, if it's live and young enough.
--
Purely applicative languages are poorly applicable.
-- Alan Perlis
>>>>> "Duane" == Duane Rettig <·····@franz.com> writes:
Duane> Heh - yup, that would be "in place" vs "copying". Of course, it
Duane> probably is true that most conservative GC's are in-place, and I
Duane> think it's very likely that all generational gcs have some copying
Duane> component within, but the two pairs really are disjoint. I would
Duane> make a _guess_ that CMUCL on x86, which purports to be conservative
Duane> and generational, is nonetheless copying. Raymond?
My understanding is limited, but when a full GC is done, I believe it
is a copying collector. Perhaps Dan Barlow knows more since he has
worked on the gc code for SBCL.
Ray
Raymond Toy <···@rtp.ericsson.se> writes:
>>>>>> "Duane" == Duane Rettig <·····@franz.com> writes:
>
> Duane> Heh - yup, that would be "in place" vs "copying". Of course, it
> Duane> probably is true that most conservative GC's are in-place, and I
> Duane> think it's very likely that all generational gcs have some copying
> Duane> component within, but the two pairs really are disjoint. I would
> Duane> make a _guess_ that CMUCL on x86, which purports to be conservative
> Duane> and generational, is nonetheless copying. Raymond?
>
> My understanding is limited, but when a full GC is done, I believe it
> is a copying collector. Perhaps Dan Barlow knows more since he has
> worked on the gc code for SBCL.
In general even the partial collections copy.
We don't have separate virtual address areas for different spaces:
instead we have a page_table structure that stores the generation for
each page. Pages locked by potential pointers on the C stack are
promoted in-place to the 'oldspace' generation (comments in the code
suggest that this is non-optimal but a necessary evil; I haven't taken
the time to think about it too hard), ditto pages containing
page-sized objects, but otherwise, yes, we copy.
-dan
--
http://www.cliki.net/ - Link farm for free CL-on-Unix resources
Daniel Barlow <···@telent.net> writes:
> Pages locked by potential pointers on the C stack are promoted
> in-place to the 'oldspace' generation (comments in the code suggest
> that this is non-optimal but a necessary evil;
I think this refers to the size of the pages used in gencgc. The
write barrier we need to implement the remembered set of older
generations forces us to use the OS' VM page size, while Bartlett
found much smaller page sizes to work better, in his non-generational
GC.
Gerd Moellmann wrote:
> I think this refers to the size of the pages used in gencgc. The
> write barrier we need to implement the remembered set of older
> generations forces us to use the OS' VM page size, while Bartlett
> found much smaller page sizes to work better, in his non-generational
> GC.
Are VM-assisted write barriers really superior to non-assisted algorithms?
IIRC, Self's card marking scheme required just two extra instructions
per write.
Paul
"Paul F. Dietz" <·····@dls.net> writes:
> Gerd Moellmann wrote:
>
> > I think this refers to the size of the pages used in gencgc. The
> > write barrier we need to implement the remembered set of older
> > generations forces us to use the OS' VM page size, while Bartlett
> > found much smaller page sizes to work better, in his non-generational
> > GC.
>
> Are VM-assisted write barriers really superior to non-assisted algorithms?
> IIRC, Self's card marking scheme required just two extra instructions
> per write.
The write barrier in gencgc just unprotects the page written to and
sets a flag indicating that the page has been written to. All objects
on such pages implicitly become members of the remembered set.
That's not too bad, I guess, except for the relatively large page size,
because writes into older generations shouldn't happen often, and the
write barrier is hit only once per page. And it has the advantage
that writes into the youngest generation incur zero overhead, because
the youngest generation doesn't need a remembered set.
If this is superior to software write barriers in practice, I don't
know; I don't remember having read a direct comparison of both
methods. My gut feeling is that it usually is, because of the
zero-overhead writes in the youngest generation, but YMMV.
Gerd Moellmann wrote:
> The write barrier in gencgc just unprotects the page written to and
> sets a flag indicating that the page has been written to. All objects
> on such pages implicitly become members of the remembered set.
>
> That's not too bad, I guess, except for the relatively large page size,
> because writes into older generations shouldn't happen often, and the
> write barrier is hit only once per page. And it has the advantage
> that writes into the youngest generation incur zero overhead, because
> the youngest generation doesn't need a remembered set.
>
> If this is superior to software write barriers in practice, I don't
> know; I don't remember having read a direct comparison of both
> methods. My gut feeling is that it usually is, because of the
> zero-overhead writes in the youngest generation, but YMMV.
A disadvantage of the VM approach could be that the pages are too big.
This increases the scanning overhead at scavenge time. Cards can
be made smaller.
There are a bunch of papers online; start from
http://citeseer.nj.nec.com/hosking93protection.html
for example.
This paper is a decade old; I don't know how the tradeoffs have
changed since then. If VM pages have been getting bigger then
the VM-assisted schemes may be noticably worse now.
If I understand correctly, Allegro CL uses a software write barrier.
Paul
"Paul F. Dietz" <·····@dls.net> writes:
> A disadvantage of the VM approach could be that the pages are too big.
> This increases the scanning overhead at scavenge time. Cards can
> be made smaller.
Yes, that's a potential down-side, and even more so the mostly-copying
algorithm because it promotes whole pages referenced from ambiguous
roots.
> There are a bunch of papers online; start from
>
> http://citeseer.nj.nec.com/hosking93protection.html
Thanks.
From: Christopher C. Stacy
Subject: Re: Conservative vs. precise GC
Date:
Message-ID: <u65sydp6m.fsf@dtpq.com>
>>>>> On 09 Jan 2003 19:28:13 +0100, Edi Weitz ("Edi") writes:
Edi> the second notion talks about memory that isn't reclaimed
Edi> (i.e. _can't_ be reclaimed) no matter how you tune your Lisp's GC.
Edi> My understanding of what I've read was that conservative GC can
Edi> lead to the second form of memory leaks.
You are correct about that: a conservative GC may leak, because it
might see a bit pattern (eg. on the stack) that looks like a valid
object pointer. It will consider that to be an active reference
(eg. an object in a local variable) and won't collect it.
Suppose those lucky bits were not really object reference, but
there was an allocated object, say, pointing into the middle of
a list that was otherwise garbage. That "reference" will prevent
that object from being collected at that time. Maybe it will
never be collected.
They say that this doesn't happen too often, but it seems
to me it would depend entirely on the application program.
(The usual comparison is how much less a conservative GC leaks
versus experience with programs that do manual deallocation.
This is a qualitatively different experience than a comparison
to a typical Lisp memory model that can precisely collect garbage.)
In other words, you can fake out this kind of GC because it is
not in full collusion with the memory allocator side of things
in such a way that object references can be exactly identified.
(If there were BiBoP or type tags, then the GC can be exact,
as is common in Lisp implementations.) Since this kind of GC
is only ever making a good guess as to what pointers look like,
it must be "conservative".
There are additional ramifications of this kind of memory system.
If you don't know for sure whether you've got an object reference,
you can't go moving things around in memory willy-nilly; the GC
doesn't always know for sure what it's looking at!
At least, that's how I understand the term.
This does not mean that precise generational GCs don't ever leak,
but those can be tuned to eliminate the leaks. In the worst case,
you can demand an immediate precise collection, which will find
promoted garbage along with everything else. Just don't do that
when the sponsors are watching the demo.
In article <··············@cartan.de>, Nils Goesche <······@cartan.de> wrote:
>The reason generational garbage collectors are used despite of this is
>that they are fast -- simply because they don't have to look at all
>generations all the time -- and some generations are not scanned by
>default at all. If, for some strange reason, objects are regularly
>promoted to generations that are not scanned by default, you have a
>memory leak. In this case you should tweak the GC in such a way that
>this doesn't happen anymore.
I don't see how this promotion could happen "regularly". In order for an
object to be promoted to the oldest generation, it has to survive several
GC's, so it has to stay live for a significant amount of time. For it to
happen often, the application would need to have a regular pattern of using
some objects for a long time and then releasing them.
I could see this happening occasionally if you run an application for a
while, so it builds up some data, and then exit the application. Suddenly,
all its data becomes garbage, but because you'd been running it for a long
time it had all graduated to the uncollected generation. But it doesn't
seem like this would happen frequently, just on those occasions when you
exit a long-running application.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
In article <·················@paloalto-snr1.gtei.net>, Barry Margolin
<······@genuity.net> wrote:
> In article <··············@cartan.de>, Nils Goesche <······@cartan.de> wrote:
> >The reason generational garbage collectors are used despite of this is
> >that they are fast -- simply because they don't have to look at all
> >generations all the time -- and some generations are not scanned by
> >default at all. If, for some strange reason, objects are regularly
> >promoted to generations that are not scanned by default, you have a
> >memory leak. In this case you should tweak the GC in such a way that
> >this doesn't happen anymore.
>
> I don't see how this promotion could happen "regularly". In order for an
> object to be promoted to the oldest generation, it has to survive several
> GC's, so it has to stay live for a significant amount of time. For it to
> happen often, the application would need to have a regular pattern of using
> some objects for a long time and then releasing them.
>
> I could see this happening occasionally if you run an application for a
> while, so it builds up some data, and then exit the application. Suddenly,
> all its data becomes garbage, but because you'd been running it for a long
> time it had all graduated to the uncollected generation. But it doesn't
> seem like this would happen frequently, just on those occasions when you
> exit a long-running application.
I can think of many more examples:
* An application that keeps some kind of history object. As new updates
come in, old data gets dropped, but any given item in the history stays
there for a long time.
* An application that has a driving data structure that gets thrown out
and replaced with an updated one from time to time (e.g. a new predictive
model of some sort).
* An application where code updates happen in a live image without exiting
the application.
E.
From: Nils Goesche
Subject: Re: Conservative vs. precise GC
Date:
Message-ID: <lyof6qjcwj.fsf@cartan.de>
Barry Margolin <······@genuity.net> writes:
> In article <··············@cartan.de>, Nils Goesche <······@cartan.de> wrote:
> >The reason generational garbage collectors are used despite of this
> >is that they are fast -- simply because they don't have to look at
> >all generations all the time -- and some generations are not
> >scanned by default at all. If, for some strange reason, objects
> >are regularly promoted to generations that are not scanned by
> >default, you have a memory leak. In this case you should tweak the
> >GC in such a way that this doesn't happen anymore.
> I don't see how this promotion could happen "regularly". In order
> for an object to be promoted to the oldest generation, it has to
> survive several GC's, so it has to stay live for a significant
> amount of time. For it to happen often, the application would need
> to have a regular pattern of using some objects for a long time and
> then releasing them.
Yes, that's exactly what I was thinking of. Why is this so
inconceivable? Edi was talking about a program that would be running
for months or years. Suppose it is some kind of server, and clients
usually connect and stay connected for, say, several hours. There
might be some ``connection object�� associated with such a connection,
and this might be promoted quite high. When the client finally
disconnects, this object becomes garbage but will not be reclaimed
unless higher generations are scanned, too, once in a while.
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
In article <··············@cartan.de>, Nils Goesche <······@cartan.de> wrote:
>Barry Margolin <······@genuity.net> writes:
>
>> In article <··············@cartan.de>, Nils Goesche <······@cartan.de> wrote:
>
>> >The reason generational garbage collectors are used despite of this
>> >is that they are fast -- simply because they don't have to look at
>> >all generations all the time -- and some generations are not
>> >scanned by default at all. If, for some strange reason, objects
>> >are regularly promoted to generations that are not scanned by
>> >default, you have a memory leak. In this case you should tweak the
>> >GC in such a way that this doesn't happen anymore.
>
>> I don't see how this promotion could happen "regularly". In order
>> for an object to be promoted to the oldest generation, it has to
>> survive several GC's, so it has to stay live for a significant
>> amount of time. For it to happen often, the application would need
>> to have a regular pattern of using some objects for a long time and
>> then releasing them.
>
>Yes, that's exactly what I was thinking of. Why is this so
>inconceivable? Edi was talking about a program that would be running
>for months or years. Suppose it is some kind of server, and clients
>usually connect and stay connected for, say, several hours. There
>might be some ``connection object�� associated with such a connection,
>and this might be promoted quite high. When the client finally
>disconnects, this object becomes garbage but will not be reclaimed
>unless higher generations are scanned, too, once in a while.
Although the server itself is long-lived, individual connections are likely
to be more transient, so their connection-specific data would not be
promoted very high.
If a connection lasts a long time, then I agree that its data could make it
up to the uncollected generation. This is likely to be a problem only if
it's very common to have long-lived client connections. Since most
services that I'm familiar with do *not* involve lots of long-lived
connections, that's why I said I didn't think it would happen "regularly".
Only someone familiar with the actual application involved can tell whether
it doesn't fit this more common mold.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin wrote:
> I don't see how this promotion could happen "regularly". In order for an
> object to be promoted to the oldest generation, it has to survive several
> GC's, so it has to stay live for a significant amount of time. For it to
> happen often, the application would need to have a regular pattern of using
> some objects for a long time and then releasing them.
Exactly typical behavior of applications that use window systems. The
advent of windowized IDEs significantly altered typical demands on memory
management. Open up an inspector window on some frob while you are
debugging and leave it around for a while, its storage will likely get
significantly aged.
Edi Weitz <···@agharta.de> writes:
> I've read the GC FAQ but that's basically all I know about garbage
> collection. What I noticed is that some CL implementations on some
> platforms have conservative GC while others have precise GC. I
> understand that conservative GC may keep objects alive (infinitely?)
> that are otherwise garbage.
I'd say there's a pretty low chance that you'll get significant memory
leaks using a conservative GC like CMUCL's, because it's only
conservative on the stack and registers. I'd try just using it, and
seeing what happens. If it turns out that you do leak (too much)
memory, you can try a stack-scrubbing solution, which might help. It
probably wouldn't be too hard to write code that would zero out the
dead stack frames so you don't have phantom references to dead objects
when the stack grows again.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> If it turns out that you do leak (too much) memory, you can try a
> stack-scrubbing solution, which might help. It probably wouldn't be
> too hard to write code that would zero out the dead stack frames so
> you don't have phantom references to dead objects when the stack
> grows again.
See SYSTEM:SCRUB-CONTROL-STACK in CMUCL. It's already being called in
various places.