View mode: basic / threaded / horizontal-split · Log in · Help
January 22, 2007
Transitioning to a type aware Garbage Collector
To improve GC performance, we need to transition to a GC that is aware 
of the types of what it is allocating.

So problems can happen if the type of allocated memory is changed after 
it is allocated, via casting. The way to avoid this is to allocate as 
void[] memory that will be cast, as in:

struct Foo { ... };
Foo[] f;

p = new void[100];
f = cast(Foo[])p;	// ok
byte[] b = cast(byte[])p;
f = cast(Foo[])b;	// ok, GC still regards memory as void[]

rather than:

p = new byte[100];
f = cast(Foo[])p;	// will likely eventually corrupt memory

The GC will regard void[] as a chunk of memory containing arbitrary data 
of arbitrary types, and so will treat it conservatively.

In general, regard memory allocated by the GC as anything other than 
void[] as being *strongly typed*.
January 22, 2007
Re: Transitioning to a type aware Garbage Collector
Walter Bright wrote:
> 
> In general, regard memory allocated by the GC as anything other than 
> void[] as being *strongly typed*.

I very much agree.  This is already an assumption in Tango and a failure 
to comply will result in undefined behavior.


Sean
January 22, 2007
Re: Transitioning to a type aware Garbage Collector
Walter Bright wrote:
> To improve GC performance, we need to transition to a GC that is aware 
> of the types of what it is allocating.
> 
> So problems can happen if the type of allocated memory is changed after 
> it is allocated, via casting. The way to avoid this is to allocate as 
> void[] memory that will be cast, as in:
> 
> struct Foo { ... };
> Foo[] f;
> 
> p = new void[100];
> f = cast(Foo[])p;    // ok
> byte[] b = cast(byte[])p;
> f = cast(Foo[])b;    // ok, GC still regards memory as void[]
> 
> rather than:
> 
> p = new byte[100];
> f = cast(Foo[])p;    // will likely eventually corrupt memory
> 
> The GC will regard void[] as a chunk of memory containing arbitrary data 
> of arbitrary types, and so will treat it conservatively.
> 
> In general, regard memory allocated by the GC as anything other than 
> void[] as being *strongly typed*.

Yay!  Will there also be explicit calls to take specific ranges out of 
the scan list if needed? (Or to tell the GC what type a void-allocated 
chunk has changed to.)

--bb
January 22, 2007
Re: Transitioning to a type aware Garbage Collector
Walter Bright wrote:
> To improve GC performance, we need to transition to a GC that is aware 
> of the types of what it is allocating.
> 
> So problems can happen if the type of allocated memory is changed after 
> it is allocated, via casting. The way to avoid this is to allocate as 
> void[] memory that will be cast, as in:
> 
> struct Foo { ... };
> Foo[] f;
> 
> p = new void[100];
> f = cast(Foo[])p;    // ok
> byte[] b = cast(byte[])p;
> f = cast(Foo[])b;    // ok, GC still regards memory as void[]
> 
> rather than:
> 
> p = new byte[100];
> f = cast(Foo[])p;    // will likely eventually corrupt memory
> 
> The GC will regard void[] as a chunk of memory containing arbitrary data 
> of arbitrary types, and so will treat it conservatively.
> 
> In general, regard memory allocated by the GC as anything other than 
> void[] as being *strongly typed*.

Sounds great. Any possibility to type memory post factum (useful in e.g. 
implementing allocators)? That is, allocate memory as void[] and then 
mark it to be of type Foo.

Andrei
January 22, 2007
Re: Transitioning to a type aware Garbage Collector
Walter Bright wrote:
> To improve GC performance, we need to transition to a GC that is aware 
> of the types of what it is allocating.
> 
> So problems can happen if the type of allocated memory is changed after 
> it is allocated, via casting. The way to avoid this is to allocate as 
> void[] memory that will be cast, as in:
> 
> struct Foo { ... };
> Foo[] f;
> 
> p = new void[100];
> f = cast(Foo[])p;    // ok
> byte[] b = cast(byte[])p;
> f = cast(Foo[])b;    // ok, GC still regards memory as void[]
> 
> rather than:
> 
> p = new byte[100];
> f = cast(Foo[])p;    // will likely eventually corrupt memory
> 
> The GC will regard void[] as a chunk of memory containing arbitrary data 
> of arbitrary types, and so will treat it conservatively.
> 
> In general, regard memory allocated by the GC as anything other than 
> void[] as being *strongly typed*.

Very nice!

-- 
Kirk McDonald
Pyd: Wrapping Python with D
http://pyd.dsource.org
January 22, 2007
Re: Transitioning to a type aware Garbage Collector
Walter Bright wrote:
> To improve GC performance, we need to transition to a GC that is aware 
> of the types of what it is allocating.
> 
> So problems can happen if the type of allocated memory is changed after 
> it is allocated, via casting. The way to avoid this is to allocate as 
> void[] memory that will be cast, as in:
> 
> struct Foo { ... };
> Foo[] f;
> 
> p = new void[100];
> f = cast(Foo[])p;    // ok
> byte[] b = cast(byte[])p;
> f = cast(Foo[])b;    // ok, GC still regards memory as void[]
> 
> rather than:
> 
> p = new byte[100];
> f = cast(Foo[])p;    // will likely eventually corrupt memory
> 
> The GC will regard void[] as a chunk of memory containing arbitrary data 
> of arbitrary types, and so will treat it conservatively.
> 
> In general, regard memory allocated by the GC as anything other than 
> void[] as being *strongly typed*.

As this move happens, some interesting possibilities open for more 
efficient garbage collection. One innovation is CBGC, connectivity based 
garbage collection.

The paper describing this class of algorithm can be found here: 
http://portal.acm.org/citation.cfm?id=949337&coll=GUIDE&dl=ACM&CFID=6079566&CFTOKEN=11708043

I have done an extensive review of the literature regarding garbage 
collection in compiled languages (and others) and this seems to me to be 
the best bet for a modern GC for D.

Thoughts?
January 22, 2007
Re: Transitioning to a type aware Garbage Collector
Andrei Alexandrescu (See Website For Email) wrote:
> Sounds great. Any possibility to type memory post factum (useful in e.g. 
> implementing allocators)? That is, allocate memory as void[] and then 
> mark it to be of type Foo.

Looks like that will have to be implemented.
January 22, 2007
Re: Transitioning to a type aware Garbage Collector
Walter Bright wrote:
> Andrei Alexandrescu (See Website For Email) wrote:
> 
>> Sounds great. Any possibility to type memory post factum (useful in 
>> e.g. implementing allocators)? That is, allocate memory as void[] and 
>> then mark it to be of type Foo.
> 
> 
> Looks like that will have to be implemented.

Tango could certainly use this in its IO-Protocol layer
January 23, 2007
Re: Transitioning to a type aware Garbage Collector
Kyle Furlong wrote:
> Walter Bright wrote:
>> To improve GC performance, we need to transition to a GC that is aware 
>> of the types of what it is allocating.
>>
>> So problems can happen if the type of allocated memory is changed 
>> after it is allocated, via casting. The way to avoid this is to 
>> allocate as void[] memory that will be cast, as in:
>>
>> struct Foo { ... };
>> Foo[] f;
>>
>> p = new void[100];
>> f = cast(Foo[])p;    // ok
>> byte[] b = cast(byte[])p;
>> f = cast(Foo[])b;    // ok, GC still regards memory as void[]
>>
>> rather than:
>>
>> p = new byte[100];
>> f = cast(Foo[])p;    // will likely eventually corrupt memory
>>
>> The GC will regard void[] as a chunk of memory containing arbitrary 
>> data of arbitrary types, and so will treat it conservatively.
>>
>> In general, regard memory allocated by the GC as anything other than 
>> void[] as being *strongly typed*.
> 
> As this move happens, some interesting possibilities open for more 
> efficient garbage collection. One innovation is CBGC, connectivity based 
> garbage collection.
> 
> The paper describing this class of algorithm can be found here: 
> http://portal.acm.org/citation.cfm?id=949337&coll=GUIDE&dl=ACM&CFID=6079566&CFTOKEN=11708043 
> 
> 
> I have done an extensive review of the literature regarding garbage 
> collection in compiled languages (and others) and this seems to me to be 
> the best bet for a modern GC for D.
> 
> Thoughts?

From what little I know of the approach, I agree.  A strongly typed 
moving GC may be a bit unrealistic, but CBGB seems a pretty solid 
compromise.


Sean
January 23, 2007
Re: Transitioning to a type aware Garbage Collector
Walter Bright wrote:
> To improve GC performance, we need to transition to a GC that is aware 
> of the types of what it is allocating.

This is awesome.  This is my number one wish for D.  I can't wait.

-Joel
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home