The advantage w.r.t references is that with Slotmap, you can express cyclical data structures, whereas with references you can't.
The advantage w.r.t plain Vec and juggling integer indices is that unlike integers, Slotmap keeps track of the "identity" of the stored object; the keys are unique to that object, and you can't accidentally refer to a wrong object with them.
> errors risk being silent references to wrong objects
Slotmap is specifically designed to prevents this. I recommend you to read its documentation; the generational indices system is quite nice!
> Slotmap keeps track of the "identity" of the stored object
(I am not sure if slotmap uses this strategy)
To give more details some of these data structures use generational indexes, a pair (generation, index) where index is a plain index of the underlying vector and generation is a bookkeeping counter of how many times you have allocated a value to that index. These two values can be combined in a single 32bit-64bit value but additional memory would be required to keep track of the counter.
E.g. with a vector of length 2
{meta: [0,0], data:[...]}
malloc -> (1,0)
{meta: [1,0], data:[...]}
malloc -> (1,1)
{meta: [1,1], data:[...]}
free(0)
{meta: [2,1], data:[...]}
malloc -> (3,0)
{meta: [3,1], data:[...]}
free(0)
{meta: [4,1], data:[...]}
malloc -> (5,0)
{meta: [5,1], data:[...]}
free(0)
free(1)
{meta: [6,2], data:[...]}
malloc -> (7,0)
malloc -> (3,1)
{meta: [7,3], data:[...]}
This way if you tried to access the pointer (5,0) the library can check that at index zero of the meta array the generation is 7 and conclude that you are doing a use after free (in this example even generations denote unallocated memory).
This is a description of a very simplified algorithm.
I meant counted references that were mentioned as an alternative in the GP comment.
A generation count indeed could mitigate "use after free" style bugs, but may have a high false negative ratio if many/most objects have same generation. But a glance at slotmap docs didn't yield any hits for a generation I'd being used, do you have a specific link?
> I meant counted references that were mentioned as an alternative in the GP comment.
The main problem with reference counted pointers is detecting cycles. Rust doesn't have a cycle detector, but only a concept of "weak" pointers that don't prevent the object they're pointing at from being destroyed, just detect if it has been. This works fine if you have a tree with parent pointers, you make the parent pointers weak and everything works. It doesn't work so well if you don't have a clear tree structure though, because then you can't really tell which pointers should be strong and which should be weak.
> but may have a high false negative ratio if many/most objects have same generation. But a glance at slotmap docs didn't yield any hits for a generation I'd being used, do you have a specific link?
Apart from wrapping around after 2^32 frees of a specific slot, I don't believe any false positives are possible. The trade off is that there's more overhead than I think you're imagining.
Once I get around to slotmap 2.0 (as noted by my inactivity, I haven't had much of the good free time + energy combination last year), the default behavior will be to leak the memory of a slot after 2^31 alloc/free pairs in that slot rather than wrapping around. You can still get the old wrapping behavior, but the default will be to never, ever allow spurious references, at the cost of leaking a couple bytes of memory once in a blue moon if you have heavy, heavy churn. That means, amortized, each insertion will leak 3.726 nanobytes if you're storing u32s, which is a fun unit. Note that if you destruct the slotmap the memory is reclaimed of course, I just mean that slotmap itself will not use that piece of memory again.
> The trade off is that there's more overhead than I think you're imagining.
I don't think the overhead is as large as this implies. For SlotMap the memory overhead is ~4bytes plus alignment per element, and insertion/deletion is only a handful instructions and one branch extra compared to a vector push:
> I don't think the overhead is as large as this implies. For SlotMap the memory overhead is ~4bytes plus alignment per element, and insertion/deletion is only a handful instructions and one branch extra compared to a vector push:
I think they were imagining one generation counter for the entire map instead of one per slot. I agree it's not particularly high.
The advantage w.r.t plain Vec and juggling integer indices is that unlike integers, Slotmap keeps track of the "identity" of the stored object; the keys are unique to that object, and you can't accidentally refer to a wrong object with them.
> errors risk being silent references to wrong objects
Slotmap is specifically designed to prevents this. I recommend you to read its documentation; the generational indices system is quite nice!