4 ms·

> It's a limitation because there are some extremely important and common relationships (e.g. putting an object in multiple containers simultaneously) that cann

by Twisol 7y ago

> It's a limitation because there are some extremely important and common relationships (e.g. putting an object in multiple containers simultaneously) that cannot be expressed in Rust's type system without using unsafe, RC boxes, etc, which create tremendous friction. That is not a difficult relationship to capture, IMHO. The problem is that it's too easy to conflate "address" and "name" in most languages. An address is the physical location of a thing. A name is a location-independent way to look up a thing. Only one thing can live at an address, but you can use a name to look up multiple addresses depending on what question you want answered. (There is a parallel here with domain names and IP addresses.) Rust associates ownership with every address. This causes serious problems when you've been using addresses as names. The solution is to use different names. For instance, let's represent a graph as a vector of nodes. Every node has an index within that vector. Given this index, we can look up any node -- but critically, having the index does not confer ownership of the node. It's a completely orthogonal concern. So a node can quite happily possess a vector of the indices of its neighbors. You might complain that this is a poor naming scheme for a graph structure, since it complicates deletion of nodes from the vector. Great! We have these exact same problems when using pointers (observe that the index plus the vector base address is the node address), but now that naming is a first-class concept, we can consider it on its own terms. There are alternative index spaces we can apply. I've used this kind of design in a compiler hobby project. The intermediate representation is a set of tables representing different information about the program. With each pass, I can easily add new tables or transform existing ones, so long as I keep the names consistent. I can easily represent relationships between entities by using their indices. And I can easily attach more information to certain entities in compiler passes by adding a new table keyed on the same index.

wahern 7y ago
I've always found this a very odd rationalization. These games are unnecessary to get the same sort of type safety and double-free protection.[1] They're sufficient to subvert the Rust compiler, but that's it. The "benefit" only exists in the context of Rust because it's the only way to accomplish this. And of course the extra indirection is costly, especially for a systems language. And you're also doing much more memory management. Hacks like these are why people say handling OOM is too difficult, because such hacks turn a simple logical operation into a series of multiple memory allocations, each of which could individually fail, which explodes the number of possible failure points, creating significantly more tension than necessary between memory management and functional clarity. [1] The analog in the land of pointers is simply to NULL node member pointers and fail if a member is non-NULL at destruction or insertion, which is effectively the same as with the index tables hack. And for type safety you can of course use container-specific member types, which is exactly how the canonical linked-list and tree implementations work in BSD. (See https://man.openbsd.org/queue#LIST_EXAMPLE https://man.openbsd.org/queue#LIST_EXAMPLE and https://man.openbsd.org/tree#EXAMPLES. https://man.openbsd.org/tree#EXAMPLES.) And like with many things in Rust, but-for the single ownership limitation Rust would otherwise make doing all of this much easier because it makes it easier to maintain the NULL invariants.
- Twisol 7y ago
  I think that we are subtly talking past each other, because what you're saying doesn't line up against what I thought I was saying. I'm not looking for additional type safety or security protections from this model. See my sibling comment to your earlier comment for a little more context [1]. As someone who works with Rust often, your assertions don't match my experience. I want to engage honestly and understand where Rust itself falters, versus where we need to invest in educating newcomers about what kinds of models are better represented in Rust than others. I have found the model I'm describing to be valuable in many ways -- more than a "hack" to get around Rust. > And of course the extra indirection is costly, especially for a systems language. To my knowledge, base-offset addressing is natively present on at least x86. With a vector-based index space like I was describing, a[b] == * (a + b) is no more costly than * b. If you would need a more complex index space, you were probably doing more than bare pointers already. > And you're also doing much more memory management. > because such hacks turn a simple logical operation into a series of multiple memory allocations No, no more than you would have needed with pointer-based naming. The top-level arena (a vector in the graph example) owns everything and can be deallocated all at once when you're done with it. Arenas were already a well-known pattern before Rust, and they can reduce the amount of manual memory management over tracking a bunch of small, separate heap allocations. Relatedly, Catherine West gave an excellent talk at RustConf 2018 on how the Entity-Component-System architecture maps nicely into Rust [2]. The address/name distinction comes from ECS, but it becomes even more useful in Rust. > The analog in the land of pointers is simply to NULL node member pointers and fail if a member is non-NULL at destruction or insertion I don't see how this is hindered by Rust. We use an Option type -- with Some(T) and None variants -- to model something that might not be present, so the logic can be exactly the same. Rust can even optimize away the "extra" space you would need for the Some/None variant flag in common situations [3]. [1] https://news.ycombinator.com/item?id=20822003 https://news.ycombinator.com/item?id=20822003 [2] https://kyren.github.io/2018/09/14/rustconf-talk.html https://kyren.github.io/2018/09/14/rustconf-talk.html [3] https://github.com/rust-lang/rust/pull/45225 https://github.com/rust-lang/rust/pull/45225
  - wahern 7y ago
    My original point is that real-world programs are complex data structures where any particular object may need to be referenced from multiple containers. At which point you're right back to square one--which container is the true owner responsible for maintaining all invariants and releasing the object when it's dead? Rust memory management does not and cannot automatically "free" resources with such references; you're still doing this manually. Indeed, this is irreducible complexity; it's why programming is hard, even in GC'd languages. The indexing scheme is a hack to subvert Rust's typing system. It's even admitted in the talk you mentioned, > One more criticism of this style is that you might say that using indexes instead of pointers is “safe” in the strict sense, but possibly only technically, you’re trading UB and potential crashes with pointers for “random but unspecified” behavior if you access the wrong or outdated index, and potentially panics. You’d be right, btw! The generational indexing discussed therein is just a runtime invariant assertion, just as-if you asserted on internal pointer members being NULL at destruction (which implies but doesn't guarantee that the node has been properly unlinked). This is all just more memory games.[1] In some respects they may be marginally safer, but they're also marginally more complicated. And that's friction. And even if on the whole it makes programs safer, the cost exists. ATS is an even safer language than Rust. If we're gonna pretend that the friction doesn't matter why wouldn't we just pretend we should all use ATS? I'm not arguing that C or C++ is better than Rust. It just bugs me the way people rationalize some of the difficulty with arguments about why it makes things easier. Yeah, single-ownership does make things easier. Good C programs and good programmers generally learn to strive for single ownership semantics. Without an argument, Rust's enforcement of this invariant makes programs safer. But arguing that the enforcement of the invariant makes it easier to program? Come on! I know single-ownership is safer and simpler, which means when I choose to have a more complex ownership pattern it's for a darned good reason. Having to jump through hoops to accomplish it, even if it's "good" for me, is still jumping through hoops. [1] And game makers love memory hacks; it's why their apps crash all the time, and why the thought of handling allocation failure would never cross their minds. To understand why people stopped using arenas and ad hoc invariant assertions for systems programming, see Heartbleed.

by Twisol 7y ago

wahern 7y ago

I've always found this a very odd rationalization. These games are unnecessary to get the same sort of type safety and double-free protection.[1] They're sufficient to subvert the Rust compiler, but that's it. The "benefit" only exists in the context of Rust because it's the only way to accomplish this. And of course the extra indirection is costly, especially for a systems language. And you're also doing much more memory management. Hacks like these are why people say handling OOM is too difficult, because such hacks turn a simple logical operation into a series of multiple memory allocations, each of which could individually fail, which explodes the number of possible failure points, creating significantly more tension than necessary between memory management and functional clarity. [1] The analog in the land of pointers is simply to NULL node member pointers and fail if a member is non-NULL at destruction or insertion, which is effectively the same as with the index tables hack. And for type safety you can of course use container-specific member types, which is exactly how the canonical linked-list and tree implementations work in BSD. (See https://man.openbsd.org/queue#LIST_EXAMPLE https://man.openbsd.org/queue#LIST_EXAMPLE and https://man.openbsd.org/tree#EXAMPLES. https://man.openbsd.org/tree#EXAMPLES.) And like with many things in Rust, but-for the single ownership limitation Rust would otherwise make doing all of this much easier because it makes it easier to maintain the NULL invariants.

Twisol 7y ago
I think that we are subtly talking past each other, because what you're saying doesn't line up against what I thought I was saying. I'm not looking for additional type safety or security protections from this model. See my sibling comment to your earlier comment for a little more context [1]. As someone who works with Rust often, your assertions don't match my experience. I want to engage honestly and understand where Rust itself falters, versus where we need to invest in educating newcomers about what kinds of models are better represented in Rust than others. I have found the model I'm describing to be valuable in many ways -- more than a "hack" to get around Rust. > And of course the extra indirection is costly, especially for a systems language. To my knowledge, base-offset addressing is natively present on at least x86. With a vector-based index space like I was describing, a[b] == * (a + b) is no more costly than * b. If you would need a more complex index space, you were probably doing more than bare pointers already. > And you're also doing much more memory management. > because such hacks turn a simple logical operation into a series of multiple memory allocations No, no more than you would have needed with pointer-based naming. The top-level arena (a vector in the graph example) owns everything and can be deallocated all at once when you're done with it. Arenas were already a well-known pattern before Rust, and they can reduce the amount of manual memory management over tracking a bunch of small, separate heap allocations. Relatedly, Catherine West gave an excellent talk at RustConf 2018 on how the Entity-Component-System architecture maps nicely into Rust [2]. The address/name distinction comes from ECS, but it becomes even more useful in Rust. > The analog in the land of pointers is simply to NULL node member pointers and fail if a member is non-NULL at destruction or insertion I don't see how this is hindered by Rust. We use an Option type -- with Some(T) and None variants -- to model something that might not be present, so the logic can be exactly the same. Rust can even optimize away the "extra" space you would need for the Some/None variant flag in common situations [3]. [1] https://news.ycombinator.com/item?id=20822003 https://news.ycombinator.com/item?id=20822003 [2] https://kyren.github.io/2018/09/14/rustconf-talk.html https://kyren.github.io/2018/09/14/rustconf-talk.html [3] https://github.com/rust-lang/rust/pull/45225 https://github.com/rust-lang/rust/pull/45225
- wahern 7y ago
  My original point is that real-world programs are complex data structures where any particular object may need to be referenced from multiple containers. At which point you're right back to square one--which container is the true owner responsible for maintaining all invariants and releasing the object when it's dead? Rust memory management does not and cannot automatically "free" resources with such references; you're still doing this manually. Indeed, this is irreducible complexity; it's why programming is hard, even in GC'd languages. The indexing scheme is a hack to subvert Rust's typing system. It's even admitted in the talk you mentioned, > One more criticism of this style is that you might say that using indexes instead of pointers is “safe” in the strict sense, but possibly only technically, you’re trading UB and potential crashes with pointers for “random but unspecified” behavior if you access the wrong or outdated index, and potentially panics. You’d be right, btw! The generational indexing discussed therein is just a runtime invariant assertion, just as-if you asserted on internal pointer members being NULL at destruction (which implies but doesn't guarantee that the node has been properly unlinked). This is all just more memory games.[1] In some respects they may be marginally safer, but they're also marginally more complicated. And that's friction. And even if on the whole it makes programs safer, the cost exists. ATS is an even safer language than Rust. If we're gonna pretend that the friction doesn't matter why wouldn't we just pretend we should all use ATS? I'm not arguing that C or C++ is better than Rust. It just bugs me the way people rationalize some of the difficulty with arguments about why it makes things easier. Yeah, single-ownership does make things easier. Good C programs and good programmers generally learn to strive for single ownership semantics. Without an argument, Rust's enforcement of this invariant makes programs safer. But arguing that the enforcement of the invariant makes it easier to program? Come on! I know single-ownership is safer and simpler, which means when I choose to have a more complex ownership pattern it's for a darned good reason. Having to jump through hoops to accomplish it, even if it's "good" for me, is still jumping through hoops. [1] And game makers love memory hacks; it's why their apps crash all the time, and why the thought of handling allocation failure would never cross their minds. To understand why people stopped using arenas and ad hoc invariant assertions for systems programming, see Heartbleed.