[PATCH net-next 0/2] rhashtable: Quick initial table growth

[PATCH net-next 0/2] rhashtable: Quick initial table growth

[Thomas Graf]

Besides a trivial cleanup. This proposes to introduce a quicker growth
algorithm for very small table sizes to avoid a large number of resize
cycles to go through. I experienced up to 15 chained resizes when
growing from small table sizes. A typical use case where this matters
is the nft set restore if no hint for the table size is given.

Thomas Graf (2):
  rhashtable: Simplify iterator code
  rhashtable: Quick initial growth of tables

 lib/rhashtable.c | 45 +++++++++++++++++++++++++++++++++++++--------
 1 file changed, 37 insertions(+), 8 deletions(-)

-- 
1.9.3

[PATCH net-next 1/2] rhashtable: Simplify iterator code

[Thomas Graf]

Remove useless obj variable and goto logic.

Signed-off-by: Thomas Graf <tgraf@suug.ch>
---
 lib/rhashtable.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index b28df40..4936fc4 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -579,7 +579,6 @@ void *rhashtable_walk_next(struct rhashtable_iter *iter)
 	struct bucket_table *tbl = iter->walker->tbl;
 	struct rhashtable *ht = iter->ht;
 	struct rhash_head *p = iter->p;
-	void *obj = NULL;
 
 	if (p) {
 		p = rht_dereference_bucket_rcu(p->next, tbl, iter->slot);
@@ -599,8 +598,7 @@ next:
 		if (!rht_is_a_nulls(p)) {
 			iter->skip++;
 			iter->p = p;
-			obj = rht_obj(ht, p);
-			goto out;
+			return rht_obj(ht, p);
 		}
 
 		iter->skip = 0;
@@ -618,9 +616,7 @@ next:
 
 	iter->p = NULL;
 
-out:
-
-	return obj;
+	return NULL;
 }
 EXPORT_SYMBOL_GPL(rhashtable_walk_next);
 
-- 
1.9.3

[PATCH net-next 2/2] rhashtable: Quick initial growth of tables

[Thomas Graf]

Grow the table quicker than 2x in the beginning to avoid long chains
of rehashes. The effect is observable in the self-test where table
jumps are reduced to a minimum after a lot of entries have been added
in a short period of time. The iterator is able to get a consistent
view most of the time.

Signed-off-by: Thomas Graf <tgraf@suug.ch>
---
 lib/rhashtable.c | 37 +++++++++++++++++++++++++++++++++++--
 1 file changed, 35 insertions(+), 2 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 4936fc4..23e7f18 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -271,6 +271,38 @@ static int rhashtable_rehash_table(struct rhashtable *ht)
 	return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
 }
 
+static int table_growth_log(unsigned int size)
+{
+	/*
+	 * Table growth:
+	 *     2 ->   64
+	 *     4 ->  128
+	 *     8 ->  128
+	 *    16 ->  256
+	 *    32 ->  512
+	 *    64 ->  512
+	 *   128 -> 1024
+	 *   256 -> 2048
+	 *   512 -> 2048
+	 *  1024 -> 4096
+	 *  2048 -> 8192
+	 *  4096 -> 8192
+	 */
+	int log = 5 - (ilog2(size) / 3);
+
+	return log > 1 ? log : 1;
+}
+
+static unsigned int grow_table(struct rhashtable *ht, unsigned int old_size)
+{
+	unsigned int new_size;
+
+	new_size = old_size << table_growth_log(old_size);
+	new_size = min(new_size, ht->p.max_size);
+
+	return new_size;
+}
+
 /**
  * rhashtable_expand - Expand hash table while allowing concurrent lookups
  * @ht:		the hash table to expand
@@ -295,7 +327,8 @@ static int rhashtable_expand(struct rhashtable *ht)
 
 	old_tbl = rhashtable_last_table(ht, old_tbl);
 
-	new_tbl = bucket_table_alloc(ht, old_tbl->size * 2, GFP_KERNEL);
+	new_tbl = bucket_table_alloc(ht, grow_table(ht, old_tbl->size),
+				     GFP_KERNEL);
 	if (new_tbl == NULL)
 		return -ENOMEM;
 
@@ -404,7 +437,7 @@ int rhashtable_insert_rehash(struct rhashtable *ht)
 	size = tbl->size;
 
 	if (rht_grow_above_75(ht, tbl))
-		size *= 2;
+		size = grow_table(ht, size);
 	/* Do not schedule more than one rehash */
 	else if (old_tbl != tbl)
 		return -EBUSY;
-- 
1.9.3

Re: [PATCH net-next 1/2] rhashtable: Simplify iterator code

[Herbert Xu]

Thomas Graf <tgraf@suug.ch> wrote:
> Remove useless obj variable and goto logic.
> 
> Signed-off-by: Thomas Graf <tgraf@suug.ch>

Acked-by: Herbert Xu <herbert@gondor.apana.org.au>

Thanks,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH net-next 2/2] rhashtable: Quick initial growth of tables

[Herbert Xu]

Thomas Graf <tgraf@suug.ch> wrote:
> Grow the table quicker than 2x in the beginning to avoid long chains
> of rehashes. The effect is observable in the self-test where table
> jumps are reduced to a minimum after a lot of entries have been added
> in a short period of time. The iterator is able to get a consistent
> view most of the time.
> 
> Signed-off-by: Thomas Graf <tgraf@suug.ch>

Wouldn't automatic shrinking immediately undo your quick growth?

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH net-next 2/2] rhashtable: Quick initial growth of tables

[Thomas Graf]

On 05/01/15 at 07:45am, Herbert Xu wrote:
> Thomas Graf <tgraf@suug.ch> wrote:
> > Grow the table quicker than 2x in the beginning to avoid long chains
> > of rehashes. The effect is observable in the self-test where table
> > jumps are reduced to a minimum after a lot of entries have been added
> > in a short period of time. The iterator is able to get a consistent
> > view most of the time.
> > 
> > Signed-off-by: Thomas Graf <tgraf@suug.ch>
> 
> Wouldn't automatic shrinking immediately undo your quick growth?

Yes, that can happen. Since shrinks are ordered to the end of the
chain it is often the case that enough entries have been added so the
shrink is not carried out in the end. Obviously this is also not the
case if no entries are actually removed.

What about we apply quick growing on >100% utilization? It is a
clear indication that we are growing rapidly.

Re: [PATCH net-next 2/2] rhashtable: Quick initial growth of tables

[Herbert Xu]

On Fri, May 01, 2015 at 06:30:25AM +0200, Thomas Graf wrote:
>
> Yes, that can happen. Since shrinks are ordered to the end of the
> chain it is often the case that enough entries have been added so the
> shrink is not carried out in the end. Obviously this is also not the
> case if no entries are actually removed.

It's just a matter of logical consistency.  At 75% if you grow by
a factor of 4, you get 18.75% utilisation which is way below the
30% shrink threshold.

> What about we apply quick growing on >100% utilization? It is a
> clear indication that we are growing rapidly.

Even at 100%, a factor of 4 leads you to 25% which is less than 30%.

Perhaps we could lower the shrink thresholds? Alternatively, only
grow quickly if automatic shrinking is disabled.  After all, the one
case that's inspring all of this, netlink really wants to grow
quickly as well as only shrink at specific points in time.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH net-next 2/2] rhashtable: Quick initial growth of tables

[Sergei Shtylyov]

Hello.

On 5/1/2015 1:46 AM, Thomas Graf wrote:

> Grow the table quicker than 2x in the beginning to avoid long chains
> of rehashes. The effect is observable in the self-test where table
> jumps are reduced to a minimum after a lot of entries have been added
> in a short period of time. The iterator is able to get a consistent
> view most of the time.

> Signed-off-by: Thomas Graf <tgraf@suug.ch>
> ---
>   lib/rhashtable.c | 37 +++++++++++++++++++++++++++++++++++--
>   1 file changed, 35 insertions(+), 2 deletions(-)

> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
> index 4936fc4..23e7f18 100644
> --- a/lib/rhashtable.c
> +++ b/lib/rhashtable.c
> @@ -271,6 +271,38 @@ static int rhashtable_rehash_table(struct rhashtable *ht)
>   	return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
>   }
>
> +static int table_growth_log(unsigned int size)
> +{
> +	/*
> +	 * Table growth:
> +	 *     2 ->   64
> +	 *     4 ->  128
> +	 *     8 ->  128
> +	 *    16 ->  256
> +	 *    32 ->  512
> +	 *    64 ->  512
> +	 *   128 -> 1024
> +	 *   256 -> 2048
> +	 *   512 -> 2048
> +	 *  1024 -> 4096
> +	 *  2048 -> 8192
> +	 *  4096 -> 8192
> +	 */
> +	int log = 5 - (ilog2(size) / 3);
> +
> +	return log > 1 ? log : 1;

    max(log, 1)?

[...]

WBR, Sergei

Re: [PATCH net-next 2/2] rhashtable: Quick initial growth of tables

[Thomas Graf]

On 05/01/15 at 12:37pm, Herbert Xu wrote:
> On Fri, May 01, 2015 at 06:30:25AM +0200, Thomas Graf wrote:
> >
> > Yes, that can happen. Since shrinks are ordered to the end of the
> > chain it is often the case that enough entries have been added so the
> > shrink is not carried out in the end. Obviously this is also not the
> > case if no entries are actually removed.
> 
> It's just a matter of logical consistency.  At 75% if you grow by
> a factor of 4, you get 18.75% utilisation which is way below the
> 30% shrink threshold.
> 
> > What about we apply quick growing on >100% utilization? It is a
> > clear indication that we are growing rapidly.
> 
> Even at 100%, a factor of 4 leads you to 25% which is less than 30%.
> 
> Perhaps we could lower the shrink thresholds? Alternatively, only
> grow quickly if automatic shrinking is disabled.  After all, the one
> case that's inspring all of this, netlink really wants to grow
> quickly as well as only shrink at specific points in time.

Lowering the shrink threshold in combination with quick growth
above 100% sounds good to me. The whole point of this is to detect
when we are likely to see a lot of inserts with only a few or no
removals.

Re: [PATCH net-next 2/2] rhashtable: Quick initial growth of tables

[Thomas Graf]

On 05/01/15 at 02:04pm, Sergei Shtylyov wrote:
> >+	return log > 1 ? log : 1;
> 
>    max(log, 1)?

Sure