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.
