Thread overview
[Dlang-study] [lifetime] Local garbage collector for pure functions
Dec 23, 2015
Ralph Tandetzky
Dec 24, 2015
Amaury SECHET
Dec 25, 2015
Marc Schütz
December 23, 2015
Some pure functions use the garbage collector, but the allocated memory cannot escape the function due to its signature. Therefore all the created garbage could be locally collected at function exit.

    int f( const int[] arr ) pure; // @localgc ?

The only requirements on the function would be, that they are pure and that return types and argument types do not allow allocated memory to escape.

And here's how I imagine it to work: At function entry the GC could be instructed to use a region allocator. At function exit the whole allocated memory is discarded all at once. The only problem I see with this, is that internally functions could be called which allocate memory in a tight loop producing to much garbage. Hence, collecting the garbage may be necessary in extreme cases. Therefore, the region allocator should not allow to much memory to be allocated, but fall back to garbage collection, if a lot of memory is requested. The good news is though, that this garbage collection can be local to our pure function.

Therefore, it is not necessary to freeze the whole application or to scan the whole stack and global memory. Instead, only the running thread needs to scan the stack from our function upwards and the local pool of allocated memory and collect there.

Pushing it all a little further: In templated code, where the all function definitions are visible to the compiler and no allocations are done in loops, heap allocations could be transformed into stack allocations by the compiler and the functions could even be marked @nogc. Standard library algorithms could use lambdas with captures like crazy again and do things idiomatically and functional in D while still ensuring @nogc.

What do you think?
_______________________________________________
Dlang-study mailing list
[email protected]
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

December 24, 2015
Very nice idea, and realizable regardless of other work on lifetime management. Could you please submit it as a bugzilla issue?

Thanks much, awesome idea!


Andrei

On 12/23/2015 07:49 AM, Ralph Tandetzky wrote:
> Some pure functions use the garbage collector, but the allocated memory
> cannot escape the function due to its signature. Therefore all the
> created garbage could be locally collected at function exit.
>
>      int f( const int[] arr ) pure; // @localgc ?
>
> The only requirements on the function would be, that they are pure and
> that return types and argument types do not allow allocated memory to
> escape.
>
> And here's how I imagine it to work: At function entry the GC could be
> instructed to use a region allocator. At function exit the whole
> allocated memory is discarded all at once. The only problem I see with
> this, is that internally functions could be called which allocate memory
> in a tight loop producing to much garbage. Hence, collecting the garbage
> may be necessary in extreme cases. Therefore, the region allocator
> should not allow to much memory to be allocated, but fall back to
> garbage collection, if a lot of memory is requested. The good news is
> though, that this garbage collection can be local to our pure function.
>
> Therefore, it is not necessary to freeze the whole application or to
> scan the whole stack and global memory. Instead, only the running thread
> needs to scan the stack from our function upwards and the local pool of
> allocated memory and collect there.
>
> Pushing it all a little further: In templated code, where the all
> function definitions are visible to the compiler and no allocations are
> done in loops, heap allocations could be transformed into stack
> allocations by the compiler and the functions could even be marked
> @nogc. Standard library algorithms could use lambdas with captures like
> crazy again and do things idiomatically and functional in D while still
> ensuring @nogc.
>
> What do you think?
> _______________________________________________
> Dlang-study mailing list
> [email protected]
> http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study
_______________________________________________
Dlang-study mailing list
[email protected]
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

December 24, 2015
Not only this is desirable but in fact this is REQUIRED to implemented any kind of qualifier aware GC in D. pure function returns can be promoted to various heaps, so you need to segregate them somehow.

2015-12-24 7:51 GMT+01:00 Andrei Alexandrescu <[email protected]>:

> Very nice idea, and realizable regardless of other work on lifetime management. Could you please submit it as a bugzilla issue?
>
> Thanks much, awesome idea!
>
>
> Andrei
>
>
> On 12/23/2015 07:49 AM, Ralph Tandetzky wrote:
>
>> Some pure functions use the garbage collector, but the allocated memory cannot escape the function due to its signature. Therefore all the created garbage could be locally collected at function exit.
>>
>>      int f( const int[] arr ) pure; // @localgc ?
>>
>> The only requirements on the function would be, that they are pure and that return types and argument types do not allow allocated memory to escape.
>>
>> And here's how I imagine it to work: At function entry the GC could be instructed to use a region allocator. At function exit the whole allocated memory is discarded all at once. The only problem I see with this, is that internally functions could be called which allocate memory in a tight loop producing to much garbage. Hence, collecting the garbage may be necessary in extreme cases. Therefore, the region allocator should not allow to much memory to be allocated, but fall back to garbage collection, if a lot of memory is requested. The good news is though, that this garbage collection can be local to our pure function.
>>
>> Therefore, it is not necessary to freeze the whole application or to scan the whole stack and global memory. Instead, only the running thread needs to scan the stack from our function upwards and the local pool of allocated memory and collect there.
>>
>> Pushing it all a little further: In templated code, where the all function definitions are visible to the compiler and no allocations are done in loops, heap allocations could be transformed into stack allocations by the compiler and the functions could even be marked @nogc. Standard library algorithms could use lambdas with captures like crazy again and do things idiomatically and functional in D while still ensuring @nogc.
>>
>> What do you think?
>> _______________________________________________
>> Dlang-study mailing list
>> [email protected]
>> http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study
>>
> _______________________________________________
> Dlang-study mailing list
> [email protected]
> http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study
>


December 25, 2015
This is a very nice idea. Note that LDC already transforms certain GC allocations into stack allocations, but only as an optimization. There need to be fixed rules about which kinds of allocations are guaranteed to be moved to the stack or a dedicated region allocator.

By the way, you seem to have in mind a special function attribute, but this isn't necessary. In fact, apart from making the function @nogc, how it allocates is memory is purely an implementation detail. Your suggestions therefore don't require (formal) purity or any special attribute in the function signature.
_______________________________________________
Dlang-study mailing list
[email protected]
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study