www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Can the current D handle a compacting garbage collector

reply Daniel Horn <hellcatv hotmail.com> writes:
IMO D shouldn't go 1.0 at least until there is an example compacting 
garbage collector that actually moves memory around- (or a line in the 
spec explaining that the GC shall not move memory)

The spec or implementations may need to be severely altered to make this 
a reality, and that's best done before 1.0, no?

for instance, moving pointers requires that the garbage collector know 
what each type is...
for instance...

char * globvar=new char[1000].ptr;

union {
int x;
char * v;
}tmp;

if I needed to move around globvar's allocation...and tmp.x happened to 
contain the address of globvar's memory (but really contained the result 
of a previous calculation that randomly matched the pointer contents), 
tmp.x's value might be *incorrectly* adjusted to match that other pointer.

How is the GC supposed to know?  is there another implicit bit in a 
union that lets the GC know if it's contained a pointer or not?  if so, 
can I have access to that bit?


Without an example implementation of a GC that moves around memory it 
would be quite difficult to bugtest current libraries that are  in their 
infant stages.  I'd imagine many libraries use the default opCmp in an 
object--which (as I understand) might cause a problem with quicksort if 
their orders magically changes during a sort operation.
(I've had C++'s std::sort *crash* if < was not defined to be transitive)
May 01 2005
next sibling parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
There are two poles in the programming world :
"GCable" systems and non GCable systems with explicit
allocation schemas.

The truth as you know is in between. And between is the place where
D resides (seems like D is everywhere "in between").
And this is extremely good. IMHO.

If you are allocating some chunk than you'd better delete it after if you 
know
that there are no external references to it. This is good and
"technically literate" behavior.

GC helps a lot (simplifies life) if you have big object hierarchies with
possible cyclic references and the like. you don't need those
super smart_ptr<> and co if you are using GC there.

I think that the way GC implemented in D - non-compacting mark-n-sweep
is just right - yes, it is not so effective (btw I'd like to know criterias 
of this)
as e.g. copying generational GC, but it does the job - it is collecting 
garbage and
not moving what is used by and belongs to you.

Yes, you are right, it makes sense to mention this behavior in the doc but
anyway as soon as you have "std.c.memcpy' & co. such GC implementation
is the only one available.

Sorry for the bombastic statement :)

Andrew.
http://terrainformatica.com



"Daniel Horn" <hellcatv hotmail.com> wrote in message 
news:d53nmc$ch3$1 digitaldaemon.com...
 IMO D shouldn't go 1.0 at least until there is an example compacting 
 garbage collector that actually moves memory around- (or a line in the 
 spec explaining that the GC shall not move memory)

 The spec or implementations may need to be severely altered to make this a 
 reality, and that's best done before 1.0, no?

 for instance, moving pointers requires that the garbage collector know 
 what each type is...
 for instance...

 char * globvar=new char[1000].ptr;

 union {
 int x;
 char * v;
 }tmp;

 if I needed to move around globvar's allocation...and tmp.x happened to 
 contain the address of globvar's memory (but really contained the result 
 of a previous calculation that randomly matched the pointer contents), 
 tmp.x's value might be *incorrectly* adjusted to match that other pointer.

 How is the GC supposed to know?  is there another implicit bit in a union 
 that lets the GC know if it's contained a pointer or not?  if so, can I 
 have access to that bit?


 Without an example implementation of a GC that moves around memory it 
 would be quite difficult to bugtest current libraries that are  in their 
 infant stages.  I'd imagine many libraries use the default opCmp in an 
 object--which (as I understand) might cause a problem with quicksort if 
 their orders magically changes during a sort operation.
 (I've had C++'s std::sort *crash* if < was not defined to be transitive)
 

May 01 2005
parent reply Daniel Horn <hellcatv hotmail.com> writes:
Is this the final say here? So there's no chance for a compacting GC 
because of the examples I have listed below?

Andrew Fedoniouk wrote:
 I think that the way GC implemented in D - non-compacting mark-n-sweep
 is just right - yes, it is not so effective (btw I'd like to know criterias 
 of this)
 as e.g. copying generational GC, but it does the job - it is collecting 
 garbage and
 not moving what is used by and belongs to you.
 
 Yes, you are right, it makes sense to mention this behavior in the doc but
 anyway as soon as you have "std.c.memcpy' & co. such GC implementation
 is the only one available.
 
 Sorry for the bombastic statement :)
 
 Andrew.
 http://terrainformatica.com
 
 
 
 "Daniel Horn" <hellcatv hotmail.com> wrote in message 
 news:d53nmc$ch3$1 digitaldaemon.com...
 
IMO D shouldn't go 1.0 at least until there is an example compacting 
garbage collector that actually moves memory around- (or a line in the 
spec explaining that the GC shall not move memory)

The spec or implementations may need to be severely altered to make this a 
reality, and that's best done before 1.0, no?

for instance, moving pointers requires that the garbage collector know 
what each type is...
for instance...

char * globvar=new char[1000].ptr;

union {
int x;
char * v;
}tmp;

if I needed to move around globvar's allocation...and tmp.x happened to 
contain the address of globvar's memory (but really contained the result 
of a previous calculation that randomly matched the pointer contents), 
tmp.x's value might be *incorrectly* adjusted to match that other pointer.

How is the GC supposed to know?  is there another implicit bit in a union 
that lets the GC know if it's contained a pointer or not?  if so, can I 
have access to that bit?


Without an example implementation of a GC that moves around memory it 
would be quite difficult to bugtest current libraries that are  in their 
infant stages.  I'd imagine many libraries use the default opCmp in an 
object--which (as I understand) might cause a problem with quicksort if 
their orders magically changes during a sort operation.
(I've had C++'s std::sort *crash* if < was not defined to be transitive)


May 02 2005
next sibling parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"Daniel Horn" <hellcatv hotmail.com> wrote in message 
news:d560sf$2i8q$1 digitaldaemon.com...
 Is this the final say here? So there's no chance for a compacting GC 
 because of the examples I have listed below?

I'm not sure what you mean by "no chance". Without the type information being available to the GC there is no chance, I agree. With type information it should be possible (as long as the bits in phobos that use the address as a unique id change as well). For the example you gave using a union the GC would have to be conservative in that it has to assume the pointer field were always active. The spec lays out the hacks to avoid in order to work with a compacting GC (eg - don't xor pointers or store them in non-pointer types etc etc). It would presumably be non-trivial to change the compiler and phobos to use a compacting GC which is why Walter hasn't tested it out yet. He has said in the past he knows how it would work, though. It's "just a small matter of programming".
May 02 2005
parent reply "Walter" <newshound digitalmars.com> writes:
"Ben Hinkle" <bhinkle mathworks.com> wrote in message
news:d561g5$2k62$1 digitaldaemon.com...
 "Daniel Horn" <hellcatv hotmail.com> wrote in message
 news:d560sf$2i8q$1 digitaldaemon.com...
 Is this the final say here? So there's no chance for a compacting GC
 because of the examples I have listed below?

I'm not sure what you mean by "no chance". Without the type information being available to the GC there is no chance, I agree. With type

 it should be possible (as long as the bits in phobos that use the address

 a unique id change as well). For the example you gave using a union the GC
 would have to be conservative in that it has to assume the pointer field
 were always active. The spec lays out the hacks to avoid in order to work
 with a compacting GC (eg - don't xor pointers or store them in non-pointer
 types etc etc). It would presumably be non-trivial to change the compiler
 and phobos to use a compacting GC which is why Walter hasn't tested it out
 yet. He has said in the past he knows how it would work, though. It's

 a small matter of programming".

It's a lot of work to implement it. But it shouldn't change existing (non-Phobos) D code, as long as the guidelines are adhered to (i.e. no pointer punning, no storing bit flags in pointers, etc.).
May 03 2005
next sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
Walter wrote:
<snip>
 It's a lot of work to implement it. But it shouldn't change existing
 (non-Phobos) D code, as long as the guidelines are adhered to (i.e. no
 pointer punning, no storing bit flags in pointers, etc.).

Storing bit flags in pointers can already break even with good old-fashioned mark-sweep GC. Though it would depend on whether you use the high-order bits or the low-order bits, and the smallest allocatable block size.... Stewart. -- My e-mail is valid but not my primary mailbox. Please keep replies on the 'group where everyone may benefit.
May 04 2005
prev sibling parent "Andrew Fedoniouk" <news terrainformatica.com> writes:
 It's a lot of work to implement it. But it shouldn't change existing
 (non-Phobos) D code, as long as the guidelines are adhered to (i.e. no
 pointer punning, no storing bit flags in pointers, etc.).

I think that any universal soulution, as always, will have its own price - speed of execution and size of code. I think that it make sense to move such compacting GC out of core of runtime. To make it e.g. as a part of Phobos. So if I do need compacting GC in some application domain I will be able to do something like: mp = new MemoryPool(GC_THRESHOLD, NUM_GENERATIONS, etc); MyClass cls = new myClass in mp; or MyClass cls = new(mp) myClass; Such solution will give at least a choice of what to use rather than "Hop, everybody, all together, move left.... move right... good guys!" Andrew.
May 04 2005
prev sibling parent Sean Kelly <sean f4.ca> writes:
In article <d560sf$2i8q$1 digitaldaemon.com>, Daniel Horn says...
Is this the final say here? So there's no chance for a compacting GC 
because of the examples I have listed below?

I know Walter is interested in making D compatible with compacting garbage collectors as he has comments in the Object class code to this effect. But as no one has implemented one yet, supporting one is really just a "to do" item. Sean
May 02 2005
prev sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
[responding to the subject]

No.

D/26273

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
May 03 2005