
<html><body><div style="font-family: arial, helvetica, sans-serif; font-size: 12pt; color: #000000"><div><span id="zwchr" data-marker="__DIVIDER__">----- On Mar 26, 2018, at 11:01 AM, Denis Yevgenyevich <denis.yevgenyevich@gmail.com> wrote:<br></span></div><div data-marker="__QUOTED_TEXT__"><blockquote style="border-left:2px solid #1010FF;margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div dir="ltr"><div><div><div><div>Hello,<br><br>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.<br><br>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:<br></div>after about 100 insertions, the table was resized to 512<br>after about 500 insertions, the table was resized to 4096<br></div>after about 1300 insertions, the table was resized to 16384 and immediately to 32768<br><br></div><div>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!</div></div></div></blockquote><div><br></div><div>The "accounting" option is meant to be enabled, otherwise you're using the hash table only with</div><div>the bucket-length resize threshold, which has the imperfections you noticed.<br></div><div><br data-mce-bogus="1"></div><div>With accounting enabled, the bucket length is used as an approximation for when resize is needed<br data-mce-bogus="1"></div><div>only for small tables. Beyond a certain size, the numbers of elements in the hash table are used<br data-mce-bogus="1"></div><div>as a criterion for resize.<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div>Why is it unexpected that the table stops growing beyond 4096 after 900 insertions ? How many<br data-mce-bogus="1"></div><div>more insertions did you do beyond 900 ?<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div>Thanks,<br data-mce-bogus="1"></div><div><br data-mce-bogus="1"></div><div>Mathieu</div><blockquote style="border-left:2px solid #1010FF;margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div dir="ltr"><div><div><br><br></div>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?<br><br></div>Cheers, Denis.<br></div><br>_______________________________________________<br>lttng-dev mailing list<br>lttng-dev@lists.lttng.org<br>https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev<br></blockquote></div><div><br></div><div data-marker="__SIG_POST__">-- <br></div><div>Mathieu Desnoyers<br>EfficiOS Inc.<br>http://www.efficios.com</div></div></body></html>