----- On Mar 26, 2018, at 11:01 AM, Denis Yevgenyevich <denis.yevgenyev...@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@lists.lttng.org > https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
_______________________________________________ lttng-dev mailing list lttng-dev@lists.lttng.org https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
