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

[Sergei Shtylyov <sergei.shtylyov@cogentembedded.com>]

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