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

[Mathieu Desnoyers]

----- On Mar 26, 2018, at 11:01 AM, Denis Yevgenyevich <denis.yevgenyevich at gmail.com> wrote: 

> 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!

The "accounting" option is meant to be enabled, otherwise you're using the hash table only with 
the bucket-length resize threshold, which has the imperfections you noticed. 

With accounting enabled, the bucket length is used as an approximation for when resize is needed 
only for small tables. Beyond a certain size, the numbers of elements in the hash table are used 
as a criterion for resize. 

Why is it unexpected that the table stops growing beyond 4096 after 900 insertions ? How many 
more insertions did you do beyond 900 ? 

Thanks, 

Mathieu 

> 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.

> _______________________________________________
> lttng-dev mailing list
> lttng-dev at lists.lttng.org
> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

-- 
Mathieu Desnoyers 
EfficiOS Inc. 
http://www.efficios.com 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.lttng.org/pipermail/lttng-dev/attachments/20180326/a81c971e/attachment.html>