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)?

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

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.

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.

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

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

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).

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

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

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?