View mode: basic / threaded / horizontal-split · Log in · Help
December 26, 2011
Re: Carmack about static analysis
Le 26/12/2011 05:23, Andrei Alexandrescu a écrit :
> On 12/25/11 8:56 PM, deadalnix wrote:
>> Le 25/12/2011 05:27, Andrei Alexandrescu a écrit :
>>> Got the GC book this morning, already read 2.5 chapters :o).
>>>
>>>
>>> Andrei
>>>
>>
>> You'll find that you can do a lot when GC is aware of immutability (in
>> functionnal languages, most things tends to be immutable).
>>
>> In the actual state of druntime, the GC is bad, but worse, cannot be
>> imporoved to take advantage of this, and never will unless a major
>> changement is done in GC interface.
>
> What changes do you have in mind?

I think GC should be aware of immutable/shared on type qualifier.

Thread lcoal can be collected in a given thread without caring about 
others. immutable can be used as great advantage to collect concurrently.

>
> I've gone through a larger portion of the book and one thing has become
> very clear to me: we must improve the precision of the collector. This
> would be a gating feature towards taking the GC pretty much anywhere.
>
> As a first step, we must make all allocations except stack type-aware,
> and leave only the stack to be imprecise.
>

I dpo agree. However, this will generate a lot of code bloat. This seems 
to be an issue for many people (see topic on static this and executable 
size for more on that).

This tell us that we need a way to choose between GC. (just like JVM does).

For swap friendlyness, we can separate memory blocks that may contains 
pointer and the ones that cannot. If something is swapped, the GC 
soesn"t need to go throuw it and generate a huge amount of (slow as 
hell) IO.

For the same reason, we may want to use different memory blocks for TLS 
of each thread. If a thread is sleeping and swapped you don't want an 
working thread to prevent this memory to go on swap. The exemple or 
Chrome browser on a notebook is very explicit on that point : it has a 
huge memory footprint and will swap almost inevitably on thoses 
machines. However, it keep being fast because each tab has its own 
memory pool and a tab that hasn't the focus can be swapped almost 
completely. Firefox has a smaller memory fooprint, however, users 
complains more about its memory consuption. Because they are not aware 
of want is really different. Firefox consume less memory, but is way 
less cache friendly and slow down dramatically when it has to swap.

This is a big topic, and we may want to start a topic on that point 
specifically instead of hijacking this thread.
December 26, 2011
Re: Carmack about static analysis
On 2011-12-26 05:23, Andrei Alexandrescu wrote:
> On 12/25/11 8:56 PM, deadalnix wrote:
>> Le 25/12/2011 05:27, Andrei Alexandrescu a écrit :
>>> Got the GC book this morning, already read 2.5 chapters :o).
>>>
>>>
>>> Andrei
>>>
>>
>> You'll find that you can do a lot when GC is aware of immutability (in
>> functionnal languages, most things tends to be immutable).
>>
>> In the actual state of druntime, the GC is bad, but worse, cannot be
>> imporoved to take advantage of this, and never will unless a major
>> changement is done in GC interface.
>
> What changes do you have in mind?
>
> I've gone through a larger portion of the book and one thing has become
> very clear to me: we must improve the precision of the collector. This
> would be a gating feature towards taking the GC pretty much anywhere.
>
> As a first step, we must make all allocations except stack type-aware,
> and leave only the stack to be imprecise.
>
> A tactical detail of the above has become equally clear to me - we MUST
> use D's reflection and introspection capabilities in increasing the
> precision of the collector.
>
> It's fairly easy to write a generic function mark() (as in the "mark"
> stage of the mark/sweep collector) that accepts any object type with
> indirections (class, array, associative array, pointer to struct). The
> function marks the pointer and then iterates through all fields of the
> object and recurses to itself to mark other reference/pointer/etc fields
> of the object.
>
> This one generic function obviates a lot of the code necessary today for
> conservatively marking pointers, and also reduces and simplifies
> enormously the new code that would otherwise be needed in order to
> define precise collection.
>
> Pointers to instances of that generic functions would be accessible from
> each allocated block; to transitively mark the block, the function is
> called via pointer.
>
> Essentially instances of that function (which I estimate to a 50-liner)
> would take care of mark() for the entire universe of D types - a
> humongous success of compile-time reflection.
>
>
> Andrei

What about the parallel/concurrent collector that has been linked a 
couple of times in this newsgroup. Would that be possible and a good 
idea to implement?

-- 
/Jacob Carlborg
December 26, 2011
Re: Carmack about static analysis
On 12/26/11 6:53 AM, Jacob Carlborg wrote:
> What about the parallel/concurrent collector that has been linked a
> couple of times in this newsgroup. Would that be possible and a good
> idea to implement?

A parallel collector would be, of course, a valuable addition.

Andrei
December 26, 2011
Re: Carmack about static analysis
On 2011-12-26 15:52, Andrei Alexandrescu wrote:
> On 12/26/11 6:53 AM, Jacob Carlborg wrote:
>> What about the parallel/concurrent collector that has been linked a
>> couple of times in this newsgroup. Would that be possible and a good
>> idea to implement?
>
> A parallel collector would be, of course, a valuable addition.
>
> Andrei

This is the collector I was referring to: 
http://www.artima.com/lejava/articles/azul_pauseless_gc.html

-- 
/Jacob Carlborg
December 26, 2011
Re: Carmack about static analysis
Le 26/12/2011 05:23, Andrei Alexandrescu a écrit :
> I've gone through a larger portion of the book and one thing has become
> very clear to me: we must improve the precision of the collector. This
> would be a gating feature towards taking the GC pretty much anywhere.

Do you know what is the impact of 64bits on false positive proportion 
when the GC isn't precise ?
December 26, 2011
Re: Carmack about static analysis
On Monday, 26 December 2011 at 00:40:47 UTC, Andrei Alexandrescu 
wrote:
> I might be biased, but I ask for it to be corrected if I see it 
> during a code review at work, and if someones writes such 
> during an interview, it doesn't gain them any points.

To conclude our chat here too, I do think you have a legitimate
point.
December 26, 2011
Re: Carmack about static analysis
On 12/26/11 10:29 AM, deadalnix wrote:
> Le 26/12/2011 05:23, Andrei Alexandrescu a écrit :
>> I've gone through a larger portion of the book and one thing has become
>> very clear to me: we must improve the precision of the collector. This
>> would be a gating feature towards taking the GC pretty much anywhere.
>
> Do you know what is the impact of 64bits on false positive proportion
> when the GC isn't precise ?

No.

Andrei
December 26, 2011
Re: Carmack about static analysis
On 12/26/2011 3:47 AM, Jacob Carlborg wrote:
> It's like when you see code like this (Ruby):
>
> unless !foo
>
> end
>
> Double negation. Code like the snippet above can be really annoying.

In general, variables and conditions should never be labeled with negation:

    bool notFeature;
December 26, 2011
Re: Carmack about static analysis
On Mon, 26 Dec 2011 07:43:46 -0800, Jacob Carlborg <doob@me.com> wrote:
> On 2011-12-26 15:52, Andrei Alexandrescu wrote:
>> On 12/26/11 6:53 AM, Jacob Carlborg wrote:
>>> What about the parallel/concurrent collector that has been linked a
>>> couple of times in this newsgroup. Would that be possible and a good
>>> idea to implement?
>>
>> A parallel collector would be, of course, a valuable addition.
>>
>> Andrei
>
> This is the collector I was referring to:
> http://www.artima.com/lejava/articles/azul_pauseless_gc.html

The C4 pause-less GC, while very cool, is its own operating system. It doesn't run on-top of Windows, Linux, Mac, etc. CDGC, on the other hand, is a concurrent collector that only runs on *nixes. Thread-local GCs are a form of mostly parallel/concurrent collectors which are a good match for D, but requires our memory model to support/include regions. There has also been some work recently in making fully precise collectors for C, which would be directly applicable to D.
December 26, 2011
Re: Carmack about static analysis
Robert Jacques:

> The C4 pause-less GC, while very cool, is its own operating system.
> It doesn't run on-top of Windows, Linux, Mac, etc.

I think that eventually Linux will have to include some of those ideas, to allow language designers or virtual machine designers, to implement better garbage collectors. At the moment the interaction between GCs and virtual memory managers of the OS is often naive or bad.

In the meantime a serious D programmer that has to process lot of data efficiently is possibly willing to use a patched Linux to use a C4-like GC from D code.

But I think such garbage collectors are a lot of work to implement, so I think for now it's better to aim to something simpler for D2, that requires a smaller number of human-years of programming to be built :-)

Bye,
bearophile
2 3 4 5 6 7 8 9
Top | Discussion index | About this forum | D home