> IMO it would be great to get folks who write the enormous base of existing realtime apps driving critical devices everywhere to sit up and take notice of Rust.
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.
Copying collection in this case takes literally zero time, but it's pathological case is when all referenced data survives the current GC cycle, ie. proportional to live objects.
> 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).
You will always have these pathological cases when you choose to use higher level memory management like simple reference counting or garbage collection no matter what language you use, whether it's Rust or assembler. The point of Rust is that you have complete control over what you use and pay for. If your concern is the overhead of lifetimes then you need to evaluate if you can afford heap allocation in the first place. Otherwise you can make de/allocation explicit in Rust just like in C, without losing the benefits of ownership checking.
Embedded hardware and software can only provide realtime guarantees because they are simpler, without complex pipelines, caches, branch predictors, or thread schedulers. If you want low latency embedded software you have to document the pathological cases, test whether they happen in real world use, and profile the code with each microarchitecture you're targetting anyway, let alone every product family. What language you use doesnt change that.
> You will always have these pathological cases when you choose to use higher level memory management like simple reference counting or garbage collection no matter what language you use
Not true, soft and hard realtime garbage collectors exist. Your runtime simply needs to bound the amount of reclamation work done at any given time.
For instance, the cascading free behaviour Rust is currently susceptible to can be broken up into a bounded series of free operations interleaved with ordinary program execution. Rust would then be realtime without truly changing its observable behaviour, except its timing in some programs.
> For instance, the cascading free behaviour Rust is currently susceptible to can be broken up into a bounded series of free operations interleaved with ordinary program execution.
You can probably make this work by plugging in a different allocator, if jemalloc doesn't do this already. The ability to batch up frees and mallocs isn't tied to GCs.
This won't reduce the perf impact of running a large tree of `Drop` impls, but it will reduce the free calls.
> You can probably make this work by plugging in a different allocator, if jemalloc doesn't do this already. The ability to batch up frees and mallocs isn't tied to GCs.
That gets tricky, because Rust people no doubt expect deterministic destruction on scope exit. But yes, my ultimate point is that low latency is a property of a runtime, not a language. C/C++ or Rust aren't going to automatically give you bounded latency, and adding tracing GC doesn't automatically take it away.
But this expectation is transitive. If you have an array of file handles, if you defer deallocating some of them but destruct them all upfront, you still have the latency issue we've been discussing. And if you defer destructing too, then you still have non-deterministic destruction and deallocation. I'm not sure there's a way around this tradeoff.
>> Not true, soft and hard realtime garbage collectors exist. Your runtime simply needs to bound the amount of reclamation work done at any given time.
That doesn't change anything! You're just choosing a garbage collector with a default deterministic pathological case, which is a guarantee you can make about almost any GC by carefully tailoring your memory usage to your scenario and choice of algorithm. That's all realtiem embedded software development is all about: writing code that has predictable timing given your expected inputs and environment. If all you need to do is flip a bit once every 10 minutes with a precision of 1 second while reading 1 bps from a sensor even a full blown Linux distribution on a modern Intel i7 running a Python or Ruby daemon can be considered "realtime". The language doesn't matter as long as you can predict how long everything is going to take in the worst case and your micro[controller/processor] is fast enough to react.
>> For instance, the cascading free behaviour Rust is currently susceptible to can be broken up into a bounded series of free operations interleaved with ordinary program execution. Rust would then be realtime without truly changing its observable behaviour, except its timing in some programs.
You know that's what the Drop trait is for, right? All you have to do is add whatever memory management code you'd have (in your C program) into the trait implementation and your memory deallocation will behave exactly as it would in any other low level language. These low level facilities have been part of the Rust design from the start, they just don't require you to manually call free() by default. That doesn't mean anything in Rust is stopping you from doing so and if you want to, you can opt out of that behavior entirely by providing a blank Drop implementation. After that, literally anything you can do in C you can also do in a Rust unsafe block.
> That doesn't change anything! You're just choosing a garbage collector with a default deterministic pathological case, which is a guarantee you can make about almost any GC by carefully tailoring your memory usage to your scenario and choice of algorithm.
The fact that you don't have to tailor anything is precisely the point. Latency is a property of a runtime, not a language. This has been my point all along. C/C++ or Rust don't guarantee low-latency realtime properties, and introducing tracing GC doesn't guarantee high-latency non-realtime properties.
> You know that's what the Drop trait is for, right? All you have to do is add whatever memory management code you'd have (in your C program) into the trait implementation and your memory deallocation will behave exactly as it would in any other low level language.
Great, but it doesn't guarantee any properties of code you haven't written, so it still can't achieve the global properties I've been talking about.
> C/C++ or Rust don't guarantee low-latency realtime properties, and introducing tracing GC doesn't guarantee high-latency non-realtime properties.
We completely agree.
> Great, but it doesn't guarantee any properties of code you haven't written, so it still can't achieve the global properties I've been talking about.
How is this any different from C/C++? They do not give you any guarantees that Rust takes away in this regard. Any library that uses Box::new or vec! is exactly the same as a C library that calls malloc/free internally and you can implement the same heap allocation free algorithms in Rust as you can in C/C++.
I don't understand what global properties you expect a low level systems language to guarantee. They definitely can't guarantee that code you haven't written doesn't heap allocate, you have to check that they don't call malloc/free yourself.
> Your runtime simply needs to bound the amount of reclamation work done at any given time.
Wouldn't this transform the problem into a "no more predictable maximum memory usage" problem? As you can't really know if and when your GC will keep up it with the amount of work to do.
Possibly, but maximum memory usage is rarely predictable anyway. I expect it might be even less predictable than maximum latency.
However, it may still be possible to conservatively bound your maximum memory usage too, as long as your reclamation-work phase keeps up with your program's allocation rate, then you achieve a steady-state.
Suppose some amount of reclamation is done on malloc(), a tunable parameter could measure the ratio of allocation speed of the running program and amount of unreclaimed garbage. This ratio would control how much reclamation work to do before returning from malloc() so you can fall into steady-state.
> Possibly, but maximum memory usage is rarely predictable anyway. I expect it might be even less predictable than maximum latency.
Well, if you don't need a bound on memory usage you can just never deallocate.
> Suppose some amount of reclamation is done on malloc(), a tunable parameter could measure the ratio of allocation speed of the running program and amount of unreclaimed garbage. This ratio would control how much reclamation work to do before returning from malloc() so you can fall into steady-state.
Sure, but that doesn't guarantee anything about what your maximum spikes are going to be. You can have a firm bound on memory consumption or a firm bound on latency, but you can't get both without doing some serious application-specific work.
I keep seeing this latency claim about GC, but it would be trivial to solve with free if it were actually a problem: just add freed objects to a list and incrementally free over time to achieve whatever latency guarantees you wish.
The reason why no malloc/free implementations that I'm aware of actually do this is that the latency of freeing isn't a problem in practice.
> The reason why no malloc/free implementations that I'm aware of actually do this is that the latency of freeing isn't a problem in practice.
Partly, and the other part is that it degrades allocation performance for the majority of non-problematic programs, which is what most people actually focus on.
But if we're being fair, latency of tracing GC isn't a problem for most programs either. So latency is largely a red herring, except when it's not, and you had better know when it's not, regardless of whether you're using C/C++/Rust or a runtime with tracing GC.
It's worth mentioning that there are several strategies for avoiding cascading deallocations like arenas or arena-backed graph abstractions. For example:
Indeed, if you can live with the wasted memory use of objects outliving their conceptual lifetime, regions/arenas are a good solution.
Note however that you'd probably still have to run destructors when destroying an arena (to free file handles for instance), so you can still see high latency. With an arena you can perhaps schedule this better though.
> if you can live with the wasted memory use of objects outliving their conceptual lifetime, regions/arenas are a good solution.
If you can live with the wasted memory use of objects outliving their conceptual lifetime, garbage collectors can be a good solution too.
Not that that's a bad thing for many use cases, but your above comment implies a comparison between Rust and GC. I think the quoted critique falls down a bit when Rust lets you opt-in to generational-esque GC-ish behavior with a very similar downside to what you'd get from a GC.
> Lifetimes are compile-time only and do not do any reference counting.
I never said they did, I said lifetimes and reference counting both have this pathological case.
C also doesn't provide latency guarantees, as the same pathological programs can exist in C as well. It's a total myth that you need C in realtime domains due to "latency".
Maximum pause times are a property of a particular runtime, not a language.
> With GC you are not in control so there are fewer choices. You will not be able to make guarantees.
Not true. Hard and soft realtime GCs with sub-microsecond latencies exist. Latency is a property of a runtime, not of manual vs. automatic storage reclamation.
"No latency" is a fiction. The only question of any relevance is how much latency is tolerable for a given domain. And describing latency in worst-case timings is standard, so I understand latency just fine thanks.
What is the pathological case with lifetimes? You're saying it takes "time proportional to the number of dead objects to free", but as the parent said, lifetimes are a compile-time construct, so they have no runtime properties.
(I'm not saying that for sure there are none, I'm saying that it seems like you're talking about refcounting only, the lifetime bit is unclear to me.)
I suspect they're referring to graphs of Drop implementors, based on the sibling thread. If you for some reason have a linked-sea-of-nodes data structure that has to traverse itself on drop, that can behave similarly to dropping an Rc graph, though it still doesn't use lifetimes.
Yes, C/C++ would also have this problem. The point I was trying to make is that incrementality/latency is a property of a runtime. If your program has deep ownership graphs, any kind of naive reclamation procedure is going to have high latency, even if it's written in C/C++.
Wait, why would you have to do that? Most ownership is determininstically resolved at compile time, so you can know exactly when a resource will be freed. What you do have to know is about the rare refcounted variable, and what edge cases require ownership checking at runtime.
The latency problem isn't caused by determining what to free, the latency problem is caused by actually freeing. Imagine an array with 2^31 pointers, and now fill it with with 2^31 distinct pointers to the remainder of the 2^32 bit address space. When that array goes out of scope, you can now enjoy 2^31 individual free operations, because reclamation for Rust lifetimes and reference counting are both proportional to the number of dead objects (copying collection takes zero time in this case).
If bounded latency is a goal, you have to bound the depth of of your ownership graph if you're working on a platform that doesn't impose global latency properties. C/C++ and Rust do not do this.
This is only true for pure two-space copying collectors, which are rarely used in practice because of the absurd memory overhead. Once you introduce mark/sweep for some portion of the heap (like production GCs do), you reintroduce overhead proportional to the number of dead objects during the sweep phase.
But C has this problem as well. If you've malloc(3)ed an array of 2^31 pointers, each pointing to an object, enjoy your 2^31 free(3)s, or prepare to start leaking RAM.
Yes, C/C++ and Rust have the same problems, as I said elsewhere. My ultimate point is that low latency is a property of a runtime, not a language. Using C/C++ or Rust aren't going to automatically give you bounded latency, and adding tracing GC doesn't automatically take it away.
The language and runtime typically cooperate to provide the operational semantics that developers are looking for. The case of Objective-C is especially interesting in this regard: developers evolved a number of conventions around reference counting, because reference counting allowed for controllable, minimal latency and contributed to a snappy UI. The language gradually absorbed these conventions into the compiler, such that certain patterns of use are part of the language specification (certain method names, basically) and the ARC code is generated for developers.
I believe their point is that an object can own potentially many objects, and when it is dropped it could cause a cascade of dropping. Which may not be expected by someone.
Well, the good news for you then is that there is progress underway to implement Gc-as-a-library in Rust, to give you this option if you need it as well.
The latency of your Rust or C program is "static" in that you can infer it from the program text. This is not actually true of most garbage collected languages. (Erlang, with per thread heaps, is a notable exception.)
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.
Copying collection in this case takes literally zero time, but it's pathological case is when all referenced data survives the current GC cycle, ie. proportional to live objects.
There's no free lunch!