More radical ideas about gc and reference counting

[Timon Gehr via Digitalmars-d]

On 05/11/2014 10:05 PM, Walter Bright wrote:
> On 5/11/2014 8:54 AM, Timon Gehr wrote:
>> It is not an escape from ARC per se. It is a way to write type safe
>> code which
>> is not dependent on the allocation strategy of the processed data.
>> (One can e.g.
>> safely borrow mutable data as immutable and the type system ensures
>> that during
>> the time of the borrow, the data does not mutate.)
>
> That's clearly an additional benefit of the borrowed pointer notion. But
> have you examined generated Rust code for the cost of inc/dec? I
> haven't, but I don't see any way they could avoid this (very expensive)
> cost without borrowed pointers.
> ...

Sure, but performance is the additional benefit.

>
>> The type system tracks lifetimes across function and data structure
>> boundaries.
>> The main restriction is that such a pointer cannot be escaped. (But
>> borrowed
>> pointers may still be stored in data structures.)
>
> The idea must be that the borrowed pointer lifetime cannot exceed the
> lifetime of the lender.
>
> The thing is, if the compiler is capable of figuring out these lifetimes
> by examining the code,

There are explicit lifetime annotations in function signatures.

> then there would be no need for the programmer to
> specify a pointer as borrowed - the compiler could infer it.

Not modularly. (Yes, global lifetime analysis exists, but this is not 
what they are doing.)

> Hence, there have got to be significant restrictions to the point where the
> compiler could figure out the rest.
> ...

It is simply not true that type systems are inherently restricted to 
checking trivial properties. They can be made as strong as mathematical 
logic without much fuss.

>
>>> 2. Introducing an annotation to distinguish a borrowed pointer from an
>>> ARC pointer. If you don't use the annotation, you get pervasive ARC with
>>> all the poor performance that entails.
>>> ...
>> No, this is completely inaccurate: Both choices are explicit,
>
> Yes, one is & and the other is @.

No, actually currently one is & and the other is RC<T> AFAIK.

> This does not change my point.

In my opinion it actually does, to the point of rendering it invalid.

> Back in
> the bad old DOS days, there was near* and *. The choices were explicit,

Explicit among near* and *. I.e. between adding 'near' and leaving it 
out. Also, if you add 'near' it will not be compatible with pointers 
that do not have it.

> but the results were there anyway - people overwhelmingly chose the more
> general *, performance be damned.
> ...

RC<T> is not more general. It cannot refer to stack-allocated data, for 
instance.

>
>> and reference
>> counting is just one of the possible memory management schemes. (Hence
>> borrowed
>> pointers are used unless there is a reason not to.)
>
> Yes, I can see it supports other schemes, but I predict that RC will
> dominate, and other schemes will be about as pervasive as using Boehm's
> GC with C++.
> ...

The point is, borrowing does not depend on the allocation scheme, as 
long as it is safe.

>
>>> Implicit in borrowed pointers is Rust did not solve the problem of
>>> having the compiler eliminate unnecessary inc/dec.
>> Avoiding inc/dec is not what justifies borrowed pointers.
>
> I find that very hard to believe. It implies that there is little cost
> to inc/dec, or the compiler is clever enough to eliminate the bulk of
> the inc/dec pairs.
> ...

Sure, borrowing is very lightweight, but ultimately what is most 
important is that it solves the problem of multiple incompatible pointer 
types and makes the type system more expressive as well.

>
>>> My experience with pointer annotations to improve performance is pretty
>>> compelling - almost nobody adds those annotations. They get their code
>>> to work with the default, and never get around to annotating it.
>> The 'default' way to pass by reference is by borrowed pointer.
>
> Time will tell how well having the most restrictive pointer type be the
> default works out.
> ...

A function that uses none of the specific pointer capabilities is more 
general, so what other choice of 'default' makes sense?

>
>>> They do not mix. A function taking one type of
>>> pointer cannot be called with the other type.
>> A function taking a borrowed pointer can be called with a reference
>> counted
>> pointer. Abstracting over allocation strategy is the point of borrowing.
>
> Right, and a function in DOS taking a * would accept a near*. But the
> other way did not work, and so people wrote their functions using *,
> performance was thrown under the bus.
>
>
>>> Are these valid concerns with Rust?
>> I don't think they are.
>
> Perhaps you're right. But my experience with DOS programming is
> programmers preferred convenience and reusable functions, and hence used
> plain * everywhere. And like I said, this provided a huge competitive
> advantage for me.
> ...

Convenience and reusable functions means using borrowed pointers 
whenever possible.

> The great boon with 32 bit code was the elimination of special pointer
> types, now it was easy to write fast, reusable functions, and the effort
> involved in creating efficient data structures dropped by probably half.
>
> It seems clear that the decisions of borrow/managed are going to pervade
> Rust code.

But they are often obvious.

> How well is that going to work with complex programs and data
> structures? How well with average programmers? How well is it going to
> work when some leaf has to change from borrowed to managed, and the
> ripple effects of that change?
>
> These are all unknowns, not proven successful technology.

They are using Rust to write a safe and performant web browser while 
developing the language.

> My experience with a similar system (16 bit C) does not make it look
> promising, as far as performance goes.

Borrowed pointers are not even superficially similar to near*. They are 
compatible with everything else, because they can store data that was 
borrowed from anywhere else.