From: Sergei Shtylyov <sergei.shtylyov@cogentembedded•com>
To: Thomas Graf <tgraf@suug•ch>, davem@davemloft•net
Cc: netdev@vger•kernel.org, herbert@gondor•apana.org.au, kaber@trash•net
Subject: Re: [PATCH net-next 2/2] rhashtable: Quick initial growth of tables
Date: Fri, 01 May 2015 14:04:35 +0300 [thread overview]
Message-ID: <55435DC3.4060304@cogentembedded.com> (raw)
In-Reply-To: <1430434005-6143-3-git-send-email-tgraf@suug.ch>
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
next prev parent reply other threads:[~2015-05-01 11:04 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-04-30 22:46 [PATCH net-next 0/2] rhashtable: Quick initial table growth Thomas Graf
2015-04-30 22:46 ` [PATCH net-next 1/2] rhashtable: Simplify iterator code Thomas Graf
2015-04-30 23:41 ` Herbert Xu
2015-04-30 22:46 ` [PATCH net-next 2/2] rhashtable: Quick initial growth of tables Thomas Graf
2015-04-30 23:45 ` Herbert Xu
2015-05-01 4:30 ` Thomas Graf
2015-05-01 4:37 ` Herbert Xu
2015-05-01 13:38 ` Thomas Graf
2015-05-01 11:04 ` Sergei Shtylyov [this message]
2015-05-01 13:38 ` Thomas Graf
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=55435DC3.4060304@cogentembedded.com \
--to=sergei.shtylyov@cogentembedded$(echo .)com \
--cc=davem@davemloft$(echo .)net \
--cc=herbert@gondor$(echo .)apana.org.au \
--cc=kaber@trash$(echo .)net \
--cc=netdev@vger$(echo .)kernel.org \
--cc=tgraf@suug$(echo .)ch \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox