On 12/11/2011 4:26 PM, Timon Gehr wrote:
> We are talking about supporting precise GC, not about custom runtime
> reflection. There is no way to get precise GC right without compiler
> support.

FWIW my original precise heap scanning patch generated pointer offset information using CTFE and templates.  The code to do this is still in Bugzilla and only took a couple hours to write.

Le 11/12/2011 23:31, Timon Gehr a écrit :
> On 12/11/2011 11:27 PM, deadalnix wrote:
>> Le 11/12/2011 22:26, Timon Gehr a écrit :
>>> On 12/11/2011 10:13 PM, deadalnix wrote:
>>>> Le 11/12/2011 21:55, Timon Gehr a écrit :
>>>>> On 12/11/2011 07:02 PM, deadalnix wrote:
>>>>>> Le 11/12/2011 16:43, Dejan Lekic a écrit :
>>>>>>>
>>>>>>> It would be really great to implement a generational GC similar to
>>>>>>> the
>>>>>>> C4 mentioned in this presentation:
>>>>>>> http://www.infoq.com/presentations/Understanding-Java-Garbage-Collection
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> . There is a research-paper about C4 as well:
>>>>>>> http://dl.acm.org/citation.cfm?id=1993491 .
>>>>>>
>>>>>> This GC (like all compacting GC) require that the GC knows what is a
>>>>>> reference/pointer and what isn't.
>>>>>>
>>>>>> This is possible in D using the compile time reflexion to build a
>>>>>> runtime reflexion. But the standard lib is far away from that. This
>>>>>> will
>>>>>> also bloat the executable with reflexion's data, thing that some
>>>>>> don't
>>>>>> want.
>>>>>
>>>>> The information has to be generated by the compiler, not by the
>>>>> library.
>>>>>
>>>>
>>>> This is not the way choosen by D. And the way choosen by D is, IMO,
>>>> supperior.
>>>>
>>>> D choosed to have compiler time reflexion, but no runtime reflexion
>>>> (compiler won't generate it). Given that, and the great capability of D
>>>> for generic programming, the best solution is to generate
>>>> information at
>>>> using compile time reflexion using a lib, to get runtime reflexion.
>>>>
>>>> Many application do not want the bloat created by runtime reflexion.
>>>> This is up to the user to compile with such a lib or not.
>>>
>>> We are talking about supporting precise GC, not about custom runtime
>>> reflection. There is no way to get precise GC right without compiler
>>> support.
>>
>> It is clearly possible by marking not movable what is possibly pointer
>> in the stack and registers and some runtime reflexion used by the GC.
>
> In *precise GC* speak, 'possibly pointer' is a banned term. You
> understand that? Also compile-time reflection is IMPOSSIBLE if you don't
> have the source code. It cannot work in a meaningful way.
>
> GC support must be built-in. Every attempt to make such a fundamental
> feature depend on the standard library is comical.

Well, you are the only one here talking about a precise GC. The post you reponded to was talking about a compacting GC. Which isn't the same.

So please don't go as hominem. I could do the same but it will ends up nowhere.

On 12/11/2011 11:46 PM, deadalnix wrote:
> Le 11/12/2011 23:31, Timon Gehr a écrit :
>> On 12/11/2011 11:27 PM, deadalnix wrote:
>>> Le 11/12/2011 22:26, Timon Gehr a écrit :
>>>> On 12/11/2011 10:13 PM, deadalnix wrote:
>>>>> Le 11/12/2011 21:55, Timon Gehr a écrit :
>>>>>> On 12/11/2011 07:02 PM, deadalnix wrote:
>>>>>>> Le 11/12/2011 16:43, Dejan Lekic a écrit :
>>>>>>>>
>>>>>>>> It would be really great to implement a generational GC similar to
>>>>>>>> the
>>>>>>>> C4 mentioned in this presentation:
>>>>>>>> http://www.infoq.com/presentations/Understanding-Java-Garbage-Collection
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> . There is a research-paper about C4 as well:
>>>>>>>> http://dl.acm.org/citation.cfm?id=1993491 .
>>>>>>>
>>>>>>> This GC (like all compacting GC) require that the GC knows what is a
>>>>>>> reference/pointer and what isn't.
>>>>>>>
>>>>>>> This is possible in D using the compile time reflexion to build a
>>>>>>> runtime reflexion. But the standard lib is far away from that. This
>>>>>>> will
>>>>>>> also bloat the executable with reflexion's data, thing that some
>>>>>>> don't
>>>>>>> want.
>>>>>>
>>>>>> The information has to be generated by the compiler, not by the
>>>>>> library.
>>>>>>
>>>>>
>>>>> This is not the way choosen by D. And the way choosen by D is, IMO,
>>>>> supperior.
>>>>>
>>>>> D choosed to have compiler time reflexion, but no runtime reflexion
>>>>> (compiler won't generate it). Given that, and the great capability
>>>>> of D
>>>>> for generic programming, the best solution is to generate
>>>>> information at
>>>>> using compile time reflexion using a lib, to get runtime reflexion.
>>>>>
>>>>> Many application do not want the bloat created by runtime reflexion.
>>>>> This is up to the user to compile with such a lib or not.
>>>>
>>>> We are talking about supporting precise GC, not about custom runtime
>>>> reflection. There is no way to get precise GC right without compiler
>>>> support.
>>>
>>> It is clearly possible by marking not movable what is possibly pointer
>>> in the stack and registers and some runtime reflexion used by the GC.
>>
>> In *precise GC* speak, 'possibly pointer' is a banned term. You
>> understand that? Also compile-time reflection is IMPOSSIBLE if you don't
>> have the source code. It cannot work in a meaningful way.
>>
>> GC support must be built-in. Every attempt to make such a fundamental
>> feature depend on the standard library is comical.
>
> Well, you are the only one here talking about a precise GC. The post you
> reponded to was talking about a compacting GC. Which isn't the same.

The post was talking about C4, which I believed was precise. Anyway, a compacting GC which is mostly precise also is very hard to get to work using static reflection features. The user would have to explicitly mark every module with some mixin.

>
> So please don't go as hominem. I could do the same but it will ends up
> nowhere.

I didn't, but you just did. Let's stop.

On 12/11/2011 11:37 PM, dsimcha wrote:
> On 12/11/2011 4:26 PM, Timon Gehr wrote:
>> We are talking about supporting precise GC, not about custom runtime
>> reflection. There is no way to get precise GC right without compiler
>> support.
>
> FWIW my original precise heap scanning patch generated pointer offset
> information using CTFE and templates. The code to do this is still in
> Bugzilla and only took a couple hours to write.

But it is not precise for the stack, right? How much work is left to the programmer to generate the information?

On 12/11/2011 9:41 PM, Timon Gehr wrote:
> On 12/11/2011 11:37 PM, dsimcha wrote:
>> On 12/11/2011 4:26 PM, Timon Gehr wrote:
>>> We are talking about supporting precise GC, not about custom runtime
>>> reflection. There is no way to get precise GC right without compiler
>>> support.
>>
>> FWIW my original precise heap scanning patch generated pointer offset
>> information using CTFE and templates. The code to do this is still in
>> Bugzilla and only took a couple hours to write.
>
> But it is not precise for the stack, right? How much work is left to the
> programmer to generate the information?

It wasn't precise on the stack, but for unrelated reasons.  As far as work left to the programmer, I has created templates for new (which I thought at the time might get integrated into the compiler).  To use the precise heap scanning, all you had to do was:

class C {
    void* ptr;
    size_t integer;
}

void main() {
    auto instance = newTemplate!C();
}

On Sun, 11 Dec 2011 10:43:14 -0500, Dejan Lekic <dejan.lekic@gmail.com> wrote:
>
> It would be really great to implement a generational GC similar
> to the C4 mentioned in this presentation:
> http://www.infoq.com/presentations/Understanding-Java-Garbage-Collection
> . There is a research-paper about C4 as well:
> http://dl.acm.org/citation.cfm?id=1993491 .
>

C4 is really an impressive GC operating system/runtime for JAVA. But, like many advance GCs it is really impressive because of the restrictions of the JVM memory model. First, most of the really awesome features of C4 (like scaling to 50GB of ram with 10 msec pauses) are entirely due to that fact that C4 is an operating system. C4 works through a bunch of memory interrupts that are not available to user-mode code on Windows, Linux, OSX, etc. Impressive work I'd like to see integrated into said OSes, but that's unlikely to happen soon. Second, being a systems language means that D can not implement a lot of GC algorithms including copying, generational and the good concurrent collectors. In D we are really limited in terms of GC strategies; for example, the concurrent D garbage collector (CDGC) leverages *nix specific OS features to work, and the general concurrency strategy it uses is IIRC slower than the JAVA concurrent collectors. D can also go with thread-local GCs, which are very competitive, but would introduce regions to D's memory model.

Also, the presence of D's structs and use stack allocation greatly increases the average lifetime of objects in general and decreases the need for generational collectors.

On Sun, Dec 11, 2011 at 10:55 PM, Robert Jacques <sandford@jhu.edu> wrote:
> Second, being a systems language means that D can not implement a lot of
GC algorithms including copying, generational and the good concurrent collectors.

What about being a systems language prevents generational?  The page on garbage collection on the D website says while it doesn't use a generational GC it will some day and gives tips on what to avoid so you don't fall victim to the behavior of a moving GC.

On 12/12/2011 03:56 AM, dsimcha wrote:
> On 12/11/2011 9:41 PM, Timon Gehr wrote:
>> On 12/11/2011 11:37 PM, dsimcha wrote:
>>> On 12/11/2011 4:26 PM, Timon Gehr wrote:
>>>> We are talking about supporting precise GC, not about custom runtime
>>>> reflection. There is no way to get precise GC right without compiler
>>>> support.
>>>
>>> FWIW my original precise heap scanning patch generated pointer offset
>>> information using CTFE and templates. The code to do this is still in
>>> Bugzilla and only took a couple hours to write.
>>
>> But it is not precise for the stack, right? How much work is left to the
>> programmer to generate the information?
>
> It wasn't precise on the stack, but for unrelated reasons. As far as
> work left to the programmer, I has created templates for new (which I
> thought at the time might get integrated into the compiler).

That is compiler support. ;)

> To use the
> precise heap scanning, all you had to do was:
>
> class C {
> void* ptr;
> size_t integer;
> }
>
> void main() {
> auto instance = newTemplate!C();
> }

Ok, nice. I template my allocations anyway. (even though it creates some bloat)

dsimcha:

> My optimizations make very little difference on this benchmark, but for good reason:  It's not a very good GC benchmark.  I ran it with my GC profiling code enabled and it only spends around 10% of its execution time in GC.  We need to figure out why else this benchmark may be so slow.

Thank you for your timings. At the moment I don't know why this D program is slow.

Bye,
bearophile

On Mon, 12 Dec 2011 01:06:14 -0500, Brad Anderson <eco@gnuk.net> wrote:

> On Sun, Dec 11, 2011 at 10:55 PM, Robert Jacques <sandford@jhu.edu> wrote:
>> Second, being a systems language means that D can not implement a lot of
> GC algorithms including copying, generational and the good concurrent
> collectors.
>
> What about being a systems language prevents generational?  The page on
> garbage collection on the D website says while it doesn't use a
> generational GC it will some day and gives tips on what to avoid so you
> don't fall victim to the behavior of a moving GC.

Regarding moving collectors.
D supports semi-precise collection. Therefore D can support some types of moving collectors, i.e. compactors, which is what the website is talking about. Copying collectors, on the other hand, require full precision to work; you must be able to fully evacuate a region of memory. D doesn't support full precision, for a couple of performance (unions, the call stack,C/C++ interop) and technical reasons (the inline assembler).

Regarding generational collectors.
Both generational and concurrent collectors require that every pointer assignment is known to the compiler, which then instruments the assignment to flag mark bits, etc. For generational collectors, you need this information to know which objects/memory pages to search for roots into the young generation. Without this information, you have to search the entire heap, i.e. do a full collection. Again, both performance and technical reasons come into play here. Instrumentation represents a performance cost, which even if it pays for itself, looks bad in newsgroups posting. Indeed, concurrent collectors are mostly about trading throughput for latency. So, like JAVA, you'd want to use version statements to select your GC style, but you'd also have to make sure your entire codebase was compiled with the same flags; with 3rd party DLLs and objects, this can become non-trivial. From a technical perspective, complete pointer assignment instrumentation is a non-starter because the D compiler doesn't have complete access to all the code; both C/C++ and assembler code can modify pointers and are not subject to instrumentation. Now, if we supported C/C++ through marshaling, like JAVA and C# do, and made the assembler a bit more smart or required manual pointer instrumentation of asm code, we could use these types of collectors.

* Note that the above doesn't take into account the types of virtual memory tricks C4 can do, which may open these algorithms up to D and other system programming languages.