9 ms·

I know this works, but whenever I hear this advice, I can't help thinking: Aren't indexes and vectors basically just a way of smuggling pointers past the borrow

by chc 8y ago

I know this works, but whenever I hear this advice, I can't help thinking: Aren't indexes and vectors basically just a way of smuggling pointers past the borrow checker?

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 ago
  Yeah, 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 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?)
PyroLagus 8y ago
Kind of but not really. You still can't access an undeclared element, and you still can't take a mutable and an immutable reference to an element by index. The borrow checker only cares about memory safety, and index accessors are implemented in a memory safe manner (whether that's panic!ing or returning an Option<>). If you want… umm… "data safety" (I'll call it for now), so you can't use an index to access an element that you didn't intend to access because stuff got shifted around for instance, then generational indexes will solve that issue for you. And to clarify something that's probably obvious. A direct pointer to a vector element could easily end up becoming invalid when the vector has to be copied somewhere else for it to grow or if the element gets deleted in another thread, so you can't just easily use pointers to vector (or array) elements in Rust.
- esrauch 8y ago
  I think the point is that Rust's checking allows you to statically know you don't have a dangling pointer. Indices explicitly can be dangling or accidentally incorrectly point at a new value that replaced the same slot or whatever. You suddently need to manually decide when to free values. It does avoids the worst security issues (bad reads are at least contained to the same data structure, which can easily be a serious security issue but at least not arbitrary memory reads) but for a lot of purposes it has the same properties that you have with C style pointers. It seems like a giant problem that Rust advocates are strangle quick to gloss over as a good pattern.
  - skybrian 8y ago
    Indexes in an ECS system are basically a way to implement weak references. If you use generational indexes, it's a checked weak reference. Otherwise it's unchecked. Perhaps some future Rust-like language will have weak references built in? Even with unchecked weak references, you can't get arbitrary undefined behavior. It's more like Java where you can defeat the type system due to the way generics work, but it's still memory-safe. Also, relational databases work the same way. Sometimes people use constraints to avoid dangling references, but not always.
  - malkia 8y ago
pcwalton 8y ago
If you think about it, an index is just a pointer that's checked for validity every time it's used. That's precisely what you want in the case of irregular memory access patterns.
- derefr 8y ago
  I feel like raw pointers and indices are about the same. Indices can be runtime bounds-checked, with a violation resulting in a crash. Raw pointers—if they're single heap allocations—are also runtime validity-checked, in the sense that violations will (probabilistically) result in a General Protection Fault, given a large address space and ASLR. References (i.e. pointers the compiler knows about), on the other hand, are strictly better than either. Indices can only be bounds-checked at runtime, while references can be both alias-checked and bounds-checked (if they're references into a slice of memory that is known to the compiler) at compile-time. But, of course, you can't do math to references. Construct a pointer by through an integer cast + math, and now the compiler has no idea what that thing is, what it's inside of, or how many other pointers point to the same place it does.
  - evmar 8y ago
    ASLR loads segments into random places, but it doesn't split the heap up. Memory allocators typically (always?) arrange things contiguously for ease of management.
  - MaulingMonkey 8y ago
    > Raw pointers—if they're single heap allocations—are also runtime validity-checked I prefer my runtime validity checking to not come with CVE numbers, the corruption of instances of completely unrelated types, and other such heisenbugs. > I feel like raw pointers and indices are about the same On a large codebases with lots of contributors, there's several orders of magnitude of difference - between the number of bounds checked indices that could be "corrupting" your instances of type T (only those used to index arrays of T or things containing them), vs the number of pointers that could be corrupting your instances of type T (basically any pointer in the program whatsoever.) Frequently with a similar "several orders of magnitude" difference in debug times. Conceptually similar, practically not.
wokwokwok 8y ago
This was extensively discussed on reddit and a few other places (not HN afaik, or I couldn't find the thread), after the video^ Jonathan Blow posted on the topic. I think the tldr; is, opinions vary. Using indexes manually doesn't by-pass the borrow checker, its just a different, manual, memory allocation and management strategy. It preserves memory-safety, but, it's questionable if you're better or worse off in terms of correctness of application logic when you use it. ...you're probably better off using the borrow checker (that's why it exists) or an abstraction in a crate to deal with this sort of problem, regardless of whatever implementation strategy it uses internally (unsafe, this, etc). [1] - https://www.youtube.com/watch?v=4t1K66dMhWk https://www.youtube.com/watch?v=4t1K66dMhWk
thristian 8y ago
Yes, but that's kind of the point: Rust's borrow checker only really works for data-ownership graphs that are trees, and although it does pretty well for that use-case, it's not perfect and research continues on how to make it less conservative while still being safe (consider the non-lexical-lifetimes feature arriving in a near-future release of Rust). A static borrow-checker that works for directed-acyclic or even cyclic ownership graphs would be wonderful, but that's definitely an open research topic, not a production-quality-compiler topic. So if you can't prove your ownership graph is safe at compile time, you have to do it at runtime. For some ownership graphs, reference counting with Rc<T> is the right choice, but in the general case indexes and vectors are the least-verbose way to represent a runtime ownership graph.
MaulingMonkey 8y ago
You have lots of options for non-borrowing references to instances of T: Indicies, Arc<T>, RefCell<T>, Cell<T>, dictionary keys, paths to files containing serialized Ts... the list is unbounded. This is all perfectly fine: It's not the goal of the borrow checker to prevent simultaneous references to data, that'd be ridiculous and useless. The goal is to prevent unsafe simultaneous access of data. And accessing data through an index still requires you to first acquire e.g. a borrow, and the useful invariants of that borrow still hold: for the duration of that borrow, you have freedom from data races - there will be no other borrows to that instance when you're holding a &mut T, or there will be no other mutable borrows to that instance when you're holding a &T. An index may allow you to reduce the scope and lifetimes of your borrows, but it does not allow you to eliminate your borrows.
- malkia 8y ago
  a nice side effect - index can now be "compressed" - e.g. just 1 bytes, 2, 4 or more. Such approach comes useful in GC languages too, as you limit the work a GC has to do, going through the roots, checking anything that can be a pointer.
  - beagle3 8y ago
    Indeed. If you take that to the logical conclusion, you reach the K/J/APL mindset - objects are not a useful abstraction. Just use arrays with correlates indexes and be done with it.
cjhanks 8y ago
No. On 64bit machines, a 32bit index saves you significant memory, and if you can use a 16bit... even more. These savings matter a lot in some domains of computing.
- doomrobo 8y ago
  An index into any std data structure has type usize, though, and usize is 64 bits on a 64 bit machine.
  - dbaupp 8y ago
    They don't have to be stored as a usize. This is slightly annoying because it may add casts, but not if one already has a newtype wrapper around the integers: the type stored in the wrapper could be a u32, with the conversions to usize hidden by the indexing APIs.
    - cjhanks 8y ago
      2 cycles or so, I think. In my experience, this cost is usually overwhelmed by the inherent (to this class of algorithms) cache misses.
      - dbaupp 8y ago
        2 cycles for a 32-bit to 64-bit extension? I don't think that makes sense: for instance, on x86-64, there's no cast necessary, just use the %rax register instead of the %eax one (plus, memory addressing works fine with 32 bit registers directly). I believe the same is true of AArch64 (64-bit ARM) with the 32-bit register W0 being the bottom half of the 64-bit register X0.
        cjhanks 8y ago
        Yeah, your intuition seems correct to me. I wonder if I was thinking about 64 to 32 signed, or if just didn't know.
kibwen 8y ago
It's not bypassing the borrow checker; it's bypassing references. C++ doesn't have a borrow checker, and the same pattern of forgoing references for integer IDs is seen there. References are a just a tool to express certain pointer patterns, and like every other tool they have contexts for which they work well and contexts for which they don't. Really the most surprising result of all this is the broadening realization that references aren't the end-all abstraction for reasoning about pointer-like behavior (familiarity with smart pointers like C++'s shared_ptr makes this less of a surprising realization, but it's easy to initially dismiss a library-level feature as being less intrinsically fundamental than a language-level feature). This isn't to say that futzing with integers is the best imaginable solution for these tasks. Language-level support (or at least stdlib support) for generational indices would be an interesting subject to pursue.
- rtpg 8y ago
  I think the point is that if you're juggling integers open you up to the huge correctness messes from before, even if theoretically you've gotten rid of your memory mess. Granted, you could `Option`-up all your operations, but the dynamic GC languages (or even C++) will let you operate on stuff "correctly", so long as your implementation is right. You can go `unsafe` and implement correct stuff and still be better than C++. I really feel like reference IDs aren't a great way to solve something like a doubly-linked list. Reference IDs make you lose almost all guarantees of correctness, unsafe + a good API will at least give you a fighting chance. There are problems (like entity system stuff) where reference IDs are just the way to go, though
  - kibwen 8y ago
    > I think the point is that if you're juggling integers But I don't think anyone should be juggling integers themselves; they should be using a library (just like a library-defined smart pointer) that handles that (the presentation at https://www.youtube.com/watch?v=P9u8x13W7UE https://www.youtube.com/watch?v=P9u8x13W7UE may be of interest). > There are problems (like entity system stuff) where reference IDs are just the way to go, though Sure, and there isn't anything stopping anyone from both using them where they're practical and not using them where they're not. Some of the comments in this thread seem to be suggesting that you must choose one or the other, but that's simply not the case; using references in one part of one's program and indices in another is totally fine, as is using references and indices together in the same part of the program. They're not exclusive. In particular, nobody is saying that one should be reaching for indices regularly; I've written Rust for years and have never, ever needed them. References work just fine for plenty of applications. But we have other smart pointers for good reasons, and sometimes an application will call for the use one of those smart pointers, and that's totally cool; again, references may be thoroughly useful, but they are not the end-all be-all of pointer-like abstractions.
ryani 8y ago
So I used to think this, but I've come around a bit. What indexes do is let you put a pointer "to sleep"; it can be woken up only by pairing it with a live data structure which you correctly have safe ownership of at the time. This "dormant" pointer can be safely stored in data structures that have no concept of the containing object's lifetime, which in games is exactly the common use of entity handles (usually implemented as generational indices), hibernating until the original object is really needed. I think it's possible to write a DormantPtr library that encapsulates this pattern with better ergonomics than vec<> + generational index.
- pas 8y ago
  Kind of like a WeakRef in Java?

by chc 8y ago

I know this works, but whenever I hear this advice, I can't help thinking: Aren't indexes and vectors basically just a way of smuggling pointers past the borrow checker?

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 ago
Yeah, 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 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?)

PyroLagus 8y ago

Kind of but not really. You still can't access an undeclared element, and you still can't take a mutable and an immutable reference to an element by index. The borrow checker only cares about memory safety, and index accessors are implemented in a memory safe manner (whether that's panic!ing or returning an Option<>). If you want… umm… "data safety" (I'll call it for now), so you can't use an index to access an element that you didn't intend to access because stuff got shifted around for instance, then generational indexes will solve that issue for you. And to clarify something that's probably obvious. A direct pointer to a vector element could easily end up becoming invalid when the vector has to be copied somewhere else for it to grow or if the element gets deleted in another thread, so you can't just easily use pointers to vector (or array) elements in Rust.

esrauch 8y ago
I think the point is that Rust's checking allows you to statically know you don't have a dangling pointer. Indices explicitly can be dangling or accidentally incorrectly point at a new value that replaced the same slot or whatever. You suddently need to manually decide when to free values. It does avoids the worst security issues (bad reads are at least contained to the same data structure, which can easily be a serious security issue but at least not arbitrary memory reads) but for a lot of purposes it has the same properties that you have with C style pointers. It seems like a giant problem that Rust advocates are strangle quick to gloss over as a good pattern.
- skybrian 8y ago
  Indexes in an ECS system are basically a way to implement weak references. If you use generational indexes, it's a checked weak reference. Otherwise it's unchecked. Perhaps some future Rust-like language will have weak references built in? Even with unchecked weak references, you can't get arbitrary undefined behavior. It's more like Java where you can defeat the type system due to the way generics work, but it's still memory-safe. Also, relational databases work the same way. Sometimes people use constraints to avoid dangling references, but not always.
- malkia 8y ago

pcwalton 8y ago

If you think about it, an index is just a pointer that's checked for validity every time it's used. That's precisely what you want in the case of irregular memory access patterns.

derefr 8y ago
I feel like raw pointers and indices are about the same. Indices can be runtime bounds-checked, with a violation resulting in a crash. Raw pointers—if they're single heap allocations—are also runtime validity-checked, in the sense that violations will (probabilistically) result in a General Protection Fault, given a large address space and ASLR. References (i.e. pointers the compiler knows about), on the other hand, are strictly better than either. Indices can only be bounds-checked at runtime, while references can be both alias-checked and bounds-checked (if they're references into a slice of memory that is known to the compiler) at compile-time. But, of course, you can't do math to references. Construct a pointer by through an integer cast + math, and now the compiler has no idea what that thing is, what it's inside of, or how many other pointers point to the same place it does.
- evmar 8y ago
  ASLR loads segments into random places, but it doesn't split the heap up. Memory allocators typically (always?) arrange things contiguously for ease of management.
- MaulingMonkey 8y ago
  > Raw pointers—if they're single heap allocations—are also runtime validity-checked I prefer my runtime validity checking to not come with CVE numbers, the corruption of instances of completely unrelated types, and other such heisenbugs. > I feel like raw pointers and indices are about the same On a large codebases with lots of contributors, there's several orders of magnitude of difference - between the number of bounds checked indices that could be "corrupting" your instances of type T (only those used to index arrays of T or things containing them), vs the number of pointers that could be corrupting your instances of type T (basically any pointer in the program whatsoever.) Frequently with a similar "several orders of magnitude" difference in debug times. Conceptually similar, practically not.

wokwokwok 8y ago

This was extensively discussed on reddit and a few other places (not HN afaik, or I couldn't find the thread), after the video^ Jonathan Blow posted on the topic. I think the tldr; is, opinions vary. Using indexes manually doesn't by-pass the borrow checker, its just a different, manual, memory allocation and management strategy. It preserves memory-safety, but, it's questionable if you're better or worse off in terms of correctness of application logic when you use it. ...you're probably better off using the borrow checker (that's why it exists) or an abstraction in a crate to deal with this sort of problem, regardless of whatever implementation strategy it uses internally (unsafe, this, etc). [1] - https://www.youtube.com/watch?v=4t1K66dMhWk https://www.youtube.com/watch?v=4t1K66dMhWk

thristian 8y ago

Yes, but that's kind of the point: Rust's borrow checker only really works for data-ownership graphs that are trees, and although it does pretty well for that use-case, it's not perfect and research continues on how to make it less conservative while still being safe (consider the non-lexical-lifetimes feature arriving in a near-future release of Rust). A static borrow-checker that works for directed-acyclic or even cyclic ownership graphs would be wonderful, but that's definitely an open research topic, not a production-quality-compiler topic. So if you can't prove your ownership graph is safe at compile time, you have to do it at runtime. For some ownership graphs, reference counting with Rc<T> is the right choice, but in the general case indexes and vectors are the least-verbose way to represent a runtime ownership graph.

MaulingMonkey 8y ago

You have lots of options for non-borrowing references to instances of T: Indicies, Arc<T>, RefCell<T>, Cell<T>, dictionary keys, paths to files containing serialized Ts... the list is unbounded. This is all perfectly fine: It's not the goal of the borrow checker to prevent simultaneous references to data, that'd be ridiculous and useless. The goal is to prevent unsafe simultaneous access of data. And accessing data through an index still requires you to first acquire e.g. a borrow, and the useful invariants of that borrow still hold: for the duration of that borrow, you have freedom from data races - there will be no other borrows to that instance when you're holding a &mut T, or there will be no other mutable borrows to that instance when you're holding a &T. An index may allow you to reduce the scope and lifetimes of your borrows, but it does not allow you to eliminate your borrows.

malkia 8y ago
a nice side effect - index can now be "compressed" - e.g. just 1 bytes, 2, 4 or more. Such approach comes useful in GC languages too, as you limit the work a GC has to do, going through the roots, checking anything that can be a pointer.
- beagle3 8y ago
  Indeed. If you take that to the logical conclusion, you reach the K/J/APL mindset - objects are not a useful abstraction. Just use arrays with correlates indexes and be done with it.

cjhanks 8y ago

No. On 64bit machines, a 32bit index saves you significant memory, and if you can use a 16bit... even more. These savings matter a lot in some domains of computing.

doomrobo 8y ago
An index into any std data structure has type usize, though, and usize is 64 bits on a 64 bit machine.
- dbaupp 8y ago
  They don't have to be stored as a usize. This is slightly annoying because it may add casts, but not if one already has a newtype wrapper around the integers: the type stored in the wrapper could be a u32, with the conversions to usize hidden by the indexing APIs.
  - cjhanks 8y ago
    2 cycles or so, I think. In my experience, this cost is usually overwhelmed by the inherent (to this class of algorithms) cache misses.
    - dbaupp 8y ago
      2 cycles for a 32-bit to 64-bit extension? I don't think that makes sense: for instance, on x86-64, there's no cast necessary, just use the %rax register instead of the %eax one (plus, memory addressing works fine with 32 bit registers directly). I believe the same is true of AArch64 (64-bit ARM) with the 32-bit register W0 being the bottom half of the 64-bit register X0.
      - cjhanks 8y ago
        Yeah, your intuition seems correct to me. I wonder if I was thinking about 64 to 32 signed, or if just didn't know.

kibwen 8y ago

It's not bypassing the borrow checker; it's bypassing references. C++ doesn't have a borrow checker, and the same pattern of forgoing references for integer IDs is seen there. References are a just a tool to express certain pointer patterns, and like every other tool they have contexts for which they work well and contexts for which they don't. Really the most surprising result of all this is the broadening realization that references aren't the end-all abstraction for reasoning about pointer-like behavior (familiarity with smart pointers like C++'s shared_ptr makes this less of a surprising realization, but it's easy to initially dismiss a library-level feature as being less intrinsically fundamental than a language-level feature). This isn't to say that futzing with integers is the best imaginable solution for these tasks. Language-level support (or at least stdlib support) for generational indices would be an interesting subject to pursue.

rtpg 8y ago
I think the point is that if you're juggling integers open you up to the huge correctness messes from before, even if theoretically you've gotten rid of your memory mess. Granted, you could `Option`-up all your operations, but the dynamic GC languages (or even C++) will let you operate on stuff "correctly", so long as your implementation is right. You can go `unsafe` and implement correct stuff and still be better than C++. I really feel like reference IDs aren't a great way to solve something like a doubly-linked list. Reference IDs make you lose almost all guarantees of correctness, unsafe + a good API will at least give you a fighting chance. There are problems (like entity system stuff) where reference IDs are just the way to go, though
- kibwen 8y ago
  > I think the point is that if you're juggling integers But I don't think anyone should be juggling integers themselves; they should be using a library (just like a library-defined smart pointer) that handles that (the presentation at https://www.youtube.com/watch?v=P9u8x13W7UE https://www.youtube.com/watch?v=P9u8x13W7UE may be of interest). > There are problems (like entity system stuff) where reference IDs are just the way to go, though Sure, and there isn't anything stopping anyone from both using them where they're practical and not using them where they're not. Some of the comments in this thread seem to be suggesting that you must choose one or the other, but that's simply not the case; using references in one part of one's program and indices in another is totally fine, as is using references and indices together in the same part of the program. They're not exclusive. In particular, nobody is saying that one should be reaching for indices regularly; I've written Rust for years and have never, ever needed them. References work just fine for plenty of applications. But we have other smart pointers for good reasons, and sometimes an application will call for the use one of those smart pointers, and that's totally cool; again, references may be thoroughly useful, but they are not the end-all be-all of pointer-like abstractions.

ryani 8y ago

So I used to think this, but I've come around a bit. What indexes do is let you put a pointer "to sleep"; it can be woken up only by pairing it with a live data structure which you correctly have safe ownership of at the time. This "dormant" pointer can be safely stored in data structures that have no concept of the containing object's lifetime, which in games is exactly the common use of entity handles (usually implemented as generational indices), hibernating until the original object is really needed. I think it's possible to write a DormantPtr library that encapsulates this pattern with better ergonomics than vec<> + generational index.

pas 8y ago
Kind of like a WeakRef in Java?