Re: [PATCH] kernel-shark: Increase the size of the task hash

["Yordan Karadzhov (VMware)" <y.karadz@gmail.com>]

On 28.08.19 г. 21:00 ч., Steven Rostedt wrote:
> From: Steven Rostedt (VMware) <rostedt@goodmis.org>
> 
> When loading a data file that contained 100,000s of tasks, using a 256
> bucket size hash crippled it. By increasing the hash to 2^16 (65536) it
> solves the issue (still small enough not to waste too much memory).
> 
> In the process, I changed the knuth_hash() in libkshark.c to use the 32
> bit version and just have the key use what it needs:

If the size the hash table is 65536 then the multiplicative hashing 
function has to multiply the key by a prime number which is closer to 
65536 / 1.61803398875 (the so called "golden ratio" of the size).
It makes no sense to multiply by a number that is several orders of 
magnitude bigger than the size of the hash table.

> 
>    key = knuth_hash();
>    key += knuth_hash >> SHIFT;
>    key &= (1 << SHIFT) - 1;
> 
> Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
> ---
> diff --git a/kernel-shark/src/libkshark.c b/kernel-shark/src/libkshark.c
> index 4201fa02..41572e18 100644
> --- a/kernel-shark/src/libkshark.c
> +++ b/kernel-shark/src/libkshark.c
> @@ -252,19 +252,19 @@ void kshark_free(struct kshark_context *kshark_ctx)
>   	free(kshark_ctx);
>   }
>   
> -static inline uint8_t knuth_hash(uint32_t val)
> +static inline uint32_t knuth_hash(uint32_t val)
>   {
>   	/*
> -	 * Small table hashing function adapted from Donald E. Knuth's 32 bit
> +	 * Hashing function adapted from Donald E. Knuth's 32 bit
>   	 * multiplicative hash.  See The Art of Computer Programming (TAOCP).
>   	 * Multiplication by the Prime number, closest to the golden ratio of
> -	 * 2^8.
> +	 * 2^32.
>   	 */
> -	return UINT8_C(val) * UINT8_C(157);
> +	return val * UINT32_C(2654435761);

So according to my understanding of the idea in the book, this line 
should look look this:

	return UINT16_C(val) * UINT8_16(65537);

and you do not need to do any additional manipulation of the key (PID).
Also the function has to return uint16_t.

Thanks!
Yordan

>   }
>   
>   static struct kshark_task_list *
> -kshark_find_task(struct kshark_context *kshark_ctx, uint8_t key, int pid)
> +kshark_find_task(struct kshark_context *kshark_ctx, uint32_t key, int pid)
>   {
>   	struct kshark_task_list *list;
>   
> @@ -280,9 +280,12 @@ static struct kshark_task_list *
>   kshark_add_task(struct kshark_context *kshark_ctx, int pid)
>   {
>   	struct kshark_task_list *list;
> -	uint8_t key;
> +	uint32_t key;
>   
>   	key = knuth_hash(pid);
> +	key += key >> KS_TASK_HASH_SHIFT;
> +	key &= (1 << KS_TASK_HASH_SHIFT) - 1;
> +
>   	list = kshark_find_task(kshark_ctx, key, pid);
>   	if (list)
>   		return list;
> diff --git a/kernel-shark/src/libkshark.h b/kernel-shark/src/libkshark.h
> index 04e9cbfc..3407db19 100644
> --- a/kernel-shark/src/libkshark.h
> +++ b/kernel-shark/src/libkshark.h
> @@ -72,7 +72,8 @@ struct kshark_entry {
>   };
>   
>   /** Size of the task's hash table. */
> -#define KS_TASK_HASH_SIZE 256
> +#define KS_TASK_HASH_SHIFT 16
> +#define KS_TASK_HASH_SIZE (1 << KS_TASK_HASH_SHIFT)
>   
>   /** Linked list of tasks. */
>   struct kshark_task_list {
>