Possible quick win in GC?

[Abdulhaq via Digitalmars-d]

On Monday, 29 September 2014 at 09:45:38 UTC, Mike wrote:
> On Monday, 29 September 2014 at 07:03:29 UTC, Abdulhaq wrote:
>> 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.
>
> Sounds a little like http://wiki.dlang.org/DIP46
>
> Mike

Ah thanks for the link yes there are definite similarities, 
Walter identifies sets of objects to go in his region through 
having a boundary on the pure function. My set is determined by 
static analysis and does not require the function to be pure. 
However, thedeemon has pointed out that this technique is in fact 
well known - I'm left to wonder if I should have a go at an 
implementation, but my wife would not be too chuffed about that.