On Fri, 24 May 2013 01:11:17 +0100, Manu <turkeyman@gmail.com> wrote:
> /agree, except the issue I raised, when ~ is used in phobos.
> That means that function is now off-limits. And there's no way to know
> which functions they are...

It's not the allocation caused by ~ which is the issue though is it, it's the collection it might trigger, right?

So what you really need are 3 main things:

1. A way to prevent the GC collecting until a given point(*).
2. A way to limit the GC collection time.
3. For phobos functions to be optimised to not allocate or to use alloca where possible.

#1 should be trivial.
#2 is much harder to achieve in the general case (I believe).
#3 is not essential but desirable and could be added/improved over time.

(*) Until the collection point the GC would ask the OS for more memory (a new pool or page) or fail and throw an Error.  Much like in Leandro's concurrent GC talk/example where he talks about eager allocation.

In order to make #2 easier to achieve I had an idea, not sure how workable this is..

Lets imagine you can mark a thread as not stopped by the pause-the-world.  Lets imagine it still does allocations which we want to collect at some stage.  How would this work..

1. The GC would remove the thread stack and global space from it's list of roots scanned by normal collections.  It would not pause it on normal collections.

2. (*) above would be in effect, the first allocation in the thread would cause the GC to create a thread local pool, this pool would not be shared by other threads (no locking required, not scanned by normal GC collections).  This pool could be pre-allocated by a new GC primitive "GC.allocLocalPool();" for efficiency.  Allocation would come from this thread-local pool, or trigger a new pool allocation - so minimal locking should be required.

3. The thread would call a new GC primitive at the point where collection was desired i.e. "GC.localCollect(size_t maxMicroSecs);".  This collection would be special, it would not stop the thread, but would occur inline.  It would only scan the thread local pool and would do so with an enforced upper bound collection time.

4. There are going to be issues around 'shared' /mutable/ data, e.g.

 - The non-paused thread accessing it (esp during collection)
 - If the thread allocated 'shared' data

I am hoping that if the thread main function is marked as @notpaused (or similar) then the compiler can statically verify neither of these occur and produce a compile time error.

So, that's the idea.  I don't know the current GC all that well so I've probably missed something crucial.  I doubt this idea is revolutionary and it is perhaps debatable whether the complexity is worth the effort, also whether it actually makes placing an upper bound on the collection any easier.

Thoughts?

R

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/

On Friday, 24 May 2013 at 10:24:13 UTC, Regan Heath wrote:
> It's not the allocation caused by ~ which is the issue though is it, it's the collection it might trigger, right?

Depends. When it comes to real-time software you can't say without studying specific task requirements. Stop-the-world collection is a complete disaster but, for example, if you consider concurrent one like Leandro has shown - it can satisfy soft real-time requirements. But only if heap size managed by GC stays reasonably low - thus the need to control that you don't allocate in an unexpected ways.

> So what you really need are 3 main things:
>
> 1. A way to prevent the GC collecting until a given point(*).

You can do it now. Does not help if world is stopped and/or you can't limit collection time.

> 2. A way to limit the GC collection time.

Or run it concurrently with low priority. Will do for lot of _soft_ real-time.

> 3. For phobos functions to be optimised to not allocate or to use alloca where possible.

Really important one as helps not only game dev / soft real-time servers, but also hardcore embedded.

On Fri, 24 May 2013 11:38:40 +0100, Dicebot <m.strashun@gmail.com> wrote:

> On Friday, 24 May 2013 at 10:24:13 UTC, Regan Heath wrote:
>> It's not the allocation caused by ~ which is the issue though is it, it's the collection it might trigger, right?
>
> Depends. When it comes to real-time software you can't say without studying specific task requirements. Stop-the-world collection is a complete disaster but, for example, if you consider concurrent one like Leandro has shown - it can satisfy soft real-time requirements. But only if heap size managed by GC stays reasonably low - thus the need to control that you don't allocate in an unexpected ways.
>
>> So what you really need are 3 main things:
>>
>> 1. A way to prevent the GC collecting until a given point(*).
>
> You can do it now. Does not help if world is stopped and/or you can't limit collection time.

If you disable collection, then the GC runs out of memory what happens?  Does it simply ask the OS for more memory?  I assumed, from Leandro's talk, that it would block on the GC lock until collection completed, or simply fail if collection was disabled.

Also, the key to the idea I gave was to control collection only in the real-time thread/part of the application.

>> 2. A way to limit the GC collection time.
>
> Or run it concurrently with low priority. Will do for lot of _soft_ real-time.

I don't think Manu is doing _soft_ real-time, he wants a hard guarantee it will not exceed 100us (or similar).

Concurrent may be a possible solution as well, but if you think about it my idea is basically a second isolated collector running in a real-time context concurrently.

>> 3. For phobos functions to be optimised to not allocate or to use alloca where possible.
>
> Really important one as helps not only game dev / soft real-time servers, but also hardcore embedded.

Sure, it's desirable to be more efficient but it's no longer essential if the allocations no longer cost you anything in the real-time thread - that's the point.

What do you think of the idea of making marked threads except from normal GC processing and isolating their allocations to a single page/pool in order to control and reduce collection times?

R

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/

On 2013-05-24 07:02, Manu wrote:

> I don't think it's hack-ish at all, that's precisely what the stack is
> there for. It would be awesome for people to use alloca in places that
> it makes sense.
> Especially in cases where the function is a leaf or leaf-stem (ie, if
> there is no possibility of recursion), then using the stack should be
> encouraged.
> For safety, obviously phobos should do something like:
>    void[] buffer = bytes < reasonable_anticipated_buffer_size ?
> alloca(bytes) : new void[bytes];
>
> toStringz is a very common source of allocations. This alloca approach
> would be great in those cases, filenames in particular.

Basically every function in Tango that operates on some kind of array takes an array and an optional buffer (also an array). If the buffer is too small it will allocate using the GC. If not, it won't allocate and builds the array in place. That worked great with D1 where strings weren't immutable.

-- 
/Jacob Carlborg

On 2013-05-24 12:01, Peter Alexander wrote:

> In that case it should only allocate when needed. Most strings are ASCII
> and will not change size.

What I mean is that something called "InPlace" doesn't go hand in hand with something that allocates. There's always std.ascii.

-- 
/Jacob Carlborg

On Friday, 24 May 2013 at 12:29:43 UTC, Jacob Carlborg wrote:
> On 2013-05-24 12:01, Peter Alexander wrote:
>
>> In that case it should only allocate when needed. Most strings are ASCII
>> and will not change size.
>
> What I mean is that something called "InPlace" doesn't go hand in hand with something that allocates. There's always std.ascii.

Ah right, I see your point. My bad.

On 05/24/2013 11:49 AM, Jacob Carlborg wrote:
> toUpper/lower cannot be made in place if it should handle all Unicode. Some characters will change their length when convert to/from uppercase. Examples of these are the German double S and some Turkish I.

Surely it's possible to put in-place checks for whether the character length changes, and ensure in-place replacement without any allocation if it doesn't. (To be honest, feels a bit of a design flaw in Unicode that character length can change between lower- and uppercase.)

On Friday, 24 May 2013 at 13:37:36 UTC, Joseph Rushton Wakeling wrote:
> (To be honest, feels a bit of a design flaw in Unicode that character length can
> change between lower- and uppercase.)

Unfortunately it's either that or lose compatibility with ASCII. Lower case dotted-i needs to be one byte for ASCII, and upper case dotted-i isn't ASCII, so it needs to be more than one byte.

P.S. it's a problem with UTF-8, not Unicode.

On 24 May 2013 17:57, Don <turnyourkidsintocash@nospam.com> wrote:

> On Thursday, 23 May 2013 at 18:22:54 UTC, Joseph Rushton Wakeling wrote:
>
>> On 05/23/2013 08:13 PM, Brad Anderson wrote:
>>
>>> Now I'm wondering what can be done to foster this newly acquired
>>> credibility in
>>> games.  By far the biggest issue I hear about when it comes to people
>>> working on
>>> games in D is the garbage collector.  You can work around the GC without
>>> too
>>> much difficulty as Manu's experience shared in his DConf talk shows but
>>> a lot of
>>> people new to D don't know how to do that.  We could also use some tools
>>> and
>>> guides to help people identify and avoid GC use when necessary.
>>>
>>
>
> It's worth noting that our code at Sociomantic faces *exactly* the same
> issues.
> We cannot use Phobos because of its reliance on the GC.
> Essentially, we want to have the option of avoiding GC usage in every
> single function.
>
>
>  As a starting point, do we have a list of the Phobos functions that
>> allocate
>> using GC when there's no need to?  That's a concern of Manu's that it
>> ought to
>> be possible to address relatively swiftly if the information is to hand.
>>
>
> That is only part of the problem with Phobos. The bigger problem is with
> the functions that DO need to allocate memory. In Tango, and in our code,
> all such functions accept a buffer to store the results in.
> So that, even though they need to allocate memory, if you call the
> function a thousand times, it only allocates memory once, and keeps reusing
> the buffer.
>
> I'm not sure how feasible it is to add that afterwards. I hope it can be done without changing all the API's, but I fear it might not be.
>

Yeah, I've often wanted API's in that fashion too.
I wonder if it would be worth creating overloads of allocating functions
that receive an output buffer argument, rather than return an allocated
buffer...
Too messy?


But anyway, after fixing the obvious Phobos offenders, another huge step
> would be to get TempAlloc into druntime and used wherever possible in Phobos.
>

How does that work?

One pattern I've used a lot is, since we have a regular 60hz timeslice and
fairly a regular pattern from frame to frame, we use a temp heap which
pushes allocations on the end like a stack, then wipe it clean at the state
of the next frame.
Great for any small allocations that last no longer than a single frame.
It's fast (collection is instant), and it also combats memory
fragmentation, which is also critically important when working on memory
limited systems with no virtual memory/page file.

On 24 May 2013 18:01, Jacob Carlborg <doob@me.com> wrote:

> On 2013-05-24 01:51, Joseph Rushton Wakeling wrote:
>
>  This also seems to suggest that an ideal solution might be to have several
>> different GC strategies, the choice of which could be made at compile time depending on what's most suitable for the application in question.
>>
>
> You can already swap the GC implementation at link time.


Sure, but there's not an established suite of options to choose from. How do I select the incremental GC option? :)