7 ms·
> 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
by naasking 10y ago
> 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.
There's no free lunch!
- Rusky 10y agoLifetimes are compile-time only and do not do any reference counting. So Rust has the same latency guarantees as C, for example.
- naasking 10y ago> 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.
- steveklabnik 10y agoWhat 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.)
- Rusky 10y agoI 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.
- steveklabnik 10y agoI guess that would make sense, but I'm not sure it's lifetime-specific though. C++ doesn't have lifetimes but would still have this problem.
- naasking 10y agoYes, 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++.
- steveklabnik 10y agoQuite fair! Thanks for elaborating.
- webkike 10y agoRegardless there is no overhead for lifetimes. It is a data flow analysis problem used solely to verify correctness of the code.
- wtetzner 10y agoI think they're referring the the calls to "free" that are automatically injected.
- worik 10y ago"C also doesn't provide latency guarantees, as the same pathological programs can exist in C as well." But you have to code them. They are predictable, or you let them in by allowing data structures to grow indefinitely With C you can make latency guarantees. You can write code that does not have such guarantees but it is your choice With GC you are not in control so there are fewer choices. You will not be able to make guarantees.
- naasking 10y ago> 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.
- worik 10y agoThat is a misunderstanding of latency. "Very fast" is still latency.
- naasking 10y ago"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.
- deleted 10y ago[deleted]
- qwertyuiop924 10y agoRust itself can't, but you as the programmer can. It's not quite C, but you can do a lot of reasoning about what the compiler will do with your code, and avoid pathological cases.
- naasking 10y agoAbsolutely, you have to be aware of the ownership graph depth in both C and Rust if you want to bound latency. You don't have to do this with tracing GC though, you just need a runtime that implements latency bounds.
- qwertyuiop924 10y agoWait, 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.
- naasking 10y agoThe 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.
- pcwalton 10y agoThis 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.
- Manishearth 10y ago> 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.
- Animats 10y agoTrees 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.
- Manishearth 10y agoRight, 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.
- Animats 10y agoLinked 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. [1] http://cglab.ca/~abeinges/blah/too-many-lists/book/ http://cglab.ca/~abeinges/blah/too-many-lists/book/
- dikaiosune 10y agoIt's worth mentioning that there are several strategies for avoiding cascading deallocations like arenas or arena-backed graph abstractions. For example: https://crates.io/crates/typed-arena https://crates.io/crates/typed-arena https://crates.io/crates/petgraph https://crates.io/crates/petgraph Rust's generics make this fairly pleasant to work with, and lifetimes/borrowck ensure safety when managing your own object allocations.
- naasking 10y agoIndeed, 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.
- dikaiosune 10y ago> 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.
- akiselev 10y agoYou 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.
- naasking 10y ago> 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.
- Manishearth 10y ago> 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.
- 10y ago
- pcwalton 10y agoI 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.
- naasking 10y ago> 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.
- solidsnack9000 10y agoThe 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.)