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

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

On 20.09.19 г. 18:15 ч., 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).
> 
> Also switched to the tracecmd_quick_hash() which is basically the same
> as the local knuth_hash() function in libkshark.c.
> 
> Link: http://lore.kernel.org/linux-trace-devel/20190828140016.3ce1be4f@gandalf.local.home
> 
> Signed-off-by: Steven Rostedt (VMware) <rostedt@goodmis.org>
> ---
>   kernel-shark/src/libkshark.c | 18 ++++--------------
>   kernel-shark/src/libkshark.h |  3 ++-
>   2 files changed, 6 insertions(+), 15 deletions(-)
> 
> diff --git a/kernel-shark/src/libkshark.c b/kernel-shark/src/libkshark.c
> index 4207ae6ffdb2..a36157835ce0 100644
> --- a/kernel-shark/src/libkshark.c
> +++ b/kernel-shark/src/libkshark.c
> @@ -252,19 +252,8 @@ void kshark_free(struct kshark_context *kshark_ctx)
>   	free(kshark_ctx);
>   }
>   
> -static inline uint8_t knuth_hash(uint32_t val)
> -{
> -	/*
> -	 * Small table 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.
> -	 */
> -	return UINT8_C(val) * UINT8_C(157);
> -}
> -
>   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 +269,10 @@ 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 = tracecmd_quick_hash(pid, KS_TASK_HASH_SHIFT);
>   
> -	key = knuth_hash(pid);
>   	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 04e9cbfc71df..3407db197320 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 {
> 

Both patches look good to me.
Thanks!


Reviewed-by: Yordan Karadzhov (VMware) <y.karadz@gmail.com>