[Caml-list] Hashtbl and shrinking

["Armaël Guéneau" <armael.gueneau@ens-lyon.fr>]

Dear caml-list,

It happens Arthur Charguéraud and myself were looking this afternoon at
the implementation of the Hashtbl module, provided in our beloved OCaml
standard library.

We noticed there is no shrinking implemented, that would typically
happen when the number of elements goes under a certain threshold
compared to the size of the underlying array.

This yields a space complexity that we think may not be what people
might expect: an almost empty hashtable will consume as much memory as
when it was full. The time complexity might also be worse than expected,
because the GC will still spend time scanning the whole array even when
there are only a few elements.

What do people here think about this?
If we submitted a patch implementing shrinking for Hashtbl, could it be
detrimental for some specific workloads?

— Armaël