On 4/16/2014 5:06 PM, Michel Fortin wrote:
> It's not just ARC. As far as I know, most GC algorithms require some action to
> be taken when changing the value of a pointer. If you're seeing this as
> unnecessary bloat, then there's not much hope in a better GC for D either.

Yeah, those are called write gates. The write gate is used to tell the GC that "I wrote to this section of memory, so that bucket is dirty now." They're fine in a language without pointers, but I just don't see how one could write fast loops using pointers with write gates.

> But beyond that I wonder if @nogc won't entrench that stance even more. Here's
> the question: is assigning to a pointer allowed in a @nogc function?  Of course
> it's allowed! Assigning to a pointer does not involve the GC in its current
> implementation... but what if another GC implementation to be used later needs
> something to be done every time a pointer is modified, is this "something to be
> done" allowed in a @nogc function?

It would have to be.

On Wednesday, 16 April 2014 at 22:42:23 UTC, Adam Wilson wrote:

> Long story short, Tracing vs. Ref-counting are algorithmic duals and therefore do not significantly differ. My read of the article is that all the different GC styles are doing is pushing the cost somewhere else.

All memory management schemes cost, even manual memory management.  IMO that's not the point.  The point is that each memory management scheme distributes the cost differently.  One distribution may be more suitable for a certain problem domain than another.

> ARC may in fact be the most advantageous for a specific use case, but that in no way means that all use cases will see a performance improvement, and in all likelihood, may see a decrease in performance.

The same can be said about stop-the-world mark-and-sweep.  It is also specialized to a specific problem domain.  As an example, it doesn't scale well to the real-time/embedded domain.

> That makes ARC a specialization for a certain type of programming, which would then remove D the "Systems" category and place it in a "Specialist" category. One could argue that due to the currently non-optional status of the GC that D is currently a "Specialist" language, and I would be hard pressed to argue against that.

D is currently in the "Specialist" category.  It is already specialized/biased to PC/Server applications.  C/C++ are the only languages I know of that scale reasonably well to all systems.  I think D has the potential to change that, but it will require, first, recognition that D is not yet a "Systems" language like C/C++ are, and second, the will to change it.

> @nogc removes the shackles of the GC from the language and thus brings it closer to the definition of "Systems". @nogc allows programmers to revert to C-style resource management without enforcing a specialized RM system, be it GC or ARC. @nogc might not make you run through the fields singing D's praises, but it is entirely consistent with the goals and direction of D.

@nogc doesn't allow users to revert to C-style resource management because they don't have control over implicit allocations in druntime and elsewhere.  It just disables them.  Users still have to build alternatives.  There's no escaping the cost of memory management, but one could choose how to distribute the cost.

Mike

On 17 April 2014 03:37, Walter Bright via Digitalmars-d < digitalmars-d@puremagic.com> wrote:

> On 4/16/2014 4:50 AM, Manu via Digitalmars-d wrote:
>
>> I am convinced that ARC would be acceptable,
>>
>
> ARC has very serious problems with bloat and performance.
>

This is the first I've heard of it, and I've been going on about it for ages.


Every time a copy is made of a pointer, the ref count must be dealt with,
> engendering bloat and slowdown. C++ deals with this by providing all kinds of ways to bypass doing this, but the trouble is such is totally unsafe.
>

Obviously, a critical part of ARC is the compilers ability to reduce
redundant inc/dec sequences. At which point your 'every time' assertion is
false. C++ can't do ARC, so it's not comparable.
With proper elimination, transferring ownership results in no cost, only
duplication/destruction, and those are moments where I've deliberately
committed to creation/destruction of an instance of something, at which
point I'm happy to pay for an inc/dec; creation/destruction are rarely
high-frequency operations.

Have you measured the impact? I can say that in realtime code and embedded code in general, I'd be much happier to pay a regular inc/dec cost (a known, constant quantity) than commit to unknown costs at unknown times. I've never heard of Obj-C users complaining about the inc/dec costs.

If an inc/dec becomes a limiting factor in hot loops, there are lots of things you can do to eliminate them from your loops. I just don't buy that this is a significant performance penalty, but I can't say that experimentally... can you?

How often does ref fiddling occur in reality? My guess is that with redundancy elimination, it would be surprisingly rare, and insignificant. I can imagine that I would be happy with this known, controlled, and controllable cost. It comes with a whole bunch of benefits for realtime/embedded use (immediate destruction, works in little-to-no-free-memory environments, predictable costs, etc).


Further problems with ARC are inability to mix ARC references with non-ARC
> references, seriously hampering generic code.


That's why the only workable solution is that all references are ARC
references.
The obvious complication is reconciling malloc pointers, but I'm sure this
can be addressed with some creativity.

I imagine it would look something like:
By default, pointers are fat: struct ref { void* ptr, ref_t* rc; }
malloc pointers could conceivably just have a null entry for 'rc' and
therefore interact comfortably with rc pointers.
I imagine that a 'raw-pointer' type would be required to refer to a thin
pointer. Raw pointers would implicitly cast to fat pointers, and a
fat->thin casts may throw if the fat pointer's rc is non-null, or compile
error if it can be known at compile time.

Perhaps a solution is possible where an explicit rc record is not required
(such that all pointers remain 'thin' pointers)...
A clever hash of the pointer itself can look up the rc?
Perhaps the rc can be found at ptr[-1]? But then how do you know if the
pointer is rc allocated or not? An unlikely sentinel value at ptr[-1]?
Perhaps the virtual memory page can imply whether pointers allocated in
that region are ref counted or not? Some clever method of assigning the
virtual address space so that recognition of rc memory can amount to
testing a couple of bits in pointers?

I'm just making things up, but my point is, there are lots of creative possibilities, and I have never seen any work to properly explore the options.

 and I've never heard anyone suggest
>> any proposal/fantasy/imaginary GC implementation that would be acceptable...
>>
>
> Exactly.


So then consider ARC seriously. If it can't work, articulate why. I still
don't know, nobody has told me.
It works well in other languages, and as far as I can tell, it has the
potential to produce acceptable results for _all_ D users.
iOS is a competent realtime platform, Apple are well known for their
commitment to silky-smooth, jitter-free UI and general feel. Android on the
other hand is a perfect example of why GC is not acceptable.


 In complete absence of a path towards an acceptable GC implementation, I'd
>> prefer to see people that know what they're talking about explore how
>> refcounting could be used instead.
>> GC backed ARC sounds like it would acceptably automate the circular
>> reference
>> catching that people fuss about, while still providing a workable
>> solution for
>> embedded/realtime users; disable(/don't link) the backing GC, make sure
>> you mark
>> weak references properly.
>>
>
> I have, and I've worked with a couple others here on it, and have completely failed at coming up with a workable, safe, non-bloated, performant way of doing pervasive ARC.
>

Okay. Where can I read about that? It doesn't seem to have surfaced, at
least, it was never presented in response to my many instances of raising
the topic.
What are the impasses?

I'm very worried about this. ARC is the only imaginary solution I have
left. In lieu of that, we make a long-term commitment to a total fracturing
of memory allocation techniques, just like C++ today where interaction
between libraries is always a massive pain in the arse. It's one of the
most painful things about C/C++, and perhaps one of the primary causes of
incompatibility between libraries and frameworks. This will transfer into
D, but it's much worse in D because of the relatively high number of
implicit allocations ('~', closures, etc).
Frameworks and libraries become incompatible with each other, which is a
problem in C/C++ that modern languages (java, C#, python, etc) typically
don't suffer.

My feeling is that, if D doesn't transcend these fundamental troubles we wrestle in C++, then D is a stepping stone rather than a salvation. @nogc, while seemingly simple and non-destructive, feels kinda like a commitment, or at least an acceptance, of fracturing allocation paradigms between codebases. Like I say before, I kinda like the idea of @nogc, but I'm seriously concerned about what it implies...

On 17 April 2014 08:42, Adam Wilson via Digitalmars-d < digitalmars-d@puremagic.com> wrote:

> On Wed, 16 Apr 2014 04:50:51 -0700, Manu via Digitalmars-d < digitalmars-d@puremagic.com> wrote:
>
>  I am convinced that ARC would be acceptable, and I've never heard anyone
>>
>> suggest any proposal/fantasy/imaginary GC implementation that would be
>> acceptable...
>> In complete absence of a path towards an acceptable GC implementation, I'd
>> prefer to see people that know what they're talking about explore how
>> refcounting could be used instead.
>> GC backed ARC sounds like it would acceptably automate the circular
>> reference catching that people fuss about, while still providing a
>> workable
>> solution for embedded/realtime users; disable(/don't link) the backing GC,
>> make sure you mark weak references properly.
>>
>
> I'm just going to leave this here. I mentioned it previously in a debate over ARC vs. GC but I couldn't find the link at the time.
>
> http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf
>
> The paper is pretty math heavy.
>
> Long story short, Tracing vs. Ref-counting are algorithmic duals and therefore do not significantly differ. My read of the article is that all the different GC styles are doing is pushing the cost somewhere else.
>

Of course, I generally agree. Though realtime/embedded values smooth predictability/reliability more than burst+stutter operation.

That said, I do think that GC incurs greater cost than ARC in aggregate though. The scanning process, and the cache implications of scanning the heap are cataclysmic. I don't imagine that some trivial inc/dec's would sum to the same amount of work, even though they're happening more frequently.

GC has a nasty property where its workload in inversely proportional to
available memory.
As free memory decreases, frequency of scans increase. Low-memory is an
important class of native language users that shouldn't be ignored
(embedded, games consoles, etc).

Further, The cost of a GC sweep increases with the size of the heap. So, as free memory decreases, you expect longer scans, more often... Yeah, win!

There are some other disturbing considerations; over time, as device memory
grows, GC costs will increase proportionally.
This is silly, and I'm amazed a bigger deal isn't made about the
future-proof-ness of GC. In 5 years when we all have 512gb of ram in our
devices, how much time is the GC going to spend scanning that much memory?

GC might work okay in the modern sweet-spot of 100-mb's to low-gb of total memory, but I think as memory grows with time, GC will become more problematic.

ARC on the other hand has a uniform, predictable, constant cost, that never changes with respect to any of these quantities. ARC will always perform the same speed, even 10 years from now, even on my Nintendo Wii, even on my PIC microcontroller. As an embedded/realtime programmer, I can work with this.


ARC may in fact be the most advantageous for a specific use case, but that
> in no way means that all use cases will see a performance improvement, and in all likelihood, may see a decrease in performance.
>

If you had to choose one as a default foundation, would you choose one that
eliminates a whole class of language users, or one that is an acceptable
compromise for all parties?
I'd like to see an argument for "I *need* GC. GC-backed-ARC is unacceptable
for my use case!". I'll put money on that requirement never emerging, and I
have no idea who that user would be.

Also, if you do see a decrease in performance, I suspect that it's only
under certain conditions. As said above, if your device begins to run low
on memory, or your users are working on unusually large projects/workloads,
all of a sudden your software starts performing radically differently than
you observe during development.
Naturally you don't typically profile that environment, but it's not
unlikely to occur in the wild.


That makes ARC a specialization for a certain type of programming, which
> would then remove D the "Systems" category and place it in a "Specialist" category.


What it does, is NOT eliminate a whole class of users. Are you going to tell me that you have a hard dependency on the GC, and something else that does exactly the same thing is incompatible with your requirements? There's nothing intrinsically "systems" about GC over ARC, whatever that means.


One could argue that due to the currently non-optional status of the GC
> that D is currently a "Specialist" language, and I would be hard pressed to argue against that.
>

So what's wrong with a choice that does exactly the same thing, but is less exclusive?


@nogc removes the shackles of the GC from the language and thus brings it
> closer to the definition of "Systems". @nogc allows programmers to revert to C-style resource management without enforcing a specialized RM system, be it GC or ARC. @nogc might not make you run through the fields singing D's praises, but it is entirely consistent with the goals and direction of D.


I see some value in @nogc. I'm not arguing against it. My point what that I
feel it is missing the point, and I fear for the implications... does this
represent a dismissal of the root problem?
See my points about fracturing frameworks and libraries into isolated
worlds. This is a critical problem in C/C++ that I would do literally
anything to see not repeated in D.

On 17 April 2014 09:20, Walter Bright via Digitalmars-d < digitalmars-d@puremagic.com> wrote:

> On 4/16/2014 3:42 PM, Adam Wilson wrote:
>
>> ARC may in fact be the most advantageous for a specific use case, but
>> that in no
>> way means that all use cases will see a performance improvement, and in
>> all
>> likelihood, may see a decrease in performance.
>>
>
> Right on. Pervasive ARC is very costly, meaning that one will have to define alongside it all kinds of schemes to mitigate those costs, all of which are expensive for the programmer to get right.
>

GC is _very_ costly. From my experience comparing iOS and Android, it's
clear that GC is vastly more costly and troublesome than ARC. What measure
do you use to make that assertion?
You're also making a hidden assertion that the D GC will never improve,
since most GC implementations require some sort of work similar to ref
fiddling anyway...

On 17 April 2014 10:06, Michel Fortin via Digitalmars-d < digitalmars-d@puremagic.com> wrote:

> On 2014-04-16 23:20:07 +0000, Walter Bright <newshound2@digitalmars.com> said:
>
>  On 4/16/2014 3:42 PM, Adam Wilson wrote:
>>
>>> ARC may in fact be the most advantageous for a specific use case, but
>>> that in no
>>> way means that all use cases will see a performance improvement, and in
>>> all
>>> likelihood, may see a decrease in performance.
>>>
>>
>> Right on. Pervasive ARC is very costly, meaning that one will have to define alongside it all kinds of schemes to mitigate those costs, all of which are expensive for the programmer to get right.
>>
>
> It's not just ARC. As far as I know, most GC algorithms require some action to be taken when changing the value of a pointer. If you're seeing this as unnecessary bloat, then there's not much hope in a better GC for D either.
>

Indeed.

But beyond that I wonder if @nogc won't entrench that stance even more.


This is *precisely* my concern. I'm really worried about this.

On Wednesday, 16 April 2014 at 23:14:27 UTC, Walter Bright wrote:
> On 4/16/2014 3:45 PM, "Ola Fosheim Grøstad" I've written several myself that do not use malloc.

If it is shared or can call brk() it should be annotated.

> Even the Linux kernel does not use malloc. Windows offers many ways to allocate memory without malloc. Trying to have a core language detect attempts to write a storage allocator is way, way beyond the scope of what is reasonable for it to do.

Library and syscalls can be marked, besides you can have dynamic tracing in debug mode.

> And, frankly, I don't see a point for such a capability.

Safe and contention free use of libraries in critical code paths. The alternative is to guess if it is safe to use.

> malloc is hardly the only problem people will encounter with realtime callbacks. You'll want to avoid disk I/O, network access, etc., too.

Yes, all syscalls. But malloc is easier to overlook and it might call brk() seldom, so detecting it without support might be difficult.

On Thursday, 17 April 2014 at 03:14:21 UTC, Manu via Digitalmars-d wrote:
> Obviously, a critical part of ARC is the compilers ability to reduce
> redundant inc/dec sequences.

You need whole program opimization to do this well. Which I am strongly in favour of, btw.

> I've never heard of Obj-C users complaining about the inc/dec costs.

Obj-C has lots of overhead.

> Further problems with ARC are inability to mix ARC references with non-ARC
>> references, seriously hampering generic code.
>
>
> That's why the only workable solution is that all references are ARC references.

I never understood why you cannot mix. If your module owns a shared object you should be able to use regular pointers from that module.

> So then consider ARC seriously. If it can't work, articulate why.

It can work if the language is designed for it, and code is written to enable optimizations.

IMHO you need a seperate layer to enable compiletime proofs if you want to have safe and efficient system level programming. A bit more than @safe, @pure etc.

> iOS is a competent realtime platform, Apple are well known for their
> commitment to silky-smooth, jitter-free UI and general feel.

Foundational libraries does not use ARC? Only higher level stuff?

Ola

On Thursday, 17 April 2014 at 04:19:00 UTC, Manu via
Digitalmars-d wrote:
> On 17 April 2014 09:20, Walter Bright via Digitalmars-d <
> digitalmars-d@puremagic.com> wrote:
>
>> On 4/16/2014 3:42 PM, Adam Wilson wrote:
>>
>>> ARC may in fact be the most advantageous for a specific use case, but
>>> that in no
>>> way means that all use cases will see a performance improvement, and in
>>> all
>>> likelihood, may see a decrease in performance.
>>>
>>
>> Right on. Pervasive ARC is very costly, meaning that one will have to
>> define alongside it all kinds of schemes to mitigate those costs, all of
>> which are expensive for the programmer to get right.
>>
>
> GC is _very_ costly. From my experience comparing iOS and Android, it's
> clear that GC is vastly more costly and troublesome than ARC. What measure
> do you use to make that assertion?
> You're also making a hidden assertion that the D GC will never improve,
> since most GC implementations require some sort of work similar to ref
> fiddling anyway...

Except Dalvik's GC sucks, because it is hardly improved since
Android 2.3 and very simple when compared to any other commercial
JVM for embedded scenarios, for example Jamaica JVM
https://www.aicas.com/cms/.

Even Windows Phone .NET GC is better and additionally .NET is
compiled to native code on the store.

There is a reason why Dalvik is being replaced by ART.

--
Paulo

On Thursday, 17 April 2014 at 06:56:11 UTC, Paulo Pinto wrote:
> There is a reason why Dalvik is being replaced by ART.

AoT compilation?

Btw, AFAIK the GC is deprecated for Objective-C from OS-X 10.8. Appstore requires apps to be GC free... Presumably for good reasons.