Extending STRING Class - lisp

In article <g8kmia$745$1$8300dec7@news.demon.co.uk>,
Robert Swindells <rjs@fdy2.demon.co.uk> wrote:

> On Thu, 21 Aug 2008 12:27:40 -0700, Don Geddis wrote:
>
> > rpw3@rpw3.org (Rob Warnock) wrote on Thu, 21 Aug 2008:
> >> You are correct that there is no built-in FREE in CL. But all you have
> >> to do in CL to "free" an object is remove *all* references to the
> >> object [turning it into "garbage"], and the GC will (eventually) come
> >> along and discover the lack of any such references and collect the
> >> space used by the object.
> >
> > You know, everybody describes it that way. But GCs really work by
> > finding still-used memory (and copying it elsewhere), not by finding
> > garbage. They never actually "discover the lack of references".
> > There's not an explicit step in the algorithm, where it suddenly
> > concludes: "Ah ha! There are no longer any references to this little
> > block of memory! I'll collect it."
>
> Mark-and-sweep really can work in the way Rob Warnock described.

And reference counting really does suddenly conclude that there are no
references to the block of memory, when its refcount drops to 0.

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***

On Thu, 21 Aug 2008 12:27:40 -0700, Don Geddis <don@geddis.org> wrote:

>rpw3@rpw3.org (Rob Warnock) wrote on Thu, 21 Aug 2008:
>> You are correct that there is no built-in FREE in CL. But all you have to
>> do in CL to "free" an object is remove *all* references to the object
>> [turning it into "garbage"], and the GC will (eventually) come along and
>> discover the lack of any such references and collect the space used by the
>> object.
>
>You know, everybody describes it that way. But GCs really work by finding
>still-used memory (and copying it elsewhere), not by finding garbage. They
>never actually "discover the lack of references". There's not an explicit
>step in the algorithm, where it suddenly concludes: "Ah ha! There are no
>longer any references to this little block of memory! I'll collect it."

Not exactly. Any non-copying collector has the potential to work by
identifying garbage - all reference counters do and I know of at least
one concurrent mark-sweep design that does also. But for almost all
purposes it's more efficient to identify live objects instead.

Non-copying collectors also must touch the garbage space to recycle it
so it obviously has to be identified.


>Obviously you know this already, but I always found it ironic that the
>standard one-line explanation (and even the name!) of "garbage collection"
>isn't really correct.
>
> -- Don

Yeah, it's really a combination of census taker and undertaker.

George

På Fri, 22 Aug 2008 21:18:47 +0200, skrev George Neuner
<gneuner2@comcast.net>:

>
> Not exactly. Any non-copying collector has the potential to work by
> identifying garbage - all reference counters do and I know of at least
> one concurrent mark-sweep design that does also. But for almost all
> purposes it's more efficient to identify live objects instead.
>

It it common to collect garbage rather than copy 'live' data in C/C++
garbage collectors.
Lisp keeps a array of locations on the heap where the data is stored. The
location the variable stores is just a index in this array.
In C on the other hand you store the address on the heap directly so
moving the memory here would be disastrous.
Hence you need to keep things where they were.
The Boehm-Demers-Weiser conservative garbage collector is a example of
this.

--------------
John Thingstad

"John Thingstad" <jpthing@online.no> wrote on Fri, 22 Aug 2008:
> > Fri, 22 Aug 2008 21:18:47 +0200, skrev George Neuner <gneuner2@comcast.net>:
>> Not exactly. Any non-copying collector has the potential to work by
>> identifying garbage - all reference counters do and I know of at least
>> one concurrent mark-sweep design that does also. But for almost all
>> purposes it's more efficient to identify live objects instead.
>
> It it common to collect garbage rather than copy 'live' data in C/C++
> garbage collectors. Lisp keeps a array of locations on the heap where the
> data is stored. The location the variable stores is just a index in this
> array. In C on the other hand you store the address on the heap directly
> so moving the memory here would be disastrous. Hence you need to keep
> things where they were. The Boehm-Demers-Weiser conservative garbage
> collector is a example of this.

Thanks for the corrections, everybody. Sorry for my misinformation.

I confused the typical way that modern CL GC works, with the obvious
way that every GC ought to work. Clearly, the standard description
indeed does apply to some GCs (especially older ones or non-CL ones).

-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ don@geddis.org
I wish I would have a real tragic love affair and get so bummed out that I'd
just quit my job and become a bum for a few years, because I was thinking about
doing that anyway. -- Deep Thoughts, by Jack Handey

On Aug 22, 9:44 pm, "John Thingstad" <jpth...@online.no> wrote:
> På Fri, 22 Aug 2008 21:18:47 +0200, skrev George Neuner  
> <gneun...@comcast.net>:
>
>
>
> > Not exactly.  Any non-copying collector has the potential to work by
> > identifying garbage - all reference counters do and I know of at least
> > one concurrent mark-sweep design that does also.  But for almost all
> > purposes it's more efficient to identify live objects instead.
>
> It it common to collect garbage rather than copy 'live' data in C/C++  
> garbage collectors.
> Lisp keeps a array of locations on the heap where the data is stored. The 
> location the variable stores is just a index in this array.

What? Uh, no.

> In C on the other hand you store the address on the heap directly so  
> moving the memory here would be disastrous.

No, most/all Lisp implementations store pointers on the heap.

> Hence you need to keep things where they were.
> The Boehm-Demers-Weiser conservative garbage collector is a example of  
> this.

The conservativism is because you cannot unambiguously tell a pointer
from an integer from a ... in C. In implementing languages intended to
have GCs, if you know how to find the root set of pointers (stack,
registers), you can find all live objects by following those. When you
find a pointer to some place on the stack, you can tell by the tag
bits where the pointers are.

And you can implement moving collectors for C++, if you require the
user to always use smart pointers.

På Fri, 22 Aug 2008 21:44:49 +0200, skrev John Thingstad
<jpthing@online.no>:

> På Fri, 22 Aug 2008 21:18:47 +0200, skrev George Neuner
> <gneuner2@comcast.net>:
>
>>
>> Not exactly. Any non-copying collector has the potential to work by
>> identifying garbage - all reference counters do and I know of at least
>> one concurrent mark-sweep design that does also. But for almost all
>> purposes it's more efficient to identify live objects instead.
>>
>
> It it common to collect garbage rather than copy 'live' data in C/C++
> garbage collectors.
> Lisp keeps a array of locations on the heap where the data is stored.
> The location the variable stores is just a index in this array.
> In C on the other hand you store the address on the heap directly so
> moving the memory here would be disastrous.
> Hence you need to keep things where they were.
> The Boehm-Demers-Weiser conservative garbage collector is a example of
> this.

Looking this over I think I should have added that that CL compilers that
compile to C mainly ECL and GCL use the above mentioned collector.
Thus you might encounter this in CL as well.

--------------
John Thingstad

On Sat, 23 Aug 2008 03:46:37 -0700 (PDT), "Thomas F. Burdick"
<tburdick@gmail.com> wrote:

>On Aug 22, 9:44 pm, "John Thingstad" <jpth...@online.no> wrote:
>> På Fri, 22 Aug 2008 21:18:47 +0200, skrev George Neuner  
>> <gneun...@comcast.net>:
>>
>>
>>
>> > Not exactly.  Any non-copying collector has the potential to work by
>> > identifying garbage - all reference counters do and I know of at least
>> > one concurrent mark-sweep design that does also.  But for almost all
>> > purposes it's more efficient to identify live objects instead.
>>
>> It it common to collect garbage rather than copy 'live' data in C/C++  
>> garbage collectors.
>> Lisp keeps a array of locations on the heap where the data is stored. The  
>> location the variable stores is just a index in this array.
>
>What? Uh, no.
>
>> In C on the other hand you store the address on the heap directly so  
>> moving the memory here would be disastrous.
>
>No, most/all Lisp implementations store pointers on the heap.
>
>> Hence you need to keep things where they were.
>> The Boehm-Demers-Weiser conservative garbage collector is a example of  
>> this.
>
>The conservativism is because you cannot unambiguously tell a pointer
>from an integer from a ... in C. In implementing languages intended to
>have GCs, if you know how to find the root set of pointers (stack,
>registers), you can find all live objects by following those. When you
>find a pointer to some place on the stack, you can tell by the tag
>bits where the pointers are.
>
>And you can implement moving collectors for C++, if you require the
>user to always use smart pointers.

Or if you arrange that the compiler always maintains the base pointer
to the allocated block. One of the main challenges for GC in C/C++ is
that there is no requirement for base pointers to be kept intact.
Optimized code can easily result in the only pointer to an allocation
being internal or past the end of the block.

George

Don Geddis schrieb:
> rpw3@rpw3.org (Rob Warnock) wrote on Thu, 21 Aug 2008:
>> You are correct that there is no built-in FREE in CL. But all you have to
>> do in CL to "free" an object is remove *all* references to the object
>> [turning it into "garbage"], and the GC will (eventually) come along and
>> discover the lack of any such references and collect the space used by the
>> object.
>
> You know, everybody describes it that way. But GCs really work by finding
> still-used memory (and copying it elsewhere), not by finding garbage. They
> never actually "discover the lack of references". There's not an explicit
> step in the algorithm, where it suddenly concludes: "Ah ha! There are no
> longer any references to this little block of memory! I'll collect it."
>
> Obviously you know this already, but I always found it ironic that the
> standard one-line explanation (and even the name!) of "garbage collection"
> isn't really correct.

Also have a look at page 16 of the comic of Googles new web browser:
http://www.google.com/googlebooks/chrome/


André
--