Presumably when ‘v’ goes out of scope, it all gets cleaned up because the ‘Cell’ is owned by the vector. I guess what I meant to say is you cannot get a cycle of ‘owning’ references in Rust. You also cannot get a cycle of ‘borrows’, but you can get a cycle of non-owning references (using Cell or raw pointers). I think I can claim I over-simplified it, rather than getting it completely wrong
There’s still RC cycles to worry about…
I would have thought RC as it represents ‘shared ownership’ should not be allowed to have cycles? That would fit with the semantics of ownership (and we are just talking about sharing it after all). I guess I don’t agree with the design choice to allow cycles in shared ownership. (but me not liking it doesn’t change the fact that people have to deal with it, if that is how Rust is currently implemented).
There was sort of a proposal that would use the typesystem in a complicated way to prevent some kinds of cycles/leaks with Rc, but it was decided against.
Defining what a “memory leak” even is is difficult, and memory leaks are memory safe. Rust’s focus is very specific; we don’t claim to solve all problems.
Please kindly do not quote me out-of-context. I didn’t write that Rust will allow statically checked owned circular references. I wrote that sometimes we encounter circular dependencies required by the most straightforward implementation of an algorithm, and then I presumed we would have to use unsafe code or mangle our algorithm sufficiently to appease Rust.
The others covered the other potential points. Seems I agree with all that was written.
So in conclusion compared to GC, Rust’s lifetimes incur more hassles and force you to declare code unsafe to handle circular or multiple mutable references, but have the advantage:
In other words, as I documented upthread, GC can achieve the same average throughput performance as explicit memory mgmt but requires 3 - 5 times more memory and/or it can attain the same average (or maximum) pauses latency but with a loss in average throughput. Rust’s lifetime management can optimize both but at the cost of more hassles and complexity.
I have an additional thought which is that most software that is not for mission critical applications typically will have those sort of semantic “memory leaks” I mentioned upthread, thus asymptotic memory leak performance may dominate in both GC and Rust’s lifetimes for these sort of programs and thus Rust may not have a significant advantage over GC for these non-mission critical apps. Does that make sense? Note as mentioned at one of my upthread links, C++ would simply crash sooner than reach asymptotic memory leak performance because of accessing freed memory instead of maintaining a circular reference that is no longer accessible by the program (even though still accessible by the chain of references from the variables on the stack).
Blog Post: Lifetime Parameters in Rust
The eternal GC vs. manual-memory-management comparison depends on your usage pattern. High-performance code (in all languages) avoids most memory allocation overhead by intelligent use of object pools. Ownership/borrowing makes object pool usage quite safe and easy in Rust.
GC is generally much faster in “Lisp-style” code - if you have lots of tiny objects referencing each-other and frequently created and destroyed. Manual memory management is generally faster in “kernel-style” code - when you have a large heap of large objects that are rarely created or destroyed.
I understood all you wrote, except this part. Why faster? Do you mean less hassle to code?
Do you mean the generational GC can be more optimized to recycle and free these temporal objects?
When you have lots of object churn and only few objects leaving eden / young gen / whateveryounameit, GC can become arena allocation + a bit of copying, whereas manual management must free each object by itself.
I see. That is what I thought, but now I understand how to phrase it better. Efficiency is gained through batching because the GC has an orthogonal statistical or batch perspective, versus point-by-point allocation and deallocation of explicit memory mgmt.
Of course you can always manually use the ‘arena’ pattern, where you allocate all the memory you need before running the algorithm. Also because the entire stack requirement for a function is allocated in one go, looping results in less allocations than recursion. GC is never going to be more efficient than a well designed manual allocation using appropriate batching of allocation and deallocation, but it might easily be more efficient than bad memory management.
I also think that there are scenarios where specialized GCs will be beneficial. Apart from arena allocation, epoch-based GC (see crossbeam) can be a good solution.
IMHO Rust is in the unique position to try out new specialized memory management scheme, as the guarantees give us the needed leeway to integrate those schemes within the context of global compiler-supported memory management.
In my opinion, the other thread has added some more clarity on those points.
Afaics, we can’t model a high-level semantic fix with a low-level semantic checker. Anything you could have constructed would have ostensibly been heuristic thus fraught with corner cases. I am happy it wasn’t pursued.
Imperative boilerplate does not have as many degrees-of-freedom as functional composition, thus it is akin to claiming we can optimize globally instead of locally. Although immutability is O(log(n)) slower than the ideal imperative code, I will soon attempt to argue it is actually faster in practice because only locality of optimization is realistic.
My conceptual intuition or understanding derives from my theoretical interpretation that the universe is composed of partial orders, for if there was a total ordering it would require the speed-of-light to be infinite so that the single top-down observer could be omniscient in real-time, but this would collapse the past and the future into an infinitesimal pointless nothingness. Our existence is predicated on friction. Friction imparts the fundamental matter of the universe which is the continuum of the frequency domain, and this is why the order of the universe is fractal, and there is hidden order (the strange attractor in Chaos theory) in fractal cross-correlation. In other words, the less localized (functional composition modularized) our paradigm, the less entropy our paradigm can handle before it losses its order (in a soup of incomprehensible cascading spaghetti which is effectively indistinguishable from noise):
Inversion-of-control resource management
I disagree, for many programs all allocation can be done in a single block, and kept for the program lifetime, which is optimal (IE you cannot do better than this for performance), or kept for the duration of static scope (this is the Arena pattern). GC can never be this efficient as is has a mark/sweep overhead on top of this. Also most garbage collectors have to “stop the world” to do the mark/sweep which stops all threads in the program, so the more parallel the program the worse GC is.
Further to allow the GC to move memory between pools of different lifetimes every dereference to memory involves an extra indirection, and on modern highly chached speculative out-of-order super-scalar architectures this is really costly for performance.
In the real world no GC language gets close to ‘C’ performance.
Let me start with an abstract analogy. We can in theory extract more grain from the field if we do it by hand because our hands are more meticulous, but in reality we extract more grain with lossy mechanization because manual labor is not reproducible nor economically viable.
Yes you can make an example program that is faster than the same example in GC, but that is not my point. The point I will attempt to argue is that the low-level choice has sacrificed other things which are more economically viable and thus in reality of software development are faster (both in development time and in execution performance because the latter relies on the ability to have time to do the former well).
Of course there will still exist cases where one decides that a certain portion of the program is deserving of forsaking some aspects of high-level composability and reasoning, in exchange for more performance and/or low-level control. I am referring to how we should write the majority of code, and not about those special cases.
Edit: and I am going to make a new thread to discuss this, because I am not pushing for Rust to adopt this philosophy. I just want to discuss it, and what better place to discuss it than this excellent forum of intelligent and experienced skeptics. I should go make my case where there is the most contention, not in the fanboys forum. Rust is still a young language and the people coming here from C++ and C# represent a very different audience perhaps than those in the functional language forums. Rust has typeclasses. Rust has since its inception experimented with many different ideas.
How many times do you write the program vs running it? Even if it doubles development time, that is only the time of the people in the dev team. The runtime saving is for every run of every user, which is normally vastly more people. Therefore in total cost it is worth getting this right. For example a 10% efficiency improvement can save big companies millions annually in server costs.
Further if you use the collections libraries like C++ STL you don’t need to worry about detailed memory management, and GC will do nothing to help you if you put data into a collection and forget to delete it (it’s still reachable).
My general point is don’t roll your own data-structures, use the standard collections (vectors, sets, maps, etc). With generics most complex data structures can be encoded without writing your own spaghetti pointer code and having to do manual allocation. RAII has really changed C++, and as far as I can see is the normal way to do things in Rust.
I appreciate that point! And afaics with my current helicopter view (which may end up incorrect) that will add another reason that pure functions and immutability are crucial, because if we can guarantee the shared references to the temporary objects are encapsulated, then don’t need the double indirection, nor GC, nor RC, nor lifetime annotation. We simply destruct the object as it goes out of scope of the encapsulation barrier. But I might be wrong.
Why is indirection necessarily egregiously costly? Afaik, what is costly is random access and non-locality of access.
The issue is memory fragmentation. As you allocate objects you advace the end of free memory pointer. To make allocation fast you always allocate at the end of used memory. As you deallocate you leave holes. In a divergent program (one that may loop forever) you will eventually run out of memory. To prevent this the GC relocates the objects compacting them to the bottom of the memory space, releasing the freed space for re-use. This requires double indirection because the actual address of an object can change the program cannot keep its real address, but instead keeps the address of the address, so the GC can rewrite it. As the GC can run at any time, all dereferences have to be double dereferences.
The performance hit of an additional indirection results from non-locality (the pointer indirection table cannot be in the GC memory block as it cannot move), cache misses (if the GC moved the object then it’s new location and it’s old location have to be flushed from the cache), pipeline stalls (as we don’t know if GC will run between now and when we do the lookup we cannot speculatively execute ahead as the pointer might be pointing somewhere else when we get there, so we cannot have references to the old address in the instruction re-order buffer).
How many times is (or more saliently what is the derivative combinatorial network effects explosion impact of) open source code read, edited, forked, and reused as snippets inserted into other projects.
Fine grained (i.e. localized) functional composition modularity is preferred over refactoring.
But afaics those are incompatible with high-level functional composition which is where I am headed with this…
Agreed, but I am going to attempt to argue that functional composition encapsulation may help immensely, at least w.r.t. to temporary objects. And none of the safe paradigms can help you with such semantic errors, so you’ve constructed a strawman to blame GC. Can you wait for my argument in a new thread?
Afaics, that isn’t compatible with higher-order composition. We will get into that in the new thread I will create shortly.