Thread overview
[Dlang-study] [lifetime] Let's focus on escape analysis
Nov 01, 2015
deadal nix
Nov 02, 2015
Marc Schütz
Jan 19, 2016
György Andrasek
Jan 20, 2016
Amaury SECHET
Nov 02, 2015
Martin Nowak
November 01, 2015
There has been a fair amount of discussion about RC here, but I think it is missing the bigger picture.

There are a lot of variation of RC that can be done, but it doesn't really matter. After all, the problem that we want to solve as languages designer here is to control how references escape.

This is mandatory to have safe RC. After all, reference counted objects will have member data, which aren't themselves reference counted, and the language have to ensure these do not escape in unsafe manner.

But here is the plot twist: if we can provide a language solution that
ensure member data do not escape in unsafe manner, then we can ensure that
whatever is in a RC wrapper doesn't escape in an uncontrolled manner. We
win 2 things going that road:
 - All variations of RC become a library problems. We don't need to make a
judgement call on them at language level.
 - Functionality and memory management can be decoupled (upcast problem,
library can delegate RC/GC choice on their users).

Additionally, RC is a fairly small part of the problem. Unique reference
require the same kind of escape analysis while being WAY more common than
RC. Some here already did some grepping in Rust's source code to get an
idea of this, but here are the number I get grepping into clang/llvm :
$ grep -r ../llvm/lib/ ../clang/lib/ -e unique_ptr | wc -l
    1362
$ grep -r ../llvm/lib/ ../clang/lib/ -e shared_ptr | wc -l
      73

It is not even close.


November 02, 2015
On Sunday, 1 November 2015 at 22:09:04 UTC, deadal nix wrote:
> There has been a fair amount of discussion about RC here, but I think it is missing the bigger picture.
>
> There are a lot of variation of RC that can be done, but it doesn't really matter. After all, the problem that we want to solve as languages designer here is to control how references escape.

Needless to say, I agree. But various proposals to achieve that goal have been dismissed as "too complicated". I think this is therefore what we have to tackle first.

I can see complexity in three forms:

1.) Complexity of the concept

A system equivalent to Rust's is very complicated and requires various analysis passed to be added to the compiler frontend, considerably increasing the language's complexity. While I think that the escape analysis itself can be fairly simple (Walter's already implemented it partially for DIP25), a larger difficulty seems to be to make sure that the original owner does not somehow get invalidated during the lifetime of dependent references. This involves alias analysis. It also is an additional burden for the users and their understanding of the language.

Maybe there is a way to get the same guarantees that Rust provides by adding some additional restrictions that would enable both the implementation and the concept to be easier to understand? Or attacking the problem from a different angle, could we cut back on the guarantees (making some corner cases unsafe) to reduce the complexity?

There's also the question whether we want to integrate the related topic of uniqueness at the same time.

2.) Complexity in use of the language

Walter and others have rightly pointed out that we already have a plethora of annotations. We have to be careful not to make the situation worse. There are different ways to handle this: a) we can have the compiler infer attributes/annotations in more cases that it does now, and b) we can change some defaults so that frequent patterns are enabled by default and have to be opted out if necessary. Both ways will likely break some existing code, so we have to weigh out options and decide how much breakage is acceptable to simplify common use cases.

There's also the general point of ergonomy. The feature should integrate well with the existing language, and it shouldn't "get in our way". The latter is not only important for those who don't want to use it, but also for those who do, because we want to make it as easy as possible to write safe and efficient code that takes advantage of it.

3.) Compatibility

While it is probably possible to introduce this feature without breaking any code, this goal clashes with ease-of-use. If we make it completely opt-in (e.g. by requiring special keywords), this would mean that none of the existing code, including Phobos, is usable with it. We would essentially create a new version of the language.

We therefore need to design the feature in a way so that as much code as possible is automatically compatible. For example, many of the string processing functions only borrow references to the original string and don't keep them around after they returned; likewise, many of them return a reference to it. It would be nice if those need as few modifications as possible (ideally none) to take advantage of this fact.
_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

November 02, 2015
On 11/01/2015 11:09 PM, deadal nix wrote:
> There has been a fair amount of discussion about RC here, but I think it is missing the bigger picture.

I couldn't agree more.



November 02, 2015
On 11/02/2015 07:49 AM, Marc Schütz wrote:
> I can see complexity in three forms:
>
> 1.) Complexity of the concept
>
> A system equivalent to Rust's
[snip]

I don't follow Rust much, but my perception from following the trade news is that since launched it has scored a few victories (an OS project, a safe Doom implementation) but by and large the excitement has subsided after the pre-release excitement gave way to the post-1.0 certainty. The status seems to be - things aren't as great as they were cracked to be. Putting ownership front and center just makes things difficult, often for no good outcome.

(Our dmd downloads dropped strongly after the 1.0 announcement (May 15, 2015), but then they climbed back (http://erdani.com/d/downloads.daily.png).)

Do we have someone following Rust closely?

Let me add that D is already a large language - much larger that "Rust minus ownership"; it is my opinion that adding anything as involved as Rust's ownership to today's D, it will just crumble under its own weight. Of course I'm willing to change this opinion with good arguments and evidence.

> Maybe there is a way to get the same guarantees that Rust provides by
> adding some additional restrictions that would enable both the
> implementation and the concept to be easier to understand? Or attacking
> the problem from a different angle, could we cut back on the guarantees
> (making some corner cases unsafe) to reduce the complexity?

That's my hope. There has been a lot of recent work on reference counting (ARC, Petrank et al, Blackburn et al) that is very very compelling. I also believe we can creatively do new things, too, in addition to integrating such recent work.

> There's also the question whether we want to integrate the related topic
> of uniqueness at the same time.

I'd be fine with some restricted form of uniqueness - e.g. have a "box" that carries a unique value or null, and can be opened only destructively.

Also, there's the dynamic check for uniqueness that can be done with RC.



Andrei
_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

January 19, 2016
On Monday, 2 November 2015 at 16:03:04 UTC, Andrei Alexandrescu wrote:
> I don't follow Rust much, but my perception from following the trade news is that since launched it has scored a few victories (an OS project, a safe Doom implementation) but by and large the excitement has subsided after the pre-release excitement gave way to the post-1.0 certainty. The status seems to be - things aren't as great as they were cracked to be. Putting ownership front and center just makes things difficult, often for no good outcome.

The Rust devs have made a bunch of braindead design decisions that turned it from a promising systems language into a RAII tutorial for Rubyists. Finalizing those in 1.0 is what drove people away, including me.

That said, lifetime management is the one thing they did exactly right.

The key thing to observe here is that we already have lifetime semantics everywhere, it's just not always checked by the compiler. GC languages get around the issue by extending the unchecked lifetimes to infinity, the problem we have now is that this is incorrect without the GC. We don't need to add extra complexity or runtime overhead to do it right, just keep more information in the compiler and some syntax to talk about it.

In Rust, all object and reference lifetimes are tracked by the compiler, at no runtime cost. You can say "I'm only allocating objects that don't outlive me", and have it checked transitively for all references into those objects. You can say "my lifetime will be the shortest of the constructor arguments" or "my lifetime is independent of them".

Safe RC is almost trivial in Rust, they have both a thread-local `Rc<T>` and an atomic `Arc<T>` in the standard library. It's also very easy to write, say, lifetime-safe glib bindings, where the refcount semantics are documented externally.

It's almost always inferred away, there's no syntax overhead for the common case. Most people don't need to care beyond what they're already familiar with from the curly braces. In fact, neither `Rc<T>` nor `Arc<T>` have a single explicit lifetime annotation in their public API. It Just Works(tm), wrong usage will simply not compile.

For D, I believe this could be implemented without breaking any existing correct code, maybe with syntax like

    C!A foo(A: scope)(C!A c) { return c; }

or

    scope!A C foo(scope(A) C c) { return c; }

which with lifetime inference could safely be written as

   C foo(C c) { return c; }

Of course it gets tricky with mutability, raw pointers, non-static lifetimes etc, but Rust has been exploring the solution space for years now. It would be a shame to just ignore them, especially when people are already starting to do the same for C++: https://www.youtube.com/watch?v=hEx5DNLWGgA

_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

January 19, 2016
Well, Rust, as well as Swift, as irreducible control flow (understand no goto) which makes the analysis WAY easier to specify. I discussed this with Chris Latner in Dec and this was a very delibrate Swift design to go that road (we also discussed exception handling and he made some very good points, but that is for another time).


@Walter, could you describe the algorithm used by DMD to figure out where to put the destructors ? Especially when it comes to goto. That would help tremendously.

2016-01-19 13:44 GMT-08:00 György Andrasek <jurily@gmail.com>:

> On Monday, 2 November 2015 at 16:03:04 UTC, Andrei Alexandrescu wrote:
>
>> I don't follow Rust much, but my perception from following the trade news is that since launched it has scored a few victories (an OS project, a safe Doom implementation) but by and large the excitement has subsided after the pre-release excitement gave way to the post-1.0 certainty. The status seems to be - things aren't as great as they were cracked to be. Putting ownership front and center just makes things difficult, often for no good outcome.
>>
>
> The Rust devs have made a bunch of braindead design decisions that turned it from a promising systems language into a RAII tutorial for Rubyists. Finalizing those in 1.0 is what drove people away, including me.
>
> That said, lifetime management is the one thing they did exactly right.
>
> The key thing to observe here is that we already have lifetime semantics everywhere, it's just not always checked by the compiler. GC languages get around the issue by extending the unchecked lifetimes to infinity, the problem we have now is that this is incorrect without the GC. We don't need to add extra complexity or runtime overhead to do it right, just keep more information in the compiler and some syntax to talk about it.
>
> In Rust, all object and reference lifetimes are tracked by the compiler, at no runtime cost. You can say "I'm only allocating objects that don't outlive me", and have it checked transitively for all references into those objects. You can say "my lifetime will be the shortest of the constructor arguments" or "my lifetime is independent of them".
>
> Safe RC is almost trivial in Rust, they have both a thread-local `Rc<T>` and an atomic `Arc<T>` in the standard library. It's also very easy to write, say, lifetime-safe glib bindings, where the refcount semantics are documented externally.
>
> It's almost always inferred away, there's no syntax overhead for the common case. Most people don't need to care beyond what they're already familiar with from the curly braces. In fact, neither `Rc<T>` nor `Arc<T>` have a single explicit lifetime annotation in their public API. It Just Works(tm), wrong usage will simply not compile.
>
> For D, I believe this could be implemented without breaking any existing correct code, maybe with syntax like
>
>     C!A foo(A: scope)(C!A c) { return c; }
>
> or
>
>     scope!A C foo(scope(A) C c) { return c; }
>
> which with lifetime inference could safely be written as
>
>    C foo(C c) { return c; }
>
> Of course it gets tricky with mutability, raw pointers, non-static lifetimes etc, but Rust has been exploring the solution space for years now. It would be a shame to just ignore them, especially when people are already starting to do the same for C++: https://www.youtube.com/watch?v=hEx5DNLWGgA
>
>
> _______________________________________________
> Dlang-study mailing list
> Dlang-study@puremagic.com
> http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study
>


November 16
On Wednesday, 20 January 2016 at 02:33:03 UTC, Amaury SECHET wrote:
> Well, Rust, as well as Swift, as irreducible control flow (understand no goto) which makes the analysis WAY easier to specify. I discussed this with Chris Latner in Dec and this was a very delibrate Swift design to go that road (we also discussed exception handling and he made some very good points, but that is for another time).

Can you elaborate on this? What are the pros and cons?
_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study