www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Garbage Collector

reply "js.mdnq" <js_adddot+mdng gmail.com> writes:
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)?
Nov 30 2012
next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Nov 30 2012
next sibling parent "js.mdnq" <js_adddot+mdng gmail.com> writes:
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.
Nov 30 2012
prev sibling parent reply "Maxim Fomin" <maxim maxim-fomin.ru> writes:
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.
Nov 30 2012
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Nov 30 2012
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Dec 01 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 01 2012
parent Rainer Schuetze <r.sagitario gmx.de> writes:
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?
Dec 01 2012
prev sibling next sibling parent reply "thedeemon" <dlang thedeemon.com> writes:
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).
Dec 01 2012
parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Dec 01 2012
prev sibling parent "Michael" <pr m1xa.com> writes:
If it possible maybe some info can be taken from mono project?
Dec 01 2012