search

orlp / slotmap

Slotmap data structure for Rust
zlib License
1.16k stars 70 forks source link

Clarification on allocation/deallocation #68

Closed ErikNatanael closed 3 years ago

ErikNatanael commented 3 years ago

Hi! I'm using a DenseSlotMap to store nodes that produce audio in an audio engine. Since the DenseSlotMap is on the audio thread, it is not allowed to allocate or deallocate memory after initialisation. A data structure that reuses memory seems like a great fit, but it turns out I'm not quite clear on how the DenseSlotMap deals with allocation.

My DenseSlotMap contains a struct that contains a boxed closure, which will need to be deallocated when the node is finished. Therefore, I'm sending it to another thread for deallocation. However, since the DenseSlotMap is reusing the memory where the element was stored, what memory is actually returned from calling remove()? Is a clone of the object allocated at removal?

Similarly, is any memory deallocated on insertion into the map?

Apologies if this is documented somewhere, I couldn't find it nor quite understand the code.

orlp commented 3 years ago

My DenseSlotMap contains a struct that contains a boxed closure, which will need to be deallocated when the node is finished. Therefore, I'm sending it to another thread for deallocation. However, since the DenseSlotMap is reusing the memory where the element was stored, what memory is actually returned from calling remove()? Is a clone of the object allocated at removal?

For all (secondary) slot maps, calling remove gives you back the original object for all intents and purposes similar to how Vec::pop gives you back the original object.

It is technically a bit-by-bit copy of the data that used to be in the slot map (note that this means just copying a pointer for Box - not the data inside the Box), but this data is never accessed again or Dropped, and instead will silently be overwritten the next time that slot is used. This is exactly how Vec works under the hood as well.

Similarly, is any memory deallocated on insertion into the map?

Only if the slot map needs to resize for more capacity. If you pre-allocate sufficient capacity the existing allocation is exclusively used and none of the slot maps will do any further (de-)allocation.

ErikNatanael commented 3 years ago

That sounds like what I need, thanks!