4 ms·

Could someone help me understand how "generational indexes" differ from usual indexes? Does this have to do with how you allocate the indexes or with how you us

by ufo 8y ago

Could someone help me understand how "generational indexes" differ from usual indexes? Does this have to do with how you allocate the indexes or with how you use them? Are there run-time tests to check if the index is stale? (For example, check if the generation of the index I am holding matches the generation of the object stored in the entity array).

meheleventyone 8y ago
Each generation represents a new ‘giving out’ of the index. As you say this provides a runtime check against accessing a stale value. It’s a common pattern for ‘object pool’ allocators in game engines.
steveklabnik 8y ago
I released a crate that implements a doubly linked list this way. Here's an index. As you can see, it's got an index, but also a generation https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L174-L178 https://github.com/steveklabnik/indexlist/blob/master/src/li... The list itself keeps track of the current generation: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L104 https://github.com/steveklabnik/indexlist/blob/master/src/li... When an entry is removed, this is increased: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L680-L682 https://github.com/steveklabnik/indexlist/blob/master/src/li... Each entry also keeps track of the generation it was inserted with: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L119 https://github.com/steveklabnik/indexlist/blob/master/src/li... When you call get, which takes an Index, the generation is checked https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L577-L582 https://github.com/steveklabnik/indexlist/blob/master/src/li... Same as if you try to delete something at a given index: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L661 https://github.com/steveklabnik/indexlist/blob/master/src/li... Does that make sense?
- ufo 8y ago
  Thanks. It wasn't as clear to me in the article that there was a run-time check but it makes much more sense now.
  - steveklabnik 8y ago
    You're welcome. One interesting property of the current implementation is that you can use an Index across multiple IndexLists. That may or may not be what you want. There's a way to add a compile-time check to prevent this, but I haven't implemented it yet (https://github.com/steveklabnik/indexlist/issues/7 https://github.com/steveklabnik/indexlist/issues/7)
- thegeekpirate 8y ago
  What a wonderful explanation! Keep up the good work <3

by ufo 8y ago

meheleventyone 8y ago

Each generation represents a new ‘giving out’ of the index. As you say this provides a runtime check against accessing a stale value. It’s a common pattern for ‘object pool’ allocators in game engines.

steveklabnik 8y ago

I released a crate that implements a doubly linked list this way. Here's an index. As you can see, it's got an index, but also a generation https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L174-L178 https://github.com/steveklabnik/indexlist/blob/master/src/li... The list itself keeps track of the current generation: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L104 https://github.com/steveklabnik/indexlist/blob/master/src/li... When an entry is removed, this is increased: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L680-L682 https://github.com/steveklabnik/indexlist/blob/master/src/li... Each entry also keeps track of the generation it was inserted with: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L119 https://github.com/steveklabnik/indexlist/blob/master/src/li... When you call get, which takes an Index, the generation is checked https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L577-L582 https://github.com/steveklabnik/indexlist/blob/master/src/li... Same as if you try to delete something at a given index: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L661 https://github.com/steveklabnik/indexlist/blob/master/src/li... Does that make sense?

ufo 8y ago
Thanks. It wasn't as clear to me in the article that there was a run-time check but it makes much more sense now.
- steveklabnik 8y ago
  You're welcome. One interesting property of the current implementation is that you can use an Index across multiple IndexLists. That may or may not be what you want. There's a way to add a compile-time check to prevent this, but I haven't implemented it yet (https://github.com/steveklabnik/indexlist/issues/7 https://github.com/steveklabnik/indexlist/issues/7)
thegeekpirate 8y ago
What a wonderful explanation! Keep up the good work <3