6 ms·
It has worse ergonomics, though. Most obviously, every time you want to access data through an index ‘reference’, you need to name two things: the array and th
by comex 8y ago
It has worse ergonomics, though. Most obviously, every time you want to access data through an index ‘reference’, you need to name two things: the array and the index. With a pointer you only have to name one thing. Thus, you might have to write `self.widgets[widget].foo` instead of `widget.foo`: not the end of the world, but annoying if you have a lot of references floating around.
Further, even if Rust guarantees memory safety, the approach is still less safe in the broader sense of guaranteeing program correctness. For one thing, if you just use raw integers for your indices, you basically have the equivalent of a C void pointer, a pointer to some unknown type. The compiler doesn’t know what the index is for and can’t catch you if you accidentally index into the wrong array. You can partially solve this by making a newtype wrapper for indices into each type of array, but even that can’t differentiate between multiple arrays of the same type.
Also, if you have a system for ‘freeing’ array indices and reusing those array slots for new data, you run the risk of keeping an index around too long and causing a semantic use-after-free: not as bad as a traditional memory use-after-free, usually, but certainly a source of incorrect and unpredictable behavior. And whereas tools like ASan let you ‘flip a switch’ to catch traditional use-after-frees if they happen in development builds, with arrays you have to add the extra checking manually. (On the other hand, if you do design extra checks, they might be cheap enough to run in production, where ASan is probably not. And yes, I know, when it comes to security, “if they happen in development builds” is quite meager comfort.)
But I’m not saying all this just to be negative. Personally, it’s my hope that someday in the future, Niko and co. will find ways to make the borrow checker more expressive when it comes to parent-child relationships, and in other situations where it currently struggles. If so, it won’t just help with pointers, but with array-based designs as well: it’ll become a more viable approach to have the borrow checker check array indices, by adding lifetimes to those array index newtypes. That would remove all of the aforementioned safety issues, while keeping the performance benefit of arrays – indeed, increasing it, since with the right design you would be able to safely disable the bounds check when indexing.
- pcwalton 8y ago> Also, if you have a system for ‘freeing’ array indices and reusing those array slots for new data, you run the risk of keeping an index around too long and causing a semantic use-after-free One of the many great things described by Catherine's keynote about ECS's in Rust: generational indices. Generational indices are a dynamic fix for this problem. > Personally, it’s my hope that someday in the future, Niko and co. will find ways to make the borrow checker more expressive when it comes to parent-child relationships, and in other situations where it currently struggles. I agree it'd be nice, and I've given it a lot of thought, as has Niko. In the limit, though, I think you're always going to have the situation in which there just aren't any static guarantees and the graph structure is truly unrestricted. In those cases, I'm not sure you can really do much better than dynamic checks of some kind, and it's hard to get much more efficient than a single bounds check.
- comex 8y ago> One of the many great things described by Catherine's keynote about ECS's in Rust: generational indices. Generational indices are a dynamic fix for this problem. Hmm… I'd heard of stuffing a generation ID into unused bits (which can help but is limited), but I see this proposes having the index type be a full (index: usize, generation: u64). Well, that works, but now instead of indices potentially being half the size of pointers (if you don't need more than 2^32 objects), they're double the size. Also, each object must store a generation, and you have to check that each time you use the index. (So it's not just a single bounds check, though I suppose you could turn the generation check off in release builds or something.) If you're willing to accept that overhead, it seems to me that you may as well just store a pointer instead of an index; design the arena to ensure that the pointers remain valid as long as the arena itself lives, and use lifetimes to track that (much easier than managing lifetimes of each object). That way you don't need to keep track of the array and the index separately, and you also save on the bounds check. Well… I guess that with an array you can have unique mutable access, whereas with pointers you'd have to rely on interior mutability. But it sounds like a pain to ensure uniqueness when threading around &mut references to the arrays (especially if there's one big object with all the arrays); you could never keep references across calls even when that would be completely safe. I would rather rely on interior mutability. (Have I mentioned that I think Cell should be built into the language?)
- pcwalton 8y agoYeah, I've given a lot of thought to ideas similar to your last paragraph, but all my attempts ended up having worse usability than just using arrays and indices. I eventually gave up and decided to stop worrying and love the indices. :) I should note that one nice thing about the ECS style is that it's built around threading around Systems, which consist of references to the various Components. So it's a natural fit for the borrow checker.
- idubrov 8y agoFWIW, it is possible to make it a bit more ergonomic: pub struct SmartRef<'a> { container: &'a Container, widget: usize, } impl <'a> std::ops::Deref for SmartRef<'a> { type Target = Widget; // Widget provides non-traversing functionality fn deref(&self) -> &Widget { &self.container.widgets[self.widget] } } impl <'a> SmartRef<'a> { fn children(&'a self) -> impl Iterator<Item = SmartRef<'a>> { self.container .widgets[self.widget] .children.iter().map(move |w| SmartRef { container: self.container, widget: *w }) } } fn boo(container: &Container) { let root = SmartRef { container, widget: 0 }; println!("name: {}", root.name); for child in root.children() { println!("child name: {}", child.name); } } (removed GAT remark -- it does not apply here; was thinking about generalizing this with traits)
- comex 8y agoHmm… that would work, but at the cost of requiring the data to be immutable or use interior mutability. It also removes the size advantage of storing indices over pointers, unless you only make SmartRefs temporarily rather than storing them in your data structures.
- idubrov 8y agoYes, the idea is that you only create them temporarily. Mutability is also possible to some extent with these "smart" pointers. It gets a bit trickier and less ergonomic, though. See https://play.rust-lang.org/?gist=fbf1c24397e7020c95774bf09060b6fd&version=stable&mode=debug&edition=2015 https://play.rust-lang.org/?gist=fbf1c24397e7020c95774bf0906... Another option would be to store something like "Rc<RefCell<Container>>" instead of "&'a mut Container", in which case you will be able to achieve something that behaves like multiple mutable references (with all the concurrency issues of them).
- meheleventyone 8y agoThough one of the nice things about using indexes is that you can lookup multiple arrays with the same index. This can be very useful for performance to break up a large data structure into smaller ones (e.g. to fit more elements in a cache line when you only use a subset of the structure for a complex operation) whilst still keeping their relationship intact. Further it’s also useful for all the reasons a relational database is in terms of querying data relationships.
- beagle3 8y agoIndeed. As a colleague of mine once noted, “eventually you write FORTRAN code, no matter what programming language you happen to do that in”.