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