On 28 May 2013 23:33, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> On Sat, 25 May 2013 01:52:10 -0400, Manu <turkeyman@gmail.com> wrote:
>
>  What does ObjC do? It seems to work okay on embedded hardware (although
>> not
>> particularly memory-constrained hardware).
>> Didn't ObjC recently reject GC in favour of refcounting?
>>
>
> Having used ObjC for the last year or so working on iOS, it is a very nice memory management model.
>
> Essentially, all objects (and only objects) are ref-counted automatically by the compiler.  In code, whenever you assign or pass a pointer to an object, the compiler automatically inserts retains and releases extremely conservatively.
>
> Then, the optimizer comes along and factors out extra retains and releases, if it can prove they are necessary.
>
> What I really like about this is, unlike a library-based solution where every assignment to a 'smart pointer' incurs a release/retain, the compiler knows what this means and will factor them out, removing almost all of them.  It's as if you inserted the retains and releases in the most optimized way possible, and it's all for free.
>
> Also, I believe the compiler is then free to reorder retains and releases since it understands how they work.  Of course, a retain/release is an atomic operation, and requires memory barriers, so the CPU/cache cannot reorder, but the compiler still can.
>

Right. This is almost precisely how I imagined it would be working.
I wonder what it would take to have this as a GC strategy in D?
I'm more and more thinking this would be the best approach for realtime
software.
It's deterministic, and while being safe like a GC, the programmer retains
absolute control.
Also, things are destroyed when you expect (again, the deterministic thing).
I think this GC strategy will open D for use on much more embedded hardware.


I asked David Nadlinger at the conference whether we could leverage this
> power in LDC, since LLVM is the compiler back-end used by Apple, but he said all those optimization passes are in the Objective-C front-end.
>

Yeah, this would require D front-end work I'm sure.


It would be cool/useful to have compiler-native reference counting.  The
> only issue is, Objective-C is quite object-heavy, and it's statically checkable whether a pointer is an Object pointer or not.  In D, you would have to conservatively use retains/releases on every pointer, since any memory block could be ref-counted.  But just like Objective-C most of them could be factored out.  Add in that D has the shared-ness of the pointer built into the type system, and you may have something that is extremely effective.
>

Yep, I can imagine it would work really well, if the front-end implemented the logic to factor out redundant inc/dec ref's.

On Tue, 28 May 2013 09:50:42 -0400, David Nadlinger <see@klickverbot.at> wrote:

> On Tuesday, 28 May 2013 at 13:33:39 UTC, Steven Schveighoffer wrote:
>> I asked David Nadlinger at the conference whether we could leverage this power in LDC, since LLVM is the compiler back-end used by Apple, but he said all those optimization passes are in the Objective-C front-end.
>
> Hm, apparently I was imprecise or I slightly misunderstood your question:

More like I am a compiler ignorant and didn't understand/properly remember your answer :)  Thanks for clarifying.

-Steve

On Tuesday, 28 May 2013 at 13:56:03 UTC, Manu wrote:
> Yep, I can imagine it would work really well, if the front-end implemented
> the logic to factor out redundant inc/dec ref's.

It isn't the best idea to do this sort of optimizations (entirely) in the front-end, because you really want to be able to aggressively optimize away such redundant operations after inlining at what previously were function boundaries.

But then again, if you use AST-based inlining like DMD does, it might just work… ;)

David

On 29 May 2013 00:01, David Nadlinger <see@klickverbot.at> wrote:

> On Tuesday, 28 May 2013 at 13:56:03 UTC, Manu wrote:
>
>> Yep, I can imagine it would work really well, if the front-end implemented the logic to factor out redundant inc/dec ref's.
>>
>
> It isn't the best idea to do this sort of optimizations (entirely) in the front-end, because you really want to be able to aggressively optimize away such redundant operations after inlining at what previously were function boundaries.
>
> But then again, if you use AST-based inlining like DMD does, it might just work… ;)


Can you comment on the complexity of implementing this sort of garbage collection? (not really garbage collection, but serves the same purpose)

Am 28.05.2013 15:33, schrieb Steven Schveighoffer:
> On Sat, 25 May 2013 01:52:10 -0400, Manu <turkeyman@gmail.com> wrote:
>
>> What does ObjC do? It seems to work okay on embedded hardware
>> (although not
>> particularly memory-constrained hardware).
>> Didn't ObjC recently reject GC in favour of refcounting?
>
> Having used ObjC for the last year or so working on iOS, it is a very
> nice memory management model.
>
> Essentially, all objects (and only objects) are ref-counted
> automatically by the compiler.  In code, whenever you assign or pass a
> pointer to an object, the compiler automatically inserts retains and
> releases extremely conservatively.
>
> Then, the optimizer comes along and factors out extra retains and
> releases, if it can prove they are necessary.
>
> What I really like about this is, unlike a library-based solution where
> every assignment to a 'smart pointer' incurs a release/retain, the
> compiler knows what this means and will factor them out, removing almost
> all of them.  It's as if you inserted the retains and releases in the
> most optimized way possible, and it's all for free.
>
> Also, I believe the compiler is then free to reorder retains and
> releases since it understands how they work.  Of course, a
> retain/release is an atomic operation, and requires memory barriers, so
> the CPU/cache cannot reorder, but the compiler still can.
>...

I imagine Microsoft also does a similar thing with their C++/CX language extensions (WinRT handles).

On 29 May 2013 03:27, Paulo Pinto <pjmlp@progtools.org> wrote:

> Am 28.05.2013 15:33, schrieb Steven Schveighoffer:
>
>> On Sat, 25 May 2013 01:52:10 -0400, Manu <turkeyman@gmail.com> wrote:
>>
>>  What does ObjC do? It seems to work okay on embedded hardware
>>> (although not
>>> particularly memory-constrained hardware).
>>> Didn't ObjC recently reject GC in favour of refcounting?
>>>
>>
>> Having used ObjC for the last year or so working on iOS, it is a very nice memory management model.
>>
>> Essentially, all objects (and only objects) are ref-counted automatically by the compiler.  In code, whenever you assign or pass a pointer to an object, the compiler automatically inserts retains and releases extremely conservatively.
>>
>> Then, the optimizer comes along and factors out extra retains and releases, if it can prove they are necessary.
>>
>> What I really like about this is, unlike a library-based solution where every assignment to a 'smart pointer' incurs a release/retain, the compiler knows what this means and will factor them out, removing almost all of them.  It's as if you inserted the retains and releases in the most optimized way possible, and it's all for free.
>>
>> Also, I believe the compiler is then free to reorder retains and
>> releases since it understands how they work.  Of course, a
>> retain/release is an atomic operation, and requires memory barriers, so
>> the CPU/cache cannot reorder, but the compiler still can.
>> ...
>>
>
> I imagine Microsoft also does a similar thing with their C++/CX language
> extensions (WinRT handles).
>

Yeah certainly. It's ref counted, not garbage collected. And Android's V8
uses a "generational<http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Generational_GC_.28ephemeral_GC.29>
 incremental<http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Stop-the-world_vs._incremental_vs._concurrent>
collector"...
That'd be nice!
ObjC and WinRT are both used successfully on embedded hardware, I'm really
wondering if this is the way to go for embedded in D.
V8 uses an incremental collector (somehow?), which I've been saying is
basically mandatory for embedded/realtime use. Apparently Google agree.
Clearly others have already had this quarrel, their resolutions are worth
consideration.

Implementing a ref-counted GC would probably be much simpler than V8's mythical incremental collector that probably relies on Java restrictions to operate?

On Tue, 28 May 2013 20:40:03 -0400, Manu <turkeyman@gmail.com> wrote:


> ObjC and WinRT are both used successfully on embedded hardware, I'm really
> wondering if this is the way to go for embedded in D.
> V8 uses an incremental collector (somehow?), which I've been saying is
> basically mandatory for embedded/realtime use. Apparently Google agree.
> Clearly others have already had this quarrel, their resolutions are worth
> consideration.

An interesting thing to note, Apple tried garbage collection with Obj-C, but only on MacOS, and it's now been deprecated since automatic reference counting was introduced [1].  It never was on iOS.

So that is a telling omission I think.

-Steve

[1] https://en.wikipedia.org/wiki/Objective-C#Garbage_collection

On Wednesday, 29 May 2013 at 00:40:16 UTC, Manu wrote:
> On 29 May 2013 03:27, Paulo Pinto <pjmlp@progtools.org> wrote:
>
>> Am 28.05.2013 15:33, schrieb Steven Schveighoffer:
>>
>>> On Sat, 25 May 2013 01:52:10 -0400, Manu <turkeyman@gmail.com> wrote:
>>>
>>>  What does ObjC do? It seems to work okay on embedded hardware
>>>> (although not
>>>> particularly memory-constrained hardware).
>>>> Didn't ObjC recently reject GC in favour of refcounting?
>>>>
>>>
>>> Having used ObjC for the last year or so working on iOS, it is a very
>>> nice memory management model.
>>>
>>> Essentially, all objects (and only objects) are ref-counted
>>> automatically by the compiler.  In code, whenever you assign or pass a
>>> pointer to an object, the compiler automatically inserts retains and
>>> releases extremely conservatively.
>>>
>>> Then, the optimizer comes along and factors out extra retains and
>>> releases, if it can prove they are necessary.
>>>
>>> What I really like about this is, unlike a library-based solution where
>>> every assignment to a 'smart pointer' incurs a release/retain, the
>>> compiler knows what this means and will factor them out, removing almost
>>> all of them.  It's as if you inserted the retains and releases in the
>>> most optimized way possible, and it's all for free.
>>>
>>> Also, I believe the compiler is then free to reorder retains and
>>> releases since it understands how they work.  Of course, a
>>> retain/release is an atomic operation, and requires memory barriers, so
>>> the CPU/cache cannot reorder, but the compiler still can.
>>> ...
>>>
>>
>> I imagine Microsoft also does a similar thing with their C++/CX language
>> extensions (WinRT handles).
>>
>
> Yeah certainly. It's ref counted, not garbage collected. And Android's V8
> uses a "generational<http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Generational_GC_.28ephemeral_GC.29>
>  incremental<http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Stop-the-world_vs._incremental_vs._concurrent>
> collector"...
> That'd be nice!
> ObjC and WinRT are both used successfully on embedded hardware, I'm really
> wondering if this is the way to go for embedded in D.
> V8 uses an incremental collector (somehow?), which I've been saying is
> basically mandatory for embedded/realtime use. Apparently Google agree.
> Clearly others have already had this quarrel, their resolutions are worth
> consideration.
>
> Implementing a ref-counted GC would probably be much simpler than V8's
> mythical incremental collector that probably relies on Java restrictions to
> operate?

Actually what I was implying was the cleverness of the compiler to remove unnecessary increment/decrement operations via dataflows, similar to what Clang does.

Otherwise you pay too much for performance impact specially if multiple threads access the same objects. An incremental real time GC wins hands down in such scenarios.

Google IO is always a nice source of information on how V8 works,

https://developers.google.com/events/io/sessions/324431687
https://developers.google.com/events/io/sessions/324908972

--
Paulo

On Wednesday, 29 May 2013 at 00:46:18 UTC, Steven Schveighoffer wrote:
> On Tue, 28 May 2013 20:40:03 -0400, Manu <turkeyman@gmail.com> wrote:
>
>
>> ObjC and WinRT are both used successfully on embedded hardware, I'm really
>> wondering if this is the way to go for embedded in D.
>> V8 uses an incremental collector (somehow?), which I've been saying is
>> basically mandatory for embedded/realtime use. Apparently Google agree.
>> Clearly others have already had this quarrel, their resolutions are worth
>> consideration.
>
> An interesting thing to note, Apple tried garbage collection with Obj-C, but only on MacOS, and it's now been deprecated since automatic reference counting was introduced [1].  It never was on iOS.
>
> So that is a telling omission I think.
>
> -Steve
>
> [1] https://en.wikipedia.org/wiki/Objective-C#Garbage_collection

The main reason was that the GC never worked properly given the C underpinnings of Objective-C.

Too many libraries failed to work properly with GC enabled, plus you needed to fill your code with GC friendly annotations.

So I imagine Apple tried to find a compromises that would work better in a language with C "safety".

Even that is only supported at the Objective-C language level and it requires both compiler support and that objects inherit from NSObject as top most class, as far as I am aware.

Anyway it is way better than pure manual memory management.

--
Paulo

On 29.05.2013 02:46, Steven Schveighoffer wrote:
> On Tue, 28 May 2013 20:40:03 -0400, Manu <turkeyman@gmail.com> wrote:
>
>
>> ObjC and WinRT are both used successfully on embedded hardware, I'm
>> really
>> wondering if this is the way to go for embedded in D.
>> V8 uses an incremental collector (somehow?), which I've been saying is
>> basically mandatory for embedded/realtime use. Apparently Google agree.
>> Clearly others have already had this quarrel, their resolutions are worth
>> consideration.
>
> An interesting thing to note, Apple tried garbage collection with Obj-C,
> but only on MacOS, and it's now been deprecated since automatic
> reference counting was introduced [1].  It never was on iOS.
>
> So that is a telling omission I think.
>
> -Steve
>
> [1] https://en.wikipedia.org/wiki/Objective-C#Garbage_collection

Please note that you have to deal with circular references manually in Objective-C, introducing two types of pointers, strong and weak. I don't think this is optimal. If you want to deal with circular references automatically you again need some other kind of other garbage collection running.

A problem with the naive approach of atomic reference counting a counter inside the object (as usually done in COM interfaces, I don't know how it is done in Objective-C) is that it is not thread-safe to modify a pointer without locking (or a CAS2 operation that you don't have on popular processors). You can avoid that using deferred reference counting (logging pointer changes to some thread local buffer), but that introduces back a garbage collection step with possibly massive destruction. This step might be done concurrently, but that adds another layer of complexity to finding circles.

Another issue might be that incrementing a reference of an object when taking an interior pointer (like you do when using slices) can be pretty expensive because you usually have to find the base of the object to access the counter.

I won't dismiss RC garbage collection as impossible, but doing it efficiently and concurrently is not so easy.