Blog Post: Lifetime Parameters in Rust


#21

My upthread off-the-top-of-my-head idea was to have the compiler infer them and write them to a shadow file. I posited we can still see them in an IDE (toggle) and/or in error messages. So I posited we would only have to write them when we need to overrule the inference or when inference is undecideable (and then the can be removed after compiling because written to the shadow file). I am not arguing that is a good idea. I am just trying to figure out if what Rust is now is best, and for which use cases it is best fit.

My thought is that most of the time I don’t want to look at or think about that detail. The inference could probably be good enough 80% of the time perhaps. I am prioritizing looking at the other semantics of my code. But maybe I am mistaken, because maybe I am thinking about how when I code only my innermost performance routines in C, I am always passing in borrowed pointer to a C function which doesn’t leak any references, so I don’t even need to think about it. And in other code (ever since using C++ with refcounting for the last time in 2002), I have been using a GC so I didn’t have to think about it.

Perhaps this is related to my point that what probably or perhaps dominates the asymptotic memory performance of 80+% of my code is avoiding the type of “memory leaks” that can occur with both Rust’s checked lifetimes and GC. I just can’t imagine writing a mobile game (speed not a major factor, i.e. not 3D), word processing, or other productivity app with such coding precision that the entire body of code is compile-time checked manual memory mgmt (although I did ref counting for my last C++ app finished in 2002). Instead I would write most of the code employing GC and then the critical parts that need to be super fast I would write in C as stated above.

Thus for me, I envision a language that combined high level and low level coding, would allow me to write my “C” code in the same language, but still alllow me to use GC for most of my code. What aggravates me about managed languages such as Java, JS, is I have to switch to a FFI and other language to write the performance bits of code. I would prefer it was all unified if that makes sense.

Yet I am also paying attention to what others say here and trying to relate it to my experience. So I am still trying to for a clear analysis of what I want and for which use cases. I realize there are other use cases where perhaps different priorities and patterns apply.

Afair most of my code is not passing Copy types. Seems boxes are the norm, except in some requirement for highly performant (lower-level) homogeneous (or hetereogenous via enum) arrays and vectors.

I’m eager to read different perspectives.

Edit: if asymptotic “memory leaks” is the main culprit to attack (thus Rust’s lifetimes wouldn’t fix it), perhaps for example the browser should isolate memory partitions for each tab open in my browser and kill tabs that are overconsuming when GC starts thrashing instead of locking up my entire Linux desktop as Firefox does now. And it is probably all that adware bloat scripting that google et al dump on every web page with advertising.


#22

IMO the advantage of the current system is, that the lifetimes are hidden for the common/intuitive cases. And they are explicit where they don’t conform to the obvious rules. This raises attention that something is different.

I think it would probably be more confusing if they were omitted in all cases. Because you would always expect the default case at first and only notice the difference after compilation fails.

Also, I’m always a bit sceptical about inference. Yes, there exist powerful algorithms, but they can only infer what is possible to infer. If I make a mistake, inference cannot point me to it because I didn’t write up my expectations.

Like const-correctness in C++ for example. I often hear that it is unnecessary because it can be inferred.
Sometimes I see a parameter that should “obviously” be const. In a different language I’d just think “well inference will do it correctly”, but in C++ i can actually mark it as const. Then most of the time it doesn’t just compile as is, but there are missing annotations here and there and often there’s a little detail that actually prevents the whole thing from being const without some refactoring. It’s tedious but I can refactor until it compiles. And often this means improving encapsulation and correcting design flaws.


#23

That’s where my Rust code is very different from my C++ code. In C++ I use new much more often than box in Rust. This is mainly because of the “move by default” policy. A combination of pass by value (moving) and some clone() calls here and there is usually sufficient.
In Rust, even the new() functions usually return by value.

In C++ projects that make extensive use of reference counting, ownership is often not clear anymore. That means you have to RC everything, because maybe it is needed somewhere and allocating on the stack could lead to nasty stack corruptions. In Rust ownership and borrowing is always explicit and that problem simply doesn’t exist anymore.


#24

This makes me think of IDE friendly features like being able to directly give the compiler an abstract-syntax-tree in some kind of easy to use format like JSON, and have the compiler give back the syntax tree with type annotations. That way the types can appear as tool-tips when you hover over code.

Regarding Copy types, I have so far preferred to use explicit Clones rather than requiring Copy in my code, and the only place I have needed a Box so far is returning a closure from a function. I am hoping that need for a Box will go away soon, and I can return a closure as a trait, allowing better inlining possibilities.

I really don’t understand the need for Boxes everywhere, they should only be needed where you have runtime polymorphism, which in most programs is a small subset of the total code (where you would need virtual functions in C++). Certainly in Haskell you only want to use existential types when strictly necessary? How much use do you see of existential types (the equivalent of boxes) in the average Haskell program? Maybe people need to look at using more functional design patterns?


#25

Afaics, we’ve established that refcounting is worse in every way:


#26

I don’t think that “we” have established anything.

Your citing a blog post that is over 10 years old. All the downsides of RC that are mentioned in that article are IMO solved in Rust or not valid:

  • It is very OO-centric and assumes that everything can be casted to System.Object
  • It outrightly dismisses value types with very questionable reasoning
  • It ignores moving as it is the default in Rust and also possible in C++ (move constructors).
  • It assumes that if you use RC, you have to use it everywhere. Which is not true at all as Rust shows.
  • It assumes pervasive multithreading and thus atomic RC, which is not necessary most of the times and safely so in Rust
  • It mentions memory consumption as a downside of RC because every object is 4 bytes larger. WTF
  • It mentions deterministic finalization as one of the key points of RC, but in the end they decided against it because of language interop with other GC-languages.

Circular references are really the only problem from the entire list that is a valid point.

OTOH, they gloss of over the problems of GC, for example:

  • Increased memory consumption (now really).
  • If used sparingly and if without producing much garbage, GC has still a high overhead while RC has not.
  • Interop issues with non-GC languages. Finalizer running in a different thread is a PITA.
  • Deterministic destruction which is mentioned but not considered important enough (which I disagree).

EDIT, another point:

  • Dependencies on the order of finalization is not possible with GC.

EDIT2, yet another point:

  • In interop, GC doesn’t know about allocations in other languages. With C#, I’ve even experienced OOM in native code because of the GC being such a memory hog.

#27

Haven’t you argued that RC is inferior to Rust’s lifetimes in your prior comment that I had replied to?

META: I want to make sure we are on the same wavelength in terms of not intending any animosity. I had to choose between ‘I’, ‘you’, ‘they’, or ‘we’; so I chose the word that seemed the most fit even though it isn’t a perfect word. We can either blame the English language or just accept that I am (we are?) trying to achieve a goal which is to try to reach some clarity on comparisons of strategies for resource lifetimes, especially memory but also other resources. I suppose you are just clarifying and not intending animosity; and so I also want you to know I wasn’t also trying to declare (without your participation what you think and that) ‘you’ wouldn’t have other points to make in response. I make the post, so you can agree or disagree and provide additional points. Afaics, that is the nature of discussion. Thanks.

Do you know of more recent benchmarks to offer?

I cited that blog post w.r.t. to RC, not w.r.t. to Rust’s compile-time checked lifetimes. Are you introducing Rust’s advantages as a rebuttal to my point about RC’s disadvantages? Is your point that RC is better in Rust?

The cited performance had even the single-threaded RC slower than GC.

Taken out-of-context their point does seem silly because GC also uses more memory to achieve the same performance as Rust’s compile-time checked lifetimes. Also I read that Apple’s use of RC on 64-bit Android puts the refcount in the upper unused 19 bits of the 64-bit pointers. But I think perhaps their point could be that RC and GC can consume more memory than explicit memory management, but according to their benchmarks RC isn’t any faster than GC (and egregiously slower in the multi-threaded case) and RC doesn’t free circular references but GC does. Afaics, their goal was to compare RC and GC.

META: Hey all of us have had those moments where we look at something and we think to ourself, “wtf was this guy not thinking, this doesn’t make any sense”. I assume we both agree to not go there. We give each other more than one or two posts to understand what the other person is attempting to communicate. Thanks.

At that time, they had to choose between explicit memory management (EMM), RC, and GC, or some combination of them. EMM doesn’t provide safety. RC doesn’t free circular references. GC doesn’t provide deterministic finalization.

It might be helpful for Rust to provide a table on their website and note this table is mitigated when asymptotic memory consumption is primarily due to the semantic “memory leaks” which can’t be tracked by any of the following strategies and which are ostensibly inherent in many non-mission critical apps:

EMM…Rust…RC…GC
…x…x…x… safety{}
x…x…x… frees circular
x…x…x… deterministic finalization
x…x…x…x… higher throughput even with higher memory consumption{
}
x…x… higher throughput with lowest memory consumption
x…x…x…x… lower latency pauses even with lower throughput
x…x… lower latency pauses with highest throughput
x…x…x… lower memory consumption at the same throughput{
}
…x… simpler (i.e. not as complex) to code {
*}

{} Only true for RC if single-threaded, even in the case of RC in Rust.
{} RC not included bcz need to reason about circular references
{
} not including checking mutability conflicts, which Rust can do at compile-time

Note the above table also doesn’t deal with the issue of efficiency and complexity w.r.t. temporary objects. I am planning to discuss that separately.

Looking at the above chart, I can see why one of my first comments on this forum was that the main reason for choosing Rust’s compile-time checked lifetimes is performance. The item I forgot was deterministic finalization, which afaics applies to resources other than memory (which wasn’t my focus originally). Note I’ve read that there has been some experimentation with making GC’s aware of the other resource types they are collecting and thus collect them when they are nearing exhaustion.

In your prior comment you wrote:

Okay I think I was missing your point before. Notice when I replied before, I didn’t quote the last sentence because I didn’t see how it related to your comment about RC. It seems your point is that given the ability to know that all references are either RC or statically checked, then RC doesn’t have to be used everywhere, but it can still be used selectively.

Can you provide a compelling example where one would want to use RC and not Rust’s static checking?

I am not understanding why you mentioned these points?

Maybe in the context of combined with Rust’s compile-time checked resources that is so, if you can make the single-threaded performance as fast as GC and you never need to use RC in the multi-threaded scenario.

Aren’t you missing the case where we have shared immutable references in the multi-threaded scenario?

Readers note I am registering in my mind that the asynchronously threaded (i.e. single-threaded, multiple code paths) is not a performance issue for RC.

For the Java example research paper I had cited, double the memory for 70% loss of throughput, triple the memory for 17% reduction in throughput, and 5X the memory for equivalent throughput. Note I am not sure if that is factoring in latency pauses, which to keep to a minimum may require a further erosion of throughput for the concurrent GC.

But how much does programmer time, maintenance, readability of code, and slower-to-market cost? Memory cost is declining exponentially, but we have very few methods of increasing programmer productivity. Thus I conclude the argument for prioritizing by default lower memory consumption is a losing one. Why did even Raytheon invest in the research to produce a guaranteed low latency GC algorithm ostensibly for mission critical applications.

The salient forward problem with memory allocation are the semantic “memory leaks” that none of the above strategies can fix.

EMM and Rust can also attain low latency without incurring lower throughput. But again my retort is CPU performance is increasingly exponentially, at least in the case of parallelism.

Sorry I can be sort of an unintentional pita that way, when one raises their hand to say, “but what happens when people move” or “but Bitcoin’s double hashing may be a back door vulnerable to Boomerang attack”.

Perhaps you can make a more defensible point w.r.t. to resource types other than memory?

I think that might not be true with a generation GC if the language and design patterns are well optimized w.r.t. to temporary objects? This is the topic I am soon going to get into when I write down my thoughts on temporary objects and inversion-of-control and also present my ideas to replace iterators. I think we need to look at this holistically. Perhaps I have a mistake. We will get into it soon.

I am wondering if I won’t end up concluding that we should only be using GC. And then finalization may be an orthogonal issue and I am contemplating if we should be thinking about finalization more high-level semantically. My conceptualization is not yet fully formed. Hopefully I can come to a complete understanding asap. My intuition may be incorrect.

I have enough experience in my life to learn that humans build tools because they don’t like to dig canals with spoons. Masochism is not a virtue that most people want to emulate. “C is manly, but Python is for n00bs”. Hey I am very masochist when I ran a 10K in under 35 minutes, but that is irrelevant.

I am still trying to discern the use cases why I would need the tool of compile-time lifetimes. I suppose at this time, GC on popular VMs have horrible asymptotic latency (pauses) and mobile is currently RAM constricted. So those are current use cases in my realm. But I am also future thinking.

Shouldn’t that be modeled high-level semantically and not by some low-level opaque mechanism.

Are you sure that is not due to the asymptotic memory consumption due to the semantic “memory leaks” I’ve mentioned?

Again I am not sure I want to use any memory allocation other than GC. I am still trying to make that determination.


Rust as a High Level Language
Inversion-of-control resource management
#28

That is what I was thinking also. But that obviously applies as an idea for those who decide they need Rust’s lifetime checking. I am still trying to decide if I even need it.

By what nikomatsakis confirmed, I am contemplating that for me it will not be intuitive because my mind expects it to do what should be inferred (but I say this with no experience of coding with it). It is a set of arbitrary rules about position and structure, that I must remember and it doesn’t have any inference intelligence.

My idea is that when you don’t want to accept the inference of the compiler, you would explicitly annotate.

But any way, I don’t want to argue too far along this idea, because I think the interaction of inference and piece-meal annotation will probably be very hard to predict in some cases. Corner cases are certain to arise. Where I am with this in my mind right now, is I am really hoping I can justify choosing GC every where and not have to go down this road of complexity. Sorry that is my intuitive stance. But I will be sure to let only rationality form my decision. So again, I remain eager to read the counter points of others.

Note I will reply about Copy types, moving, and temporary objects in a separate post.


#29

Thanks for clarifying this. You seemed to imply that it is an universally agreed fact that GC is superior to RC in all aspects. I just wanted to point out that I have a different opinion, thus excluding myself from the “we”.

No, I don’t have recent benchmarks. My point is not primarily about benchmarks but about different preconditions now and then. You just cannot apply the same arguments to early .NET and todays Rust.

But I also think that the numbers could be different today. Optimizers are improving constantly and I think RC has better optimization potential (elision of redundant inc/dec) than GC. But this is just speculation.

That’s a good summary. And I suspect that GC performs worse in that case. At least in the border case where you don’t use RC/GC at all, there’s still overhead for GC but not for RC. I don’t know where the point of equal overhead is, though…

It’s not always possible:

  • References imply no ownership
  • Box / value types implies unique ownership
  • Rc for shared single-threaded ownership
  • Arc for shared multi-threaded ownership

IME, the usage frequency of those is descending in the order that I listed them. In only use Rc/Arc where true shared ownership is semantically necessary, which is actually very seldom the case.

Just to show how different the preconditions are. Rust is not OO, it uses value types and moving extensively. All those points lead to lower overhead for RC, but not (necessarily) for GC.

Sure, that case exists. But I don’t think this is needed very often (in contrary to purely functional languages), and if you use it, it is always explicit by using Arc or something similar.

That’s true and I agree that using a GC is often convenient. But in the cases where you reach the limits it will produce more work than not using one.

With cloud computing, using more resources automatically means more expensive.

The list of downsides of GC is not a theory, it’s what caused me headaches in real world projects:

Onfortunately, patterns like IDisposable break down completely with true shared ownership. I one project, I had objects that represent temporary folders and files. Ownership was truly shared so the only mechanism there is to manage those is GC. Finalizing the file objects is dependent on finalization of the folders. I had to resort to nasty hacks like “resurrecting” folder objects during finalization when their contained file objects were not finalized yet.

Yes, I’m sure. I did extensive heap profiling and the memory consumption was due to dead objects. The system worked well under low load but broke down under high load. I also thought that generational GC could cope well with many short lived objects but apparently I was wrong.

The only way to make it work was avoiding allocations where ever possible. There are many hidden allocations in C#. For example, I had to use SortedList instead of Dictionary, because Dictionary uses a node object for every stored object. I could not even use the default comparison function for SortedList because its arguments are implicitly boxed. I could not use C#-events because EventArgs is a class and thus boxed. I had to “expand” parameter objects to pass them individually. Use struct instead of class wherever possible.

In the end I brought the runtime from several minutes (using all of my memory and still thrashing) down to about 1 second and almost not using any memory. Just by avoiding temporary allocations at all cost. But the result is not pretty.

This was a project, where the low level performance critical work was done in C++ and the high-level coordinative stuff in C#. Still, I had to dive deep into profiling even for the high-level part to make it scale well.


Inversion-of-control resource management
#30

@graydon’s idea of Rust was that GC is used in most places, with references only used in high-performance fragments. For that, older versions of Rust had a (reference-counting-based) garbage collector that was used everywhere, with plans to introduce a proper tracing-based garbage collector.

Eventually, we realised that borrowed references are sufficiently easy to use that we wanted to use them everywhere, and the special syntax for @ was removed. The plans to integrate a tracing-based GC remain (ask @pnkfelix), but are low-priority because of the popularity of references.


#31

I am thinking borrowed immutable references are shared ownership, and mutable borrows are exclusive ownership. I don’t understand the mention of Box.

Am I correct to understand that you want to use Rc / Arc where you need shared mutable references where the invariants of safe mutable coordination can’t be modeled by the low-level lifetimes checker? So in order words, your Rc / Arc is unsafe (i.e. not checked by the compiler) from the standpoint of mutability invariants.

Note I updated the chart in my prior post to reflect the safety of mutability issue.

Discussion of this I think should be tied into discussing optimizing temporary objects and the points I want to make about inversion-of-control and imperative versus functional structure.

I am not totally dismissing your point, as evident by my prior remark about memory/battery limitations on mobile and afaik non-tunability of the performance priorities of the current crop of mainstream GC. But I am wanting to register another perspective, which is that the cost of hosting (hardware) is probably nearly always irrelevant compared to the things that matter to humans. I spent 100X more on advertising than I did on hosting on my last commercial success.

Lately I have come to view the programmer as the customer, not the masochist who I sacrifice at the altar to the “user”. In other words, the living product is the open source, not just the executable. I hope we are headed to a world where many of the users are also programmers. The world is changing. We are leaving the Industrial Age and entering the Knowledge Age. Fixed capital investment is dying. No one can amass nearly constant marginal utility economies-of-scale of knowledge creation (links to my Rise of Knowledge essay).

The last file object implicitly finalizes the parent folder object that it points to, unless the folder object has other references to it. If you use GC then finalization time won’t be deterministic, but otherwise I don’t see the problem nor need to “resurrect”? For deterministic finalization if you need the resources to be freed asap, you’d need either some semantic sharing mechanism or use RC.

So these were not permanently stored, yet stored long enough to escape the generational GC?

Apparently some generational GCs are not tuned to cull the older generational garbage often, so perhaps you can overwhelm it then it doesn’t have enough working physical memory so is thrashing virtual memory?

These are very short-lived objects and one would think they would be cleaned from the younger garbage on each generation. Do you have any idea why this failed? Were you holding a reference to these temporary objects too long?

Edit: could it be that the generational GC was not able to be sure that you hadn’t referenced the temporary objects from the mutable objects in the older region? See the a key advantage of immutability for Haskell.


Rust as a High Level Language
Inversion-of-control resource management
#32

References do not have ownership, at all. Ownership implies that when the owner goes out of scope, the resource is freed, but this is very much not the case with references.


#33

Borrowing is the opposite of ownership (as the name implies). You always need an owner to be able to borrow, you cannot have only references.
For shared ownership (mutable or immutable) if the last owner goes dies, the resource is finalized. But it does not matter which one is last.

Box is the prototype of unique ownership. It’s the equivalent of the C++ std::unique_ptr.

No, Rc / Arc is only for immutable references AFAIK. (I don’t have much experience using them). If you need mutable shared ownership you have to use Cell / RefCell (I have even less experience using those).

Yeah, it’s not an ideal example because there are other means to determine the parent directory of a file. But that may not always be the case with other resources. Or finalization needs additional information, not just the resource itself. It’s not even clear that the finalizer still has access to the path of the file. Strings are probably not a problem, but in general you cannot access any child objects in a finalizer.
I just don’t like the concept of finalizers, they are too brittle.

Honestly, I didn’t investigate much why the GC wasn’t able to deal with it.

In that application, all objects were immutable (well, not really immutable but just never mutated) and passed between components. “Mutation” always produced new objects, which produces much garbage.


#34

There’s an interesting note in the documentation of std::rc about cycles:

Rust actually makes it somewhat difficult to produce this loop in the first place: in order to end up with two objects that point at each other, one of them needs to be mutable. This is problematic because Rc<T> enforces memory safety by only giving out shared references to the object it wraps, and these don’t allow direct mutation. We need to wrap the part of the object we wish to mutate in a RefCell, which provides interior mutability: a method to achieve mutability through a shared reference. RefCell enforces Rust’s borrowing rules at runtime. Read the Cell documentation for more details on interior mutability.


#35

To explain more, Rc and Arc provide shared ownership while Cell, RefCell and atomics provide shared mutability. Sometimes you just need shared mutability, sometimes just shared ownership, and when you need both, then you use something like Rc<Cell<T>>.


#36

I was thinking of Box as just another reference that can have shared or exclusive ownership. My concept was that ‘borrowed’ means all the references are sharing. I realize my conceptualization was incorrect, because the stack based borrowing always has to unwind to only the instance that created the Box reacquiring exclusive ownership, unless of course it had moved that ownership.

But I still don’t understand the distinction between a Box and a reference & in the context of ownership. Seems I can move ownership from a Box to a &? I was thinking of a Box as only the way to construct object on the heap. Is my function required to input the type of Box when it demands the ownership be moved to the function?

Rust checks two dimensions of resource lifetimes safety: allocation and mutability.

So we forsake Rust’s compile-time safety when the allocation and/or mutability sharing can’t be modelled by Rust’s stack based borrows.

Afaics, the stack is the key word that we needed to introduce to distil to the generative essence.

Edit: or more accurately stack based and block scope based within a function. And there there is also the issue of closures and Box inside objects that out live stack frames.


Rust as a High Level Language
#37

In a mutable language such as C#, how would it know that these temporary objects haven’t been referenced by some mutable objects in the older area of the generational GC? If it can’t know, then it can’t free these objects efficiently at the end of the generation, because it would require tracing all the possible paths to these temporary objects in the older area as well.

When I post about inversion-of-control and temporary objects, I think we will see that immutability is crucial. Otherwise the only choice we appear to have is to unwrap all the elegance of higher-level composition and force the programmer to do boilerplate.

This is why I am coming to the intuition that we are approaching the problems from the wrong direction with Rust’s lifetimes. But again, this is complex subject matter and so I am probably wrong or it may be different priorities for different use cases. That’s why I want to discuss it.


Inversion-of-control resource management
Rust as a High Level Language
#38

When a Box goes out of scope, the heap-allocated object it points to gets deallocates. You can create &-references to the boxed object, too, but those references can’t outlive the box, so they never dangle even though they can’t make it live longer. It is impossible, however, to free an object if all you have is a reference to it.

That’s what it means to be the owner. The owner of an object defined how long it exists; equivalently, an object’s owner is responsible for destroying it.


#39

So when a function declares the type of the input as Box does that mean the function takes ownership?

Can a Box give up its ownership with a move?


#40

A function like this takes ownership:

fn eat(_: Box<Cookies>) {
    // ...
}

And using it like this will give an error at compile time, because once I give ownership up, I can’t do it again:

struct Cookies;
let c = Box::new(Cookies);
eat(c);
eat(c);