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.
_______________________________________________ lttng-dev mailing list lttng-dev@lists.lttng.org https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
