[RFC]Proposal for better garbage collection

[Dmitry Olshansky]

On 22.02.2012 22:56, Benjamin Thaut wrote:
> As I'm not satisfied with the current GC D has and don't see the
> situation improving in the future without significant changes to the
> compiler I wrote the following document that points out all the possible
> issues with garbage collection I could think of and possible solutions
> for them. This document is just a draft and only a proposal, critics and
> comments are welcome.
>
> Kind Regards
> Benjamin Thaut
>
>
> 1) Preface
>
> All modern Languages with fast and efficient GCs have build in support
> for garbage collection within the compiler / virtual machine. Currently
> the D language does have as much GC support as C++ has but fully relies
> on the GC with a lot of language features and the standard library. As a
> result the GC is slow, non parallel and always needs to stop all threads
> before collection. This document suggests to build in better support for
> garbage collection into the language so that creating a fast and
> efficient GC becomes possible. A list of features that would be required
> is described in this document.
>
> 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.

  I think walking up the stack to collect this info again and again (the 
stack has a lot of "heavy frames" on the bottom, right?) sounds like a 
tremendously slow way of getting necessary memory ranges. I'm no expert 
though.

The stack frame of
> every function generated by the D compiler starts which a bitfield
> (usually the size of a machine register) where each bit indicates that
> these bytes are a pointer / reference. The bitfield needs to be large
> enough to cover the whole stack frame of the function.
>
> 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.

Again I'm no expert, but what happens when GC starts collecting a thread 
stack amid this patching operation?

> 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);
>

Why would you need these? And if you start calling callback on every 
operation, you may just as well pass direct ranges of memory to GC 
without stack walk.
+ you can call D function from C one that in turn calls D one, think 
extern(C) and callbacks.

> 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.

Bye-bye any speed of p++ ? I mean I'm horrified, and I bet I'm not alone.

>
> 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.

Combinatorial explosion of sets of options that doesn't necessary allow 
a particular GC?
>
> 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.

Well, that was critic ;)

-- 
Dmitry Olshansky