> Rust cannot make any latency guarantees either. Reference counting and its lifetimes also have pathological cases, ie. worst-case, an object can reference the entire heap which will take time proportional to the number of dead objects to free.
Rust doesn't use reference counting by default. Refcounting is very rare in Rust, much more rare than it is in C++. Most large C++ codebases I've worked with have thrown in the towel and started refcounting all the things. In Servo, for example most of the refcounting is across threads (where you basically have no other option), and a few interesting cases in the DOM, each with very good reasons for using refcounting.
Lifetimes are a concept at compile time and don't exist at runtime.
Edit: Oh, I see what you're talking about. A sufficiently large owned tree/graph in Rust will introduce latency. It's predictable latency though. I can make the same argument about for loops.
Unpredictably sized large trees in Rust are again pretty rare in general.
Trees don't have to be refcounted in Rust. Single-ownership trees are possible.
As long as they don't have backpointers. Backpointers are a problem under single ownership.
Right, I never said that trees have to be refcounted. A sufficiently large ownership tree will get deallocated all at once, which is the kind of latency the GP is talking about.
Linked data structures in Rust get complicated, though. See the "Too many lists" book.[1] Doubly linked lists, or trees with backlinks, are especially difficult. Either you have to use refcounts, or the forward pointer and backward pointer need to be updated as an unsafe unit operation. There might be an elegant way to do this with swapping, but I'm not sure yet.
Right, so you implement them with unsafe. While you can implement doubly linked lists safely with refcounting, you're perfectly free to implement them with unsafe code. This is what unsafe code is for, designing low level abstractions with clean API boundaries.
If you need unsafe code for basic operations within the language, something is wrong with the language. This isn't about talking to hardware, or an external library. It's pure Rust code.
(Some pointer manipulations can be built from swap as a basic operation. That may work for doubly-linked lists. The other big
problem is partially valid arrays, such as vectors with extra space
reserved. There's no way to talk about that concept within the language. There could be, but this isn't the place to discuss it.)
> need unsafe code for basic operations within the language
Building custom back-referencing data structures is not a "basic operation" anywhere outside programming classes. Adding significant complexity to rust Rust to make a 2% case marginally safer would be make the language worse. As long as the vast majority of code is not unsafe, then it achieves its goal.
I have been writing Rust code for almost three years now.
I have helped design a low level data structure exactly twice. In both cases, this was a highly custom concurrent data structure, which would have been even harder to get right in C++ or some other language.
If you need a regular run-of-the-mill datastructure it will exist in the stdlib or crates ecosystem. This is not a "basic task". Just because schools teach it early does not make it a "basic task". It's a task that needs to be done at some point, but doing it once and making it part of the stdlib or a crate is all that is necessary. It has become a "basic task" in C++ because it's easy enough to do that you don't need to reach for the stdlib, but that doesn't mean that it's necessary to have a bespoke implementation of a DLL that often in C++; usually the stdlib one will do.
The same "too many lists" book you linked to explains why DLLs are niche datastructures on the first page (singly linked lists can be implemented safely in Rust, though they can be somewhat niche too).
Rust doesn't use reference counting by default. Refcounting is very rare in Rust, much more rare than it is in C++. Most large C++ codebases I've worked with have thrown in the towel and started refcounting all the things. In Servo, for example most of the refcounting is across threads (where you basically have no other option), and a few interesting cases in the DOM, each with very good reasons for using refcounting.
Lifetimes are a concept at compile time and don't exist at runtime.
Edit: Oh, I see what you're talking about. A sufficiently large owned tree/graph in Rust will introduce latency. It's predictable latency though. I can make the same argument about for loops.
Unpredictably sized large trees in Rust are again pretty rare in general.