View mode: basic / threaded / horizontal-split · Log in · Help
May 01, 2005
Can the current D handle a compacting garbage collector
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
Re: Can the current D handle a compacting garbage collector
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 02, 2005
Re: Can the current D handle a compacting garbage collector
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
Re: Can the current D handle a compacting garbage collector
"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
Re: Can the current D handle a compacting garbage collector
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 03, 2005
Re: Can the current D handle a compacting garbage collector
[responding to the subject]

No.

http://www.digitalmars.com/drn-bin/wwwnews?D/26273

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on 
the 'group where everyone may benefit.
May 04, 2005
Re: Can the current D handle a compacting garbage collector
"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
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".

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 04, 2005
Re: Can the current D handle a compacting garbage collector
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
Re: Can the current D handle a compacting garbage collector
> 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.
Top | Discussion index | About this forum | D home