> 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 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.
https://docs.rs/slotmap/1.0.6/slotmap/#performance-character...