www.digitalmars.com         C & C++   DMDScript  

D - 2 level Garbage Collection

reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Some classes (and many structs) are used and reused throughout a
program, but don't necessarily need to be reconstructed for every use.
In these cases, it is desirable to recycle the object rather than
destroy and recreate them.

For example, in one of my projects, I have a number of threads accessing
a very large number of objects.  In some cases, one thread will need to
wait until another thread changes the object state.  I do this with
Signal objects, which the first thread sets to Stop() and then Wait()s
on; the latter thread (which changes the object) sets the Signal to Go()
after changing it.

It is impractical to statically create a Signal with each object; thus,
each object has a pointer to a Signal contained in it.  When a thread
needs to wait on an object, it grabs a Signal object from a global pool
of Signal's, it calls Stop() and then Wait().  The latter thread then
checks the pointer, and finding it non-NULL, sets the Signal to Go().
The Signal is later returned to the global pool.

Thus, I never have to create or recreate Signal objects; there is a
small pool of them (less than the count of threads) that are passed
around and shared as needed.

I would very much like the garbage collector to do this for me.  When I
get rid of the last reference to a Signal, it is put into a global pool
rather than destroyed.  This has some complexities, however:

* The garbage collector must be able to detect low-memory conditions and
start "flushing" pooled objects to free memory; otherwise we will build
a great backlog of wasted memory that might never be reused.
* Some objects will act differently based on whether they are being
destroyed or just being stored in a pool.  This implies that we might
need 2 different destructors.

The idea of 2 destructors is new to me, so I'm not sure what it would
look like.  There should probably be some mechanism where the programmer
could inform the compiler whether it was ok or not to "pool" this type
of object.  I don't know what the default should be, nor do I know how
inheritance should affect it all...

--
The Villagers are Online! villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]
Nov 02 2001
parent reply "Walter" <walter digitalmars.com> writes:
The concept of "weak pointers" sounds what you're looking for. It's a
popular idea, and likely will go into D's garbage collector at some
point. -Walter

"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3BE31C6C.9E041904 deming-os.org...
 Some classes (and many structs) are used and reused throughout a
 program, but don't necessarily need to be reconstructed for every use.
 In these cases, it is desirable to recycle the object rather than
 destroy and recreate them.

 For example, in one of my projects, I have a number of threads accessing
 a very large number of objects.  In some cases, one thread will need to
 wait until another thread changes the object state.  I do this with
 Signal objects, which the first thread sets to Stop() and then Wait()s
 on; the latter thread (which changes the object) sets the Signal to Go()
 after changing it.

 It is impractical to statically create a Signal with each object; thus,
 each object has a pointer to a Signal contained in it.  When a thread
 needs to wait on an object, it grabs a Signal object from a global pool
 of Signal's, it calls Stop() and then Wait().  The latter thread then
 checks the pointer, and finding it non-NULL, sets the Signal to Go().
 The Signal is later returned to the global pool.

 Thus, I never have to create or recreate Signal objects; there is a
 small pool of them (less than the count of threads) that are passed
 around and shared as needed.

 I would very much like the garbage collector to do this for me.  When I
 get rid of the last reference to a Signal, it is put into a global pool
 rather than destroyed.  This has some complexities, however:

 * The garbage collector must be able to detect low-memory conditions and
 start "flushing" pooled objects to free memory; otherwise we will build
 a great backlog of wasted memory that might never be reused.
 * Some objects will act differently based on whether they are being
 destroyed or just being stored in a pool.  This implies that we might
 need 2 different destructors.

 The idea of 2 destructors is new to me, so I'm not sure what it would
 look like.  There should probably be some mechanism where the programmer
 could inform the compiler whether it was ok or not to "pool" this type
 of object.  I don't know what the default should be, nor do I know how
 inheritance should affect it all...

 --
 The Villagers are Online! villagersonline.com

 .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
 .[ (a version.of(English).(precise.more)) is(possible) ]
 ?[ you want.to(help(develop(it))) ]

Nov 03 2001
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Walter wrote:

 The concept of "weak pointers" sounds what you're looking for. It's a
 popular idea, and likely will go into D's garbage collector at some
 point. -Walter

I've been reading up on garbage collection, and I'm pretty sure that weak pointers won't do what I'm looking for. In fact, they are the exact opposite. Take a look at the properties: Weak Pointers: * Allow user to store a pointer to the object * If only remaining references to the object are weak pointers, garbage collect anyway. * No change in algorithm when low memory Pooling: * User has NO remaining pointers to the object, weak or strong * Garbage collector keeps one "hidden" pointer to the object, which will be used to recycle the object on the next call to "operator new" * Garbage collector automatically flushes pooled objects in low memory conditions. Perhaps there's a way to do this with weak pointers that I haven't thought of... -- The Villagers are Online! http://villagersonline.com .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ] .[ (a version.of(English).(precise.more)) is(possible) ] ?[ you want.to(help(develop(it))) ]
Nov 03 2001
parent reply "Walter" <walter digitalmars.com> writes:
The pool is maintained using weak pointers. Objects only pointed to by weak
pointers get collected only under adverse memory conditions.

"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3BE43E93.D83BEA2E deming-os.org...
 Walter wrote:

 The concept of "weak pointers" sounds what you're looking for. It's a
 popular idea, and likely will go into D's garbage collector at some
 point. -Walter

I've been reading up on garbage collection, and I'm pretty sure that weak pointers won't do what I'm looking for. In fact, they are the exact opposite. Take a look at the properties: Weak Pointers: * Allow user to store a pointer to the object * If only remaining references to the object are weak pointers, garbage collect anyway. * No change in algorithm when low memory Pooling: * User has NO remaining pointers to the object, weak or strong * Garbage collector keeps one "hidden" pointer to the object, which will

 used to recycle the object on the next call to "operator new"
 * Garbage collector automatically flushes pooled objects in low memory
 conditions.

 Perhaps there's a way to do this with weak pointers that I haven't thought
 of...

 --
 The Villagers are Online! http://villagersonline.com

 .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
 .[ (a version.of(English).(precise.more)) is(possible) ]
 ?[ you want.to(help(develop(it))) ]

Nov 03 2001
parent reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Walter wrote:

 The pool is maintained using weak pointers. Objects only pointed to by weak
 pointers get collected only under adverse memory conditions.

Ok, that makes sense, I guess. How does the pool.Get() function know if the data has been collected or not? Or is that too far out into theorhetical land to answer? -- The Villagers are Online! http://villagersonline.com .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ] .[ (a version.of(English).(precise.more)) is(possible) ] ?[ you want.to(help(develop(it))) ]
Nov 03 2001
next sibling parent reply "Sean L. Palmer" <spalmer iname.com> writes:
You know, that brings up a good point.  It'd be *way* nice to be able to
plug into the garbage collection system.  Install your own subsystem and
have it called whenever creating an object associated with your GC
subsystem.  Maybe we could assign a GC type with any class we wanted and
then author that GC to provide the main GC with a list of "pointers" for it
to scan for, as well as access to any data it controls that should be
scanned.  Your GC could get its memory from whatever GC it wants, or by
managing some arbitrary system resource. All these GC classes could inherit
from the default GC class if they chose.
That basically means you can set up your own "pools" which are managed by
some reclamation scheme.  You could write your own memory manager at that
layer if you wanted.  Limit access to memory (this often is an issue when
making games).  Insert debugging code.  Maybe it would be possible to
install your own "global" GC (the default for that whole program).  That
would have to be standard system library supported if we were ever to have
portable code that deals with such things.

To answer your question, pool.Get() knows because it is the only thing that
allocates and reclaims objects of the type managed by pool.

In the above scenario the GC class would be asked to allocate the object and
return a pointer, and it'd be the one to know whether the data had been
collected because it's the one that collected it.  It could choose to only
collect when it decides that it's out of room.  The neat thing is that the
compiler could provide some support for the default GC implementation to
know which areas of memory it should scan for pointers.  Seems that you'd be
able to break that optimization by typecasting these handles to void and
back, or something, but I bet the compiler could figure out data transfer
graphs that would let it, at any point in the code, figure out what areas of
memory could possibly contain pointers to the objects returned by a given
GC.  If not, you wouldn't want to use the GC for managing fixed pools, or
the overhead for the eventual fillup that will certainly happen when doing
anything involving a create/destroy cycle will be unbearable as the GC
searches everything for pointers everytime some sub-pool fills up.  Of
course you should avoid unnecessary memory allocations, but sometimes the
most natural way to do OO involves creating and destroying different virtual
classes (you can make a nice clean state machine that way).

I'm still not sold on garbage collection myself, but I'd be damn impressed
by a language that supported builtin smart pointers (including weak ones).
I know those work and are useable in a game project situation.  All of my
first paragraph would apply equally well to a system wide smart pointer
class.  I bet with that you wouldn't need pointer typecasting as often.
Hell it almost is starting to sound like a language-supported bag class.
Associative arrays might even be derived from this, or vice versa..

Sean

"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3BE4C202.46160CEB deming-os.org...
 Walter wrote:

 The pool is maintained using weak pointers. Objects only pointed to by


 pointers get collected only under adverse memory conditions.

Ok, that makes sense, I guess. How does the pool.Get() function know if

 data has been collected or not?  Or is that too far out into theorhetical

 to answer?

Nov 04 2001
parent "Walter" <walter digitalmars.com> writes:
There are lots of cool things that can be done with GC. The first iteration
with D will be a straightforward global GC pool. After that, I'll be looking
at generational collectors (which offer huge improvements), weak pointers,
etc.

"Sean L. Palmer" <spalmer iname.com> wrote in message
news:9s38eo$2ks2$1 digitaldaemon.com...
 You know, that brings up a good point.  It'd be *way* nice to be able to
 plug into the garbage collection system.  Install your own subsystem and
 have it called whenever creating an object associated with your GC
 subsystem.  Maybe we could assign a GC type with any class we wanted and
 then author that GC to provide the main GC with a list of "pointers" for

 to scan for, as well as access to any data it controls that should be
 scanned.  Your GC could get its memory from whatever GC it wants, or by
 managing some arbitrary system resource. All these GC classes could

 from the default GC class if they chose.
 That basically means you can set up your own "pools" which are managed by
 some reclamation scheme.  You could write your own memory manager at that
 layer if you wanted.  Limit access to memory (this often is an issue when
 making games).  Insert debugging code.  Maybe it would be possible to
 install your own "global" GC (the default for that whole program).  That
 would have to be standard system library supported if we were ever to have
 portable code that deals with such things.

 To answer your question, pool.Get() knows because it is the only thing

 allocates and reclaims objects of the type managed by pool.

 In the above scenario the GC class would be asked to allocate the object

 return a pointer, and it'd be the one to know whether the data had been
 collected because it's the one that collected it.  It could choose to only
 collect when it decides that it's out of room.  The neat thing is that the
 compiler could provide some support for the default GC implementation to
 know which areas of memory it should scan for pointers.  Seems that you'd

 able to break that optimization by typecasting these handles to void and
 back, or something, but I bet the compiler could figure out data transfer
 graphs that would let it, at any point in the code, figure out what areas

 memory could possibly contain pointers to the objects returned by a given
 GC.  If not, you wouldn't want to use the GC for managing fixed pools, or
 the overhead for the eventual fillup that will certainly happen when doing
 anything involving a create/destroy cycle will be unbearable as the GC
 searches everything for pointers everytime some sub-pool fills up.  Of
 course you should avoid unnecessary memory allocations, but sometimes the
 most natural way to do OO involves creating and destroying different

 classes (you can make a nice clean state machine that way).

 I'm still not sold on garbage collection myself, but I'd be damn impressed
 by a language that supported builtin smart pointers (including weak ones).
 I know those work and are useable in a game project situation.  All of my
 first paragraph would apply equally well to a system wide smart pointer
 class.  I bet with that you wouldn't need pointer typecasting as often.
 Hell it almost is starting to sound like a language-supported bag class.
 Associative arrays might even be derived from this, or vice versa..

 Sean

 "Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
 news:3BE4C202.46160CEB deming-os.org...
 Walter wrote:

 The pool is maintained using weak pointers. Objects only pointed to by


 pointers get collected only under adverse memory conditions.

Ok, that makes sense, I guess. How does the pool.Get() function know if

 data has been collected or not?  Or is that too far out into


 land
 to answer?


Nov 04 2001
prev sibling parent "Walter" <walter digitalmars.com> writes:
I haven't studied it thoroughly, but the gc collector interacts with the
weak pointer pool manager to notify it. -Walter

"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3BE4C202.46160CEB deming-os.org...
 Walter wrote:

 The pool is maintained using weak pointers. Objects only pointed to by


 pointers get collected only under adverse memory conditions.

Ok, that makes sense, I guess. How does the pool.Get() function know if

 data has been collected or not?  Or is that too far out into theorhetical

 to answer?

 --
 The Villagers are Online! http://villagersonline.com

 .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
 .[ (a version.of(English).(precise.more)) is(possible) ]
 ?[ you want.to(help(develop(it))) ]

Nov 04 2001