[lttng-dev] [PATCH urcu] Fix: hash table growth (for small tables) should be limited

[Mathieu Desnoyers]

* Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
> Buckets with many entries encountered in a hash table could cause it to
> grow to a large size, beyond the scope for which this mechanism is
> expected to play a role when node accounting is available. Indeed, when
> the hash table grows to larger size, split-counter node accounting is
> expected to deal with resize/shrink rather than relying on an heuristic
> based on the largest bucket size.
> 
> This is fixing an issue where we see hash tables sometimes reaching 65k
> entries index (65536*8 = 524288 bytes) for a workload limited to adding
> 1000 entries and then removing all of them, done in a loop (random
> keys).
> 
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> ---
> diff --git a/rculfhash.c b/rculfhash.c
> index 423609d..283cd2d 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -718,9 +718,32 @@ void check_resize(struct cds_lfht *ht, unsigned long size, uint32_t chain_len)
>  	if (chain_len > 100)
>  		dbg_printf("WARNING: large chain length: %u.\n",
>  			   chain_len);
> -	if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD)
> -		cds_lfht_resize_lazy_grow(ht, size,
> -			cds_lfht_get_count_order_u32(chain_len - (CHAIN_LEN_TARGET - 1)));
> +	if (chain_len >= CHAIN_LEN_RESIZE_THRESHOLD) {
> +		int growth;
> +
> +		/*
> +		 * Ideal growth calculated based on chain length.
> +		 */
> +		growth = cds_lfht_get_count_order_u32(chain_len
> +				- (CHAIN_LEN_TARGET - 1));
> +		if ((ht->flags & CDS_LFHT_ACCOUNTING)
> +				&& (size << growth) >= (1UL << COUNT_COMMIT_ORDER)) {

Actually, I think it would be cleaner to use the chain_len based
mechanism up to

  (1UL << COUNT_COMMIT_ORDER) * (split_count_mask + 1)

so we end up taking into account that the split-counters are only
committed into the global counter every COUNT_COMMIT_ORDER
increment/decrement.

It's not bad if we just use (1UL << COUNT_COMMIT_ORDER): we just end up
with larger chains in some cases (usually bounded by the log2(number of
CPUs)).

Thoughts ?

Thanks,

Mathieu

> +			/*
> +			 * If ideal growth expands the hash table size
> +			 * beyond the "small hash table" sizes, use the
> +			 * maximum small hash table size to attempt
> +			 * expanding the hash table. This only applies
> +			 * when node accounting is available, otherwise
> +			 * the chain length is used to expand the hash
> +			 * table in every case.
> +			 */
> +			growth = COUNT_COMMIT_ORDER -
> +				cds_lfht_get_count_order_u32(size);
> +			if (growth <= 0)
> +				return;
> +		}
> +		cds_lfht_resize_lazy_grow(ht, size, growth);
> +	}
>  }
>  
>  static
> 
> -- 
> Mathieu Desnoyers
> EfficiOS Inc.
> http://www.efficios.com
> 
> _______________________________________________
> lttng-dev mailing list
> lttng-dev at lists.lttng.org
> http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

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