| Message ID | 20190920152024.729716704@goodmis.org (mailing list archive) |
|---|---|
| State | Accepted |
| Commit | d44848101fcd820c6ee29bba7fa175eb2e520a2d |
| Headers | show |
| Series | trace-cmd/kernel-shark: Use one quick hash algorithm | expand |
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>
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 {