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

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

[Mathieu Desnoyers]

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)) {
+			/*
+			 * 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] [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

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

[Mathieu Desnoyers]

I'm merging this:

commit 0f9772a234678dd5c775fadab9048f3b9472fe29
Author: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
Date:   Tue Aug 27 17:58:22 2013 -0400

    Fix: hash table growth (for small tables) should be limited
    
    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..7d39388 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -563,6 +563,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
 
 static long nr_cpus_mask = -1;
 static long split_count_mask = -1;
+static int split_count_order = -1;
 
 #if defined(HAVE_SYSCONF)
 static void ht_init_nr_cpus_mask(void)
@@ -597,6 +598,8 @@ void alloc_split_items_count(struct cds_lfht *ht)
 			split_count_mask = DEFAULT_SPLIT_COUNT_MASK;
 		else
 			split_count_mask = nr_cpus_mask;
+		split_count_order =
+			cds_lfht_get_count_order_ulong(split_count_mask + 1);
 	}
 
 	assert(split_count_mask >= 0);
@@ -713,14 +716,39 @@ void check_resize(struct cds_lfht *ht, unsigned long size, uint32_t chain_len)
 	 * Use bucket-local length for small table expand and for
 	 * environments lacking per-cpu data support.
 	 */
-	if (count >= (1UL << COUNT_COMMIT_ORDER))
+	if (count >= (1UL << (COUNT_COMMIT_ORDER + split_count_order)))
 		return;
 	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
+						+ split_count_order))) {
+			/*
+			 * 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 + split_count_order
+				- cds_lfht_get_count_order_ulong(size);
+			if (growth <= 0)
+				return;
+		}
+		cds_lfht_resize_lazy_grow(ht, size, growth);
+	}
 }
 
 static

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