digitalmars.D - Can the current D handle a compacting garbage collector
- Daniel Horn (26/26) May 01 2005 IMO D shouldn't go 1.0 at least until there is an example compacting
- Andrew Fedoniouk (27/54) May 01 2005 There are two poles in the programming world :
- Daniel Horn (3/62) May 02 2005 Is this the final say here? So there's no chance for a compacting GC
- Ben Hinkle (14/16) May 02 2005 I'm not sure what you mean by "no chance". Without the type information
- Walter (8/23) May 03 2005 information
- Stewart Gordon (10/13) May 04 2005 Storing bit flags in pointers can already break even with good
- Andrew Fedoniouk (12/15) May 04 2005 I think that any universal soulution, as always, will have its own price...
- Sean Kelly (5/7) May 02 2005 I know Walter is interested in making D compatible with compacting garba...
- Stewart Gordon (7/7) May 03 2005 [responding to the subject]
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
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
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
"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...informationIs 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 typeit should be possible (as long as the bits in phobos that use the addressasa 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"justa 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
Stewart Gordon <smjg_1998 yahoo.com> 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.
May 04 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 02 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 03 2005