[lttng-dev] [liburcu] rculfhash autoresizing creates huge tables

[Denis Yevgenyevich]

Hello,

I think rculfhash autoresizing (as enabled by CDS_LFHT_AUTO_RESIZE) does
not behave well. Each time _cds_lfht_add finds a hash bucket with more than
2 items, it basically tries to quadruple the hash table size. But even with
a perfect hash function hash collisions are not that rare, given a large
enough table. That is, every now and then the algorithm will come across a
3-long chain and will grow the table unnecessarily.

I created a table with cds_lfht_new(16, 16, 1<<16, CDS_LFHT_AUTO_RESIZE,
NULL) and began adding an item each 10ms. Each item had a unique key and
the hash function was very good (full 64-bit values of Siphash). Judging by
messages I added to rculfhash.c, this was happening:
after about 100 insertions, the table was resized to 512
after about 500 insertions, the table was resized to 4096
after about 1300 insertions, the table was resized to 16384 and immediately
to 32768

With CDS_LFHT_AUTO_RESIZE|CDS_LFHT_ACCOUNTING the behaviour was different
but still unacceptable: the table got resized to 4096 after 900 insertions
and then stopped growing!

Could someone please implement saner resize conditions, or better yet, add
a customisable hook for decisions as to when and how much should a table
grow?

Cheers, Denis.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.lttng.org/pipermail/lttng-dev/attachments/20180326/75942cbc/attachment.html>