May 01, 2005
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
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
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
"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
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
[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
"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
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
> 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