View mode: basic / threaded / horizontal-split · Log in · Help
November 30, 2012
Garbage Collector
I came across these threads:

http://stackoverflow.com/questions/13574552/d-programming-without-the-garbage-collector

http://stackoverflow.com/questions/8782627/does-the-d-garbage-collector-work

and did some investigating of my own.

I noticed that in both x64 and x86 builds the GC seems to get 
exponentially slower as the objects are allocated.

On the x64 version with about 6GB(about 7GB free, no page 
file(turned off)) usage the time I see the object allocation(by 
watching memory usage) slow to a craw after about 1GB and it just 
gets slower(in some cases allocating about 10k/s(vs about 100MB/s 
at the start).

GDC reduces does slightly better but still the same issue.

Since the sample code allocates objects sequentially without any 
deallocation it seems there is a huge "bug" in the GC code.

Maybe the GC does not handle allocating a large sequence of 
objects well because it expects some deallocations in between?

Can we expect improvements of the GC at in time in the near 
future(months, not years)?
November 30, 2012
Re: Garbage Collector
On 11/30/2012 03:21 PM, js.mdnq wrote:

> I noticed that in both x64 and x86 builds the GC seems to get
> exponentially slower as the objects are allocated.

[...]

> Since the sample code

that you have forgotten to show ;)

> allocates objects sequentially without any
> deallocation it seems there is a huge "bug" in the GC code.

Possible.

> Can we expect improvements of the GC at in time in the near
> future(months, not years)?

Yes. There is already a precise GC implementation for D, which should be 
available with dmd as early as 2.062.

Ali
November 30, 2012
Re: Garbage Collector
On Friday, 30 November 2012 at 23:35:16 UTC, Ali Çehreli wrote:
> On 11/30/2012 03:21 PM, js.mdnq wrote:
>
> > I noticed that in both x64 and x86 builds the GC seems to get
> > exponentially slower as the objects are allocated.
>
> [...]
>
> > Since the sample code
>
> that you have forgotten to show ;)
>
> > allocates objects sequentially without any
> > deallocation it seems there is a huge "bug" in the GC code.
>
> Possible.
>
> > Can we expect improvements of the GC at in time in the near
> > future(months, not years)?
>
> Yes. There is already a precise GC implementation for D, which 
> should be available with dmd as early as 2.062.
>
> Ali

Cool. The code is basically taken off the first link. I modified 
it a little but the original code should work. All I did was 
increase the size of objects that are being allocated. I was 
mainly using GDC x64 though.

What I did was run the code and watch the memory usage as it ran. 
I noticed that it was getting slower and slower. Now, one could 
expect such if the main memory was fragmented and GDC could not 
allocate contiguous blocks, but I do not think that was the case 
and it happens for much smaller amounts of memory.

My guess, and just a guess, is that it does not reserve large 
enough blocks of memory once it is initial memory block is full.
December 01, 2012
Re: Garbage Collector
On Friday, 30 November 2012 at 23:35:16 UTC, Ali Çehreli wrote:
> On 11/30/2012 03:21 PM, js.mdnq wrote:
> > Can we expect improvements of the GC at in time in the near
> > future(months, not years)?
>
> Yes. There is already a precise GC implementation for D, which 
> should be available with dmd as early as 2.062.
>
> Ali

Please elaborate about GC plans for 2.062. I saw thread related 
to GC GSOC project and precise GC, however I do not remember 
about announcements to pull it in master branch.
December 01, 2012
Re: Garbage Collector
On 11/30/2012 10:54 PM, Maxim Fomin wrote:
> On Friday, 30 November 2012 at 23:35:16 UTC, Ali Çehreli wrote:
>> On 11/30/2012 03:21 PM, js.mdnq wrote:
>> > Can we expect improvements of the GC at in time in the near
>> > future(months, not years)?
>>
>> Yes. There is already a precise GC implementation for D, which should
>> be available with dmd as early as 2.062.
>>
>> Ali
>
> Please elaborate about GC plans for 2.062. I saw thread related to GC
> GSOC project and precise GC, however I do not remember about
> announcements to pull it in master branch.

I was relaying Dmitry Olshansky's optimism:


http://forum.dlang.org/thread/k95mf2$1aar$1@digitalmars.com#post-k9autf:241jma:241:40digitalmars.com

Quote: "I'd just throw in that we have a (almost) precise GC that is 
used by  at least one large project (the VisualD apparently). Though 
there were some problems with it. Anyway I'd expect to see it in 
upstream by 2.062 at least.".

Ali
December 01, 2012
Re: Garbage Collector
12/1/2012 11:35 AM, Ali Çehreli пишет:
> On 11/30/2012 10:54 PM, Maxim Fomin wrote:
>> On Friday, 30 November 2012 at 23:35:16 UTC, Ali Çehreli wrote:
>>> On 11/30/2012 03:21 PM, js.mdnq wrote:
>>> > Can we expect improvements of the GC at in time in the near
>>> > future(months, not years)?
>>>
>>> Yes. There is already a precise GC implementation for D, which should
>>> be available with dmd as early as 2.062.
>>>
>>> Ali
>>
>> Please elaborate about GC plans for 2.062. I saw thread related to GC
>> GSOC project and precise GC, however I do not remember about
>> announcements to pull it in master branch.
>
> I was relaying Dmitry Olshansky's optimism:
>
>
> http://forum.dlang.org/thread/k95mf2$1aar$1@digitalmars.com#post-k9autf:241jma:241:40digitalmars.com
>
>
> Quote: "I'd just throw in that we have a (almost) precise GC that is
> used by  at least one large project (the VisualD apparently). Though
> there were some problems with it. Anyway I'd expect to see it in
> upstream by 2.062 at least.".
>
> Ali

Yup, being optimistic here.

In any case I don't expect it in 2.061 as this version should feature 
win64 and that's already a whole lot of work. It feels like a release is 
not far away.

So 2.062 sounds precisely like a version to go for.

The VisualD announce is more then a month ago:
http://forum.dlang.org/thread/k59kg5$4dt$1@digitalmars.com

The relevant GC fork should be this one:
https://github.com/rainers/druntime/tree/precise_gc2

So basically one should be able to try it right away.

-- 
Dmitry Olshansky
December 01, 2012
Re: Garbage Collector
On Friday, 30 November 2012 at 23:21:39 UTC, js.mdnq wrote:
> http://stackoverflow.com/questions/13574552/d-programming-without-the-garbage-collector

> and did some investigating of my own.
>
> I noticed that in both x64 and x86 builds the GC seems to get 
> exponentially slower as the objects are allocated.
>

Your program should get quadratically slower.
If you just allocate in a loop, GC is called O(n) times and each 
time it scans all the heap, each scan is O(n), so you get O(n^2) 
overall time.

In some other languages' runtimes heap growth is adapting to 
allocation rate, so there are fewer GC invocations. But anyway 
this kind of loop will be slow in any GCed language unless you 
allocate all available memory right away. In C/C++ there are no 
calls to GC, so it works in O(n).
December 01, 2012
Re: Garbage Collector
thedeemon:

> Your program should get quadratically slower.
> If you just allocate in a loop, GC is called O(n) times and 
> each time it scans all the heap, each scan is O(n), so you get 
> O(n^2) overall time.

This was a very well know problem with the simple GC of CPython, 
so about two or three years ago they have added an optimization: 
if the GC finds many nearby allocations, it switches off, to go 
back to a more linear run-time.

I vaguely remember someone talking about a similar optimization 
in the D GC, but even if it's there, it's not working well enough.

Bye,
bearophile
December 01, 2012
Re: Garbage Collector
On 12/1/12 2:35 AM, Ali Çehreli wrote:
> On 11/30/2012 10:54 PM, Maxim Fomin wrote:
>> On Friday, 30 November 2012 at 23:35:16 UTC, Ali Çehreli wrote:
>>> On 11/30/2012 03:21 PM, js.mdnq wrote:
>>> > Can we expect improvements of the GC at in time in the near
>>> > future(months, not years)?
>>>
>>> Yes. There is already a precise GC implementation for D, which should
>>> be available with dmd as early as 2.062.
>>>
>>> Ali
>>
>> Please elaborate about GC plans for 2.062. I saw thread related to GC
>> GSOC project and precise GC, however I do not remember about
>> announcements to pull it in master branch.
>
> I was relaying Dmitry Olshansky's optimism:
>
>
> http://forum.dlang.org/thread/k95mf2$1aar$1@digitalmars.com#post-k9autf:241jma:241:40digitalmars.com
>
>
> Quote: "I'd just throw in that we have a (almost) precise GC that is
> used by at least one large project (the VisualD apparently). Though
> there were some problems with it. Anyway I'd expect to see it in
> upstream by 2.062 at least.".
>
> Ali

Unfortunately Antti-Ville, the student who worked on the GSoC project, 
is not to be found. I pinged him to no avail. Hopefully nothing bad 
happened to him.

It would be great if someone else in the community took over his github 
work.


Andrei
December 01, 2012
Re: Garbage Collector
On 01.12.2012 14:32, Andrei Alexandrescu wrote:
> On 12/1/12 2:35 AM, Ali Çehreli wrote:
>> Quote: "I'd just throw in that we have a (almost) precise GC that is
>> used by at least one large project (the VisualD apparently). Though
>> there were some problems with it. Anyway I'd expect to see it in
>> upstream by 2.062 at least.".
>>
>> Ali
>
> Unfortunately Antti-Ville, the student who worked on the GSoC project,
> is not to be found. I pinged him to no avail. Hopefully nothing bad
> happened to him.
>
> It would be great if someone else in the community took over his github
> work.
>
>
> Andrei

https://github.com/rainers/druntime/tree/precise_gc2 started as a bug 
fix fork of the GSoC project, but not a lot was kept from it in the end 
but the main concept. I'm a little disappointed that it didn't catch 
more interest so far.

Precise garbage collection of the heap only does not help Visual D a 
lot, the data segment needs to be scanned precisely as well, because it 
contains a lot of text, tables (e.g. std.uni), COM GUIDs, etc. that make 
good false pointers. Even worse than for the heap, you don't have a 
NO_SCAN flag available to skip arrays that contain no pointers at all.

So I patched the compiler to generate type info for the data segment as 
well emitting (adress,typeinfo) pairs into a separate segment. There is 
no pull request yet, because it is Windows specific so far (shouldn't be 
too hard to transfer to other platforms) and it is very specific to the 
implementation (in contrast to the concept of RTInfo).

To avoid the latter I tried to generate it as the output of an 
RDInfo(alias var) template to be defined together with RTInfo, but that 
doesn't work, because

- data inside templates generated into libraries end up as comdats that 
never get linked in
- references to TLS variables cannot be generated at compile time
- placing the data into a special section to sort it together by the 
linker is not possible

Any ideas how this could be implemented?
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home