Implement automatic shrinking on key_put()

[capr]

Hi!

I noticed this TODO on kh_put():

TODO: implement automatic shrinking; resize() already supports shrinking

... and above I see there's a resize call with h.n_buckets - 1 and the comment clear "deleted" elements so it seems like it does shrink on certain situations but not in others? Can you give more details on this please?

Thanks!

[attractivechaos]

No, the table never shrinks automatically. You have to manually shrink the table by calling kh_resize().

khash may automatically rehash to the same size in order to clear "tomestones" when there are too many.

[attractivechaos]

Khash doesn't automatically shrink because it can't expect what users will do with the hash table. Automatic shrink may have big unexpected performance hits. It's better to let users decide.

[capr]

Hi @attractivechaos thanks for the explanation. Can you recommend a good strategy / formula for when to call resize periodically in order to implement auto-shrinking?

Btw, AFAIU, n_buckets is the total number of key/value pairs that there's memory allocated for, and size is the number of live pairs. Is that right? If so, what does n_occupied measure?