Possible quick win in GC?

[Abdulhaq via Digitalmars-d]

On Sunday, 28 September 2014 at 20:20:29 UTC, David Nadlinger 
wrote:
> On Sunday, 28 September 2014 at 16:29:45 UTC, Abdulhaq wrote:
>> I got the idea after thinking that it should be fairly simple 
>> for the compiler to detect straightforward cases of when a 
>> variable can be declared as going on the stack - i.e. no 
>> references to it are retained after its enclosing function 
>> returns.
>
> LDC does the "fairly simple" part of this already in a custom 
> LLVM optimizer pass. The issue is that escape analysis is 
> fairly hard in general, and currently even more limited because 
> we only do it on the LLVM IR level (i.e. don't leverage any 
> additional attributes like scope, pure, … that might be present 
> in the D source code).
>
> David

That's interesting, yes I guessed that the escape analysis would 
present the harder part, but I'm hoping that the algorithm can be 
built up incrementally, identifying the easy wins first and then 
over time extending it to cover harder cases.

One way that I see it working it is to conduct a form of lowering 
where the new operator has some information added to it to 
indicate the 'band' that the GC should place the non-root objects 
into (root objects go on the stack). Using the syntax of C++'s 
placement new (but totally different semantics) code could be 
lowered to e.g.

External externalObj = new(0) External(); // 0 means use the 
default heap
Foo foo = new(0x1234) Foo(); // 0x1234 is the heap/band id for 
this set of objects
...
Bar bar = new (0x1234) Bar();

When the GC allocates memory it does so in the indicated 
band/heap, and then when foo (the root object of the object 
graph) goes out of scope the relevant band/heap is destroyed en 
bloc. The benefit of the idea is that when scanning for objects  
that can be deleted the GC does not need to consider those 
objects in the non default bands/heaps. For some classes of 
programs such as compilers (it was Higgs that gave me the 
stimulus), and with good static analysis (aye there's the rub 
cap'n) this could represent a very substantial time saving on ech 
GC sweep.