Is a moving GC really needed?

[Chad J]

xs0 wrote:
> Chad J > wrote:
> 
>> xs0 wrote:
>>
>>>
>>> While I'm no expert, I doubt a moving GC is even possible in a 
>>> systems language like D.
>>>
>>> First, if you move things around, you obviously need to be precise 
>>> when updating pointers, lest all hell breaks loose. But how do you 
>>> update
>>>
>>> union {
>>>     int a;
>>>     void* b;
>>> }
>>>
>>> ? While you could forbid overlap of pointers and non-pointer data, 
>>> what about custom allocators, assembler, C libraries (including OS 
>>> runtime!), etc.?
>>
>>
>> For the union, I might suggest a more acceptable tradeoff - mandate 
>> that some data be inserted before every union to tell the gc which 
>> member is selected at any moment during program execution.  Whenever 
>> an assignment is done to the union, code is inserted to update the 
>> union's status.  So your union would look more like this:
>>
>> enum StructStatus
>> {
>>   a,
>>   b,
>> }
>>
>> struct
>> {
>>   StructStatus status; //or size_t, whichever works
>>
>>   union
>>   {
>>     int a;
>>     void* b;
>>   }
>> }
> 
> 
> Well, you can't simply mandate that, I think.. It can be the case that 
> the exact structure of a struct/union is mandated by requirements 
> external to the application..
> 

I think you can though, the same way that all D classes are prepended by 
a pointer to a vtable and a 'monitor', or the same way that dynamic 
arrays have not just a pointer, but an added length variable.

> And, even if it was an option, it doesn't really solve the precision 
> issue. To be precise, the GC must know the internal structure of 
> anything on its heap, which I don't think is possible unless the 
> language was severely restricted or it was required that the programmer 
> supplies that information manually whenever the purpose of a part of 
> memory changes from pointer to non-pointer and vice-versa. Both options 
> suck quite a lot.
> 

But it can be precise with said union.  It will know at compile time 
where all of the unions are stored, in the same way it knows where 
pointers are stored.  Then, when it looks at the unions, it determines 
at runtime whether or not they contain pointers by using the extra 
member info.  Either the member info says the current member is a 
pointer, or it says that the current member isn't a pointer.  There is 
no maybe.

IMO this is not a severe restriction, and it does not require any 
programmer intervention.  The compiler writes all of the code that sets 
unions' member info variables, and to the programmer the member info is 
readonly and needs no maintenance.

> 
>> Not sure how custom allocators mess up the GC, I thought these were 
>> just on their own anyways.  If a pointer to something is outside of 
>> the GC heap, the GC doesn't bother changing it or collecting it or 
>> moving anything.
> 
> 
> That's true, but a custom allocator can use the GC heap if it wants. For 
> example, if I know I'll be allocating a million linked list nodes, and 
> will then release them all at once, it can be considerably faster to 
> allocate a large byte[] and use chunks of it for my nodes. But how can 
> the GC tell which of those bytes are pointers and which aren't? At the 
> beginning none are, but later some may be..
> 

Hmmm.  In the case of the allocator I think it is the allocator writer's 
responsibility to use gc.addRange() on all of the pointers that they 
toss into the byte[].  What bugs me now though, is other arbitrary data 
cases, like std.boxer.

So far the only answer I can think of is to make people dealing with 
arbitrarily typed data be very careful about gc.addRange'ing and 
gc.removeRange'ing any references that goes into or out of their 
arbitrarily typed data, which does suck.

> 
>> Assembler is a bit tricky, maybe someone smarter than I can handle it 
>> better, but here's a shot with some psuedoasm:
>>
>> struct Foo
>> {
>>   int member1;
>>   int member2;
>> }
>> Foo bar;
>>
>> ...
>>
>> Foo* foo = &bar;
>> int extracted;
>> // foo spotted in the assembly block, never mind the context
>> // as such, foo gets pinned.
>> asm
>> {
>>   mov EAX, foo;         // EAX = foo;
>>   add EAX, 4;           // EAX += 4;
>>   mov extracted, [EAX]; // extracted = *EAX; or extracted = foo.member2;
>> }
>> // foo is unpinned here
> 
> 
> I'm sure simple cases can be detected, but am also fairly certain it's 
> impossible to generally determine which registers hold pointers and 
> which don't, and/or what will get referenced and what won't.
> 

Yeah, I realized stuff like ASM that rewrites/rearranges the stack would 
mess up the GC.  Perhaps we just need a comprehensive list of do's, 
dont's, and workarounds in D asm programming?

> 
>> As for C libraries, it seems like the same thing as custom allocators. 
>> The C heap is outside of the GC's jurisdiction and won't be moved or 
>> manipulated in any way.  C code that handles D objects will have to be 
>> careful, and the callee D code will have to pin the objects before the 
>> go out into the unknown.
> 
> 
> I meant precision again, not C's heap. Even if compiled D code somehow 
> notifies the GC what's on the stack, the C code definitely won't. Then, 
> how can the GC tell which parts of the stack point to its own heap, and 
> which are just integers that happen to look like they could point to the 
> heap?
> 

It already knows where pointers are in each frame of the stack for D 
code, can't we make it also know which frames aren't D code at all?  For 
the C code frames it doesn't look at them at all.  Any D code that could 
let references out into C code (only way I know of is with extern(C)) 
should pin that object on the D side and keep a reference until 
execution has returned to D.

> 
>> Also, I wonder, if I were to make a tool that does escape analysis on 
>> your program, then finds that a number of classes can either be stack 
>> allocated or safely deleted after they reach a certain point in the 
>> code, then would this change the effectiveness of a generational GC? 
>> Perhaps part of why young objects die so often is because they are 
>> temporary things that can often be safely deleted at the end of scope 
>> or some such.
> 
> 
> Well, I think it's quite hard to guess whether the result would be 
> better or worse, speed-wise. Obviously, allocating those objects on the 
> stack would speed things up, while using generations in the GC would be 
> less effective, because the GC would see less short-lived objects. I've 
> no idea, however, how those two effects would combine.. Most probably it 
> depends very much on the actual application (as do most things ;)
> 
> 
> xs0