Vec::pop() on Slab::remove() when possible

tokio-rs / slab

Slab allocator for Rust

MIT License

699 stars 84 forks source link

Vec::pop() on Slab::remove() when possible #58

Closed HyeonuPark closed 5 years ago

HyeonuPark commented 5 years ago

solves #38

carllerche commented 5 years ago

Thanks for the PR. Could you clarify how using pop addresses #38? As I understand, Vec::pop does not free memory?

HyeonuPark commented 5 years ago

Yes, but it actually shortens the vector so it can be shrink_to_fitted.

And I found just now that it's also needed to pop out all trailing Vacants. I'll fix it in this PR soon.

tormol commented 5 years ago

Removing other vacant entries would make remove() frequently take O(n) time, because the previous entry in the linked list that the vacant entries form must be updated and the index of that entry is not known.

With #62 shrink_to_fit() now pops trailing vacant entries on its own, so I don't think also doing that in remove() is useful.