`shrink_to_fit` won't shrink

[cramertj]

Once elements have been inserted into the inner entries Vec, they're never removed. The remove function only swaps out elements for Entries::Vacant. This means that, even after removal, the slab can never shrink to less than the maximum number of items that were ever inserted.

extern crate slab;
use slab::Slab;

fn main() {
    let mut slab = Slab::new();
    let mut keys = Vec::new();
    println!("{}", slab.capacity()); // Prints "0"
    for _ in 0..2048 {
        keys.push(slab.insert(()));
    }
    println!("{}", slab.capacity()); // Prints "2048"
    for key in keys {
        slab.remove(key);
    }
    println!("{}", slab.capacity()); // Prints "2048"
    slab.shrink_to_fit();
    println!("{}", slab.capacity()); // Prints "2048", should print "0" (or at least a lower number)
}

When shrink_to_fit is called, it should check to see where the last Entry::Occupied is, and truncate the vector to that length. Scanning linearly from the back of the vector would be O(n), which is suboptimal, but it's the only way in which this method is at all useful. Perhaps the slab and its entries could store last (occupied) indices in addition to next (vacant) indices, allowing for an O(1) implementation of shrink_to_fit.

[carllerche]

Well, the slab can reserve capacity with the inner vec. The idea is if you call shrink_to_fit before an Entry is pushed, it can dump that capacity. I don't think a linear scan should be performed.

Granted, shrink_to_fit isn't a great name.

[cramertj]

I agree that a linear scan isn't great-- I think we should be able to find a better way. Even if we can't, though, IMO there should definitely be some way to reclaim unused memory.

[oconnor663]

Maybe remove could detect when it's setting the last entry in the vec to Vacant, and do a loop at that point to drop all the vacant entries from the tail? I think that loop would count as "amortized constant time" :)

[carllerche]

My main reservation is that, at some point, you should not use slab and just use the allocator. I'm not exactly sure what that point is, but it seems that this kind of work would be entering that space.

Basically, if you want to reclaim space, why not just allocate? The goal of slab is stay constant.

[cramertj]

@carllerche slab guarantees that late accesses will not result in use-after-frees, but simply missing or incorrect elements. This allows event dispatchers such as tokio-core to safely retrieve futures based on the tokens returned by mio. If futures were allocated and freed rather than put in a slab, the token would have to be a pointer, which means that spurious events would result in use-after-free rather than missing elements or spurious wakeups.