[orlp]

Hi, author of slotmap here if anyone has any questions.

Slotmap is essentially the Vec + indices solution, while allowing memory to be reused. It is still completely safe, as it automatically versions each slot, and checks the version contained in the key when indexing.

[kubb]

Does slotmap shrink and reclaim allocated memory when most of the elements it stores get deleted?

[nightcracker]

SlotMap literally cannot, because it must keep track of versions of the used slots, and the slots include the memory space for the data.

DenseSlotMap sort of can. It still can't reclaim the memory used by empty slots for the same reason (at a cost of 8 bytes per slot), but can reclaim the memory used by the actual elements stored.

So if you store 1 million items at one point in a DenseSlotMap, and then clear them all and then shrink to fit (which is actually missing from the API, but I'll fix that soon) you will waste 7.6 megabytes on the empty slots but nothing on the actual data that used to be stored.

[cyber_kinetist]

Yes, if you use the dense version of it (DenseSlotMap). It requires an additional indirection per lookup, but makes up for the fact that it’s much cache friendlier. From looking at a simple benchmark (https://www.reddit.com/r/rust/comments/gfo1uw/benchmarking_s...) it seems that insertion/deletion gets a hit but accesses are faster (although YMMV on real world use cases)

[orlp]

This reddit post is such a shame, and I wish people would stop referring to it. The benchmarking code is not apples to apples at all in many places.

E.g. to benchmark removals they used `container.remove(index)` for data structures that support indices but for slotmap they used `slotmap.remove(keys[index])` which unfairly adds another layer of indirection.

[mattgreenrocks]

If there’s a lot of churn on the tree, does fragmentation rear its head? Or does the version in the key come into play here?

[nightcracker]

There is no fragmentation whatsoever in the traditional sense (unusable gaps left due to size mismatches), because a slotmap only stores a single type of value. Thus every slot is interchangeable and memory can always be reused.

For iteration however, there can be holes that need to be ignored, if the current number of elements in the slotmap is significantly lower than the the maximum capacity. If iteration needs to be very fast (for e.g. game engines) I do have a solution for that, which is the DenseSlotMap. It uses one extra layer of indirection for random access, but stores the actual data values contiguously in a vector, thus iteration is always fast.

[mattgreenrocks]

Yes, holes is a better term. Was wondering if double pointers (as they were) were used, looks like it was right. Thank you for the reply!

[Dowwie]

Slotmap seems to have a marketing problem. Why isn't it being promoted?

[nightcracker]

I don't know, only have some theories.

1. The name isn't particularly catchy or descriptive. It is the correct name for the data structure, but not too many people know the data structure.

2. People don't even know what they're missing. It's not a very Google-able problem to begin with. Slotmap provides an interesting solution to (circular) ownership and safe allocator / weak pointer design problems, but people don't recognize that they're having them or that slotmap could help.

As an example of this, the doubly linked list example (https://github.com/orlp/slotmap/blob/master/examples/doubly_...) can safely remove nodes from the linked list given their handle, in O(1), even from the middle, completely safely and correctly, even in the presence of double deletions or ABA memory re-use. You can't replicate this with just pointers, without introducing heavy refcounting solutions.