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

Tue Mar 27 12:17:08 EDT 2018

(Please keep the lttng-dev mailing list in CC.)

----- On Mar 27, 2018, at 12:07 PM, Denis Yevgenyevich denis.yevgenyevich at gmail.com wrote:

>> When both flags are set, check_resize() is only for the bucket-local chain
> > length algorithm that deals
>> with very small tables. Then, when the table size goes above that threshold,
> > split-counters are used to
>> adjust the required table size. We don't use the split-counters approximation of
> > the number of elements
>> in the table for small tables because they are not accurate enough for small
> > tables. It's a tradeoff
> > between accuracy and accounting overhead here.
> Thanks for the explanation.

>> Notice that ht_count_add() and ht_count_del() both invoke
> > cds_lfht_resize_lazy_count(). It's that
> > function which is responsible for the split-counter based resize algorithm.
>> If both (CDS_LFHT_ACCOUNTING | CDS_LFHT_AUTO_RESIZE) flags are set, the table
> > will
> > still grow after it has gone beyond this condition.
> That's what I overlooked. I've just repeated my test, letting it run for a
> longer time.
> After 4096 items (4-core cpu) check_resize() stopped growing the table.

4096 buckets is indeed the threshold for a 4-core cpu system. 

> After 32768 items ht_cound_add() finally grew the table to 32768. That is when
> the check
> if ((count >> CHAIN_LEN_RESIZE_THRESHOLD) < size)
> went false. The average chain length might have been 8 by that time. Isn't it
> too much?

Actually, this is not the average chain length: the resize happens when the first chain going 
beyond the threshold is encountered. I would expect the average chain length to be somewhere 
below that threshold. It would be interesting if you could provide insight into the distribution of 
your hash table bucket chain length by adding instrumentation code. 

> Perhaps you could make CHAIN_LEN_RESIZE_THRESHOLD a tunable?

That would be a possibility, yes. Would you like to propose a patch ? 

> Anyway, I am glad now I understand how this stuff works. Thank you again!

You're welcome! 

Thanks, 

Mathieu 

> On 27 March 2018 at 16:02, Mathieu Desnoyers < [
> mailto:mathieu.desnoyers at efficios.com | mathieu.desnoyers at efficios.com ] >
> wrote:

>> ----- On Mar 27, 2018, at 5:55 AM, Denis Yevgenyevich < [
>> mailto:denis.yevgenyevich at gmail.com | denis.yevgenyevich at gmail.com ] > wrote:

>>>> 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
>>> Well, given that my software has to maintain precise counts of items inserted
>>> into some of hashtables,
>>> I'd like to be able to avoid any performance overhead due to accounting.

>>>> 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 ?
>>> Ah, thanks. Turns out that the table stopped growing because of the check
>>> if (count >= (1UL << (COUNT_COMMIT_ORDER + split_count_order)))

>> If both (CDS_LFHT_ACCOUNTING | CDS_LFHT_AUTO_RESIZE) flags are set, the table
>> will
>> still grow after it has gone beyond this condition.

>> When both flags are set, check_resize() is only for the bucket-local chain
>> length algorithm that deals
>> with very small tables. Then, when the table size goes above that threshold,
>> split-counters are used to
>> adjust the required table size. We don't use the split-counters approximation of
>> the number of elements
>> in the table for small tables because they are not accurate enough for small
>> tables. It's a tradeoff
>> between accuracy and accounting overhead here.

>> Notice that ht_count_add() and ht_count_del() both invoke
>> cds_lfht_resize_lazy_count(). It's that
>> function which is responsible for the split-counter based resize algorithm.

>>> I am a bit disappointed about that. Why can't we have tables that resize
>>> 1. automatically
>>> 2. from 10s to 100,000s of buckets
>>> 3. without becoming too large too soon?

>> The only thing here is that the bucket-length algorithm used for small tables
>> can grow the
>> table more quickly than you would expect if you have hash collisions. But it
>> should not
>> matter that much because it only applies to small tables. Do you experience "too
>> aggressive"
>> hash table growth even beyond the threshold selecting the split-counters resize
>> algorithm ?

>> That threshold is calculated as:

>> (1UL << (COUNT_COMMIT_ORDER + split_count_order)

>> Where COUNT_COMMIT_ORDER = 10
>> and split_count_order = log2(nr_cpus ceiled to next power of 2)

>> Assuming a 64-core machine:

>> log2(64) = 6
>> 2 ^ (10 + 6) = 65536

>> Considering that you created your hash table with an initial size of 16 buckets,
>> specified a minimum
>> number of buckets of 16, and a maximum number of buckets of 1 << 16 (65536),
>> you'll always be
>> using the "hash-chain length" algorithm for resize on a 64-core machine. The
>> split-counter algorithm
>> would never kick in.

>> You should therefore try tweaking the @max_nr_buckets parameter to a larger
>> value when
>> calling cds_lfht_new().

>> How many cores do you have ?

>> Let me know how is goes,

>> Thanks,

>> Mathieu

>>> On 26 March 2018 at 18:32, Mathieu Desnoyers < [
>>> mailto:mathieu.desnoyers at efficios.com | mathieu.desnoyers at efficios.com ] >
>>> wrote:

>>>> ----- On Mar 26, 2018, at 11:01 AM, Denis Yevgenyevich < [
>>>> mailto:denis.yevgenyevich at gmail.com | 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
>>>>> [ mailto:lttng-dev at lists.lttng.org | lttng-dev at lists.lttng.org ]
>>>>> [ https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev |
>>>>> https://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev ]

>>>> --
>>>> Mathieu Desnoyers
>>>> EfficiOS Inc.
>>>> [ http://www.efficios.com/ | http://www.efficios.com ]

>> --
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> [ http://www.efficios.com/ | http://www.efficios.com ]

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com