4 ms·
It depends on what you mean by “smuggling.” This implies something bad; I don’t think this pattern is inherently bad. It’s just different. It’s another example
by steveklabnik 8y ago
It depends on what you mean by “smuggling.” This implies something bad; I don’t think this pattern is inherently bad. It’s just different. It’s another example of moving a compile-time check to a runtime check, and depending on what you’re doing, can have better cache locality and better performance.
- vvanders 8y agoYeah, that's a pattern we used all over the place in games where we also abused the hell out of pointers(some in-place loaders I've seen would turn your hair white) because the pattern has other merits.
- comex 8y agoIt 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?)