On Thursday, 30 May 2013 at 11:34:20 UTC, Dicebot wrote:
> On Thursday, 30 May 2013 at 11:31:53 UTC, Manu wrote:
>> Which 'both' cases?
>
> "OS support for fork+CoW" vs "no support, own implementation"

If you can modify the DMD compiler to output a special sequence of instructions whenever you assign to a pointer type then you can do a concurrent/incremental GC with minimal OS or hardware support.

On 2013-05-30 12:04:09 +0000, "Diggory" <diggsey@googlemail.com> said:

> If you can modify the DMD compiler to output a special sequence of instructions whenever you assign to a pointer type then you can do a concurrent/incremental GC with minimal OS or hardware support.

This also happens to be the same requirement for automatic reference counting. I thought about implementing that for my D/Objective-C compiler (which is stalled since a while). The job isn't that big: just replace any pointer assignments/initialization by a call to a template function (that can be inlined) doing the assignment and it becomes very easy to implement such things by tweaking a template in druntime.

-- 
Michel Fortin
michel.fortin@michelf.ca
http://michelf.ca/

On 30.05.2013 13:16, Manu wrote:
> On 30 May 2013 19:50, Rainer Schuetze <r.sagitario@gmx.de
> <mailto:r.sagitario@gmx.de>> wrote:
>
>
>
>     On 29.05.2013 10:06, Manu wrote:
>
>
>         What do you think is easier, or perhaps even POSSIBLE in D?
>         A good RC approach, or a V8 quality concurrent+incremental GC?
>
>
>     I think none of them is feasible without write-barriers on pointer
>     modifications in heap memory. That means extra code needs to be
>     generated for each pointer modification (if the compiler cannot
>     optimize it away as LLVM seems to be doing in case of Objectve-C).
>     As an alternative, Leandros concurrent GC implements them with
>     hardware support by COW, though at a pretty large granularity (page
>     size). I'm not sure if this approach can be sensibly combined with
>     RC or incremental collection.
>
>
> I'm talking about embedded hardware. No virtualisation, tight memory
> limit, no significant OS. Is it possible?
>
>         I get the feeling either would be acceptable, but I still kinda like
>         idea of the determinism an RC collector offers.
>
>
>     If you want it to be safe and efficient, it needs to use deferred
>     reference counting, and this ain't so deterministic anymore. The
>     good thing about it is that you usually don't have to scan the whole
>     heap to find candidates for reclamation.
>
>
> Well, it's a bit more deterministic, at least you could depend on the
> deferred free happening within a frame let's say, rather than at some
> un-knowable future time when the GC feels like performing a collect...
>
> That said, I'd be interested to try it without a deferred free.
> Performance impact depends on the amount of temporaries/frees... I don't
> imagine it would impact much/at-all since there is so little memory
> allocation or pointer assignments in realtime software.
> People use horrific C++ smart pointer templates successfully, without
> any compiler support at all. It works because the frequency of pointer
> assignments is so low.
> RC is key to avoid scanning the whole heap, which completely destroys
> your dcache.
>
>         I reckon this should probably be the next big ticket for D. The
>         long-standing shared library problems seem to be being addressed.
>
>
>     The GC proposed by Leandro looks very promising, though it needs
>     support by the hardware and the OS. I think we should see how far we
>     can get with this approach.
>
>
> His GC looked good, clearly works better for the sociomantic guys, but I
> can't imagine it, or anything like it, will ever work on embedded platforms?
> No hardware/OS support... is it possible to emulate the requires features?

I suspected embedded systems would not have enough support for COW. I think the only way to emulate it would be with write barriers, and then you can do better than emulating page protection.

The way Michel Fortin proposed to implement it (lowering pointer writes to some druntime-defined template) is also how imagine it. A template argument that specifies whether the compiler knows that it is a stack access would be nice aswell.
One possible complication: memory block operations would have to treat pointer fields differently somehow.

> One possible complication: memory block operations would have to treat
> pointer fields differently somehow.

Would they? Shouldn't it be possible to make this part of the post-blit constructor?

Kind Regards
Benjamin Thaut

On 30.05.2013 22:59, Benjamin Thaut wrote:
>> One possible complication: memory block operations would have to treat
>> pointer fields differently somehow.
>
> Would they? Shouldn't it be possible to make this part of the post-blit
> constructor?

Not in general, e.g. reference counting needs to know the state before and after the copy.

On 2013-05-31 06:02:20 +0000, Rainer Schuetze <r.sagitario@gmx.de> said:

> On 30.05.2013 22:59, Benjamin Thaut wrote:
>>> One possible complication: memory block operations would have to treat
>>> pointer fields differently somehow.
>> 
>> Would they? Shouldn't it be possible to make this part of the post-blit
>> constructor?
> 
> Not in general, e.g. reference counting needs to know the state before and after the copy.

No. Reference counting would work with post-blit: you have the pointer, you just need to increment the reference count once. Also, if you're moving instead of copying there's no post-blit called but there's also no need to change the reference count so it's fine.

What wouldn't work with post-blit (I think) is a concurrent GC, as the GC will likely want to be notified when pointers are moved. Post-blit doesn't help there, and the compiler currently assumes it can move things around without calling any function.

-- 
Michel Fortin
michel.fortin@michelf.ca
http://michelf.ca/

On 31.05.2013 12:54, Michel Fortin wrote:
> On 2013-05-31 06:02:20 +0000, Rainer Schuetze <r.sagitario@gmx.de> said:
>
>> On 30.05.2013 22:59, Benjamin Thaut wrote:
>>>> One possible complication: memory block operations would have to treat
>>>> pointer fields differently somehow.
>>>
>>> Would they? Shouldn't it be possible to make this part of the post-blit
>>> constructor?
>>
>> Not in general, e.g. reference counting needs to know the state before
>> and after the copy.
>
> No. Reference counting would work with post-blit: you have the pointer,
> you just need to increment the reference count once. Also, if you're
> moving instead of copying there's no post-blit called but there's also
> no need to change the reference count so it's fine.
>

I was thinking about struct assignment through copying and then calling the postblit constructor, not copy construction. But I forgot about the swap semantics involved. If I interpret the disassembly correctly, the assignment in

S s1, s2;
s2 = s1;

translates to

S tmp1, tmp2;
memcpy(&tmp1, &s1);
tmp1.__postblit;   // user defined this(this)
s2.opAssign(tmp1); // makes a copy of tmp1 on the stack
//opAssign does:
    memcpy(&tmp2,&s2);
    memcpy(&s2,&tmp1);
    tmp1.__dtor;

There are a number of additional copies of the original structs, but the number of constructor/destructor calls are balanced. That should work for reference counting.

> What wouldn't work with post-blit (I think) is a concurrent GC, as the
> GC will likely want to be notified when pointers are moved. Post-blit
> doesn't help there, and the compiler currently assumes it can move
> things around without calling any function.

It would not allow to create a write barrier that needs to atomically change the pointer at a given location, or at least to record the old value before overwriting it with the new value. But that might not exclude concurrency, for example a concurrent GC with deferred reference counting.

On 05/24/2013 01:51 AM, Joseph Rushton Wakeling wrote:
> Maybe someone else can point to an example, but I can't think of any language prior to D that has both the precision and speed to be useful for games and embedded programming, and that also has GC built in.
> 
> So it seems to me that this might well be an entirely new problem, as no other GC language or library has had the motivation to create something that satisfies these use parameters.

Don't have the experience to judge it, but someone made a remark about Nimrod
that might be relevant here:
http://www.reddit.com/r/programming/comments/1fc9jt/dmd_2063_the_d_programming_language_reference/ca968xg