[RFC]Proposal for better garbage collection

[Manu]

On 22 February 2012 20:56, Benjamin Thaut <code at benjamin-thaut.de> wrote:

> 2) Tracking references on the stack:
>
> The D compiler always needs to emit a full stack frame so that the GC can
> walk up the stack at any time in the program.


You say "every function needs a stack frame". Can you comment on this with
respect to leaf functions? No leaf function should ever generate a stack
frame, infact, typical leaf functions will never touch memory at all. This
is VERY IMPORTANT for critical loops. I have never worked on a project
where I did not depend on the performance of leaf functions to do the hard
work in the most critical parts of my application.
Obviously such functions would not be making allocations, and shouldn't be
interacting with the GC any way, so why is having a stack frame important?


> The stack frame of every function generated by the D compiler starts which
> a bitfield (*usually the size of a machine register*)...
>

Oh really? And how do we define that type? ;) (*cough* reference to
size_t/ptrdiff_t thread)



> For example on x86: 11001...
> 1 = bytes 0 to 4 are a pointer
> 1 = bytes 4 to 8 are a pointer
> 00 = bytes 8 to 16 are not a pointer
> 1 = bytes 16 to 20 are a pointer
>
> The last bit indicates whether the bitfield is continued in the following
> bytes or not. 1 means continued 0 means finished.
> Every scope generated by the D compiler would need additional code at the
> start and end of the scope. When the scope is entered the bitfield would be
> patched to represent the new variables inside the scope and when the scope
> is left the bitfield is patched again to remove the changes that were made
> on entering the scope.
> Every time a function gets called that did not get generated by the D
> compiler ( C / C++ etc functions) the compiler generates a call into the
> runtime and passes the current stack pointer and stack base pointer to it.
>
> void _d_externalCallStart(void* stackptr, void* baseptr);
>
> Every time such a function returns the compiler   generates a call into
> the the runtime too.
>
> void _d_externalCallEnd(void* stackptr, void* baseptr);
>

Can you comment on what those functions will actually do? It definitely
sounds very worrying to me to be turning every function call into THREE
calls.
Calling into extern code is certainly not rare... almost everything of any
use is an extern C lib. What about interaction with the OS? Trivial libs
like zlib? etc...

I wonder if there are alternative ways to detect a foreign stack. And I'm
not sure why it even matters, you can't depend on the extern ABI, how do
you unwind the stack reliably in the first place?


> Every time a functions that can get called from other languages (extern(C)
> etc) are executed the end callback is inserted at the start of the
> functions and the start callback is inserted at the end of the function.
> Using these callbacks the GC can mark certain parts of the stack as
> "non-D" and ignore them when scanning for bit fields and
> references/pointers. It can just skip parts of the stack that are "non-D"
> and therefore does not need a full stack frame within these "non-D"
> sections.
> All these features are required so that the GC can precisely scan
> pointers/references on the stack and change them as necessary.
> Remaining issues: The D compiler can freely move around value types on the
> stack. With such move operations it would be necessary to fix up all the
> bit fields. I needs to be investigated if this is doable.
>
> 3) Tracking references on the heap
>
> For every class / struct a mixin template which is defined inside the
> runtime gets instantiated. This template can then use introspection to
> generate the necessary information to allow the GC to scan the pointers
> within that struct / class precisely.
>
> 4) Thread local / global memory
>
> A callback into the runtime needs to happen in the following cases:
> - a __gshared variable is assigned
> - a reference / pointer is casted to immutable
> - a reference / pointer is casted to shared
>
> void _d_castToGlobalMem(void* ptr);
>
> This can be used by the GC to keep thread local pools of memory and move a
> memory block to a global memory pool as soon as it is needed there.
>
> 5) pointer / reference changed callback
>
> Every time a pointer / reference is changed the D compiler emits a call
> into the runtime and passes the new value of the reference / pointer with
> it.
>
> void _d_pointerChanged(void *ptr);
>
> This can be used when writing a generational GC to have separate pools for
> young and old generations. Every time the young generation needs to be
> collected it can be avoided to scan the old generations pool because it is
> sufficient to only check the pointers that have changed since the last time
> the young generation was collected. With the above mentioned callback it is
> easily possible to track these references.
>
> Remaining issues:
> -If the GC interrupts a thread right before any of the above mentioned
> callbacks happen it will cause a invalid state for the GC and the GC might
> access invalid pointers. It has to be investigated if this leads to invalid
> behavior. It can be fixed by not interrupting a thread but pause it the
> next time it calls any of callbacks, or other functions that can be
> interrupted by the GC. This in turn could cause a thread to be non pausable
> because it is stuck in a polling loop. The compiler could identify loops
> without any GC interruptible function and manually insert one.
> -When pointers/references are passed inside processor registers the GC
> cannot know if these values are actually pointers/references or represent
> other values. If threads are paused at defined points in the code as
> mentioned before this issues would be fixed because the state at these
> points is known and can be handled accordingly.
>
> 6) Different interface for the GC
>
> The current interface to the GC would have to change because the "this
> block of memory might contain a pointer" approach wouldn't work anymore.
> For example a block of memory and a delegate which iterates over all
> pointers within the memory block could be used for user allocated memory
> blocks. There should be a separate allocator function provided by the GC
> that allocates memory that does not get moved around so it can be used to
> pass it to non garbage collected code.
>
> 7) Compiler Options
>
> Each of the above mentioned groups of features should be exposed as
> compiler options so that you can turn them on/off depending on which type
> of GC you use. Default on/off states for these features are set within a
> config file depending on which type of GC currently ships per default with
> druntime.
>
> 8) Conclusion
>
> Garbage Collection brings a lot of advantages for the programmer using the
> language but is not free and shouldn't be treated as free. Full support for
> garbage collection is required to build a fast and efficient GC. This
> additional support requires additional features within the compiler but
> should result in a overall better performing language.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20120223/d0aff608/attachment-0001.html>