So let's talk about garbage collection, and practical strategies to avoid allocation.

GC related discussions come up basically every day, perhaps multiple times a day on IRC, and the recent reddit 2.063 release thread is dominated by C++ programmers who are keenly interested in D, but are scared by the GC. I can say with confidence, as someone who has gone out on a limb and actually invested a lot of time and energy in D, I'm as nervous (or more so) as they are, and feel their turmoil deeply!

So where are we?

I can only speak from my industry's perspective. As I see it, we are here:
 - Stopping the world is unacceptable
 - Scanning the whole heap is costly
 - Also seems extremely wasteful to scan the whole heap when the overall
temporal stability of a realtime heap is extremely high (just a few temps
allocated frome-to-frame on average, and mostly on the stack!)
 - GC runs at unpredictable moments
 - GC collection cycles become more and more frequent the less unallocated
memory overhead you have. Hint: video games usually run within kb of the
systems available memory. How often will full heap-scanning collections be
issued to collect a couple of transient/temporary allocations when there is
only a few kb free memory? Conceivably, more than once per frame...
 - In a low-free-memory environment, what is the cumulative effect of
fragmentation? Can this be measured, or will it be a nasty surprise 2
months from shipping a 20-million dollar project? (Hint: a discovery of
this sort could very well ruin a project and destroy a company)

Basically nobody will have experienced these issues to their fullest extent on a PC with plentiful memory. But they must be considered if the audience still stuck in C++ is to take D seriously (who I predict are D's greatest potential user-base).

While I do think a sufficiently advanced GC might satisfy the realtime environment, the more I think about it, the more I am thinking a GC is not applicable to the embedded (or memory limited) environment.

So what options exist?

I'm thinking more and more that I like the idea of a ref-counting GC.
People argue that managing ref-counts may be slower, perhaps true, it
requires a small amount of localised overhead, but if allocation frequency
is low, it shouldn't be much.
I think the key advantages though are:
 - determinism, memory will be immediately freed (or perhaps deferred by a
small but predictable amount of time, let's say, 1 frame)
 - elimination of full-heap scans which takes the most time
 - the refcount table is self-contained, won't destroy the dcache like a
heap scan
 - less tendency to fragment, since transient allocations can come into and
leave existence before something else allocates beside it

But this is only part of the problem.
Naturally, the fastest allocation is the one that never happened.
So an equally, or even more important aspect of the puzzle is offering
clearly documented advice, and convenient syntax/patterns on how to avoid
allocation in general.
It should be made EASY to avoid allocation. This way people will tend to do
it by habit, further alleviating the problem.

I've made the case that libraries should avoid surprise allocations at all costs. Maybe this leads back to @nogc conversations (a concept I'm not personally sold on), but something needs to be done, and best-practises/conventions need to be defined.

So I'd go so far as to say, perhaps these 2 points should be considered as
key goals for 2.064?
  * find a solution for deterministic embedded garbage collection
  * decide some realistic best-practises/conventions for reliably (and
conveniently!) avoiding allocations

Showing progress on these will show real progress on D for ex-C++ users. In my time using D, there has been exactly ZERO progress on the GC issue, which is discouraging to say the least, perhaps even kinda scary. (fortunately, people are thinking about it, and there were 2 great talks at dconf, but I don't think either address the specific issues I raise)

Discuss... (or perhaps, "destroooy")

just to toss in my quick thoughts, I wrote a couple comments on the recent reddit thread about using D with a minimal runtime and some of the talk may be relevant here too:

http://www.reddit.com/r/programming/comments/1fc9jt/dmd_2063_the_d_programming_language_reference/ca94mek


Some little things we could do is add overloads to some functions that return string to be able to take a buffer argument too.

string to(T:string)(int a) { char[] buf = new char[](16); return assumeUnique(to(a, buffer));

char[] to(int a, char[] buffer) { deposit it straight into buffer, return the slice into buffer that is actually used; }


and so on for all kinds of functions. Kinda a pain in the butt but when you need it, you have the second variant, and if you don't care, the convenient first one is still available (also avoids breaking code!)


I also mentioned on irc yesterday that I think a good, low cost idea to help find allocations is to add a global flag to druntime that makes gc_malloc throw an Error. Then you can set this flag in a critical section of code and at least get a runtime notice of a missed allocation in testing while still having the gc for the rest of the app.

Another member also suggested you can do that easily enough by running the program in a debugger and setting a breakpoint at gc_malloc, but I think the flag would be simpler yet.

On Saturday, 1 June 2013 at 02:16:02 UTC, Adam D. Ruppe wrote:
> just to toss in my quick thoughts, I wrote a couple comments on the recent reddit thread about using D with a minimal runtime and some of the talk may be relevant here too:
>
> http://www.reddit.com/r/programming/comments/1fc9jt/dmd_2063_the_d_programming_language_reference/ca94mek
>
>
> Some little things we could do is add overloads to some functions that return string to be able to take a buffer argument too.
>
> string to(T:string)(int a) { char[] buf = new char[](16); return assumeUnique(to(a, buffer));
>
> char[] to(int a, char[] buffer) { deposit it straight into buffer, return the slice into buffer that is actually used; }

I played around with adding an overload that accepted an output range to some of the std.string functions identified in my run of -vgc over phobos[1] (after Jonathan pointed out this is probably the best approach and is already what formattedWrite does).  It worked fine but it did make me realize there aren't a lot of output ranges available to plug in at the moment (appender and lockingTextWriter are the only two that come to mind though there may be others).  Appender isn't useful if your goal is to avoid the GC.  Array!char et al aren't output ranges (whether they should be or not I have no idea).  static arrays would need some sort of wrapper to make them output ranges I believe unless it was decided that put() should work by replacing the front and calling popFront for them (which I kind of doubt is the desired behavior).

(feel free to correct me on any of this, range experts)

1. http://goo.gl/HP78r

On Saturday, 1 June 2013 at 02:47:40 UTC, Brad Anderson wrote:
static
> arrays would need some sort of wrapper to make them output ranges I believe unless it was decided that put() should work by replacing the front and calling popFront for them (which I kind of doubt is the desired behavior).
>
> (feel free to correct me on any of this, range experts)

Actually I'm completely wrong about this.  Slices already work this way and you can use a slice of a static array just fine as an output range.

On Saturday, June 01, 2013 04:47:39 Brad Anderson wrote:
> I played around with adding an overload that accepted an output range to some of the std.string functions identified in my run of -vgc over phobos[1] (after Jonathan pointed out this is probably the best approach and is already what formattedWrite does).  It worked fine but it did make me realize there aren't a lot of output ranges available to plug in at the moment (appender and lockingTextWriter are the only two that come to mind though there may be others).  Appender isn't useful if your goal is to avoid the GC.  Array!char et al aren't output ranges (whether they should be or not I have no idea).  static arrays would need some sort of wrapper to make them output ranges I believe unless it was decided that put() should work by replacing the front and calling popFront for them (which I kind of doubt is the desired behavior).
> 
> (feel free to correct me on any of this, range experts)
> 
> 1. http://goo.gl/HP78r

Dynamic arrays are output ranges. The one potential hitch there though relates to the fact that they get written to rather than appended to. This is actually exactly what you want in a situation like Manu's. However, that means that you have to worry about an output range running out of space and how you deal with that.

If it's know how much will need to be appended, presumably you can check length if hasLength!R is true. Otherwise, I guess that the right thing to do is to check empty (arrays get shrunk as they're written to, so they'll be empty when you can't call put on them anymore). Unfortunately, put doesn't seem to worry about the case where the ouput range is full/empty, so the result when calling put on an empty range is undefined. The situation is even worse with narrow strings (assuming that put works with them - I'm not sure that it does at the moment) given that even if you knew their length (which you wouldn't if you were going by hasLength), you wouldn't know whether a put would succeed when the string was nearly empty, as the actual number of elements that the dchar would take up would depend on its value.

In general, I don't think that output ranges have really been sorted out on quite the level that input ranges have been, and I think that some discussion is in order with regards to how to handle things like when the range can't be put into anymore. Given that one reason to use output ranges is for performance-critical code that doesn't want to allocate, throwing when the range is empty is probably a bad idea, and it's unclear that we can reasonably determine in the general case whether you can put to an output range before you actually try it. One solution to that would be to make bool return whether it succeeded or not, but it's an issue that definitely needs to be explored a bit.

So, I very much think that the correct thing is to use output ranges, but how to use them needs to be better defined, and we probably need to better sort out some of their details (like the finish function which the hash stuff uses).

- Jonathan M Davis

On Saturday, 1 June 2013 at 04:16:44 UTC, Jonathan M Davis wrote:
> [snip]
> The situation is even
> worse with narrow strings (assuming that put works with them - I'm not sure
> that it does at the moment) given that even if you knew their length (which
> you wouldn't if you were going by hasLength), you wouldn't know whether a put
> would succeed when the string was nearly empty, as the actual number of
> elements that the dchar would take up would depend on its value.


Furthermore--you probably know this because of the conversation on GitHub but for anyone else reading--narrow strings are also hard to work with because you can't put a dchar on them currently. Kenji had a pull request (since closed) to help with narrow strings issues:

https://github.com/D-Programming-Language/phobos/pull/1000

That and all the issues and unknowns you describe would need to fixed for output ranges are going to be the approach.

I'm reminded of a forum post by monarch_dodra that talked about some of the issues you brought up: http://forum.dlang.org/thread/xyvnifnetythvrhtcexm@forum.dlang.org

On Saturday, 1 June 2013 at 02:03:07 UTC, Manu wrote:
> So let's talk about garbage collection, and practical strategies to avoid
> allocation.
>
> Discuss... (or perhaps, "destroooy")

Here is my take:
http://forum.dlang.org/post/tftjtzmfuauxwcgcolct@forum.dlang.org

Sorry, I didn't see your new discussion.

Manu:

>  - Scanning the whole heap is costly

Rust avoids this giving a different heap to each thread, and common heap to share data managed with unique references.


>  - GC runs at unpredictable moments

Is this true? I think the D GC runs only when you allocate something.

Bye,
bearophile

Nothing will get done until someone decides to put in the effort to fix the problem. D's biggest drawback at this point is the GC and one would think with all the smart people around here someone would have solved this problem by now.

We need a solution that allows one to "plug and play" different allocation strategies. One shouldn't have to rely on any particularly bad GC implementation if they don't want to(but as of now are forced to). Stop the world GC is just plain crap except for the most basic apps. Any app that requires performance is going to have issues with this, the reason being simply that there are much better ways.


The ability to avoid the GC is of utmost importance for real time apps regardless of what some want people to think.  This can't be done as because D internally uses the GC. Hence this must be worked around. @nogc/@gc has been brought up several times... seems like a start and can't hurt.

IMO the best way to deal with the situation is to use manual memory management with a GC backend.

e.g., pretend the GC is not there just like the good ol' days. If you forget to deallocate something, maybe get a warning from a sufficiently intelligent compiler, if the GC is turned on then it will clean up for you behind the scenes. If you need performance, turn it off or disable it temporarily.

This is the best of both worlds and allows one to easily go from one extreme to the other. One can actually implement a pattern to allow the user to select one extreme or the other.

One can already do this in D in user code but since the D core does not follow this approach it doesn't do one much good unless they want to avoid slices, phobos, etc...

I think it will go a long way to get a standard for D regarding memory allocation that follows these lines. All new code will be written with using the standard and old code will be updated.

On 2013-06-01 04:16, Adam D. Ruppe wrote:
> Some little things we could do is add overloads to some functions that
> return string to be able to take a buffer argument too.
>
> string to(T:string)(int a) { char[] buf = new char[](16); return
> assumeUnique(to(a, buffer));
>
> char[] to(int a, char[] buffer) { deposit it straight into buffer,
> return the slice into buffer that is actually used; }

This approach is used all over the place in Tango.

-- 
/Jacob Carlborg